The Quantum Fourier Transform

The discrete Fourier transform is one of the most useful ideas in all of computing: it re-expresses a signal as a sum of pure frequencies, and it is exactly the machinery humming inside every MP3 you stream and every JPEG you open. The quantum Fourier transform (QFT) is that same transform — but applied to the amplitudes of a quantum state, using the roots of unity as its frequencies. Its magic is efficiency: where the classical fast Fourier transform needs O(N\log N) operations on N numbers, the QFT does the job on N = 2^n amplitudes with a circuit of only O(n^2) gates — an exponential saving that powers the most famous quantum algorithms of all.

What the QFT computes

Work with an n-qubit register, so there are N = 2^n computational-basis states |0\rangle, |1\rangle, \dots, |N-1\rangle. The QFT is the unitary that sends each basis state |x\rangle to a specific balanced superposition whose amplitudes are Nth roots of unity:

\text{QFT}\,|x\rangle \;=\; \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i\,xk/N}\,|k\rangle \;=\; \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} \omega^{\,xk}\,|k\rangle,

where \omega = e^{2\pi i/N} is the primitive Nth root of unity. Read it as a change of basis: the QFT carries the computational basis over to the Fourier (frequency) basis. The input x controls how fast the phase \omega^{xk} winds around the unit circle as k runs from 0 to N-1 — so x becomes a frequency.

Being a change of basis, the QFT is unitary (hence reversible), and by linearity it acts on any superposition \sum_x a_x|x\rangle by transforming its amplitude list (a_0,\dots,a_{N-1}) exactly the way the classical DFT would.

Why it matters: periodicity becomes frequency

Here is the point of the whole construction. Suppose the amplitudes hide a periodic pattern — the state is a comb of equally spaced spikes with some period r. Classically that structure is invisible to a single glance; but a Fourier transform turns a period into a sharp frequency peak. The QFT does the same to amplitudes: it concentrates the amplitude of a period-r state onto the basis states near multiples of N/r, so a subsequent measurement is very likely to reveal the period.

Turning hidden periodicity into a measurable frequency is precisely what quantum phase estimation and Shor's factoring algorithm need. The QFT is the engine that reads out the frequency they engineer into the amplitudes.

Worked example 1: the single-qubit QFT is the Hadamard

Take the smallest case, n = 1, so N = 2^1 = 2 and \omega = e^{2\pi i/2} = e^{i\pi} = -1. The QFT matrix has entries \tfrac{1}{\sqrt2}\,\omega^{xk} = \tfrac{1}{\sqrt2}(-1)^{xk} for x, k \in \{0,1\}. Filling the four entries:

\text{QFT}_{2} = \frac{1}{\sqrt2}\begin{bmatrix} (-1)^{0\cdot0} & (-1)^{0\cdot1} \\ (-1)^{1\cdot0} & (-1)^{1\cdot1} \end{bmatrix} = \frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = H.

The one-qubit QFT is exactly the Hadamard gate. That is no coincidence: the Hadamard is the Fourier transform over the two-element group, and the full QFT is what you get by stacking this idea across n qubits.

Worked example 2: QFT of the all-zeros state

What does the QFT do to |0\cdots0\rangle? Set x = 0 in the definition. Every phase becomes \omega^{0\cdot k} = 1, so all the amplitudes are equal:

\text{QFT}\,|0\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{0}\,|k\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}|k\rangle.

Out comes the uniform superposition of all N = 2^n bitstrings — the very same state a wall of Hadamards produces, H^{\otimes n}|0\rangle^{\otimes n}. So on the all-zeros input the QFT and the Hadamard layer agree; they part ways only when the input carries a nonzero frequency x, which sprinkles the winding phases \omega^{xk} across the sum.

The circuit: Hadamards and controlled rotations

The reason the QFT is cheap is its gorgeous recursive circuit. It is built from just two kinds of gate: H and the controlled phase rotation

R_k = \begin{bmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^{k}} \end{bmatrix},

which nudges the phase of |1\rangle by a finer and finer angle as k grows (R_2 is the S gate, R_3 the T gate, and so on). On each wire you place one Hadamard, then a controlled R_k from every less-significant qubit; a final layer of swaps reverses the qubit order. Step through the three-qubit version:

Count the boxes: qubit q_0 uses 1 + 2 gates, q_1 uses 1 + 1, and q_2 uses 1 — a triangular tally of 1 + 2 + 3 + \cdots + n = \tfrac{n(n+1)}{2} gates, plus at most n/2 swaps. That is O(n^2) gates in total, against the classical FFT's O(N\log N) = O(n\,2^n) arithmetic operations on the 2^n amplitudes.

Worked example 3: the two-qubit QFT circuit

Spell out n = 2 gate by gate. Label the qubits q_0 (the more significant) and q_1, with N = 4 and \omega = e^{2\pi i/4} = i. The circuit is four gates:

H on q_0 — start the Fourier transform on the top wire.
Controlled-R_2 (the controlled-S gate) — q_1 controls a phase kick of e^{2\pi i/4} = i on q_0, the cross-term that couples the two frequencies.
H on q_1 — Fourier transform the bottom wire.
Swap q_0 and q_1 — fix up the reversed bit order the algorithm leaves behind.

Four gates realise the full 4\times4 QFT matrix. Writing out that matrix directly would mean sixteen phase entries \tfrac12\,i^{\,xk}; the circuit builds the same operator from a handful of one- and two-qubit gates — the exact economy that scales to O(n^2).

the QFT is the change of basis \text{QFT}\,|x\rangle = \tfrac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i\,xk/N}|k\rangle on N = 2^n amplitudes, using \omega = e^{2\pi i/N};
it maps the computational basis to the Fourier/frequency basis, turning periodic amplitude structure into a detectable frequency;
the single-qubit QFT is exactly the Hadamard, and \text{QFT}\,|0\cdots0\rangle is the uniform superposition;
its circuit uses only Hadamards and controlled phase rotations R_k (plus swaps) — about \tfrac{n(n+1)}{2} = O(n^2) gates, versus O(N\log N) for the classical FFT;
it is a subroutine — for phase estimation and period finding — not a classical data-processing box.

There is nothing exotic about the mathematics of the QFT — it is the ordinary discrete Fourier transform, the workhorse that separates an audio clip into frequencies so an MP3 can throw away the ones your ear won't miss, and that turns an image block into spatial frequencies so a JPEG can compress it. What is exotic is where it runs. Instead of transforming a list of numbers stored in memory, the QFT transforms the amplitudes of a quantum state, all 2^n of them at once, in only O(n^2) gates. The formula your media player evaluates in O(N\log N) steps, a quantum computer performs in the exponent — a genuinely different scaling for the very same transform.

It is tempting to conclude that because the QFT is exponentially cheaper in gates than the FFT, quantum computers give us a faster Fourier transform for everyday data. They do not. The catch is readout: the QFT leaves its answer encoded in the amplitudes of a quantum state, and measurement hands you only one basis label per run, drawn at random with probability |a_k|^2 — you can never extract the full list of 2^n transformed amplitudes. There is also no way to load an arbitrary classical signal into those amplitudes cheaply in the first place. So the QFT is a subroutine: it is powerful precisely inside algorithms like phase estimation and period finding, where you only need to read out a single frequency that interference has made overwhelmingly likely — not a data-processing black box that returns a spectrum you can print.