Explaining the Design of the Quantum Fourier Transform

The Discrete Fourier Transform (DFT) is one of the most practical mathematical tools that has been developed and is used in engineering, sciences and beyond. It converts a finite sequence of samples from the time/space domain into the frequency domain, and vice versa. Many operations and analyses are simpler in the frequency domain where after the appropriate operation (or filtering), the signal is converted back to the spatial domain. The Quantum Fourier Transform (QFT) is the quantum equivalent of the classical DFT. Instead of operating on classical signals, it operates on quantum states. Many important quantum algorithms utilize the QFT, or the inverse QFT, at their last step to extract the periodicity from their input quantum states. Some of these algorithms are Shor's, Quantum Phase Estimation (QPE), Quantum Counting and numerous other algorithms. In this work, we attempt to present QFT in a way that undergraduate students can understand the design of the algorithm and the reasoning of the implementation. We wish to utilize this work to develop a tutorial to understand the intricacies of QFT's implementation.