defined through Eq. (19.15), which gives: (19.19) See, for instance, http://en.wikipedia.org/wiki/Discrete_Fourier_transform. 19.3 Quantum Fourier transform algorithm As a matter of fact, the QFT is far simpler than the above formulas make it appear. Let us show this by considering the elementary cases N = 2 and N = 3. Applying the QFT definition for the basis transformation, we obtain in the first case: (19.20) hence: (19.21) This result indicates that in the case N = 2, the QFT reduces to the Hadamard transfor- mation with quantum matrix gate H. In the case N = 3, we obtain: (19.22) hence: (19.23) We may represent the above results through a symmetric matrix M with coef- ficients Mnk = Mkn = exp(i2nkt/N)/JN where W = exp(2i/N) and n,k=0...N - 1. The N = 3 matrix, thus, takes the form: (19.24) It is clear that, in general, the matrix M takes the following form, referred to as the Vandermonde matrix: (19.25) w²(N-1) "N-1)(N-1) Quantum database search algorithms H - R2 R3 H R2 R3 nk-2) nk-1) Figure 19.4 Quantum circuit for QFT implementation. Substituting the Vandermonde matrix into the definitions in Eqs. (19.18) and (19.19) we also obtain the general definition of the QFT, QFT+ qubit transformations: N-1 N-1 k=0 n=0 (19.26) N-1 N-1 n=0 k=0 or, equivalently, for the relations between Fourier and inverse-Fourier components (19.27) We have, thus, obtained the most general and very simple definition of the quantum Fourier operator through its corresponding matrix and its inverse, as applying to a single qubit of dimension N. We must now find an appropriate quantum circuit, taking XN-1) as the input, and the output, which would also represent an N-qubit QFT gate. To this purpose, we want to avoid the complicated implementation of an N X N Vandermonde-matrix gate, and rather seek for a greatly simplified circuit based on 2 x 2 gates. As this search is a bit tedious and somewhat tricky in formal derivation, here I shall directly give the conclusion, while the complete derivation is detailed in Appendix Q. However, the 