n then proceed to construct the QFT circuit from bottom to top, numbering the output qubits from 1 to K, accordingly. As for the second output qubit, we have 2i S22 = =in(nx-1+nx/2)and then: QFT2( We can immediately identify the above transformation as built from a Hadamard gate on the output wire 2 with input NK-1, and a controlled-phase gate (call it R2), with phase nk/2 and NK as the control qubit. The next output qubit is (Q12) Quantum Fourier transform circuit We can immediately identify the above transformation as built from a Hadamard gate on the output wire 3 with input NK-2, the controlled-phase gate R2, with NK-1 as the control qubit, followed by a second gate (call it R3), with phase nk/4 and NK as the control qubit. The gate circuit corresponding to the first three output qubits is illustrated in Fig. Q1. It is clear from the above description and the definition of Sum in Eq. (Q8) that the whole QFT circuit represents a generalization of that shown in Fig. Q1, with a sequence of controlled-phase gates defined by the matrix (Q13) On the top quantum wire, the gate sequence from left to right is thus: HR2R3 (see Fig. 19.4 in main text for a complete view of the QFT circuit). Appendix R (Chapter 20) Properties of continued fraction expansion This appendix provides the proof of three key properties of the continued fraction expansion. First, define the real number Xn through a suite of positive real numbers [ao, a1, an] according to the continued fraction with n < N. Each real number in the set {x0, X1, XN-1, XN} is called a convergent of XN, while Xn is called the nth convergent of XN. Property 1 The finite suite [a0,a],...,An] of positive real numbers corresponds to the ratio Xn = Pn/qn, as defined through: with n > q1=a for n = 0, 1. The proof of these relations comes by induction. Indeed, for n = 0, 1, we have: We then observe that: Properties of continued fraction expansion which illustrates that [ao, a1, a2] and [ao, a1, a2 + 1/a3] correspond to X2 and X3, which are the 2nd and the 3rd convergents of