113
Part Three · B · Algorithms

Phase estimation

Give a quantum computer a unitary UU and one of its eigenstates, U∣u⟩=e2πiφ∣u⟩U|u\rangle = e^{2\pi i\varphi}|u\rangle, and it can measure the phase φ\varphi to tt binary digits using tt 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 tt counting qubits in ∣+⟩|+\rangle and the target in ∣u⟩|u\rangle. Counting qubit jj controls U2jU^{2^j}; by phase kickback (Chapter 110) it picks up the phase e2πi 2jφe^{2\pi i\,2^j\varphi}. The counting register is now exactly the QFT of a state encoding φ\varphi; the inverse QFT (Chapter 112) turns it into a basis state close to 2tφ2^t\varphi, which you measure. Established

How accurate

If 2tφ2^t\varphi is an integer, you get it with certainty. Otherwise the outcomes spread over neighbours, with

P(m)=∣sin⁡(π(2tφ−m))2tsin⁡(π(φ−m/2t))∣2P(m) = \left|\frac{\sin\big(\pi(2^t\varphi - m)\big)}{2^t\sin\big(\pi(\varphi - m/2^t)\big)}\right|^2

and the nearest integer has probability at least 4/π2≈0.4054/\pi^2 \approx 0.405. Set the phase to 0.30 and the counting qubits to 4. To get nn bits with failure probability ε\varepsilon, use about n+log⁡2(2+1/2ε)n + \log_2(2 + 1/2\varepsilon) counting qubits. The cost is the controlled U2jU^{2^j}: unless powers of UU can be computed quickly, as modular exponentiation can in Shor’s algorithm, the circuit needs about 2t2^t applications of UU.

The Hadamard test, and versions used on hardware

With a single control qubit, the Hadamard test measures Re⟨u∣U∣u⟩\mathrm{Re}\langle u|U|u\rangle (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 φ\varphi 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 e−iHte^{-iHt} 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 4/π24/\pi^2 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.

When does phase estimation give the exact answer?tap
When 2^t φ is an integer.
What usually dominates its cost?tap
Implementing the controlled powers U^(2^j).
Why do current devices use iterative phase estimation?tap
It needs only one ancilla and shorter circuits.

And one to work out. What is the guaranteed minimum probability of getting the nearest tt-bit estimate, 4/π24/\pi^2, to three decimals?

P ≥

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.

Next · Chapter 114
Shor's algorithm: factoring and discrete log

One algorithm threatens most internet encryption. Here is an honest count of how far away that is.

Turn the page