result turns out to be rela- tively simple. The QFT circuit and its constituent 2 x 2 gates are represented in Fig. 19.4. As a first observation, there are only K = log2 N qubit inputs, and as many qubit outputs, labeled in the reverse order. To explain the reduced circuit size, consider, for simplicity, the case K = 3 (N = 8). The relation between the K = 3 inputs {|n1), |n2), |n3)} and 19.3 Quantum Fourier transform algorithm the N = 8 basis states {|0), |1), |2), |3), |4), |5), |6), |7)} is given by the binary-tensor representation of the latter, namely, {|000), |001), |010), |011), |100), |101), |110), |111)}. Thus, the QFT of the basis state |6) = |110) is given by the circuit input {|0), |1), |1)}, for instance (starting from the bit of lower weight). As it turns out, the order of the output qubits is reversed, and the full implementation of the QFT requires an additional series of SWAP gates. Such a SWAP operation can be performed by a cascade of three CNOT gates (see Fig. 16.3). The second observation is that the circuit in Fig. 19.4 is exclusively made of unitary gates, namely Hadamard (H) and controlled-phase (Rn) gates. This establishes the fact that QFT is both a unitary and reversible transformation (using the circuit from left to right corresponding to the inverse QFT). As shown in Appendix Q, the controlled-phase gates are defined as follows: (19.28) noting that this 2 X 2 representation is a reduced one (from Chapter 16, we know that a controlled-U gate has a 4 x 4 matrix). As detailed in Appendix Q, the output of the QFT circuit corresponds to the overall tensor product QFT)1( = (19.29) where each output |m) = (10)m + e2irsum |1)m) is characterized by the phase factor: (19.30) I shall now provide two examples, to illustrate how the QFT circuit operates. Consider first the case K = 2 (N = 4), corresponding to a 2-qubit quantum circuit. Figure 19.5 shows the corresponding layout, consistent with that shown in Fig. 19.4. The SWAP gate to restore the order of qubits is also included for QFT circuit c