The Quantum Fourier Transform

If you took a college class in signal processing and communication, chances are you would already be at home with Fourier Transforms. If this is the first time you hear the words, don’t worry about it. Simply put, the Fourier Transform is a mathematical technique that takes functions from the spatial/temporal domain to the frequency domain. The Fourier Transform of a function is a complex-valued function of frequency whose magnitude represents the amount of that frequency present in the original function and whose argument is the phase offset of the basic sinusoid in that frequency. This technique has many uses, particularly in signal processing and noise cancellation. Those are not important to us for this course. What we are more interested in is the mathematical and geometric properties of the Fourier Transform in the quantum realm.

Mathematics behind the Fourier Transform

Mathematically, the Fourier Transform maps a vector $(x_{0},...,x_{N-1})$ to the vector $(y_{0},...,y_{N-1})$. Since quantum states are vectors in complex space, we can say that the Quantum Fourier Transform (QFT) acts on wavefunctions and quantum states and generates a state $|\phi \rangle$ when acted upon $|\psi\rangle$; such that $|\phi\rangle=QFT|\psi\rangle$. What is this transformation? This transformation can be considered as taking a qubit from the computational basis $|0\rangle$ and $|1\rangle$ to the Fourier Basis $|+\rangle$ and $|-\rangle$. These states would be familiar to you, we have already seen them while studying the Hadamard Gate $H$.

In fact, the Hadamard Gate $H$ is a 1-qubit Quantum Fourier Transform. It takes $|0\rangle$ to $|+\rangle$ and $|1\rangle$ to $|-\rangle$. The Hadamard Gate $H$ is a specific case of the general formula for the Quantum Fourier Transform, which adds a phase to the vector $|y\rangle$ as follows:

$$|y\rangle=\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} e^{\frac{2\pi ixy}{N}}|y\rangle$$

For clarity, let’s derive the formula for $H$ using this. For a single qubit, we take $N=2$, since $N=2^n$, where $n$ is the number of qubits in our system. Apply the formula to the $|0\rangle$ state to produce a state on the Fourier basis. Let’s call it $$ ...