Quantum Phase Estimation

Quantum phase estimation is the algorithm that reads a number no classical measurement can see. You are handed a unitary $U$ that you may apply — and whose powers you may apply conditionally — together with one of its eigenstates $|u\rangle$ , obeying $U|u\rangle=e^{2\pi i\varphi}|u\rangle$ . The task is to determine the eigenphase $\varphi\in[0,1)$ . On its own that phase is a global factor multiplying $|u\rangle$ , and a global phase is the one thing quantum mechanics forbids you to observe: measure $|u\rangle$ in any basis and $e^{2\pi i\varphi}$ cancels in the Born rule. The information is real but invisible. The escape is to make the phase relative. Attach a register of counting qubits, put them in superposition, and let qubit $j$ control the power $U^{2^{j}}$ . By phase kickback the eigenstate is never disturbed, yet each qubit collects the phase $e^{2\pi i\,2^{j}\varphi}$ — and the geometric ladder $\varphi,2\varphi,4\varphi,\dots$ is exactly the place-value structure of a binary fraction. What the counting register now holds is the Fourier transform of the number $2^{t}\varphi$ . A single inverse quantum Fourier transform rotates that Fourier state back into the ordinary binary basis, and a measurement reads off the digits of $\varphi$ directly. When $\varphi$ is an exact $t$ -bit fraction the answer is deterministic; otherwise the inverse QFT produces a sharply peaked Dirichlet distribution over the nearest fraction, with accuracy and confidence you can dial by adding qubits. Phase estimation is the most reused subroutine in quantum computing after the QFT itself. Order finding — the engine inside Shor's factoring algorithm — is phase estimation applied to modular multiplication, and the same template of preparing eigenstates, estimating phases, and post-processing classically drives the discrete logarithm algorithm, the abelian hidden subgroup problem, and the quantum-chemistry algorithms that estimate molecular ground-state energies.

Key takeaways

Quantum phase estimation returns the eigenphase $\varphi$ of a unitary $U$ on one of its eigenstates $|u\rangle$ , where $U|u\rangle=e^{2\pi i\varphi}|u\rangle$ and $\varphi\in[0,1)$ .
The circuit is three moves: Hadamard the $t$ -qubit counting register, apply the controlled- $U^{2^{j}}$ cascade, then apply the inverse quantum Fourier transform and measure.
A global phase on an eigenstate is unobservable; controlling $U$ turns it into a relative phase, and controlling the powers $U^{2^{j}}$ writes the binary digits of $\varphi$ into a Fourier state.
If $\varphi=0.\varphi_1\varphi_2\dots\varphi_t$ terminates in $t$ bits the readout is exact; otherwise the nearest $t$ -bit fraction wins with probability at least $4/\pi^2\approx0.405$ .
For $n$ correct bits at confidence $1-\epsilon$ use $t=n+\lceil\log_2(2+\tfrac{1}{2\epsilon})\rceil$ counting qubits — the extra qubits buy confidence, not resolution.
Key idea: a global phase $e^{2\pi i\varphi}$ on an eigenstate is invisible — but if you control the unitary on a register in superposition, that phase becomes a measurable relative phase, and the inverse QFT converts the resulting Fourier state directly into the binary digits of $\varphi$ .

The core insight

A global phase $e^{2\pi i\varphi}$ on an eigenstate is invisible — but if you control the unitary on a register of qubits in superposition, that phase becomes a measurable relative phase, and the inverse QFT converts the resulting Fourier state directly into the binary digits of $\varphi$ .

Where this lives today

Phase estimation is the load-bearing beam of the fault-tolerant quantum-computing roadmap. Its most famous use is inside Shor's algorithm, where order finding — phase estimation on the modular-multiplication unitary — reduces integer factoring and discrete logarithms to a polynomial-time quantum routine, the result that made quantum computers a matter of national cryptographic policy. Its most active use today is quantum chemistry: setting $U=e^{-iHt_0}$ makes the eigenphase encode an energy $E$ , so phase estimation reads molecular and lattice ground-state energies to chemical accuracy, and small instances (the energies of $\mathrm{H}_2$ , $\mathrm{LiH}$ , and model Hubbard systems) have been run end to end on superconducting and trapped-ion processors. Because the textbook circuit demands deep, coherent controlled- $U^{2^{j}}$ cascades that today's noisy hardware cannot yet sustain, a family of near-term variants has grown up around it: iterative and Bayesian phase estimation replace the wide register with one recycled qubit and classical feedback; robust phase estimation tolerates calibration error and doubles as a gate-fidelity benchmark; and recent low-depth statistical estimators trade circuit depth for more repetitions. The open frontier is exactly that trade — how cheaply an eigenphase can be estimated on hardware that decoheres before the full cascade completes, and where the true boundary lies between what phase estimation and its variational cousins can each reach.

The physical picture

Picture $U$ as a clock whose single hand advances by $\varphi$ of a full turn every time it ticks. Read one clock and you learn nothing: an absolute hand position that is the same for every observer carries no relative information, exactly as a global phase carries none. So install a row of $t$ observers, each in a superposition of "watching" and "not watching," and let observer $j$ watch the clock through exactly $2^{j}$ ticks. Observer $0$ records $\varphi$ , observer $1$ records $2\varphi$ , observer $2$ records $4\varphi$ , and so on. No observer disturbs the clock — that is phase kickback, the eigenstate slides through untouched — yet between them the observers now hold the binary odometer reading of $\varphi$ , written in the Fourier basis. The inverse QFT is the instrument that rotates that Fourier-encoded odometer back into plain binary you can simply read. The first figure lays the circuit out gate by gate.

Figure

A 3-qubit phase-estimation circuit: Hadamards spread the counting register, each controlled power stamps the phase e^(2πi·2^j·φ) onto qubit j by kickback, and the inverse QFT writes the three binary digits of φ into the measured bits — resolving φ to a grid of spacing 1/8 = 0.125

The exponent doubling $j\mapsto 2^{j}$ is where the efficiency lives. With $t$ controlled operations the register accumulates $\varphi,2\varphi,4\varphi,\dots,2^{t-1}\varphi$ — precisely the weights of a $t$ -digit binary fraction — so $t$ operations resolve $\varphi$ to one part in $2^{t}$ , an exponential payoff for a linear number of gates. This is the same place-value logic that builds the QFT, which is why the two are duals: the QFT assembles a Fourier state from digits, and phase estimation reads digits out of a Fourier state. The second figure is the punchline — the measured distribution when the phase does not land on the grid.

Figure

Outcome distribution for φ = 1/3 with t = 3 qubits: the nearest 3-bit estimate x = 3 (the fraction 3/8 = 0.375) is measured with probability 0.688 and its neighbour x = 2 with 0.175, so the best estimate clears the guaranteed floor 4/π² ≈ 0.405 with room to spare

The core equations

Everything begins with the promise the algorithm is given: a unitary and one of its eigenstates, with the eigenvalue a pure phase because unitaries preserve length. The unknown to be extracted is that phase, written as a fraction of a full turn.

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

where: $U$ — a unitary supplied as a controllable black box; $|u\rangle$ — a known eigenstate loaded into the target register; $\varphi$ — the unknown eigenphase, the number to be estimated. The reading: because $U$ is unitary the eigenvalue has modulus one, so it is fully specified by the single real number $\varphi$ in $[0,1)$ — and on $|u\rangle$ alone that number is a global phase, hence invisible. The first move is a Hadamard on every counting qubit, which spreads the register into a uniform superposition over all $2^{t}$ basis states — the many "observers," each ready to watch a different power of $U$ .

|0\rangle^{\otimes t}|u\rangle \;\xrightarrow{\,H^{\otimes t}\,}\; \frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}|k\rangle\,|u\rangle \qquad (2)

where: $t$ — number of counting qubits; $|k\rangle$ — computational-basis state with $k=\sum_{j}k_j2^{j}$ ; $H$ — Hadamard, $H|0\rangle=(|0\rangle+|1\rangle)/\sqrt2$ . The reading: the register is now an equal-amplitude sum over every $t$ -bit integer $k$ , and the target eigenstate rides along untouched — the stage is set for the controlled powers to imprint a $k$ -dependent phase. The controlled- $U^{2^{j}}$ cascade acts, and by the eigenvalue relation each branch $|k\rangle$ collects the phase $e^{2\pi i\varphi k}$ while $|u\rangle$ is returned exactly. This is phase kickback applied bit by bit.

\frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}|k\rangle\,U^{k}|u\rangle = \frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1} e^{2\pi i\varphi k}\,|k\rangle\,|u\rangle \qquad (3)

where: $U^{k}$ — the total power applied, assembled from the controlled $U^{2^{j}}$ triggered by the bits of $k$ ; $e^{2\pi i\varphi k}$ — the accumulated branch phase. The reading: qubit $j$ fires $U^{2^{j}}$ only on its $|1\rangle$ component, and the product of those single-bit phases rebuilds $e^{2\pi i\varphi k}$ because $k=\sum_j k_j2^{j}$ — the binary expansion is doing the bookkeeping. Factoring out the untouched target, the counting register is left in a state that is literally the quantum Fourier transform of the integer nearest to $2^{t}\varphi$ . Naming it this way is what makes the next step obvious.

|\Phi\rangle = \frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1} e^{2\pi i\varphi k}\,|k\rangle = \mathrm{QFT}\,\big|2^{t}\varphi\big\rangle \qquad (4)

where: $|\Phi\rangle$ — the counting register after the cascade; $\mathrm{QFT}$ — the $t$ -qubit quantum Fourier transform; $2^{t}\varphi$ — the phase rescaled so its integer part is the $t$ -bit answer. The reading: the phase has been encoded as a Fourier state, so applying the inverse transform must decode it — the algorithm is the QFT run backwards on a state the physics prepared forwards. Applying $\mathrm{QFT}^{-1}$ and expanding both sums gives the pre-measurement amplitude on every possible outcome $x$ . The exponent $\varphi-x/2^{t}$ is the residual error of the estimate $x/2^{t}$ .

\mathrm{QFT}^{-1}|\Phi\rangle = \frac{1}{2^{t}}\sum_{x=0}^{2^{t}-1}\sum_{k=0}^{2^{t}-1} e^{2\pi i k(\varphi - x/2^{t})}\,|x\rangle \qquad (5)

where: $x$ — the integer that will be measured; $\langle x|\mathrm{QFT}^{-1}|k\rangle = 2^{-t/2}e^{-2\pi i xk/2^{t}}$ — the inverse-QFT matrix element. The reading: the outcome amplitude $a_x=2^{-t}\sum_k e^{2\pi i k(\varphi-x/2^{t})}$ is a finite geometric series in $k$ , and its magnitude peaks wherever $x/2^{t}$ sits closest to $\varphi$ . Squaring that geometric sum gives the measured probability — a squared Dirichlet (Fejér) kernel, sharply peaked at zero residual.

P(x) = \frac{1}{2^{2t}}\left|\sum_{k=0}^{2^{t}-1} e^{2\pi i k(\varphi - x/2^{t})}\right|^{2} = \frac{1}{2^{2t}}\,\frac{\sin^{2}\!\big(\pi 2^{t}(\varphi - x/2^{t})\big)}{\sin^{2}\!\big(\pi(\varphi - x/2^{t})\big)} \qquad (6)

where: $P(x)$ — probability of measuring the integer $x$ ; $\varphi-x/2^{t}$ — the estimate's error. The reading: when $\varphi=b/2^{t}$ exactly the kernel collapses to a Kronecker delta $\delta_{x,b}$ and the readout is certain; otherwise the peak sits on the nearest fraction and the width is one grid spacing. The height of that peak is bounded below by a constant that does not depend on $t$ — the guarantee that the nearest estimate is likely on a single run.

P\big(x=\text{nearest }t\text{-bit estimate}\big) \ge \frac{4}{\pi^{2}} \approx 0.405 \qquad (7)

where: nearest estimate — the integer $b$ with $|b/2^{t}-\varphi|\le 2^{-t-1}$ . The reading: even in the worst case one shot lands on the best $t$ -bit fraction more than $40\%$ of the time, so a handful of repetitions makes the correct estimate overwhelmingly likely — regardless of how many bits you are extracting. To force both accuracy and confidence, size the register by the rule that trades a few extra qubits for a suppressed failure tail.

t = n + \left\lceil \log_{2}\!\left(2 + \frac{1}{2\epsilon}\right)\right\rceil \qquad (8)

where: $n$ — number of correct leading bits required; $\epsilon$ — tolerated failure probability; $t$ — total counting qubits. The reading: the first $n$ qubits set the resolution $2^{-n}$ , and the extra $\lceil\log_2(2+1/2\epsilon)\rceil$ qubits push the Dirichlet tail below $\epsilon$ — resolution and confidence are separate budgets.

Derivation AFrom phase kickback to the inverse-QFT readout

The goal is to carry the full register — counting qubits plus target — through the three stages of the circuit, the Hadamard fan-out, the controlled-power cascade, and the inverse quantum Fourier transform, and to establish two facts in one pass: that when $\varphi$ is an exact $t$ -bit fraction the measurement returns it with certainty, and that otherwise the outgoing amplitudes form a squared Dirichlet kernel peaked on the nearest fraction. The strategy is to keep the target eigenstate factored out at every step using kickback, so the entire computation reduces to a single amplitude $a_x$ on the counting register, and then to evaluate that amplitude as a finite geometric series.

Step 1. Superpose: $H^{\otimes t}|0\rangle^{\otimes t}=2^{-t/2}\sum_{k}|k\rangle$ , so the joint state is $2^{-t/2}\sum_k|k\rangle|u\rangle$ . Why: the Hadamards create the equal-weight superposition over all $2^{t}$ counting strings that the controlled powers will each tag with a different phase.

Step 2. Kick back the phase: the controlled- $U^{2^{j}}$ cascade applies $U^{k}$ conditioned on $|k\rangle$ , and since $U^{k}|u\rangle=e^{2\pi i\varphi k}|u\rangle$ the state becomes $2^{-t/2}\sum_k e^{2\pi i\varphi k}|k\rangle|u\rangle$ . Why: the eigenvalue relation converts the conditional operation into a pure phase on the counting register while returning $|u\rangle$ intact, so the target factors out and can be ignored from here on.

Step 3. Apply the inverse QFT using $\langle x|\mathrm{QFT}^{-1}|k\rangle=2^{-t/2}e^{-2\pi i xk/2^{t}}$ , giving the outcome amplitude $a_x=2^{-t}\sum_{k=0}^{2^{t}-1} e^{2\pi i k(\varphi - x/2^{t})}$ . Why: the inverse transform is the decoder — it interferes the $2^{t}$ Fourier components so that amplitude piles up where $x/2^{t}$ matches $\varphi$ and cancels elsewhere.

Step 4. Exact case: if $\varphi=b/2^{t}$ then $a_x=2^{-t}\sum_k e^{2\pi i k(b-x)/2^{t}}=\delta_{x,b}$ , since the geometric sum is $2^{t}$ when $x=b$ and $0$ otherwise. Why: a resonant sum of $2^{t}$ equally spaced roots of unity is total constructive interference at $x=b$ and total cancellation elsewhere, so the measurement returns $b$ and hence $\varphi=b/2^{t}$ with probability one.

Step 5. General case: summing the geometric series gives $|a_x|^{2}=2^{-2t}\sin^{2}(\pi 2^{t}\delta)/\sin^{2}(\pi\delta)$ with $\delta=\varphi-x/2^{t}$ . Why: with $\varphi$ off the grid the interference is imperfect, and the squared Dirichlet kernel that results is peaked at $\delta=0$ — so the integer $b$ nearest $2^{t}\varphi$ is the most probable outcome, with a spread of about one grid step. *The exact-case collapse to $\delta_{x,b}$ and the Dirichlet-kernel distribution are textbook-standard results; the worked example $\varphi=1/3$ , $t=3$ gives $P(3)=0.688$ and $P(2)=0.175$ , and all eight outcomes sum to $1$ .*

Go deeper · Derivation B · 1 minThe accuracy bound and the extra-qubit rule

Derivation BThe accuracy bound and the extra-qubit rule

The aim is to turn the Dirichlet kernel of the previous derivation into two hard guarantees: a lower bound of $4/\pi^{2}$ on the probability of hitting the nearest $t$ -bit fraction, independent of $t$ , and the sizing rule $t=n+\lceil\log_2(2+1/2\epsilon)\rceil$ that delivers $n$ correct bits with failure probability at most $\epsilon$ . The method is to bound the kernel at its peak using elementary sine inequalities, then to bound its tail away from the peak and sum the resulting series, so that resolution and confidence emerge as two separate, controllable budgets. Let $b$ be the nearest estimate and $\delta=\varphi-b/2^{t}\in[-2^{-t-1},2^{-t-1}]$ .

Step 1. Bound the peak: $P(b)=2^{-2t}\sin^{2}(\pi 2^{t}\delta)/\sin^{2}(\pi\delta)\ge 2^{-2t}\,(2\cdot 2^{t}\delta)^{2}/(\pi\delta)^{2}=4/\pi^{2}$ . Why: on the numerator $|\sin\theta|\ge 2|\theta|/\pi$ holds for $|\theta|\le\pi/2$ (here $|\pi2^{t}\delta|\le\pi/2$ ), and on the denominator $|\sin\theta|\le|\theta|$ always — together they floor the peak at $(2/\pi)^{2}\approx0.405$ with no dependence on $t$ .

Step 2. Bound the tail: for outcomes with error window $e'$ integers away from $b$ , $\sum_{|x-b|>e'}|a_x|^{2}\le \tfrac{1}{2(2^{t}\!\cdot 2^{-t}e'-1)}=\tfrac{1}{2(e'-1)}$ using $|\sin\pi\delta_x|\ge 2|\delta_x|$ far from the peak and summing the resulting series. Why: away from resonance the kernel falls off like $1/\text{distance}^{2}$ , so the total tail probability is controlled by a convergent sum set by how many grid steps of slack you allow.

Step 3. Set the accuracy: to guarantee error below $2^{-n}$ in $\varphi$ , allow an integer window $e'=2^{t-n}-1$ , so any outcome within it estimates $\varphi$ to $n$ bits. Why: the physical error $|x/2^{t}-\varphi|$ is the integer error divided by $2^{t}$ , so demanding $n$ bits of accuracy fixes the window at $2^{t-n}$ and thereby ties $t$ to $n$ .

Step 4. Set the confidence: requiring $\tfrac{1}{2(2^{t-n}-1)}\le\epsilon$ gives $2^{t-n}\ge 2+\tfrac{1}{2\epsilon}$ , hence $t\ge n+\log_2(2+\tfrac{1}{2\epsilon})$ , and rounding up yields the boxed rule. Why: the tail bound becomes a clean inequality for the number of surplus qubits, which shows the extra $\lceil\log_2(2+1/2\epsilon)\rceil$ qubits buy confidence while the first $n$ buy resolution. *The $4/\pi^{2}$ floor is the standard Fejér-kernel constant, and for $n=6$ , $\epsilon=0.01$ the sizing rule gives $t=6+\lceil\log_2 52\rceil=12$ .*

Go deeper · Derivation C · 1 minWhy a controlled unitary turns a global phase into a relative one

Derivation CWhy a controlled unitary turns a global phase into a relative one

The purpose is to prove, from the definition of a controlled operation alone, that controlled- $U$ acting on a control qubit and an eigenstate leaves the eigenstate exactly where it started and deposits the eigenvalue as a relative phase between the control's branches. This is the conceptual heart of the whole algorithm — the single step that converts an unobservable global phase into an observable one — and everything downstream is just this identity, iterated over the powers $U^{2^{j}}$ and read out by interference. The plan is to write the controlled gate as a projector sum, act on each control branch, and collect the result.

Step 1. Define the gate: $\mathrm{c}\text{-}U=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes U$ , applying $U$ to the target only when the control is $|1\rangle$ . Why: this is the only reversible way to make $U$ 's action conditional on a qubit, and its block structure is what routes the eigenvalue onto a single control branch.

Step 2. Act on the eigenstate branch: $\mathrm{c}\text{-}U\,|1\rangle|u\rangle=|1\rangle\,U|u\rangle=e^{2\pi i\varphi}\,|1\rangle|u\rangle$ , while $\mathrm{c}\text{-}U\,|0\rangle|u\rangle=|0\rangle|u\rangle$ . Why: because $|u\rangle$ is an eigenstate the target is unchanged up to its eigenvalue, and that eigenvalue attaches to the $|1\rangle$ branch alone — the target never moves.

Step 3. Superpose the control: $\mathrm{c}\text{-}U(\alpha|0\rangle+\beta|1\rangle)|u\rangle=(\alpha|0\rangle+\beta e^{2\pi i\varphi}|1\rangle)|u\rangle$ . Why: the phase that was global on $|u\rangle$ — invisible in any measurement — is now a relative phase between $|0\rangle$ and $|1\rangle$ of the control, which is exactly what an interference measurement can detect.

Step 4. Iterate over powers: replacing $U$ by $U^{2^{j}}$ gives relative phase $e^{2\pi i\,2^{j}\varphi}$ on qubit $j$ , and the product over $j$ is the Fourier state of $2^{t}\varphi$ . Why: kickback applied to the geometric ladder of powers is what spreads the digits of $\varphi$ across the register, setting up the inverse QFT to decode them. *The target is an eigenvector of every $\mathrm{c}\text{-}U^{2^{j}}$ , so it never entangles with the control — the same kickback mechanism used by Deutsch–Jozsa and Bernstein–Vazirani, there with eigenvalue $-1$ .*

Limiting cases

The behaviour of phase estimation turns sharply on whether the phase fits the register and on what state you feed in.

Case	Result	Meaning
Exact $t$ -bit phase	$\varphi=\dfrac{b}{2^{t}},\ b\in\{0,\dots,2^{t}-1\}$	The inverse QFT produces $\vert b\rangle$ exactly; measurement returns $\varphi$ deterministically with probability $1$ .
Generic phase	$P\big(\vert b/2^{t}-\varphi\vert\le 2^{-t-1}\big)\ge \dfrac{4}{\pi^{2}}\approx0.405$	The nearest $t$ -bit value is the most likely outcome, and lands within half a grid step with probability above the $t$ -independent floor.
Superposition input	$\vert\psi\rangle=\sum_k c_k\vert u_k\rangle\Rightarrow \Pr[\varphi_k]=\vert c_k\vert^{2}$	The register samples one eigenphase $\varphi_k$ with Born weight and collapses the target onto $\vert u_k\rangle$ — spectrum sampling, not deterministic readout.
Costly powers	$\text{cost}\sim\sum_{j=0}^{t-1}\mathrm{cost}\big(U^{2^{j}}\big)$	The speedup needs fast exponentiation: repeated squaring for modular multiplication, but for $U=e^{-iHt_0}$ the cost of $U^{2^{j}}$ grows with simulation time and can dominate.

Common trapPhase estimation is not "computing f on every input at once"

The tempting misreading is that phase estimation is powerful because the superposition $2^{-t/2}\sum_k e^{2\pi i\varphi k}|k\rangle$ "holds every power of $U$ simultaneously." It does — but measure it there and you get a uniform random $k$ , learning nothing about $\varphi$ , exactly as a global phase teaches you nothing. The advantage lives entirely in the inverse QFT, whose interference converts the relative phases into a measurable population on the digits of $\varphi$ . Two further traps ride along. First, phase estimation needs a genuine eigenstate (or an efficiently preparable superposition of them): feed a generic $|\psi\rangle=\sum_k c_k|u_k\rangle$ and you measure $\varphi_k$ with probability $|c_k|^{2}$ while the target collapses to $|u_k\rangle$ — a feature when intended, a silent bug when forgotten. Second, the circuit applies $U$ a total of $2^{t}-1$ times; the polynomial cost relies on building $U^{2^{j}}$ directly by fast exponentiation. If each power must instead be assembled from $2^{j}$ sequential copies of $U$ , the runtime becomes exponential in $t$ and the advantage evaporates.

Worked examples

1 · An exact phase read out with certainty (confidence builder)

A unitary has eigenstate $|u\rangle$ with eigenphase $\varphi=5/8$ . Run phase estimation with $t=3$ counting qubits and show the outcome is deterministic.

Step 1. Express $\varphi$ in binary. $5/8=0.625=\tfrac12+\tfrac18$ , so $\varphi=0.101_2$ — an exact $3$ -bit fraction with $b=5$ . Because it terminates in $t=3$ bits, the register can represent it perfectly.

Step 2. After the Hadamards and the controlled-power cascade the counting register is $|\Phi\rangle=2^{-3/2}\sum_{k=0}^{7}e^{2\pi i(5/8)k}|k\rangle=\mathrm{QFT}|5\rangle$ . It is literally the Fourier transform of the integer $5$ .

Step 3. Apply the inverse QFT. The outcome amplitude is $a_x=2^{-3}\sum_{k=0}^{7}e^{2\pi i k(5-x)/8}=\delta_{x,5}$ : a resonant sum of eight roots of unity, equal to $8$ when $x=5$ and $0$ otherwise. The register collapses to the single string $|101\rangle$ .

Step 4. Measure. $\Pr[x=5]=1$ and every other outcome has probability $0$ ; dividing by $2^{t}=8$ recovers $\varphi=5/8$ exactly. The readout is deterministic — one run, the exact phase, no repetition needed.

2 · A phase off the grid, and the Dirichlet peak (fully worked)

Now $\varphi=1/3$ , which has no finite binary expansion. With $t=3$ qubits, find the most probable outcome, its probability, and check the $4/\pi^{2}$ guarantee.

Step 1. Locate the target on the grid. $2^{t}\varphi=8/3\approx2.667$ , so the nearest integer is $b=3$ , giving the estimate $x/2^{t}=3/8=0.375$ . The residual is $\delta=\varphi-3/8=\tfrac13-\tfrac38=-\tfrac{1}{24}\approx-0.0417$ , and $|\delta|=0.0417\le 2^{-t-1}=1/16$ , so $x=3$ is indeed the best $3$ -bit estimate.

Step 2. Evaluate the peak with equation (6). The numerator is $\sin^{2}(\pi\cdot 2^{3}\delta)=\sin^{2}(-\pi/3)=3/4$ , and the denominator is $\sin^{2}(\pi\delta)=\sin^{2}(\pi/24)=0.01704$ . So $P(3)=\tfrac{1}{64}\cdot\tfrac{0.75}{0.01704}=\tfrac{1}{64}\cdot 44.02=\mathbf{0.688}$ .

Step 3. Check the neighbour $x=2$ (estimate $2/8=0.25$ ). Here $\delta'=\tfrac13-\tfrac14=\tfrac{1}{12}$ , numerator $\sin^{2}(2\pi/3)=3/4$ , denominator $\sin^{2}(\pi/12)=0.06699$ , so $P(2)=\tfrac{1}{64}\cdot 11.20=\mathbf{0.175}$ . The two central bars already carry $0.863$ of the probability. The distribution is a Dirichlet peak straddling the true value $2.667$ .

Step 4. Confirm the guarantee. The best-estimate probability $P(3)=0.688$ comfortably exceeds the worst-case floor $4/\pi^{2}\approx0.405$ of equation (7). A single run returns the nearest fraction more than two times in three; a few repetitions with a majority vote make it a near-certainty.

3 · Sizing the counting register

You need $\varphi$ accurate to $n=6$ bits with failure probability at most $\epsilon=0.01$ . How many counting qubits does that take, and how many applications of $U$ ?

Step 1. Apply the sizing rule (8). $t=n+\lceil\log_2(2+\tfrac{1}{2\epsilon})\rceil=6+\lceil\log_2(2+50)\rceil=6+\lceil\log_2 52\rceil=6+\lceil5.70\rceil=6+6=\mathbf{12}$ qubits. The six surplus qubits are not resolution — they suppress the Dirichlet tail below $1\%$ .

Step 2. Count the oracle cost. The cascade applies $U$ a total of $\sum_{j=0}^{t-1}2^{j}=2^{t}-1=2^{12}-1=\mathbf{4095}$ times. This is only cheap if $U^{2^{j}}$ can be built directly by fast exponentiation — the assumption that separates a polynomial algorithm from an exponential one.

Physics of the portrait

Phase estimation is the point where a physicist's search for a better way to measure — the eigenvalue of an operator — became the master algorithm of quantum computation. The idea, and the topological revolution it grew alongside, belong to one person.

Origins · 1 minAlexei Kitaev and how this was discovered

Alexei Kitaev

1963– · the physicist who recast quantum algorithms as eigenvalue measurement and founded topological quantum computing

Alexei Yurievich Kitaev, born in 1963 and trained at the Landau Institute in Moscow before moving to Microsoft Research and then Caltech, reshaped quantum computing twice over. In a 1995 preprint on the abelian stabilizer problem he introduced phase estimation as a general primitive — showing that the ability to measure the eigenvalue of a unitary on one of its eigenstates was enough to reproduce Shor's factoring and discrete-logarithm results, and much else, within one unifying framework. This "eigenvalue estimation" viewpoint reoriented the field: many quantum algorithms are, at heart, spectral measurements, and phase estimation is the instrument that performs them. Kitaev is equally celebrated for founding topological quantum computation: his 1997 toric code showed how anyons — quasiparticles whose braiding is intrinsically fault-tolerant — could store and process quantum information protected by topology, launching a large experimental program. His name attaches to the Kitaev chain of Majorana fermions and, with Sachdev and Ye, to the SYK model of quantum chaos. A recipient of the inaugural Breakthrough Prize in Fundamental Physics (2012) and the Dirac Medal (2015), Kitaev embodies this article's through-line: measuring a phase you were told could never be seen turns out to be the most powerful thing a quantum computer knows how to do.

History

1994

— Shor's algorithm puts order finding, a phase-estimation problem, at the center of quantum computing

1995

— Kitaev introduces phase estimation to solve the abelian stabilizer problem

1996

— Griffiths and Niu show the inverse QFT can be replaced by a semiclassical, measurement-fed sequence

1998

— Cleve, Ekert, Macchiavello and Mosca cast Deutsch, Shor and phase estimation in one controlled-power circuit

2005

— Aspuru-Guzik and collaborators apply phase estimation to molecular ground-state energies

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information (10th anniv. ed.), §5.2 (phase estimation) and §5.3 (order finding) · Preskill, Lecture Notes for Physics 219, Ch. 6 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §13 · Mermin, Quantum Computer Science, Ch. 3 · Watrous, The Theory of Quantum Information (phase-estimation discussions) · Cleve, Ekert, Macchiavello & Mosca, Proc. R. Soc. Lond. A 454, 339 (1998). Key checkpoints for the equations above: the geometric sum yields the Dirichlet kernel; the exact-case collapse gives $a_x=\delta_{x,b}$ ; the peak bound follows from $|\sin\pi 2^{t}\delta|\ge 2|2^{t}\delta|$ ; and the tail/confidence inequality is $\tfrac{1}{2(2^{t-n}-1)}\le\epsilon$ . The worked numbers: $\varphi=1/3$ , $t=3$ gives $P(3)=0.688$ , $P(2)=0.175$ (all eight outcomes sum to $1$ ); the exact case $\varphi=5/8$ collapses to $|101\rangle$ ; and $n=6$ , $\epsilon=0.01$ gives $t=12$ with $2^{12}-1=4095$ applications of $U$ . The constant $4/\pi^{2}\approx0.405$ is the standard Fejér-kernel floor.

Prerequisites. Quantum Fourier Transform · Quantum Parallelism and the Oracle Model · Bernstein–Vazirani Algorithm. Leads to. Order Finding and Period Finding · Shor's Factoring Algorithm · Quantum Discrete Logarithm Algorithm · Hidden Subgroup Problem.

Ask the tutor: ask me to run phase estimation on any φ and t amplitude by amplitude, prove the 4/π² floor or the qubit-count rule line by line, or show exactly how order finding turns this circuit into the engine of Shor's algorithm.

Why does controlling the unitary reveal a phase that is otherwise invisible?

A global phase $e^{2\pi i\varphi}$ multiplies the whole state, so it cancels in the Born rule and no measurement of $|u\rangle$ can detect it. Controlled- $U$ changes the situation: it applies the phase only to the $|1\rangle$ branch of the control qubit, converting a global phase into a relative phase between $|0\rangle$ and $|1\rangle$ . Relative phases are physical — they govern interference — so a later Hadamard or inverse QFT can turn them into different measurement probabilities. The eigenstate itself never changes (that is phase kickback), which is why it can be reused across all the controlled powers without being disturbed.

What is the role of the inverse QFT, as opposed to the forward QFT?

After the controlled-power cascade the counting register holds $2^{-t/2}\sum_k e^{2\pi i\varphi k}|k\rangle$ , which is exactly the forward QFT of the number $2^{t}\varphi$ . To recover that number you must undo the transform, so you apply the inverse QFT, which maps the Fourier state back to the computational-basis string closest to $2^{t}\varphi$ . This is the sense in which phase estimation and the QFT are duals: the QFT builds a Fourier state out of a set of digits, and phase estimation reads a set of digits out of a Fourier state. Using the forward QFT here would transform in the wrong direction and scramble the answer.

Why is the success probability floor exactly 4/π², and does it depend on t?

It comes from bounding the squared Dirichlet kernel at its peak. For the nearest estimate the residual satisfies $|2^{t}\delta|\le\tfrac12$ , so the numerator obeys $|\sin(\pi 2^{t}\delta)|\ge 2|2^{t}\delta|$ , while the denominator obeys $|\sin(\pi\delta)|\le\pi|\delta|$ . Their ratio, squared and divided by $2^{2t}$ , gives $(2/\pi)^{2}=4/\pi^{2}\approx0.405$ . Crucially the $\delta$ factors cancel, so the floor is completely independent of $t$ : whether you extract $3$ bits or $300$ , one run lands on the nearest fraction more than $40\%$ of the time, and a handful of repetitions makes the majority answer essentially certain.

What actually happens if I run phase estimation on a state that is not an eigenstate?

You do not get an error — you get a random eigenphase. Expand the input in the eigenbasis, $|\psi\rangle=\sum_k c_k|u_k\rangle$ . The circuit is linear, so it estimates every $\varphi_k$ in superposition, and the final measurement collapses the counting register onto one estimate $\varphi_k$ with probability $|c_k|^{2}$ , simultaneously projecting the target onto $|u_k\rangle$ . This is a feature when you exploit it: in order finding the easy-to-prepare state $|1\rangle$ is a uniform superposition of eigenstates, so phase estimation returns a random $s/r$ . It is a bug when you forget it and expected a single deterministic phase — you will instead sample the spectrum.

How is phase estimation the engine inside Shor's algorithm?

For modular multiplication $U|y\rangle=|xy\bmod N\rangle$ , the eigenstates $|u_s\rangle=r^{-1/2}\sum_k e^{-2\pi i sk/r}|x^{k}\bmod N\rangle$ have eigenphases $\varphi=s/r$ , where $r$ is the order of $x$ modulo $N$ . Phase estimation returns an estimate of $s/r$ , and the continued-fractions algorithm recovers $r$ from it. Because the uniform superposition $r^{-1/2}\sum_s|u_s\rangle$ equals the trivial state $|1\rangle$ , you never need to prepare a specific eigenstate — you run phase estimation on $|1\rangle$ and read off a random $s/r$ . The powers $U^{2^{j}}$ are computed by repeated squaring, keeping the whole routine polynomial, which is why order finding is the quantum heart of factoring.

Why can't I skip the extra qubits and just repeat the circuit more times?

You can, and often you should — but the two knobs do different jobs. The register width $t$ sets the resolution: with $t$ qubits the outputs live on a grid of spacing $2^{-t}$ , so no amount of repetition can resolve $\varphi$ finer than the grid. The surplus qubits in $t=n+\lceil\log_2(2+1/2\epsilon)\rceil$ instead sharpen the peak so a single shot is reliable. Repetition with a majority vote is an alternative way to buy confidence at fixed resolution, and it is exactly what iterative phase estimation does — trading a wide coherent register for many runs of a one-qubit circuit with classical feedback, which is far friendlier to near-term hardware.