Quantum Fourier Transform

Grover's algorithm (Ch. 28) searches; the next two chapters are about a different superpower — detecting hidden periodicity, which turns out to be the actual mathematical engine behind breaking RSA encryption (Ch. 31). The Quantum Fourier Transform is the subroutine that makes it possible: the quantum analog of the ordinary discrete Fourier transform, converting a signal in "position" into the same signal described by its frequencies.

The definition

QFT|x⟩ = (1/√N) Σ_y e^(2πixy/N) |y⟩

Every basis state |x⟩ gets spread into a superposition of every |y⟩, weighted by a complex phase that depends on x and y together. Applied to a full superposition rather than a single |x⟩, the linearity from Ch. 4 does the rest.

Why this is the right generalization of the classical FFT

The classical discrete Fourier transform turns a signal sampled at N points into N frequency components, in O(N log N) classical operations via the Fast Fourier Transform. The quantum version computes the analogous transform on n=log₂N qubits using only O(n²) quantum gates — exponentially fewer gates than even the classical FFT needs additions. The catch, and it's a serious one: you can't read out all N transformed amplitudes the way classical FFT output lets you — Ch. 7's Born rule only ever gives you one measurement. The QFT's speed is only useful when, like Ch. 30's phase estimation, you only need a small amount of information out of the transformed state, not the whole thing.

How the O(n²) gate count is actually achieved

The circuit that implements the QFT efficiently uses H gates and controlled phase-rotation gates R_k = diag(1, e^(2πi/2^k)) between every pair of qubits, followed by a final bit-reversal of the output register. The controlled-phase structure is exactly Ch. 5's tensor-product machinery combined with Ch. 23's phase-oracle idea, applied recursively — it's the same building blocks from earlier chapters, arranged cleverly enough to avoid ever needing the full N×N matrix this chapter's definition writes down explicitly.