Quantum Phase Estimation

Point a spectrometer at a glowing gas and it hands you a number: the exact frequency of the light, read straight off a dial. Quantum phase estimation (QPE) is a spectrometer for quantum operations. Give it a unitary U and one of its eigenvectors, and it reads back a plain binary number: the phase of the matching eigenvalue. That one trick — turning an eigenvalue into a number you can measure — is the engine inside Shor's factoring algorithm and a huge swathe of quantum chemistry and linear-algebra routines. Learn QPE and you have the workhorse that most "famous" quantum algorithms quietly ride on.

The problem, stated precisely

Every eigenvalue of a unitary matrix has magnitude 1, so it sits on the unit circle and can always be written as a pure phase e^{2\pi i\varphi}. QPE takes as input a unitary U and an eigenvector |\psi\rangle obeying

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

and its job is to estimate the phase \varphi — a single real number between 0 and 1 — to however many binary digits you can afford. The eigenvector itself comes back unchanged; QPE only wants to know the "angle" U rotates it by.

The method: superpose, kick back, unwind

QPE bolts a fresh register of t "counting" qubits on top of the register holding |\psi\rangle, and runs three moves:

  1. Superpose. A wall of Hadamards H^{\otimes t} puts the counting register into a uniform superposition over all 2^t numbers |k\rangle.
  2. Kick the phase in. Apply controlled U^{2^j} — controlled powers of U — from each counting qubit. Phase kickback stamps the eigenphase onto the counting register, leaving it in the Fourier state \frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1} e^{2\pi i\varphi k}\,|k\rangle, whose frequency is exactly \varphi.
  3. Unwind. Apply the inverse quantum Fourier transform to that register. The forward QFT builds a frequency state out of a number; running it backwards turns the frequency \varphi back into a plain binary number you can measure.

In one line: phase kickback writes the eigenvalue's phase into the register as a frequency, and the inverse QFT reads that frequency out as bits.

The circuit

Here is the whole algorithm as a circuit, with t = 3 counting qubits. Step through it: the three counting wires get Hadamards, then each controls a power U^{2^j} acting on the target, then an inverse-QFT block, then the meters. Notice the target wire carrying |\psi\rangle is never measured and comes out unchanged — all the information lands in the counting register.

Why phase kickback works

Here is the single fact that makes the whole thing tick. Apply a controlled-U with the control qubit in |1\rangle and the target in the eigenvector |\psi\rangle:

|1\rangle|\psi\rangle \;\xmapsto{\;cU\;}\; |1\rangle\,U|\psi\rangle = |1\rangle\,e^{2\pi i\varphi}|\psi\rangle = \big(e^{2\pi i\varphi}|1\rangle\big)|\psi\rangle.

The eigenphase has jumped from the target onto the control — the target is untouched. So a control qubit in \tfrac{1}{\sqrt2}(|0\rangle+|1\rangle) becomes \tfrac{1}{\sqrt2}(|0\rangle + e^{2\pi i\varphi}|1\rangle). Using a controlled-U^{2^j} instead applies the eigenvalue 2^j times, giving phase e^{2\pi i\,2^{j}\varphi} on the j-th counting qubit. Multiply the t counting qubits together and the cross-terms assemble into precisely the Fourier state

\bigotimes_{j=0}^{t-1}\frac{|0\rangle + e^{2\pi i\,2^{j}\varphi}|1\rangle}{\sqrt2} \;=\; \frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1} e^{2\pi i\varphi k}\,|k\rangle.

Worked example 1 — an exact reading

Suppose the phase happens to be a tidy 3-bit binary fraction, \varphi = 0.101_2 = \tfrac12 + \tfrac18 = \tfrac58 = 0.625, and we use t = 3 counting qubits. After the controlled-U powers the register holds

\frac{1}{\sqrt{8}}\sum_{k=0}^{7} e^{2\pi i\,(5/8)\,k}\,|k\rangle = \frac{1}{\sqrt{8}}\sum_{k=0}^{7} e^{2\pi i\,\frac{5\cdot k}{8}}\,|k\rangle.

Compare this with the definition of the QFT: \mathrm{QFT}\,|x\rangle = \tfrac{1}{\sqrt{2^t}}\sum_k e^{2\pi i\,xk/2^t}|k\rangle. Matching exponents, our state is exactly \mathrm{QFT}\,|5\rangle with x = 2^t\varphi = 8\cdot\tfrac58 = 5. So the inverse QFT unwinds it perfectly to |5\rangle = |101\rangle, and the measurement is deterministic: every single shot reads 101. Divide by 2^t = 8 and you recover \varphi = 5/8 exactly. Whenever \varphi is a t-bit fraction, QPE is a certainty, not a gamble.

Worked example 2 — reading a phase gate

Let us feed QPE a concrete unitary: the T gate, T = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{bmatrix}. Its eigenvectors are the basis states. Take |\psi\rangle = |1\rangle:

T\,|1\rangle = e^{i\pi/4}\,|1\rangle.

Read off the eigenphase by matching e^{i\pi/4} = e^{2\pi i\varphi}, so 2\pi\varphi = \tfrac{\pi}{4} and \varphi = \tfrac18 = 0.001_2. That is again a clean 3-bit fraction, so QPE with t = 3 counting qubits and target |1\rangle measures 2^t\varphi = 1, i.e. the bits 001 — deterministically. (Feed it |\psi\rangle = |0\rangle instead, where T|0\rangle = 1\cdot|0\rangle = e^{2\pi i\cdot 0}|0\rangle, and it reads \varphi = 0, i.e. 000.) The gate's hidden rotation angle has become a number on a dial.

How precision scales

With t counting qubits you read t binary digits, pinning \varphi to a resolution of about 2^{-t} — each extra counting qubit halves the error. When \varphi is not an exact t-bit fraction the measurement is no longer certain: it lands on the nearest t-bit value with high probability and occasionally on a neighbour. Wanting the best t-bit answer with success probability at least 1-\varepsilon costs a handful of extra counting qubits, t + O\!\big(\log(1/\varepsilon)\big) in total. The price is paid in controlled-U applications: the top qubit needs U^{2^{t-1}}, so achieving t bits requires on the order of 2^{t} applications of U in total — precision is bought with circuit depth.

An eigenvalue is an abstract complex number buried inside a matrix — you cannot "look at" a quantum state and see it. QPE is the machine that drags it out into the open. The counting register acts like the ruled scale on an instrument: the controlled-U powers deposit the eigenphase onto that scale as a wave, and the inverse QFT is the pointer that settles on the mark. This is why QPE is a subroutine, not usually an algorithm you run for its own sake — it is the measuring instrument that bigger algorithms reach for. Shor's algorithm dresses period-finding up as an eigenphase and reads it with QPE; quantum chemistry casts a molecule's energy as the eigenphase of its time-evolution operator e^{-iHt} and reads that with QPE. Once you can turn an eigenvalue into bits, an astonishing amount of quantum computing becomes "set it up as a phase, then measure it."

Two assumptions do all the heavy lifting, and both bite if you forget them. First, the target must be an eigenvector. The clean Fourier state only appears because U|\psi\rangle = e^{2\pi i\varphi}|\psi\rangle lets the phase factor out cleanly. Feed in a superposition of eigenvectors |\psi\rangle = \sum_m c_m|\psi_m\rangle and QPE runs on all of them at once — but measuring the counting register collapses it to the phase \varphi_m of one eigenvector, chosen at random with probability |c_m|^2. That is a feature Shor exploits (you don't need to prepare the eigenvector), but if you expected a single deterministic number you will be surprised. Second, you must be able to apply controlled-U^{2^j} efficiently — cheaply raising U to a huge power 2^{t-1} is exactly what makes Shor's modular-exponentiation trick necessary; a naive 2^{t} repetitions of U would wipe out any speedup. And remember the exchange rate: every extra bit of precision is another counting qubit and a doubling of the largest controlled power. QPE is not free precision — it is precision paid for in qubits and depth.