n, each amounting to three CNOT gates. We can conclude that the computation time for a QFT circuit of K inputs to generate the output is of the order of K2, noted O(K²). In computer language, it is said that this algorithm (or decision problem) belongs to the complexity class P, as the implementation in a sequential machine can be performed in polynomial time.4 4 In contrast, the number of gates required in a classical FFT circuit for the same computation (data size N = log2 K) is K log K = 2N log2 2N = N2N Thus, the FFT computation time is of the order O(N2N), which is exponential in circuit size, as opposed to quadratic in the QFT case. Such a comparison remains, however, questionable, because the quantum circuit does not operate on data bits, but quantum states. Further processing circuits would be required to measure the "classical bit" or cbit counterparts, but even this observation fails to convey any equitable comparison, as such measurements are, by nature, indeterministic. Simply put, the QFT is exponentially faster than FFT, but the signal amplitudes cannot be measured, unlike in the classical case. The picture becomes even darker if we consider that there is currently no known technique to prepare the input states /nk) of the QFT circuit, except in the very limiting cases K = 1 or K = 2. The quantum Fourier transform may, thus, appear to be fully impractical, or just an interesting mathematical curiosity. As we shall see in Chapter 20, however, the QFT algorithm is the key to solving one of the major computation problems, namely the factoring of numbers into primes, famously known as the Shor algorithm. Grover quantum database search algorithm In this section, I describe another famous QC algorithm, known after its conceiver as the Grover quantum database search (GQDS). Like the previously described QFT, this algorithm nicely exploits the property of quantum parallelism. 4 This notion is not to be confused with the time required for solution verification, which is referred to as an NP (indeterministic 