Quantum Phase Estimation

Core Idea

Quantum phase estimation (QPE) estimates the eigenvalue phase of a unitary operator: given a unitary U and an eigenstate |u> with U|u> = e^(2*pi*i*phi)|u>, QPE outputs an n-bit approximation of phi using O(n) controlled applications of U and an inverse QFT. It is the core subroutine of Shor's algorithm, the HHL algorithm for linear systems, quantum chemistry simulations, and many other quantum algorithms. QPE converts the inaccessible phase information stored in a unitary's eigenvalue into a measurable computational-basis state.

Explainer

Quantum phase estimation solves a fundamental problem: given a unitary operator U and an eigenstate |u> satisfying U|u> = e^(2*pi*i*phi)|u>, determine phi. The phase phi is encoded in the complex eigenvalue of U, which cannot be directly observed through measurement of |u> (measuring |u> gives |u> with certainty, revealing nothing about phi). QPE extracts phi by converting it into a computational-basis measurement outcome using controlled unitaries and the inverse QFT.

The circuit uses two registers: an ancilla register of n qubits (determining the precision of the estimate) and a target register holding |u>. The ancilla qubits are initialized to |+> = H|0>, and each controls a different power of U applied to the target. Specifically, the j-th ancilla qubit (j = 0, 1, ..., n-1) controls U^(2^j). Because |u> is an eigenstate, U^(2^j)|u> = e^(2*pi*i * 2^j * phi)|u>, so the controlled operation applies a phase of 2^j * phi to the j-th qubit's |1> component. After all controlled unitaries, the ancilla register is in the state (1/sqrt(2^n)) sum_{k=0}^{2^n-1} e^(2*pi*i*k*phi) |k> — exactly the QFT of the state |round(2^n * phi)>.

Applying the inverse QFT to the ancilla register transforms it to a state peaked at |round(2^n * phi)>. If phi is exactly an n-bit binary fraction, the inverse QFT produces the exact binary representation with probability 1. If phi has more than n bits of precision, the result is a distribution peaked at the nearest n-bit approximation, with success probability at least 4/pi^2 ≈ 0.405 for the closest value. Adding a few extra ancilla qubits increases precision and success probability arbitrarily.

QPE is the engine inside many quantum algorithms. In Shor's algorithm, QPE is applied to the modular multiplication operator to extract the order (period) of modular exponentiation. In quantum chemistry, QPE applied to the time evolution operator e^(-iHt) of a molecular Hamiltonian estimates the ground-state energy. In the HHL algorithm for linear systems, QPE estimates eigenvalues of a matrix to enable matrix inversion. The pattern is always the same: encode a problem's answer as the phase of a unitary, then use QPE to read it out. This makes QPE perhaps the most important primitive in the quantum algorithm designer's toolkit — a universal phase-to-measurement converter.