Quantum Fourier Transform
The quantum Fourier transform (QFT) is a quantum circuit that rewrites a qubit state in terms of repeating patterns (frequencies). On n qubits it uses about n² gates, while a normal fast Fourier transform (FFT) on the same list of 2ⁿ numbers needs about n·2ⁿ steps. The catch: its input and output are stored in amplitudes and phases you can't read directly. So the QFT is never useful by itself. It is the readout step inside phase estimation and Shor's algorithm.
| Task | Best classical | Quantum |
|---|---|---|
| Fourier transform of a 2^n-point vector | O(n·2^n) — FFT on explicit data you can read | O(n^2) gates — on amplitudes you cannot read directly |
| Approximate QFT (dropping the tiniest rotations) | n/a | O(n log n) gates with negligible error |
What does the QFT actually do?
It finds repeating patterns. Say a qubit state has amplitudes (the numbers that set how likely each answer is) that repeat every r steps. We call r the period. The QFT piles the chance onto multiples of 2ⁿ/r. That turns a hidden repeating pattern into peaks you can measure. This one trick is the engine of phase estimation and Shor's algorithm.
Think of a music app showing the notes in a chord. It takes a sound wave and shows which pitches are in it. A Fourier transform does that kind of job.
But be clear about what the QFT is not. It is not a faster FFT you can plug into sound or image work. Your audio samples would first have to be loaded into 2ⁿ amplitudes, which is costly. And the result sits in amplitudes you can't read back. A measurement gives you one sample from the spread of chances, not the whole list of pitches. The QFT only pays off in one case. The repeating state must be made by a quantum process, and you must need only one number from the result.
How would a normal computer do it?
The fast Fourier transform (FFT) finds the frequencies in N data points in about N log N steps. For N = 2ⁿ, that is about n·2ⁿ steps. It is one of the most polished algorithms ever made. Whenever the data is normal data, like audio, images, or sensor readings, the FFT is the right tool. It will stay that way.
So comparing it with the QFT is apples to oranges. The FFT works on data. The QFT works on a quantum state. The QFT's much smaller gate count only matters when the state is already quantum.
Let's feel the size gap with n = 10. Then 2ⁿ = 1,024. The FFT needs about 10 × 1,024 ≈ 10,000 steps. The QFT needs about 10 × 10 = 100 gates.
How does the QFT circuit work?
The QFT on n qubits is a fixed list of steps:
- A Hadamard (H) on each qubit.
- Between them, controlled phase turns (
CP) between pairs of qubits, with angles π/2, π/4, π/8, and so on. Each angle is half the last one. - At the end, SWAP gates reverse the order of the qubits.
That is n(n+1)/2 gates plus swaps. For 3 qubits: 3 × 4 ÷ 2 = 6 gates. The count grows like n², not like 2ⁿ.
Each Hadamard splits a qubit into an equal superposition. Each controlled turn writes a piece of the input number into the relative phase between the two parts. (Phase is like the angle of a clock hand on each amplitude.) For input x, the output amplitude at position k is (1/√2ⁿ)·e^(2πi·xk/2ⁿ). Every size is the same, so every answer is equally likely. All the information is in the phases. See amplitudes and phase for why measurement can't see phase, but interference can.
Run it: what does the QFT of |101⟩ look like?
Are the phases real? Run the QFT, then undo it
Add the inverse QFT and every shot gives 101. The phase information really was there. Interference turns it back into a sure, measurable value. Compare this single bar with the flat chart above. It is the same information, seen along a different axis.
What are its limits?
- No cheap data loading. Putting 2ⁿ normal numbers into amplitudes takes at least about 2ⁿ steps in general. For normal data, that wipes out the gate-count gain.
- No full readout. Measuring after a QFT gives you one position. Getting the whole list of frequencies would take a huge number of shots, growing like 2ⁿ.
- Precision. On n qubits the smallest turn is π/2ⁿ⁻¹. For 10 qubits that is π/512. Past a few dozen qubits, these angles are far too tiny for real hardware to tune. That is why practical plans use the approximate QFT, which skips the tiniest turns. It is also why error correction matters for Shor-scale uses.
- Rewriting cost.
CPis rarely one of a chip's own gates. Each one becomes several two-qubit gates. Pairs of qubits that aren't wired together add SWAP costs too. See connectivity costs.
How does the QFT do on hardware today?
Small QFTs (3–10 qubits) run cleanly on current superconducting and trapped-ion machines. They are a standard test. At tens of qubits, results get worse. The QFT links every qubit with every other, and that clashes with chips' limited connectivity. Small errors in the fine angles also build up.
Nobody runs a QFT at a size where its gate-count advantage matters. The algorithms that need one at that size, like factoring and precise phase estimation, need error correction first. Try the 3-qubit version yourself in the lab. Or check real device specs on the hardware comparison.