 Substituting then the property in Eq. (20.16), effecting the index change j k for reading convenience, and introducing Qs = s/r, we obtain, equivalently: (20.21) Next, in 4 we apply the inverse Fourier transform to the first register, whose contents are expressed in parenthesis in Eq. (20.21). In this expression, we recognize the same state superposition as in Eq. (20.9). As we have previously seen, the inverse Fourier transform of this superposition leads to a fair approximation 10s) of the state les). Therefore, the 3 For the tensor product to the summation conversion, see previous note, while setting Q = 0. In Eq. (20.20), we also used the property according to which U@1moomo = = |x/ mod N). Shor's factorization algorithm circuit output can be expressed in the form: (20.22) A measurement of the first register projects the superposition in Eq. (20.22) into one of the r states 10s), with uniform probability p(s) = 1/r, which then yields the ratio s/r, corresponding to the phase estimation s = 4s = s/r associated with the eigenstate lus). As discussed in the previous section, if the control register size, K, is set to K = l + [log2[2 + 1/(2s)]], the measurement is an approximation of Qs = s/r that is accurate up to 2-1, with a probability of success of at least 1 - E. Assume here that we require an accuracy of l = 2L + 1 bits, a specific but most useful condition that will be justified later. The control register size is, thus, set to K = 2L + 1 + [log2[2 + 1/(2s)]]. The next step consists in the evaluation of the number r, given the knowledge of the s measurement, with S E {0, 1, 2, r - 1} being random, and the fact that s/r < is a rational number, i.e., the ratio of two bounded integers, p, q. The determination of r requires a classical computation, which is based on the continued fraction expansion algorithm described in the next section. Continued fraction expansion In this section, I introduce the continued fraction expansion (or continued fraction algorithm), and show how it can be applied to determine an 