Algorithm Zoo · Primitives
Quantum Fourier Transform
Also known as: QFT
First described: Coppersmith (1994), used by Shor (1994), Kitaev (1995), 1994
The problem
Apply the discrete Fourier transform to a quantum state's amplitude vector.
QFT|x⟩ = (1/√N) Σ_y e^{2πixy/N} |y⟩. Implemented in O(n²) gates (or O(n log n) with approximate gates) on n = log₂(N) qubits — exponentially shallower than the O(N log N) classical FFT.
Best classical
O(N log N) classical FFT — extremely fast and used everywhere.
Quantum complexity
O(n²) gates (exact), O(n log n) (approximate to constant ε)
Our verdict
The most important quantum subroutine and the most misunderstood. QFT is not 'a fast Fourier transform' — it's a basis change. Its power comes from coupling with phase estimation to extract period information. Anywhere your algorithm needs period-finding or eigenphase-readout, QFT is the engine.
When to use it
- Inside quantum phase estimation (QPE) and Shor's algorithm.
- Anywhere you're transforming between Z and X bases of a register.
- Period-finding (the core of Shor and many cousins).
When not to use it
- As a 'fast FFT replacement' — the output is a quantum state, not the vector of Fourier coefficients. Reading the coefficients undoes the speedup.
Classical baseline
Classical FFT is one of the most-engineered algorithms in human history (FFTW, MKL, cuFFT). For any task that needs the Fourier coefficients classically, classical FFT wins by enormous constants.
Hardware cost
n(n+1)/2 controlled-phase gates plus n Hadamards. Controlled-phases with tiny rotations are the practical pain point — approximate QFT drops the smallest rotations and saves depth.
Key papers
- An approximate Fourier transform useful in quantum factoring ↗
Coppersmith · 1994 · IBM Research Report
Deep-dive tutorials
Last verified: 2026-05-24