Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Phase Estimation: Error Analysis

How many qubits, how much precision, what success probability.

Phase estimation promises φ\varphi to tt bits with tt counting qubits. The fine print: the most likely outcome can have probability as low as about 40%, extra qubits buy precision rather than confidence, and the number of controlled-UU applications grows like 2t2^t. This lesson makes each of those statements precise and proves them.

What you’ll learn

  • Derive the exact output distribution of phase estimation (a Fejér kernel) for an arbitrary phase.
  • Prove that the nearest tt-bit estimate has probability at least 4/π24/\pi^2, and the two nearest together at least 8/π28/\pi^2.
  • Prove that t=n+⌈log⁡2(2+12ε)⌉t=n+\lceil\log_2(2+\tfrac{1}{2\varepsilon})\rceil counting qubits give nn bits with probability at least 1−ε1-\varepsilon, and compare with median amplification.
  • Explain Kitaev's single-qubit approach, Heisenberg-limited scaling, and phase estimation on inputs that are not eigenstates.

The exact output distribution

Let M=2tM=2^t. After the controlled powers, the counting register holds 1M∑k=0M−1e2πiφk∣k⟩\frac{1}{\sqrt M}\sum_{k=0}^{M-1}e^{2\pi i\varphi k}\ket k (the work register factors out as ∣u⟩\ket u). Phase estimation applies FM†F_M^\dagger and measures an integer mm; the estimate is φ~=m/M\tilde\varphi=m/M, with distances understood modulo 1.

DerivationThe Fejér kernel
  1. αm=⟨m∣FM†(1M∑k=0M−1e2πiφk∣k⟩)=1M∑k=0M−1e2πik(φ−m/M)\alpha_m=\bra{m}F_M^\dagger\Bigl(\frac{1}{\sqrt M}\sum_{k=0}^{M-1}e^{2\pi i\varphi k}\ket k\Bigr)=\frac1M\sum_{k=0}^{M-1}e^{2\pi i k(\varphi-m/M)}

    Use ⟨m∣FM†∣k⟩=ωM−mk/M\bra{m}F_M^\dagger\ket{k}=\omega_M^{-mk}/\sqrt M.

  2. αm=1M 1−e2πiMδ1−e2πiδ,δ=φ−mM\alpha_m=\frac1M\,\frac{1-e^{2\pi iM\delta}}{1-e^{2\pi i\delta}},\qquad\delta=\varphi-\frac mM

    Sum the geometric series (for δ∉Z\delta\notin\Z).

  3. P(m)=∣αm∣2=sin⁡2(πMδ)M2sin⁡2(πδ)P(m)=\abs{\alpha_m}^2=\frac{\sin^2(\pi M\delta)}{M^2\sin^2(\pi\delta)}

    Use ∣1−eiθ∣=2∣sin⁡(θ/2)∣\abs{1-e^{i\theta}}=2\abs{\sin(\theta/2)}. This is the Fejér kernel, normalized so that ∑mP(m)=1\sum_mP(m)=1.

  4. P(m)≤1M2sin⁡2(πδ)≤14M2δ2=14ℓ2(δ=ℓM up to a fraction of a step, ∣δ∣≤12)P(m)\le\frac{1}{M^2\sin^2(\pi\delta)}\le\frac{1}{4M^2\delta^2}=\frac{1}{4\ell^2}\qquad\Bigl(\delta=\frac{\ell}{M}\ \text{up to a fraction of a step},\ \abs\delta\le\tfrac12\Bigr)

    Tails: with δ\delta taken in (−12,12](-\tfrac12,\tfrac12] and ∣sin⁡πδ∣≥2∣δ∣\abs{\sin\pi\delta}\ge2\abs\delta, an outcome about ℓ\ell grid steps from φ\varphi has probability at most about 1/(4ℓ2)1/(4\ell^2).

The 4/π² guarantee

DerivationProof
  1. P(b)=sin⁡2(πx)M2sin⁡2(πx/M) ≥ sin⁡2(πx)(πx)2,x=Mδ, ∣x∣≤12P(b)=\frac{\sin^2(\pi x)}{M^2\sin^2(\pi x/M)}\ \ge\ \frac{\sin^2(\pi x)}{(\pi x)^2},\qquad x=M\delta,\ \abs x\le\tfrac12

    Write the distance to the nearest grid point in units of grid steps, and use sin⁡θ≤θ\sin\theta\le\theta in the denominator.

  2. sin⁡(πx)πx ≥ sin⁡(π/2)π/2=2π⟹P(b)≥4π2\frac{\sin(\pi x)}{\pi x}\ \ge\ \frac{\sin(\pi/2)}{\pi/2}=\frac2\pi\quad\Longrightarrow\quad P(b)\ge\frac{4}{\pi^2}

    sin⁡u/u\sin u/u is decreasing on (0,π/2](0,\pi/2], so the minimum over ∣x∣≤12\abs x\le\tfrac12 is at ∣x∣=12\abs x=\tfrac12: a phase exactly halfway between grid points.

  3. P(b−)+P(b+) ≥ sin⁡2(πx)[1(πx)2+1(π(1−x))2] ≥ 8π2,x∈[0,1]P(b_-)+P(b_+)\ \ge\ \sin^2(\pi x)\Bigl[\frac{1}{(\pi x)^2}+\frac{1}{(\pi(1-x))^2}\Bigr]\ \ge\ \frac{8}{\pi^2},\qquad x\in[0,1]

    Now let xx be the distance to b−b_-; the same bound applies to both neighbors, and the bracketed function is minimized at x=12x=\tfrac12, where it equals 8/π28/\pi^2. ■\blacksquare

Qubits for n bits with confidence 1 − ε

DerivationProof (following Nielsen & Chuang)
  1. ∣αℓ∣=12t ∣1−e2πi(2tδ−ℓ)∣∣1−e2πi(δ−ℓ/2t)∣ ≤ 12t+1 ∣δ−ℓ/2t∣\abs{\alpha_\ell}=\frac{1}{2^t}\,\frac{\abs{1-e^{2\pi i(2^t\delta-\ell)}}}{\abs{1-e^{2\pi i(\delta-\ell/2^t)}}}\ \le\ \frac{1}{2^{t+1}\,\abs{\delta-\ell/2^t}}

    Let b=⌊2tφ⌋b=\lfloor2^t\varphi\rfloor, δ=φ−b/2t∈[0,2−t)\delta=\varphi-b/2^t\in[0,2^{-t}), and let αℓ\alpha_\ell be the amplitude of outcome b+ℓb+\ell (mod 2t2^t) for −2t−1<ℓ≤2t−1-2^{t-1}<\ell\le2^{t-1}. Bound the numerator by 2 and the denominator below with ∣1−eiθ∣≥2∣θ∣/π\abs{1-e^{i\theta}}\ge2\abs\theta/\pi for ∣θ∣≤π\abs\theta\le\pi.

  2. Pr⁡[∣m−b∣>e] ≤ 14[∑ℓ≤−(e+1)1(ℓ−2tδ)2+∑ℓ≥e+11(ℓ−2tδ)2] ≤ 14[∑ℓ≥e+11ℓ2+∑ℓ≥e1ℓ2]\Pr[\abs{m-b}>e]\ \le\ \frac14\Bigl[\sum_{\ell\le-(e+1)}\frac{1}{(\ell-2^t\delta)^2}+\sum_{\ell\ge e+1}\frac{1}{(\ell-2^t\delta)^2}\Bigr]\ \le\ \frac14\Bigl[\sum_{\ell\ge e+1}\frac1{\ell^2}+\sum_{\ell\ge e}\frac{1}{\ell^2}\Bigr]

    Square, sum over outcomes more than ee steps from bb, and use 0≤2tδ<10\le2^t\delta<1.

  3. Pr⁡[∣m−b∣>e] ≤ 12∑ℓ≥e1ℓ2 ≤ 12∫e−1∞dℓℓ2=12(e−1)\Pr[\abs{m-b}>e]\ \le\ \frac12\sum_{\ell\ge e}\frac1{\ell^2}\ \le\ \frac12\int_{e-1}^{\infty}\frac{d\ell}{\ell^2}=\frac{1}{2(e-1)}

    Bound both sums by the larger one and compare with an integral.

  4. e=2p−1:12(2p−2)≤ε  ⟺  2p≥2+12εe=2^p-1:\quad\frac{1}{2(2^p-2)}\le\varepsilon\iff2^p\ge2+\frac{1}{2\varepsilon}

    If ∣m−b∣≤2p−1\abs{m-b}\le2^p-1 then ∣m/2t−φ∣≤(2p−1)/2t+δ<2−n\abs{m/2^t-\varphi}\le(2^p-1)/2^t+\delta<2^{-n}. Require the failure bound to be at most ε\varepsilon. ■\blacksquare

Predict before you look

You need φ\varphi to n=10n=10 bits with failure probability at most ε=0.01\varepsilon=0.01. How many counting qubits does t=n+⌈log⁡2(2+12ε)⌉t=n+\lceil\log_2(2+\tfrac{1}{2\varepsilon})\rceil prescribe?

Show the answer

16

2+10.02=522+\tfrac{1}{0.02}=52 and log⁡252≈5.70\log_252\approx5.70, so p=6p=6 and t=16t=16. Ten qubits pay for the precision, six for the confidence.

Alternative: repeat and take the median. With p=2p=2 extra qubits a single run is within 2−n2^{-n} with probability at least 1−12(4−2)=341-\tfrac{1}{2(4-2)}=\tfrac34. Repeat KK times and output the median (after unwrapping the phases around the cluster of estimates): it is wrong only if at least half the runs are, which by a Chernoff bound has probability e−Ω(K)e^{-\Omega(K)}. Confidence 1−ε1-\varepsilon then costs O(log⁡(1/ε))\order{\log(1/\varepsilon)} runs of n+2n+2 qubits instead of a wider register.

Kitaev's approach, Heisenberg scaling and mixed inputs

Kitaev's approach (1995). Phase estimation does not need a QFT at all. The Hadamard test on U2jU^{2^j} (a control qubit in ∣+⟩\ket+, a controlled-U2jU^{2^j}, an XX-basis measurement) gives outcome ++ with probability 12(1+cos⁡2π2jφ)\tfrac12(1+\cos2\pi2^j\varphi); inserting S†S^\dagger before the measurement gives 12(1+sin⁡2π2jφ)\tfrac12(1+\sin2\pi2^j\varphi). Estimating each 2jφ mod 12^j\varphi \bmod 1 to constant accuracy from O(log⁡(t/δ))\order{\log(t/\delta)} samples and stitching these estimates together recovers φ\varphi to tt bits with probability 1−δ1-\delta, using one control qubit and only single-qubit measurements.

Inputs that are not eigenstates. Expand ∣ψ⟩=∑ucu∣u⟩\ket\psi=\sum_uc_u\ket u in eigenstates of UU. By linearity the final state is ∑ucu∣φ~u⟩∣u⟩\sum_uc_u\ket{\tilde\varphi_u}\ket u, where ∣φ~u⟩\ket{\tilde\varphi_u} is the counting-register state for phase φu\varphi_u. Because the ∣u⟩\ket u are orthonormal, the outcome distribution is the mixture ∑u∣cu∣2Pφu(m)\sum_u\abs{c_u}^2P_{\varphi_u}(m): you sample an eigenphase with probability ∣cu∣2\abs{c_u}^2, and if the phases are resolved the work register collapses onto (approximately) that eigenstate. Order finding uses this with ∣1⟩=1r∑s∣us⟩\ket1=\tfrac{1}{\sqrt r}\sum_s\ket{u_s}; ground-state energy estimation uses it with a trial state that must overlap the ground state.

Check your understanding

You run phase estimation (with ample precision) on a trial state whose overlap with the ground state is ∣⟨g∣ψ⟩∣2=0.1\abs{\braket{g|\psi}}^2=0.1. On average, how many runs until the ground-state energy appears?

  1. 1: phase estimation projects onto the ground state
  2. About 3 (≈10\approx\sqrt{10})
  3. About 10
  4. About 100
Show the answer

C. About 10

Each run returns the ground-state phase with probability ∣cg∣2=0.1\abs{c_g}^2=0.1, independently, so the waiting time is geometric with mean 1/0.1=101/0.1=10. Amplitude amplification could reduce this to about 10\sqrt{10}, but only with extra coherent machinery (reflections about ∣ψ⟩\ket\psi and about the ground-state phase), not by plain repetition.

Key takeaways

  • P(m)=sin⁡2(π2tδ)/(4tsin⁡2(πδ))P(m)=\sin^2(\pi2^t\delta)/\bigl(4^t\sin^2(\pi\delta)\bigr), a Fejér kernel: exact for tt-bit phases, otherwise a main lobe of width ∼2−t\sim2^{-t} with 1/ℓ21/\ell^2 tails.
  • The nearest estimate has probability at least 4/π24/\pi^2 and the two nearest at least 8/π28/\pi^2; for φ=1/3\varphi=1/3, P(best)≈0.68P(\text{best})\approx0.68 at every tt. Precision is not confidence.
  • t=n+⌈log⁡2(2+12ε)⌉t=n+\lceil\log_2(2+\tfrac1{2\varepsilon})\rceil qubits give nn bits with probability at least 1−ε1-\varepsilon; alternatively take the median of O(log⁡(1/ε))\order{\log(1/\varepsilon)} runs.
  • 2t−12^t-1 uses of UU buy precision 2−t2^{-t}: Heisenberg scaling, optimal up to constants. Kitaev's version needs one control qubit and no QFT.
  • On a superposition of eigenstates, phase estimation samples eigenphase φu\varphi_u with probability ∣cu∣2\abs{c_u}^2: the engine of order finding and of energy estimation, whose real bottleneck is the overlap.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

The phase lies exactly halfway between two grid points, φ=(b+12)/2t\varphi=(b+\tfrac12)/2^t. As t→∞t\to\infty, the probability of outcome bb tends to

  1. 12\tfrac12
  2. 4/π2≈0.4054/\pi^2\approx0.405
  3. 8/π2≈0.818/\pi^2\approx0.81
  4. 00, because the outcome spreads over 2t2^t values
Show the answer

B. 4/π2≈0.4054/\pi^2\approx0.405

P(b)=sin⁡2(π/2)/(M2sin⁡2(π/2M))→1/(M2⋅π2/4M2)=4/π2P(b)=\sin^2(\pi/2)/(M^2\sin^2(\pi/2M))\to1/(M^2\cdot\pi^2/4M^2)=4/\pi^2. The neighbor b+1b+1 gets the same, so the two together carry 8/π28/\pi^2; the remaining ≈0.19\approx0.19 sits in the tails.

Question 2

To learn φ\varphi to 20 bits with failure probability at most 14\tfrac14, how many counting qubits does t=n+⌈log⁡2(2+12ε)⌉t=n+\lceil\log_2(2+\tfrac{1}{2\varepsilon})\rceil prescribe?

  1. 20
  2. 21
  3. 22
  4. 40
Show the answer

C. 22

2+12⋅14=42+\tfrac{1}{2\cdot\frac14}=4, log⁡24=2\log_24=2, so t=22t=22.

Question 3

Counting a controlled-U2jU^{2^j} as 2j2^j uses of UU, how many uses does textbook phase estimation with tt counting qubits make?

  1. tt
  2. t(t+1)/2t(t+1)/2
  3. t 2tt\,2^t
  4. 2t−12^t-1
Show the answer

D. 2t−12^t-1

∑j=0t−12j=2t−1\sum_{j=0}^{t-1}2^j=2^t-1. Precision 2−t2^{-t} for ≈2t\approx2^t uses is the Heisenberg scaling ε∼1/T\varepsilon\sim1/T.

Question 4

Which statement about Kitaev's approach to phase estimation is correct?

  1. It estimates each 2jφ mod 12^j\varphi \bmod 1 with Hadamard tests on a single control qubit, needs no QFT, and controls the error probability by repetition
  2. It needs 2t2^t counting qubits to reach tt bits
  3. It works only when φ\varphi has an exact tt-bit expansion
  4. It reaches precision ε\varepsilon with O(log⁡(1/ε))\order{\log(1/\varepsilon)} total uses of UU
Show the answer

A. It estimates each 2jφ mod 12^j\varphi \bmod 1 with Hadamard tests on a single control qubit, needs no QFT, and controls the error probability by repetition

Kitaev's method replaces the coherent inverse QFT by single-qubit measurements and classical stitching of the bits, with O(log⁡(t/δ))\order{\log(t/\delta)} repetitions per power for overall confidence 1−δ1-\delta.

Further reading

  • A. Yu. Kitaev, "Quantum measurements and the Abelian stabilizer problem", arXiv:quant-ph/9511026 (1995).
  • R. Cleve, A. Ekert, C. Macchiavello & M. Mosca, "Quantum algorithms revisited", Proc. R. Soc. Lond. A 454, 339 (1998).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §5.2 (Cambridge, 2010).
  • S. Kimmel, G. H. Low & T. J. Yoder, "Robust calibration of a universal single-qubit gate set via robust phase estimation", Phys. Rev. A 92, 062315 (2015).
  • L. Lin & Y. Tong, "Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers", PRX Quantum 3, 010318 (2022).