Quantum Fourier Transform
A single basis state goes in; a flat spread of amplitudes with a phase ramp comes out. The ramp's slope is the number you started with.
Quantum Fourier Transform visualization
Bar height is magnitude; the dial under each bar is that amplitude's phase. The input has one bar with a flat phase — the output has 8 equal bars whose dial hands step around by a constant amount.
A Fourier transform on amplitudes
The QFT does to a quantum state what the discrete Fourier transform does to a signal: it turns position information into frequency information. A sharp spike at position x becomes a flat magnitude spread with a phase that winds around at a rate proportional to x.
Drag the input basis state and watch the output dials. At |000⟩ every hand points the same way — zero frequency. Each step up the input adds one more full turn across the register, so the slope of the ramp is the input value. That is the entire content of the transform, and none of it shows up in the bar heights.
Where the speedup lives (and where it doesn't)
On 3 qubits the QFT needs 6 gates — about n²/2 — to transform all 8 amplitudes. The best classical FFT needs about N log N = 24 operations for the same size, and N grows exponentially in n. On 50 qubits that gap is roughly 1,275 gates against 5.6 × 10¹⁶ operations.
But you cannot read all 8 amplitudes out. One measurement gives one basis state, and the state is gone. The QFT is not a fast way to compute a Fourier transform of data you have; it is only useful inside an algorithm that arranges for the answer you want to be the thing you are likely to measure.
This is the engine of Shor's algorithm
Factoring reduces to period-finding: given f(x) = aˣ mod N, find the r with f(x + r) = f(x). A quantum computer can prepare a superposition whose amplitudes are periodic with period r — but measuring it directly just returns a random point, which tells you nothing.
The QFT turns that periodic amplitude pattern into a sharp peak at the corresponding frequency. Now measurement returns something useful, because the peak is where almost all the probability went. The period falls out of that number by continued fractions, and the factors fall out of the period.