18. The Algorithmic Paradigm
18.1What makes an algorithm quantum?
Not the use of superposition — every naive "try all inputs in parallel" idea dies at measurement (1.7). An algorithm earns the name when interference does logical work: the circuit maps the input to a state where amplitudes for wrong answers point in different phases and cancel, while amplitudes for right answers align. Three ingredients recur throughout this part: a coherent encoding of structure (parity, period, marking) into phases via an oracle; a basis change — Hadamards or a Fourier transform — that converts those phases into measurable amplitude concentration; and a classical post-processing step (linear algebra, continued fractions, gcd) that extracts the answer from samples. Remove any one and the algorithm stops working; the rest of Part VII is these three ingredients, recombined.
18.2Oracle-based algorithms
Most provable quantum speedups live in the oracle model: a function f is available only as a black-box unitary Uf: |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩, and we count queries — calls to Uf — rather than raw time. This isolates the algorithmic idea from data-loading questions and makes lower bounds provable (the polynomial and adversary methods, Part VIII). Deutsch, Deutsch–Jozsa, Bernstein–Vazirani, Simon, and Grover all live here:
| Algorithm | Problem | Quantum queries | Classical queries |
|---|---|---|---|
| Deutsch | constant vs balanced, 1 bit | 1 | 2 |
| Deutsch–Jozsa | constant vs balanced, n bits | 1 | 2ⁿ⁻¹+1 (deterministic) |
| Bernstein–Vazirani | hidden string a | 1 | n |
| Simon | hidden period s | O(n) | Θ(2^{n/2}) |
| Grover | find marked item among N | Θ(√N) | Θ(N) |
The honesty clause: an oracle is a promise that Uf is cheap to implement coherently. If building it costs more than the classical algorithm, the "speedup" is fiction — the topic of 28.9 and the dequantization results.
18.3Interference as computation
The recurring mechanism is phase kickback: prepare an ancilla in |−⟩ = (|0⟩−|1⟩)/√2, and the oracle turns function values into phases — Uf|x⟩|−⟩ = (−1)^{f(x)}|x⟩|−⟩. Phases are invisible to measurement; they are relative, structural information. The algorithm's job is to rotate phases into amplitudes: apply Hadamards (or a QFT) so that (−1)^{f(x)} terms add constructively for some outcomes and destructively for others. You never learn f(x) for any particular x; you learn a global property that no single query reveals. This one trick, scaled up, is Deutsch (one bit), Bernstein–Vazirani (a linear form), Simon (a period), and the phase oracle of Grover. Learn it once here and every circuit in chapters 19–26 decomposes into phases plus basis changes.
18.4Amplitude amplification
A template worth naming early. Suppose a probabilistic classical procedure A succeeds with probability p; repeating it k times boosts success to about 1−(1−p)^k, so error ε costs O(1/ε) repetitions. Amplitude amplification (Brassard–Høyer–Mosca–Tapp, 2000) runs a quantum version — apply A, reflect about the success subspace, reflect about the initial state — and reaches success ≈ 1 with O(1/√p) applications. That is a quadratic speedup over the best possible classical repetition, and it applies to almost any probabilistic algorithm: Monte Carlo estimation, sampling, backtracking search. Grover's algorithm is the special case where A is the Hadamard layer; the full machinery is 25.6.
18.5Phase estimation
The second template: given a unitary U, one of its eigenvectors |u⟩, and the ability to apply controlled-U, estimate φ where U|u⟩ = e^{2πiφ}|u⟩ to m bits of precision. The circuit writes e^{2πi·2^k·φ} phases into a counting register and reads them out with an inverse QFT. Phase estimation is the engine inside Shor's algorithm (order finding is phase estimation on a modular-multiplication unitary) and the accepted route to ground-state energies in chemistry. It costs t = m + O(log(1/ε)) qubits and t applications of controlled powers of U; the hard part is always U itself. Chapter 24 gives it a full treatment.
18.6Quantum walks
The analog of random walks: a walker moves on a graph by unitary steps, in discrete time (coin or Szegedy walks) or continuous time (e^{−iHt}). On unstructured problems they reproduce Grover's quadratic speedup. On structured problems they can do more: element distinctness falls to O(N^{2/3}) queries (Ambainis), and Childs exhibited an oracle problem where a continuous-time walk is exponentially faster than any classical algorithm on the same graph. Quantum walks also underlie practical Hamiltonian simulation on sparse graphs. They are less central to this part than the QFT/QPE machinery, but they share its philosophy: turn graph or spectral structure into interference, then sample.
18.7Quantum Fourier transforms
The extraction primitive behind the big results: a state whose amplitudes are periodic becomes, after a QFT, a state concentrated on a few basis states — periods become peaks you can sample. The circuit costs only O(n²) gates for N = 2ⁿ dimensions, against O(N log N) for the classical FFT — but read the fine print in 23.7: the QFT consumes a quantum state, not a list of numbers, and returns a state you sample rather than a table. It is the shared skeleton of Simon's algorithm, Shor's period finding, and phase estimation, which is why it gets its own chapter (23) before the algorithms that depend on it.