ed of Fourier transforms, as they can be implemented with classical bits in a von Neumann computer through the so-called fast Fourier transform (FFT) algorithm. Rather, QFT opens up some new perspectives in quantum computation, and we may realize this only through the next chapter. Here, Quantum database search algorithms I shall outline the formal concept and show how QFT can be practically implemented through relatively simple circuits based on 2 X 2 and controlled 2 X 2 quantum-gates. Let us begin by recalling the definition of the Fourier transform, as it applies to a discrete function or N-vector. In elementary calculus, and electrical and telecom engineering, the discrete Fourier transform (DFT) of an N-vector X = (xo, X1...XN-1) with complex coefficients Xk is a well known operation. It results in the generation of N Fourier components, yn (k = 0, 1...N as defined by the linear expansion: (19.14) It is seen that for each index k the terms contributing to the series expansion in Eq. (19.14) involve powers of the discrete frequency (or tone) fn = 2nn/N, which range from fo = 0 to fN-1 = 2 (N - 1)/N. - Thus, yn is the complex amplitude of the Fourier component at frequency fn, the ensemble of which forms the frequency spectrum of X. Similarly, the inverse discrete Fourier transform (IDFT) is defined as: (19.15) From this background, we can now introduce the quantum Fourier transform (QFT) of an orthonormal basis {|k> }k=0 N-1 = {|0), |1) |N - 1)}. Such a transform is enabled by a unitary operator, which we call QFT, and which acts on the N basis states |k) in a way exactly similar to that in Eq. (19.14): (19.16) It is left as a nontrivial, but elementary exercise to show that the QFT transformation is, indeed, unitary. Next, let 1/5/ be a qubit of dimension N with coordinates Xk in the basis {|k)}, i.e., (19.17) The quantum Fourier transform of the qubit 1/s/, which we note /is), is defined as: (19.18) This result establishes the formal correspondence between 1x) and The inverse QFT, noted QFT+, is similarly 