A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The quantum Fourier transform (QFT) maps a computational basis state |j> of an n-qubit register to (1/sqrt(2n)) * sum_{k=0}^{2n - 1} e2*pi*i*j*k/2n |k> — the discrete Fourier transform of the basis state amplitudes. It can be implemented with O(n2) gates using a circuit of Hadamard gates and controlled phase rotations, compared to the O(n * 2n) operations of the classical FFT. The QFT does not compute the Fourier transform of classical data efficiently (reading out the result requires measurement), but it is the key subroutine in quantum phase estimation, Shor's algorithm, and many other quantum algorithms that extract periodic structure.
The classical discrete Fourier transform (DFT) converts a vector of N complex numbers into its frequency-domain representation. It is computable in O(N log N) time via the FFT algorithm. The quantum Fourier transform performs the same mathematical operation on quantum amplitudes — but because the amplitudes are encoded in an n-qubit state where N = 2n, the operation takes only O(n2) gates, which is O((log N)2) in terms of the input size N. This exponential reduction in gate count is real, but its utility is constrained by the quantum context.
The QFT circuit has an elegant recursive structure. For n qubits, apply a Hadamard gate to the first qubit, then apply controlled phase rotations from each subsequent qubit (controlled-R_2 from the second qubit, controlled-R_3 from the third, and so on, where R_k applies a phase of e2*pi*i/2k to the |1> state). Then recursively apply the QFT to the remaining n-1 qubits. Finally, reverse the bit order with SWAP gates. The total gate count is n Hadamard gates plus n(n-1)/2 controlled rotations plus n/2 SWAPs, giving O(n2) gates. In practice, rotations with very small angles (large k) can be dropped with negligible error, reducing the effective gate count further.
The QFT is not useful for "computing Fourier transforms of classical data on a quantum computer" — loading classical data into amplitudes is itself a hard problem (exponential cost in general), and measuring the output collapses it to a single basis state, losing most of the transform. The QFT is powerful when the input state arises naturally from a quantum computation. The canonical example is period finding: if a quantum state has a periodic structure with period r (nonzero amplitude only at positions 0, r, 2r, ...), the QFT maps this to a state with peaks at multiples of N/r. Measuring yields a random multiple of approximately N/r, from which r can be extracted using continued fraction expansion.
This is precisely how Shor's algorithm works: it constructs a periodic state via modular exponentiation, applies the QFT, and extracts the period. Quantum phase estimation follows the same pattern — it uses the QFT to convert a phase encoded in a unitary's eigenvalue into a computational basis measurement. The QFT is the Fourier analysis engine at the heart of most "algebraic" quantum algorithms (as opposed to "search" algorithms like Grover's). Understanding the QFT is understanding the core mechanism by which quantum computers extract hidden periodic structure exponentially faster than classical machines.