The Phase Estimation Problem

Every unitary operator $U$ has eigenvalues that sit on the complex unit circle. That is not an accident — it is a direct consequence of unitarity. If $U$ is unitary and $|\psi\rangle$ is one of its eigenvectors, the eigenvalue equation reads

U|\psi\rangle = e^{2\pi i \varphi}|\psi\rangle, \qquad \varphi \in [0,1).

The real number $\varphi$ is called the phase (or eigenphase) of $U$ for that eigenvector. Estimating $\varphi$ from a quantum circuit — to as many bits of precision as needed — is the Quantum Phase Estimation (QPE) problem.

Why the phase matters

The phase $\varphi$ encodes information that is otherwise extremely hard to extract classically. Several landmark quantum algorithms reduce to phase estimation:

Shor's factoring algorithm uses QPE to find the period of a modular-exponentiation function. The period lets you factor large integers.
Quantum chemistry simulations use QPE to read out molecular ground-state energies encoded as eigenphases of a time-evolution unitary $e^{-iHt}$ .
Grover's algorithm can be analysed through the eigenphases of the Grover iterate.

In each case the key computational step is: given black-box access to controlled- $U$ , and given an eigenstate $|\psi\rangle$ , estimate $\varphi$ to $n$ bits.

Setting up the problem precisely

Before writing any circuit it helps to fix what we are given and what we want:

Given:

A unitary $U$ acting on $m$ qubits, accessible as a gate (or a family of controlled- $U^{2^k}$ gates).
An eigenstate $|\psi\rangle$ of $U$ , or a state that has significant overlap with at least one eigenstate.
A desired precision of $n$ bits.

Goal: Produce a classical $n$ -bit string $\tilde{\varphi}$ such that $|\tilde{\varphi}/2^n - \varphi| \le 2^{-n}$ with probability at least $1 - \epsilon$ for some small $\epsilon$ .

The remarkable fact is that a quantum circuit can accomplish this using only $n$ ancilla ("counting") qubits and $O(n)$ calls to controlled powers of $U$ . A classical algorithm that queries a unitary black box cannot extract phases at all — it can only learn action on specific states.

The circuit idea at a glance

The QPE circuit has three conceptual stages.

Stage 1 — Superpose the counting register. Apply $H^{\otimes n}$ to $n$ ancilla qubits initialised to $|0\rangle$ . This creates the uniform superposition

\frac{1}{2^{n/2}} \sum_{k=0}^{2^n - 1} |k\rangle.

Stage 2 — Kick back the phase. Use each ancilla qubit $j$ to control $U^{2^j}$ . Because $|\psi\rangle$ is an eigenstate, the controlled unitary does not entangle the two registers in amplitude — instead it imprints a phase factor $e^{2\pi i \varphi \cdot 2^j}$ onto the $|1\rangle$ component of ancilla qubit $j$ . After all $n$ controlled powers, the counting register holds

\frac{1}{2^{n/2}} \sum_{k=0}^{2^n - 1} e^{2\pi i \varphi k} |k\rangle.

This is precisely the Quantum Fourier Transform of the computational basis state $|2^n \varphi\rangle$ (when $\varphi$ is exactly representable in $n$ bits).

Stage 3 — Invert the QFT. Apply the inverse QFT to the counting register. The interference pattern collapses onto the state $|2^n \varphi\rangle$ , so a computational-basis measurement gives the $n$ -bit binary expansion of $\varphi$ deterministically (or near-deterministically when $\varphi$ is not exactly representable).

The coming lessons build each stage in code. The present lesson's job is to make the goal clear: read the eigenphase $\varphi$ of a unitary out of the interference pattern left by phase kickback, undone by the inverse QFT.

A worked example with numbers

Suppose $U = S$ (the phase gate, $S|1\rangle = i|1\rangle = e^{2\pi i \cdot 1/4}|1\rangle$ ) and we want the phase of its eigenstate $|1\rangle$ . The true eigenphase is $\varphi = 1/4$ .

With $n = 2$ ancilla qubits the counting register after stage 2 holds

\frac{1}{2}\bigl(|00\rangle + e^{2\pi i \cdot 1/4}|01\rangle + e^{2\pi i \cdot 2/4}|10\rangle + e^{2\pi i \cdot 3/4}|11\rangle\bigr).

The inverse QFT of this four-element superposition is exactly $|01\rangle$ (binary for $1$ , which encodes $\varphi = 1/4 = 1/2^2$ ). Measurement gives 01 with certainty, and we read off $\varphi = 0.01_2 = 1/4$ . The precision is exactly two bits, as promised.

If we had used only $n = 1$ ancilla qubit, the $\varphi = 1/4$ state would fall halfway between the two representable values ( $0$ and $1/2$ ), yielding each with probability $1/2$ — a useful reminder that precision is controlled entirely by how many ancilla qubits you allocate.

Summary

The Quantum Phase Estimation problem asks: given $U$ and an eigenstate $|\psi\rangle$ , estimate the eigenphase $\varphi$ such that $U|\psi\rangle = e^{2\pi i\varphi}|\psi\rangle$ . The answer is a circuit that combines Hadamard superposition, phase kickback through controlled- $U$ powers, and the inverse QFT. Each additional bit of precision requires one more ancilla qubit and one more application of $U$ . In the next lessons you will implement each component, culminating in a complete QPE circuit.