Part IV. Protocols and Algorithms

Phase Estimation

Phase estimation turns "this unitary has structure" into a number: it reads eigenphases at a precision you choose and pay for, one counting qubit at a time.

Listen to this chapter

Most of the cost in a phase-estimation claim hides in the controlled unitary, not in the famous inverse QFT — so the ability to price precision and controlled operations is what separates evaluating an algorithm from admiring a diagram.

By the end you will be able to lay out the phase-estimation circuit, predict its output distribution for exact and inexact phases, and name the resource questions that decide whether a claim built on it is plausible.

Core concepts: eigenphase, counting register, controlled powers, resolution, eigenstate overlap.

Notice the two registers doing different jobs: the counting register only records phase, while the eigenstate register powers every controlled operation. That is why the cost of U — not the inverse QFT — usually dominates the budget.

Reading the phase of a unitary

Every unitary has eigenstates that it leaves alone except for a phase:

U ∣ ψ ⟩ = e^{2 π i θ} ∣ ψ ⟩

Phase estimation is the algorithm that measures $θ$ . Prepare the eigenstate on one register, put $m$ counting qubits into superposition on another, apply controlled powers of $U$ — $U$ , $U^{2}$ , $U^{4}$ , and so on, each controlled by one counting qubit — and finish with the inverse QFT. The counting register then holds an $m$ -bit estimate of $θ$ , readable by an ordinary measurement.

This single subroutine is the engine room of the algorithms that made the field famous. Factoring, discrete logarithms, quantum chemistry energies, linear-systems solvers — all can be reframed as "learn a phase of a structured unitary." Learn to read a phase-estimation circuit and you can read most of the heavyweight algorithm literature.

Precision is the price list

The counting register sets the resolution:

resolution \approx 1/ 2^{m}

Each additional counting qubit doubles the resolution — and demands controlled applications of ever-higher powers of $U$ . The inverse QFT that gets all the attention is, by comparison, a modest tail of Hadamards and controlled phase gates:

QFT_{N} ∣ x ⟩ = \frac{1}{N} y \sum e^{2 π i x y / N} ∣ y ⟩

The accounting is the lesson: how many counting qubits do you need? is simultaneously a question about the precision your application requires and about the deepest, most expensive part of the circuit. Precision is not a footnote to phase estimation. It is the budget.

Worked example: exact and inexact phases

Take two counting qubits, so the representable phases are $0, 1/4, 1/2, 3/4$ . Choose a unitary whose eigenphase is exactly:

θ = 1/4 = (0.01)_{2}

The ideal circuit returns the bit string 01 with certainty. Clean, exact, satisfying — and unrepresentative. Now choose:

θ = 1/3

No two-bit string equals $1/3$ . The output distribution concentrates on the nearest estimates — mostly 01, sometimes 10 — and no single run is guaranteed correct. Adding counting qubits tightens the concentration, at the price of more controlled powers. The toy case teaches the circuit; the inexact case teaches the statistics, and real applications are always the second case.

Where the intuition fails

The first trap is believing phase estimation is always exact, because textbook examples usually pick phases with finite binary expansions. Real phases require approximation, repeated runs, confidence analysis, and an explicit resource tradeoff. An estimate is a distribution, not an answer key.

The second trap is counting only the QFT. The controlled powers of $U$ dominate the depth, and if $U$ is expensive — modular exponentiation, a chemistry time-evolution, anything compiled from a real problem — phase estimation inherits that cost at every power up to $2^{m}$ . Cheap diagram, dear circuit.

The engineering view

For a computer scientist, phase estimation is a subroutine with a sharp interface:

Input: an eigenstate of $U$ , or a state with useful overlap on one;
Operation: controlled powers of $U$ , up to $2^{m - 1}$ ;
Register: $m$ counting qubits;
Transform: inverse QFT;
Output: a sampled $m$ -bit phase estimate;
Post-processing: interpret the bits, with a confidence statement.

The interface is only as useful as its feasibility conditions. Textbook diagrams assume the input is an eigenstate. Real workflows often prepare a superposition of eigenstates, so the measurement samples from several phases at once — still useful, but the output is evidence with probabilities attached, and the state-preparation cost belongs in the budget next to the controlled unitaries.

What this buys you in diligence

When a claim invokes phase estimation, ask: what is $U$ , how is controlled- $U$ implemented, how many powers are required, how many counting qubits set the resolution, what failure probability is acceptable, and what classical method is the baseline? A claim that answers in numbers is an engineering proposal. A claim that answers with the circuit diagram from this chapter is a restatement of the textbook, not a plan.

Exercise

Price two phases. Run the pipeline for one exact and one inexact phase, and account for the difference.

Write out the full phase-estimation pipeline for $θ = 1/4$ and for $θ = 1/3$ with two counting qubits.
Compare the precision your downstream decision needs against what a classical numerical method would require for the same purpose.
Deliver a table: phase, counting qubits, expected bit estimate, resolution from $1/ 2^{m}$ , and the controlled-unitary cost concern.
Mark exactly where the inverse QFT enters and where the controlled powers enter — and which one dominates the depth.
Close with one sentence: does the precision requirement make this algorithm claim plausible or resource-heavy?

Check your understanding

Answer without notes: how does the counting-qubit count affect phase estimation, and what does each extra qubit cost?

A passing answer ties $m$ to resolution $1/ 2^{m}$ , names controlled- $U^{2^{k}}$ as the price per bit, and mentions that inexact phases give a distribution rather than a guaranteed string.

Oral defense: walk the circuit left to right and state what each register knows at each stage.

If you get stuck

If the inverse-QFT step feels unmotivated, rework Chapter 31 (Quantum Fourier Transform) — the decoding move is exactly the "phase in, bits out" reading developed there. If controlled powers of a unitary feel abstract, Chapter 12 (Unitary Operations and Reversibility) is the right repair stop before Shor.