ix convergents. The last convergent, p7/97 = 711/413, is the exact definition of Q. The algorithm has, thus, made it possible to determine Q = p/q unambiguously given the approximation 9 and its known accuracy. Appendix S (Chapter 20) Computation of inverse Fourier transform in the factorization of N = 21 through Shor's algorithm In this appendix, I detail the computation of the inverse Fourier transform involved in the factoring of N = 15 through Shor's algorithm. To recall the parameters used in Section 20.5, we have K = 11 for the first register size and, thus, M = 211 = 2048. After a measurement in the second register (z = 8), the state /uz) of the first register, which is input to the inverse Fourier transform circuit, is By definition (see Chapter 19) the inverse Fourier transform FT+ acts on the M-qubit state |n) according to Thus, from the above definition of /uz), we obtain and develop the transformation as: -e-8irk Appendix S We can rewrite the result in Eq. (S3) in the form where the amplitude coefficient Ak is defined by The corresponding probability distribution p(k) = |akl2 corresponding to the output measurement k is, therefore: We observe that for any integer k = 0, 1, M - 1, the numerator in Eq. (S6) is zero. So is the denominator whenever 4k/M is an integer multiple of IT, or M=nxr *=nx-==x22=nx512 where n is an integer. In this last case, the numerator: denominator ratio is analytically undetermined, but setting k = nM/4 + E and taking the limit: Factorization of N = 21 through Shor's algorithm p (k) 2047= M - 1 2048 = M Figure S1 Plot of p(k). (AT ) = M2, which, from Eq. (S6), yields Pmax = 1/4. In the range k = 0, 1, 2, M - 1, the maxima of p(k) are thus located at k = 0 (n = 0), k = 512 (n = 1), k = 1024 (n = 2) and k = 1536 (n = 3). The plot of p(k) is shown in Fig. S1. Appendix T (Chapter 20) Modular arithmetic and Euler's theorem In this appendix, we shall review some basic principles and properties of modular arithmetic. As Section 20.7 shows, modular arithmetic is at the root of public 