ompletion. According to Eq. (19.30), and after the swapping operation, the circuit output is: QFTn)1( (19.31) (100)1 where I have introduced W = exp(2i/2) = exp(ir/2). In the orthonormal basis {|n1n2}} = {|00), |01), |10), |11)} (taking note here of the binary ordering), we obtain Quantum database search algorithms Figure 19.5 QFT circuit for K=20 (N = 4). from Eq. (19.31) the following matrix representation of the QFT circuit: (19.32) The right-hand side of Eq. (19.32) is recognized as the 4 x 4 Vandermonde matrix, which was defined in Eq. (19.25) in the general case, i.e., for all K, with W = exp(2i/2*). This result is, therefore, consistent with all QFT definitions previously derived in this section. An interesting application example is the quantum Fourier transform of the EPR-Bell states, Bij), which is left as a straightforward exercise to calculate, using the above matrix (there is no big point about the result, except for the conclusion that QFT maintains a state of entanglement, under a more complex state mixture). The QFT circuit shown in Fig. 19.6 corresponds to the case K = 3 (N = 8), including the SWAP ordering operation. There is no point in expanding Eq. (19.29) again to define the 3-qubit circuit output explicitly. We simply need to substitute W = exp(2ir/23) = exp(i/4) into the 8 x 8 Vandermonde matrix in Eq. (19.25), which, taking into account the W periodicity yields: 1 W w2 w3 w4 w5 w6 (19.33) w2 w3 w4 w5 w6 w7 w2 w4 w6 w2 w4 = 21/2 1w3www4www5 1w4 1w41w41w4 1w5www4www 1w6ww1www 1 ww6ww4www 19.4 Grover quantum database search algorithm H R2 R3 Figure 19.6 QFT circuit for K=3 (N = 8). Is the QFT algorithm any faster than its classical counterpart, which is known as fast Fourier transform (FFT)? To answer this question, let us analyze the number of gates traversed by the signals for each circuit type. Referring back to Fig. 19.4, we observe that a K circuit requires crossing a number of gates of K + (K - 1) + (K 2) + 2 plus K/2 or (K - 1)/2 (K even or odd) twin gates to perform the SWAP operatio