Quantum Phase Estimation
Reading off a hidden eigenvalue — the workhorse subroutine of quantum computing
By the end of this topic you'll be able to
Quantum phase estimation solves a deliberately general-purpose problem: given a unitary U and one of its eigenstates |u⟩, satisfying U|u⟩ = e^{2πiθ}|u⟩ for some unknown θ, estimate θ to as many bits of precision as desired.
Framed so abstractly, the problem might not sound like much — but a striking number of quantum algorithms turn out, once unpacked, to be phase estimation applied to some cleverly chosen unitary U, which is exactly what makes it worth learning as a subroutine in its own right rather than as a one-off trick.
The circuit uses two registers: a 'counting' register of n qubits, initialized to |0⟩ and then placed in an equal superposition by Hadamard gates, and a 'target' register prepared in |u⟩.
Applying controlled powers of U — U, U², U⁴, U⁸, and so on, each one controlled by a successive qubit of the counting register — kicks phase information about θ into the counting register's amplitudes through a mechanism known as phase kickback, without ever disturbing the target register's state |u⟩.
Applying the inverse quantum Fourier transform to the counting register, then measuring it, converts that accumulated phase information into an ordinary n-bit string — a direct binary approximation of θ, extracted from a register that was never directly holding θ as a number until this final step.
Why this matters extends well beyond any single application: order-finding, which underlies Shor's algorithm, is a phase-estimation problem in disguise; so is estimating the ground-state energy of a molecule, since the phase picked up by the time-evolution unitary e^{-iHt} is directly proportional to that energy; so are several approaches to solving structured linear systems of equations.
Phase estimation is, in this sense, less an 'algorithm' in the everyday sense of solving one specific problem, and more a general-purpose subroutine — occupying roughly the same role in quantum algorithm design that a fast Fourier transform or a matrix inversion routine occupies in classical numerical computing.
Try It Yourself
Suppose U has eigenstate |u⟩ with eigenvalue e^{2πiθ} where θ = 1/4 exactly. Using a 2-qubit counting register, what basis state does phase estimation return, and how do you recover θ from it?
- 1Write θ = 1/4 as a binary fraction: 1/4 = 0×(1/2) + 1×(1/4), i.e. 0.01 in binary.
- 2Because θ is exactly representable using 2 binary digits, a 2-qubit counting register is exactly enough — phase estimation returns the counting register collapsed, with certainty (no approximation error), to the basis state whose bits spell out 0.01, i.e. |01⟩.
- 3To recover θ, read the measured bit string 01 as a binary fraction: 0×(1/2) + 1×(1/4) = 1/4 — exactly the original θ.
The counting register is measured as |01⟩ with certainty, and reading '01' as the binary fraction 0.01 gives back θ = 1/4 exactly — no error, because 1/4 happens to have an exact 2-bit binary representation.
Reference
| Problem | Estimate the phase of an eigenvalue | |
| Counting register | Ends up holding an n-bit estimate of θ | |
| Controlled-U powers | Kicks phase information into the counting register | |
| Final step | Extracts θ as a classical bit string |
Quick Check
What does quantum phase estimation take as input?
Which step directly precedes measuring the counting register?