Phase estimation
Give a quantum computer a unitary and one of its eigenstates, , and it can measure the phase to binary digits using extra qubits. That one routine, phase estimation, sits inside Shor’s algorithm, quantum chemistry, the HHL linear solver and much more. Most of the famous exponential speedups are phase estimation in disguise.
On the plate: the distribution of phase-estimation outcomes, sharpening as counting qubits are added.
The circuit
Prepare counting qubits in and the target in . Counting qubit controls ; by phase kickback (Chapter 110) it picks up the phase . The counting register is now exactly the QFT of a state encoding ; the inverse QFT (Chapter 112) turns it into a basis state close to , which you measure. Established
How accurate
If is an integer, you get it with certainty. Otherwise the outcomes spread over neighbours, with
and the nearest integer has probability at least . Set the phase to 0.30 and the counting qubits to 4. To get bits with failure probability , use about counting qubits. The cost is the controlled : unless powers of can be computed quickly, as modular exponentiation can in Shor’s algorithm, the circuit needs about applications of .
The Hadamard test, and versions used on hardware
With a single control qubit, the Hadamard test measures (and, with an S gate, the imaginary part) as the bias of a coin. Repeating with different powers and using classical post-processing gives iterative phase estimation: one ancilla, many shots, each bit fed back into the next measurement, as in Kitaev’s original 1995 scheme. Bayesian versions update a probability distribution for after each shot and choose the next experiment adaptively. These one-ancilla versions are what current devices run, because they need short circuits and few qubits. Established
Why it is everywhere
Factoring: the eigenphases of modular multiplication encode the period (Chapter 114). Chemistry: the eigenphases of are energies, so phase estimation on a molecule’s Hamiltonian, given a good approximate ground state, yields its ground-state energy (Part Five). Linear systems: phase estimation reveals the eigenvalues of a matrix, which HHL inverts (Chapter 120). Amplitude estimation (Chapter 116) is phase estimation of a Grover operator. Quantum signal processing (Chapter 119) is a refined descendant that avoids the counting register altogether.
What you now have
The phase-estimation circuit and its outcome distribution, the guarantee, how many counting qubits to use, the cost of controlled powers, the Hadamard test, iterative and Bayesian versions, and the algorithms built on it.
· · ·
Three questions to carry with you.
And one to work out. What is the guaranteed minimum probability of getting the nearest -bit estimate, , to three decimals?
Sources: A. Yu. Kitaev, arXiv:quant-ph/9511026 (1995). R. Cleve, A. Ekert, C. Macchiavello and M. Mosca, Proc. R. Soc. A 454, 339 (1998). M. A. Nielsen and I. L. Chuang, §5.2. L. Lin, Lecture Notes on Quantum Algorithms for Scientific Computation, arXiv:2201.08309. Checked by code: P(nearest) = 1 at φ = 0.25, 0.876 at φ = 0.3 and 0.685 at φ = 1/3 with t = 4; distributions sum to 1; 4/π² = 0.405.