23. Quantum Fourier Transform

23.1The classical Fourier transform

The Fourier transform decomposes a signal into frequencies: given N samples, it reports the amplitude and phase of each of the N possible periodic components. After Cooley and Tukey's 1965 FFT, it costs O(N log N) — the most-used algorithm in numerical software, from audio codecs to solving PDEs to multiplying integers. The property that matters for this part: a sequence with period r has a Fourier transform concentrated near multiples of N/r. Peaks in the frequency domain reveal periods in the data. Hold that thought; it is the entire bridge to Shor's algorithm.

23.2The discrete Fourier transform

Formally, the DFT of a vector v of length N is V_k = Σ_j v_j·e^{−2πi jk/N}, equivalently the matrix-vector product V = F·v with F_{kj} = ω^{kj}, ω = e^{−2πi/N}. Normalize F by 1/√N and it is unitary — a change of basis between the "position" basis and the "frequency" basis. Two properties carry over to the quantum setting: unitarity (the transform is reversible) and the convolution theorem (periodic structure maps to sparse support). The one property that does not carry over: classically you read all N outputs; quantum mechanically you get one sample of the transformed amplitudes.

23.3The quantum Fourier transform

Apply that unitary to a quantum state: QFT_N|j⟩ = (1/√N)·Σ_{k=0}^{N−1} e^{2πi jk/N}|k⟩, extended linearly to arbitrary states — it is the DFT matrix acting on amplitudes. On a computational basis state |j⟩ the output is a uniform superposition whose phases encode j; on a state with periodic amplitudes, the output concentrates where the classical DFT would. The caveats are the fine print of the entire chapter: the input must already be a quantum state (loading classical data is often the real cost, 50.6), and the output must be sampled, not read — one measurement, not a table of N numbers. QFT is powerful exactly when you want one sample of a sharply peaked distribution.

23.4Circuit decomposition

No black-box N×N matrix is applied; the QFT decomposes into O(n²) one- and two-qubit gates. For n = 3 (q0 = most significant bit of j):

H on q0; controlled-R2 between q0,q1; controlled-R3 between q0,q2;
H on q1; controlled-R2 between q1,q2; H on q2;  then SWAP(q0,q2)

q0: |j1> ──H────●────●────────────────
                │    │
q1: |j2> ───────R2───●────H────●──────
                     │         │
q2: |j3> ────────────R3────────R2──H──

The controlled-Rk gates are diagonal (they only phase the |11⟩ branch), so their control/target labels are conventional. The final swaps reverse the qubit order — the circuit naturally produces the bit-reversed output, and implementations either insert swaps or track the relabeling. General n: H, then controlled rotations from every later qubit, per qubit.

23.5Controlled rotations

The workhorse is Rk = diag(1, e^{2πi/2^k}) — a phase rotation by 2π/2^k, so each successive k halves the angle. Between the H on qubit i and the next, qubit i collects controlled rotations R2, R3, … from all lower-order qubits: the accumulated phase on the |1⟩ branch becomes e^{2πi·0.jᵢjᵢ₊₁…}, the binary fraction of j starting at position i. Total count: n Hadamards, n(n+1)/2 controlled rotations, ⌊n/2⌋ swaps — O(n²) gates, all diagonal except the Hadamards. On hardware each controlled rotation is a native two-qubit interaction (or an approximated sequence — synthesis over Clifford+T costs O(log(1/ε)) T gates per rotation), which is why QFT-heavy circuits are rotation-count-bound.

23.6Approximate QFT

The rotations with small k have tiny angles — R20 rotates by less than a milliradian. Drop all controlled-Rk with k > m: each discarded phase is at most 2π/2^{m+1}, and with at most n² drops the worst-case accumulated phase error is about πn²/2^{m+1}. Choosing m ≈ log₂(n²/ε) bounds the error by ε while cutting the gate count from O(n²) to O(n log n). On error-corrected hardware rotations cost real T-gates, so the approximate QFT is what serious Shor/QPE implementations actually compile to. The lesson generalizes: high-precision phases are the first place to spend accuracy budget — and the first place to reclaim it.

23.7Complexity

The honest comparison. Classical FFT: O(N log N) = O(n·2ⁿ) arithmetic operations on a vector of N = 2ⁿ numbers you already hold in memory. Quantum QFT: O(n²) gates — exponentially fewer gates — but on a state that (a) took something else to prepare and (b) yields one sample, not N coefficients. If your task is "transform this array of data", the FFT wins, permanently. If your task is "I have a quantum state with periodic structure and I want to sample its frequency content", the QFT is essentially free. Every claimed QFT speedup must state which side of that line it lives on — the same discipline as 1.9.

23.8Applications

Four, in increasing depth. Period finding: Simon-style and Shor-style — a periodic state goes in, a peak comes out (26.6). Phase estimation: the inverse QFT is the readout of QPE, the workhorse of chemistry and of Shor itself (24). Arithmetic: the Draper QFT adder performs addition by phase accumulation, and QFT-based multiplication underlies several modular-arithmetic pipelines. Fourier sampling as a primitive: any hidden-subgroup-flavored problem starts here. Notice the pattern: the QFT is never the algorithm; it is the readout layer of an algorithm whose real work happens in state preparation and in the classical post-processing.

import numpy as np
n, N = 3, 8
j = np.arange(N)
F = np.exp(2j * np.pi * np.outer(j, j) / N) / np.sqrt(N)   # QFT matrix
print("unitary:", np.allclose(F @ F.conj().T, np.eye(N)))  # True
v = np.array([1, 1, 0, 0, 0, 0, 0, 0], dtype=complex)      # |0> + |1>
print("matches np.fft.ifft * sqrt(N):",
      np.allclose(F @ v, np.sqrt(N) * np.fft.ifft(v)))     # True