Part VIII · Formalism & Frontiers — 23

Phase Estimation

Shor’s algorithm (chapter 8d) didn’t arrive from nowhere. Between the toy win of Deutsch–Jozsa and the world-shaking factoring algorithm sit two stepping stones — Simon’s and, above all, phase estimation: the engine that reads a hidden angle off a quantum gate.

↩ before you start · keep these handy

·From Ch. 16: a phase is invisible on its own — interference is what makes it readable.

·From Ch. 8d: the QFT acts as a peak-finder — it turns a wave’s frequency into a sharp spike.

·eigenstate reminder: a state a gate leaves unchanged except for an overall phase twist e²⁷ⁱᴿ.

🔑 symbol decoder · every new mark, in plain words

φthe hidden angle the gate twists its eigenstate by (written as a fraction of a full turn). eigenstatethe special input the gate only multiplies by a phase — never reshapes. nthe number of counting qubits — each one adds a binary digit of precision. 2ⁿφwhere the peak lands — read the register, divide by 2ⁿ, get φ. QFT⁻¹the inverse quantum Fourier transform — the peak-finder that converts frequency to a number.

feel

Reading a gate’s hidden angle

A unitary gate has special states — its eigenstates — that it leaves alone except for a twist of phase, e^2πiφ. That angle φ is invisible to a single measurement (chapter 16). Phase estimation is a clever circuit that stamps the phase onto a register of counting qubits, then runs the inverse Fourier transform to turn it into a number you can simply read in binary. Simon’s algorithm is the same trick aimed at a hidden XOR pattern — both find global structure by making amplitudes interfere.

📻 everyday picture

Tuning an old radio, you don’t “see” a station’s frequency — you sweep the dial until the signal peaks, and the position of that peak is the frequency. The gate’s phase φ acts like a station broadcasting at one frequency; the inverse Fourier transform is the tuner that locks onto it and shows a sharp peak on the dial. Add more counting qubits and you simply get a finer dial — more decimal places on the frequency.

recapPhase estimation stamps a gate’s hidden phase onto counting qubits, then the QFT reads it as a number.

play

Read the phase off the register

Set a true phase φ and a register size n. The Fourier transform concentrates the register’s amplitude into a peak at the integer closest to 2ⁿφ. More counting qubits → finer bins → a sharper reading.

▸ QPE output distributionpeak at y ≈ 2ⁿφ

φ

0measured register y / 2ⁿ1

                phase φ
                
                {{ phiText }}
              
qubits n

read register{{ peakBin }}
estimate φ̂{{ estPhi }}
peak probability{{ peakProb }}
error |φ̂−φ|{{ error }}

recapThe peak lands at the integer nearest 2ⁿφ; more counting qubits = finer bins = a sharper reading.

math

Kickback, then inverse QFT

Each counting qubit controls a power of the gate, kicking its phase back onto the register. The register ends in a state whose frequency is exactly φ — and the inverse QFT (chapter 8d) reads that frequency out as a binary integer:

register → (1/√2ⁿ) Σk e2πiφk |k⟩  // a wave of frequency φ
QFT⁻¹ → sharp peak at y = round(2ⁿφ)
read y in binary → φ̂ = y / 2ⁿ  // n bits of the phase
Shor = phase estimation on the “multiply by a” gate → its eigen-phase IS the period

When 2ⁿφ is a whole number the peak is perfect — one bin with probability 1. Otherwise the amplitude spreads, but stays sharply concentrated on the nearest bins, so a handful of repetitions nails the phase. Simon’s algorithm is the same interference idea on a hidden bit-string, and it was the direct clue that led Shor to factoring.

✎ worked example · read φ = 0.625 with n = 3 qubits

register size 2ⁿ = 2³ = 8 bins.
peak lands at y = 2ⁿφ = 8 × 0.625 = 5 — a whole number, so the peak is perfect (probability 1).
read 5 in binary on 3 qubits: |101⟩.
estimate φ̂ = y / 2ⁿ = 5/8 = 0.625 — exact. (A phase like 0.6 isn’t a clean eighth, so it spreads over nearby bins.) ✓

recapKickback writes a wave of frequency φ; the inverse QFT reads it as an n-bit integer — and Shor is this on the “multiply by a” gate.

⚠ common misconception

“Shor’s algorithm is a magic factoring spell.” It’s phase estimation wearing a disguise. Recast factoring as finding the period of modular multiplication, notice the period is the eigen-phase of a simple gate, and the quantum part is exactly the circuit you just drove. The famous result is a clean application of a reusable tool.

Phase estimation also powers quantum chemistry and simulation — reading energy levels is reading eigen-phases. One last frontier remains: using entanglement not to compute, but to measure the world more precisely than independent probes ever could.

✓ you can now

✓explain phase estimation: kick a gate’s eigen-phase onto counting qubits, then inverse-QFT to read it

✓predict the peak bin at 2ⁿφ and convert it to an n-bit estimate φ̂

✓see Shor’s algorithm as phase estimation in disguise — the period is an eigen-phase

← 22 State Tomography next · 24 Sensing & Metrology →