The Quantum Fourier Transform
The subroutine hiding inside Shor's algorithm and phase estimation
By the end of this topic you'll be able to
The classical discrete Fourier transform (DFT) converts a sequence of N values in the 'time domain' into N coefficients in the 'frequency domain,' describing which periodic components make it up. It is the mathematical backbone behind everything from audio compression to numerically solving differential equations.
The quantum Fourier transform (QFT) performs the identical mathematical transformation, but applied directly to the amplitudes of a quantum state rather than to an array of classical numbers: given a state Σₖ xₖ|k⟩, the QFT produces a new state whose amplitude on each basis vector |k⟩ is the discrete Fourier transform of the original amplitude sequence xₖ.
What makes this a landmark result isn't the transform itself — classically, the Fast Fourier Transform algorithm already computes a DFT on N points in O(N log N) arithmetic operations, which is already efficient. It's that the quantum circuit implementing the same transform on n qubits, where N=2ⁿ amplitudes are involved, needs only O(n²) elementary gates.
At 0° the two waves line up and reinforce — constructive interference, peak amplitude ≈ 2.00×. At 180° they cancel exactly — destructive interference, amplitude ≈ 0. Every quantum algorithm's speedup comes from arranging phases like these so the wrong answers land near 180° and cancel, leaving the right answer standing.
Since n = log₂(N), that works out to O((log N)²) gates for a transform over N amplitudes — exponentially fewer gates than even the already-efficient classical FFT needs arithmetic operations. The circuit itself is built from nothing more exotic than Hadamard gates interleaved with controlled phase-rotation gates, one register of qubits, no ancillas required.
There's an important catch that has to be stated clearly: this exponential gate-count advantage does not translate into reading out N Fourier coefficients faster than classically. Measuring the transformed state still returns only one basis state at random, never the full transformed amplitude vector — the same 'quantum parallelism doesn't give free readout' lesson encountered with Deutsch-Jozsa.
The QFT's genuine power shows up when it is used as a subroutine inside a larger algorithm that only ever needs some specific, compactly extractable piece of information from the transformed state, rather than the whole vector of coefficients. That is exactly the situation in both of the next two topics, quantum phase estimation and Shor's factoring algorithm, each of which the QFT makes possible.
Try It Yourself
The general QFT formula is QFT|x⟩ = (1/√N) Σ_{y=0}^{N-1} e^{2πixy/N}|y⟩. Apply it directly to a single qubit (N=2) in state |1⟩, and confirm it matches H|1⟩.
- 1For N=2, x=1, the sum runs over y=0 and y=1: QFT|1⟩ = (1/√2)(e^{2πi·1·0/2}|0⟩ + e^{2πi·1·1/2}|1⟩).
- 2e^{2πi·0/2} = e^0 = 1, and e^{2πi·1/2} = e^{iπ} = -1 (from the Euler's-formula derivation earlier in this curriculum), so QFT|1⟩ = (1/√2)(|0⟩ - |1⟩) = |−⟩.
- 3Compare to H|1⟩ directly from the Hadamard matrix: H|1⟩ = (1/√2)(1,-1) = |−⟩ — exactly the same result.
QFT|1⟩ = |−⟩, exactly matching H|1⟩ — confirming that for the simplest possible case (a single qubit, N=2), the general QFT formula reduces exactly to the familiar Hadamard gate.
Reference
| Classical FFT cost | N = 2ⁿ classical data points | |
| QFT circuit cost | n qubits, N = 2ⁿ amplitudes transformed | |
| QFT building blocks | The full circuit is Hadamards interleaved with controlled-R_k gates |
Quick Check
Why can't the QFT be used to simply 'read out' the Fourier transform of classical data faster than an FFT?
Roughly how many gates does the QFT circuit need for n qubits?