Quantum Cookbook

Part V · Chapter 30

Quantum Phase Estimation

Read ~20 min Prerequisites Ch. 1, Ch. 4, Ch. 29 Tools precision widget, code cell Live
Basic

Ch. 1 introduced eigenvalues; Ch. 4 noted that unitary matrices always have eigenvalues of the form e^(2πiφ) for some real φ. Quantum Phase Estimation (QPE) is the algorithm that actually measures φ — and it's the one piece standing between everything built so far and Shor's algorithm in Ch. 31.

The setup

You're given a unitary U and one of its eigenvectors |u⟩, with U|u⟩ = e^(2πiφ)|u⟩. The goal: estimate φ. The circuit uses t extra "counting" qubits, each controlling a power of U applied to |u⟩ — qubit k controls U^(2^k). Phase kickback (Ch. 23) deposits a phase onto each counting qubit proportional to φ; collectively, the counting register ends up holding exactly the kind of state Ch. 29's QFT is built to decode.

Fig. 30.1 — the QPE circuitcounting register + eigenvector register
|0⟩ |0⟩ ... |u⟩ H H controlled-Uᵏ QFT⁻¹
The purple box is exactly Ch. 29's inverse QFT — decoding the phase that kickback deposited across the counting qubits, the same "find the period" mechanism from Fig. 29.1, repurposed to read out φ.
Intermediate
Fig. 30.2 — set a true phase, adjust precision, watch it convergemore counting qubits = better estimate

Set φ to something exactly representable (try 0.25, 0.375, or any k/2ᵗ) and watch the error drop to exactly zero — then try an "ugly" value like 0.3 and watch the error shrink as you drag t upward, but never quite vanish.

Exact vs. approximate phases

If φ happens to be exactly representable in t bits (φ = k/2ᵗ for some integer k), QPE recovers it with certainty — probability exactly 1 on the correct outcome, the same all-or-nothing behavior Ch. 26's Deutsch–Jozsa showed for its promise. If φ isn't exactly representable, QPE still gives you the closest t-bit approximation with high probability, and that probability — along with the precision itself — improves as t grows.

Advanced

Why this specific algorithm is the bridge to Shor

Shor's algorithm needs to find the order r of a number modulo N — the smallest r with aʳ≡1 (mod N). The unitary U:|x⟩↦|ax mod N⟩ has eigenvalues e^(2πis/r) for integers s, and QPE applied to this U is precisely how the order r gets extracted: estimate the phase s/r, then use a classical algorithm called continued fractions to recover r from that fraction. Every single piece is now in place — Ch. 23's kickback, Ch. 29's QFT, and this chapter's phase-reading — for Ch. 31 to assemble them into an algorithm that factors numbers exponentially faster than the best known classical method.

Fig. 30.3 — code, runs in your browser
Watch the error shrink by roughly half each time t increases by 1 — the same convergence Fig. 30.2 shows visually.
Check your understanding

What does QPE estimate, given a unitary U and one of its eigenvectors |u⟩?

The phase φ in U's eigenvalue e^(2πiφ) for that eigenvector.

Check your understanding

What happens to the estimate's precision as you increase t, the number of counting qubits?

It improves — the estimate converges toward the true phase, with the error roughly halving for each additional counting qubit.

Check your understanding

When does QPE recover φ with absolute certainty?

When φ is exactly representable in t bits — φ = k/2ᵗ for some integer k. Otherwise it gives the closest t-bit approximation with high, but not certain, probability.

Check your understanding

What two earlier-chapter ideas does the QPE circuit combine?

Phase kickback (Ch. 23), which deposits φ-dependent phases onto the counting register via controlled-Uᵏ gates, and the inverse QFT (Ch. 29), which decodes those phases back into a readable number.

Check your understanding

How does QPE connect to Shor's algorithm specifically?

The unitary |x⟩↦|ax mod N⟩ has eigenvalues e^(2πis/r), where r is the order being sought. QPE estimates the phase s/r, and classical continued-fractions post-processing recovers r from that estimate.

Review queue

Scroll back to a chapter's quiz cards to review them once they're due — a full cross-chapter queue view is a planned upgrade.