Quantum Phase Estimation: The Subroutine Behind Shor's Algorithm

Shor's factoring algorithm is the most famous quantum algorithm ever discovered — the one that could one day break RSA encryption. But Shor's algorithm is not really about factoring. At its core, it is about finding the period of a function, and period-finding is, underneath, a single quantum subroutine: quantum phase estimation. Given a unitary operation U and one of its eigenstates |ψ⟩, phase estimation extracts the phase θ in the eigenvalue e^2πiθ — and in Shor's algorithm, that phase quietly encodes the factors. This article explains how the subroutine works, why phase kickback is the real trick, and how Shor turns an eigenvalue into a broken cryptosystem.

The problem, stated precisely

Every unitary operator U has eigenvectors |ψ⟩ with eigenvalues of the form e^2πiθ, where θ is a real number in [0, 1). (Unitary eigenvalues always lie on the unit circle in the complex plane.) Quantum phase estimation, or QPE, solves this task: given U and an eigenstate |ψ⟩, estimate θ to n bits of precision.

Why would anyone want that? Because in the quantum algorithms that matter, the answer you seek is hiding inside a phase. In Shor's algorithm, the period r of the modular-exponentiation function appears as the phase s/r of a certain unitary's eigenvalues. In quantum chemistry, molecular energy levels appear as phases of the time-evolution operator. QPE is the universal tool for converting those hidden phases into bit strings you can read.

A classical analogy helps. Imagine a clock hand spinning at an unknown rate, visible only through a strobe light. One glance tells you little — but a careful sequence of strobed observations, each doubling the effective observation time, pins down the rate to arbitrary precision. QPE is the quantum version of that strobe sequence.

Phase kickback: the trick everything rests on

The entire subroutine stands on one phenomenon: phase kickback. Consider a controlled-U gate where the target qubit holds an eigenstate |ψ⟩ of U, and the control qubit is in superposition:

c-U · (|0⟩ + |1⟩)/√2 ⊗ |ψ⟩ = (|0⟩ + e^2πiθ|1⟩)/√2 ⊗ |ψ⟩

Look at what happened. The target qubit is completely unchanged — it was an eigenstate, so U merely multiplied it by its eigenvalue. But that eigenvalue, a global phase as far as the target is concerned, has been kicked back onto the control qubit, where it is now a relative phase between |0⟩ and |1⟩ — and relative phases are measurable. This is the only way quantum mechanics lets you “see” an eigenvalue: never by looking at the eigenstate directly, but by letting the phase leak onto a probe qubit you control. Everything else in QPE is machinery for amplifying that leaked phase until it is large enough to read.

The circuit, piece by piece

QPE uses two registers: a counting register of n qubits (the probes) and a target register holding the eigenstate |ψ⟩. The circuit has four stages:

Superpose the probes. Apply Hadamard gates to all n counting qubits, producing an equal superposition over all 2ⁿ basis states.
The controlled-power ladder. For each counting qubit j (from 0 to n−1), apply a controlled-U^{2^j} gate, controlled on qubit j and targeting the eigenstate register. By phase kickback, qubit j picks up the phase e^{2πi·2^j·θ} on its |1⟩ component. The counting register is now in the state 2^−n/2 Σ_k=0^2ⁿ−1 e^2πiθk|k⟩ — the phase θ has been written, bit by bit, into the amplitudes.
Inverse quantum Fourier transform. The state above is exactly what the quantum Fourier transform produces from the basis state |2ⁿθ⟩. Applying the inverse QFT therefore converts it back: if 2ⁿθ is an integer, the register collapses to precisely |2ⁿθ⟩.
Measure. Read the n counting qubits as a binary fraction. If you measured the integer m, your estimate is θ ≈ m/2ⁿ.

The doubling powers 1, 2, 4, 8, … are the strobe-light sequence from the analogy: each successive probe is sensitive to the phase at twice the resolution, so n probes pin down n binary digits of θ.

Worked example: estimating θ = 1/8 with the T gate

Let us run QPE on something concrete. The T gate is diag(1, e^iπ/4), so |1⟩ is an eigenstate with eigenvalue e^iπ/4 = e^2πi·(1/8) — meaning θ = 1/8 = 0.001 in binary. Three counting qubits should recover it exactly, since 2³ · (1/8) = 1.

Here is the full circuit in Qiskit. A controlled-T^{2^j} is just a controlled phase rotation by π·2^j/4, which Qiskit provides directly as the cp gate:

from qiskit import QuantumCircuit from qiskit.circuit.library import QFT from math import pi

n = 3 qc = QuantumCircuit(n + 1, n) qc.h(range(n)) # superpose counting qubits qc.x(n) # target register: eigenstate |1> of T for j in range(n): qc.cp(pi * 2**j / 4, j, n) # controlled-T^(2^j) via phase kickback qc.append(QFT(n, inverse=True), range(n)) # inverse QFT qc.measure(range(n), range(n))

After the Hadamards and the controlled-phase ladder, the counting register holds 2^−3/2(|0⟩ + e^2πi·(1/8)|1⟩)(|0⟩ + e^2πi·(2/8)|1⟩)(|0⟩ + e^2πi·(4/8)|1⟩). The inverse QFT maps this to |001⟩, and measurement returns 001 — binary for 1 — giving θ = 1/8 exactly. Try it on a simulator: you will measure 001 every single time.

What if θ is not a clean binary fraction?

Real phases are rarely as tidy as 1/8. When 2ⁿθ is not an integer, the inverse QFT cannot produce a single basis state — instead, the measurement distribution peaks sharply around the two n-bit integers nearest to 2ⁿθ. The estimate you read off is still correct to roughly n bits: the standard analysis shows that with n counting qubits, you recover θ to m bits of precision with failure probability ε using n = m + O(log(1/ε)) qubits. A few extra probe qubits beyond the precision you want drive the failure probability down exponentially.

This graceful degradation is what makes QPE a practical subroutine rather than a mathematical curiosity. It does not demand that nature hand you a dyadic rational; it gives you the best n-bit approximation and tells you how confident to be.

How Shor's algorithm uses it

Here is where QPE earns its fame. To factor N, Shor's algorithm picks a random a coprime to N and considers the unitary U_a|x⟩ = |ax mod N⟩ — modular multiplication. Its eigenstates are

|u_s⟩ = r^−1/2 Σ_k=0^r−1 e^−2πisk/r|a^k mod N⟩

with eigenvalues e^2πis/r, where r is the order of a modulo N — the smallest r with a^r ≡ 1 mod N. The phase s/r encodes r, and r is what breaks the cryptosystem: if r is even, then gcd(a^r/2 ± 1, N) yields a nontrivial factor of N with good probability.

There is an obvious catch: preparing a specific eigenstate |u_s⟩ requires knowing r — the very thing we are trying to find. The beautiful workaround is that we do not need to. The easy-to-prepare state |1⟩ is an equal superposition of all the eigenstates: |1⟩ = r^−1/2 Σ_s |u_s⟩. Run QPE with |1⟩ as the target register, and the measurement collapses onto a random eigenstate's phase — you read off s/r for a random s. A classical continued-fractions expansion then recovers r from the fraction s/r, and the factoring step proceeds.

Two efficiency facts make this a polynomial-time algorithm rather than a thought experiment. First, the controlled-U_a^{2^j} operations are implemented by repeated squaring — computing a^{2^j} mod N classically, then building one modular-multiplication circuit per power, so the ladder costs polynomially many gates. Second, the inverse QFT needs only O(n²) gates. The quantum part of Shor's algorithm is, from end to end, QPE applied to modular multiplication.

The price tag

QPE is powerful but not free. It needs a target register with good overlap on the eigenstate of interest — Shor gets this for free via the |1⟩ superposition trick, but in quantum chemistry, preparing a state overlapping the molecular ground state is itself a hard problem. The controlled-U^{2^j} ladder can be deep: for a general U, implementing exponentially large powers is exponentially expensive, and only unitaries with fast-forwardable powers (like modular multiplication) keep the cost polynomial. And every extra bit of precision costs an extra probe qubit plus a doubling of the largest power — precision is linear in qubits but the circuit depth grows with it.

Putting it together

Quantum phase estimation is the subroutine that turns quantum phases into readable answers. Phase kickback leaks the eigenvalue onto probe qubits; the doubling ladder of controlled powers writes it across n probes at exponentially increasing resolution; the inverse QFT converts that pattern into a bit string. Shor wrapped this machinery around modular multiplication and got the most consequential quantum algorithm known. The same subroutine powers quantum chemistry simulations and the HHL linear-systems algorithm. Whenever a quantum algorithm needs to read a number out of a unitary, QPE is how.