This section describes the Quantum Fourier Transform (QFT), which is a sub-routine of many important quantum algorithms, including Shor's algorithm. It first gives an overview of the Classical Fourier Transform (CFT), which decomposes a signal, any function of time, into the frequencies which make it up. This section will require a basic knowledge of algebra. The chapter uses analogies from music to understand what a Fourier transform does and provides applications where Fourier transforms are commonly used in computation. The chapter next shows the use a classical algorithm to compute the Discrete Fourier Transform, that is, a Fourier transform of a signal represented on a classical computer. Applications of the QFT are discussed, and a QFT is compared to a Classical Fourier Transform. Finally, a QFT algorithm is given in OpenQASM, Qiskit, and in a quantum score, and the reader is given the opportunity to run this quantum algorithm on IBM QX or within the Qiskit simulator.
The following topics are covered in this chapter:
- An overview of the Classical Fourier Transform
- A demonstration of the Fast Fourier Transform algorithm for computing the Classical Fourier Transform
- The Quantum Fourier Transform
- An implementation of the Quantum Fourier Transform