The Quantum Fourier Transform

The QFT converts patterns in a quantum state's amplitudes — especially repeating, periodic patterns — into probability peaks at the corresponding frequencies, using only about n²/2 gates on n qubits where a classical FFT of the same data needs on the order of n·2ⁿ steps. The catch is that its input and output live in amplitudes you cannot read directly, so the QFT is an engine inside algorithms like phase estimation and Shor's, not a drop-in FFT accelerator.

What does a Fourier transform do, and what does the QFT transform?

If you've done signal processing, you know the discrete Fourier transform: feed it samples of a signal, get back the strength of each frequency in it. A signal repeating with period r across M samples produces spikes at multiples of M/r. The FFT is the fast classical algorithm for this.

The quantum Fourier transform applies the same mathematical transform to a different object: the amplitudes of a quantum state. Refresher: an n-qubit state assigns each of the 2ⁿ bitstrings an amplitude — a complex number whose squared magnitude is that outcome's probability, and whose angle is its phase, invisible to a single measurement (see probability amplitudes and amplitudes and phase). Treat the 2ⁿ amplitudes as 2ⁿ signal samples; the QFT outputs a state whose amplitude on string k is the sum of all input amplitudes weighted by phase factors:

output(k) = (1/√8) × Σₓ input(x) · e^(2πi·x·k/8) (written for 3 qubits, 8 amplitudes).

Two notation notes, since both appear everywhere from here on. Σₓ means: add up one term for each input value x. And e^(iθ) is the standard shorthand for a phase factor — the size-1 complex number sitting at angle θ (in radians): at θ = 0 it equals +1, at θ = π it equals −1, at θ = π/2 it equals i. So e^(2πi·x·k/8) simply means the size-1 arrow at angle 2π·x·k/8 — nothing more.

The consequence to hold onto: a periodic pattern in the amplitudes becomes a concentration of probability at the pattern's frequency — and probability, unlike phase, is something measurement can see. That single sentence is why the QFT sits inside phase estimation and Shor's algorithm.