10.1 Quantum Fourier Transform
The Quantum Fourier Transform (QFT) is widely used in quantum computing, notably in Shor’s factorization algorithm in section 10.6 H is the 1-qubit QFT and we’ve seen many examples of its use.
Most treatments of the QFT start by comparing it to the classical Discrete Fourier Transform and then the Fast Fourier Transform. If you don’t know either of these, don’t worry. I’m presenting the QFT in detail for its own sake in quantum computing. Should you know about or read up about the classical analogs, the similarities should be clear.
10.1.1 Roots of unity
We are all familiar with square roots. For example, √4 is equal to either 2 or −2. We can also write √2 = 21/2 and say that there are two ‘‘2nd-roots of 2.’’ Similarly, 5 is a cube root, or ‘‘3rd-root,’’ of 125. In general, we talk about an ‘‘Nth-root’...
