24. Phase Estimation

24.1Eigenvalues

Phase estimation solves: given a unitary U and an eigenvector |u⟩, estimate the eigenvalue. Because U is unitary, all eigenvalues lie on the unit circle — U|u⟩ = λ|u⟩ with |λ| = 1 — so every eigenvalue is λ = e^{2πiφ} for some phase φ ∈ [0, 1). Estimating λ is therefore estimating one real number φ, a fraction of a full turn. The restriction to unitary operators is not a limitation in practice: any Hermitian operator H can be exponentiated, e^{−iHt} is unitary, and its phases carry H's eigenvalues — that is exactly how chemistry applications reach Hamiltonians.

24.2Eigenphases

The phase φ is where the physics and the algorithms live. In chemistry, e^{−iHt} has eigenphase φ = −E·t/(2π) for energy E, so a phase estimate at known evolution time t yields E. In Shor's algorithm, the multiplication-by-a map on the period states has eigenphases s/r — rational, with the order r in the denominator, which is why continued fractions can dig r back out. Eigenphases are also what interferometers measure in quantum metrology, where QPE is the algorithmic version of the phase readout. In every case the same bookkeeping: phases are fractions of a turn, and turns are countable.

24.3Controlled unitaries

The circuit needs, for each counting qubit k, a controlled application of U^{2^k}. The powers are built by repeated squaring: U² = U·U, U⁴ = (U²)², and so on — so U^{2^k} costs one extra "squaring" beyond U^{2^{k−1}}, and for structured U (like modular multiplication) the whole family shares work. The counting register holds t qubits, each controlling one power; the eigenstate register holds |u⟩ throughout. In Shor's algorithm this block — modular exponentiation — is essentially the entire circuit cost: O(n³) gates naively, O(n²·polylog n) with fast multiplication. Everything else in QPE is cheap.

24.4The inverse QFT

After the controlled powers, the counting register holds (1/√2^t)·Σ_k e^{2πi·k·φ}|k⟩ — exactly the state whose QFT is a single peak at 2^t·φ. Apply the inverse QFT to the counting register and measure it:

counting:    |0>^t ──H^⊗t───●────────●────⋯────●───[QFT†]───measure: m ≈ 2^t·φ
                           │        │         │
eigenstate:   |u⟩ ─────────U^(2^0)──U^(2^1)──⋯──U^(2^(t-1))──    U|u⟩ = e^{2πiφ}|u⟩

If φ is exactly k/2^t for some integer k, the outcome is k with certainty. If not — the realistic case — the probability concentrates on the nearest integers to 2^t·φ, with tails described by 24.5. One measurement of t bits buys m ≈ t bits of the phase.

24.5Precision

The standard bound: to obtain φ accurate to 2^{−m} with probability at least 1−ε, use t = m + ⌈log₂(2 + 1/(2ε))⌉ counting qubits — the O(log(1/ε)) extra qubits suppress the tails of the peak. When φ is exactly representable in t bits, success probability is 1; when not, each shot lands on the nearest integer with probability ≈ 4/π² in the worst case (offset by half a bin), and a few shots with majority vote fix it. Alternatively spend shots instead of qubits: repeat the estimation and take the median. Precision, as always, is a budget line — you choose where to pay.

24.6Resource requirements

Count for a t-qubit, m-bit estimate: t counting qubits plus the eigenstate register; t applications of controlled U^{2^k}, which share structure so the total is close to t times the cost of one U; an inverse QFT, O(t²) gates, negligible; and O(1/ε) repetitions if you spend shots rather than qubits. The dominant line item is always U. In Shor, U is modular multiplication (24.3). In chemistry, U is e^{−iHΔt} Trotterized, with hundreds to millions of Pauli rotations per step, and the real bottleneck is not U but preparing an overlap-1 eigenvector — bad state preparation costs you repetitions proportional to 1/|⟨ψ|u⟩|². Plan resources around the eigenvector, not the QFT.

24.7Applications

Order finding (Shor, 26): estimate the eigenphase s/r of a modular-multiplication unitary, recover r by continued fractions. Chemistry: ground- and excited-state energies from e^{−iHt} — the most-cited path to useful quantum advantage, gated on state preparation. Quantum metrology: QPE is the optimal phase readout, reaching the Heisenberg limit 1/t rather than the standard quantum limit 1/√t. Linear algebra: eigenvalue estimation is the core of HHL-type algorithms for linear systems. Quantum counting: run QPE on the Grover operator to count marked items (25.6). A primitive this reusable is what "engineering-grade" means in algorithm design.

import numpy as np
t, phi = 8, 0.685
T = 2 ** t
k = np.arange(T)
cnt = np.exp(2j * np.pi * k * phi) / np.sqrt(T)           # after U^(2^k) chain
F = np.exp(2j * np.pi * np.outer(k, k) / T) / np.sqrt(T)  # QFT matrix
p = np.abs(np.conj(F) @ cnt) ** 2                          # inverse QFT, Born rule
top = np.argsort(p)[::-1][:2]
print([(m, round(p[m], 3)) for m in top], "-> phi ≈", top[0] / T)