Quantum Fourier Transform
The quantum Fourier transform (QFT) re-expresses a quantum state in the frequency basis using O(n²) gates, where a classical FFT on the same 2ⁿ-point vector needs O(n·2ⁿ) operations. The catch: input and output live in amplitudes and phases you cannot read out directly, so the QFT is never useful on its own — it is the readout stage 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 detects periodicity. Feed the QFT a state whose amplitudes repeat with period r, and it concentrates probability on multiples of 2ⁿ/r — turning a hidden repetition pattern into peaks you can measure. That single trick is the engine of phase estimation and Shor's algorithm.
Be clear about what it is not: the QFT is not a fast drop-in replacement for the FFT in signal processing. Your audio samples would first have to be loaded into 2ⁿ amplitudes (expensive), and the transformed result sits in amplitudes you cannot read back (a measurement gives you one sample from the distribution, not the spectrum). The QFT only pays off when the periodic state is produced by a quantum process and you only need one number derived from the spectrum.
The classical baseline
The fast Fourier transform computes the discrete Fourier transform of N data points in O(N log N) steps — for N = 2ⁿ, that is O(n·2ⁿ). It is one of the most optimized algorithms in existence, and for any task where the data is classical (audio, images, telemetry), the FFT is and will remain the right tool.
The comparison with the QFT is therefore apples to oranges: the FFT transforms data, the QFT transforms a quantum state. The QFT's exponentially smaller gate count only matters when the state is already quantum.
How the circuit works
The QFT on n qubits is a fixed sequence: a Hadamard on each qubit, interleaved with controlled phase rotations (CP) of angle π/2, π/4, π/8, … between qubit pairs, then a reversal of qubit order with SWAPs. That is n(n+1)/2 gates plus swaps — quadratic, not exponential.
Each Hadamard splits a qubit into an equal superposition; each controlled rotation writes a fraction of the input value into the relative phase between the two branches. The output basis state's amplitude at index k is (1/√2ⁿ)·e^(2πi·xk/2ⁿ) for input x: every outcome equally likely, all information in phase. See amplitudes and phase for why phase is invisible to measurement but decisive under interference.
Run it: QFT of |101⟩
Proof the phases are real: QFT, then inverse QFT
Append the inverse QFT and every shot returns 101. The phase information was genuinely there — interference converts it back into a definite, measurable value. Compare this single bar with the flat histogram above: same information, different basis.
Limitations
- No data loading. Getting 2ⁿ classical values into amplitudes costs at least O(2ⁿ) work in general, erasing the gate-count advantage for classical data.
- No spectrum readout. Measuring after a QFT samples one index; recovering the full spectrum would take exponentially many shots.
- Precision. The smallest rotation on n qubits is π/2ⁿ⁻¹. Beyond a few dozen qubits these angles are far below realistic gate calibration, which is why practical proposals use the approximate QFT and why fault tolerance matters for Shor-scale uses.
- Transpilation cost.
CPis rarely a native gate; each one becomes several native two-qubit gates, and non-adjacent qubit pairs add SWAP overhead — see connectivity costs.
On hardware today
Small QFTs (3–10 qubits) run cleanly on current superconducting and trapped-ion machines and are a standard benchmark. At tens of qubits, results degrade: the circuit's all-to-all controlled rotations collide with limited connectivity, and coherent errors in the fine-grained angles accumulate. Nobody runs a QFT at a scale where its theoretical gate advantage matters, because the algorithms that need one at that scale (factoring, 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.