How many qubits, how much precision, what success probability.
Phase estimation promises φ to t bits with t 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-U applications grows like 2t. 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 t-bit estimate has probability at least 4/π2, and the two nearest together at least 8/π2.
Prove that t=n+⌈log2(2+2ε1)⌉ counting qubits give n bits with probability at least 1−ε, 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=2t. After the controlled powers, the counting register holds M1∑k=0M−1e2πiφk∣k⟩ (the work register factors out as ∣u⟩). Phase estimation applies FM† and measures an integer m; the estimate is φ~=m/M, with distances understood modulo 1.
Let b=⌊2tφ⌋, δ=φ−b/2t∈[0,2−t), and let αℓ be the amplitude of outcome b+ℓ (mod 2t) for −2t−1<ℓ≤2t−1. Bound the numerator by 2 and the denominator below with 1−eiθ≥2∣θ∣/π for ∣θ∣≤π.
Square, sum over outcomes more than e steps from b, and use 0≤2tδ<1.
Pr[∣m−b∣>e]≤21ℓ≥e∑ℓ21≤21∫e−1∞ℓ2dℓ=2(e−1)1
Bound both sums by the larger one and compare with an integral.
e=2p−1:2(2p−2)1≤ε⟺2p≥2+2ε1
If ∣m−b∣≤2p−1 then ∣m/2t−φ∣≤(2p−1)/2t+δ<2−n. Require the failure bound to be at most ε. ■
Predict before you look
You need φ to n=10 bits with failure probability at most ε=0.01. How many counting qubits does t=n+⌈log2(2+2ε1)⌉ prescribe?
Show the answer
16
2+0.021=52 and log252≈5.70, so p=6 and t=16. Ten qubits pay for the precision, six for the confidence.
Alternative: repeat and take the median. With p=2 extra qubits a single run is within 2−n with probability at least 1−2(4−2)1=43. Repeat K 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). Confidence 1−ε then costs O(log(1/ε)) runs of n+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 U2j (a control qubit in ∣+⟩, a controlled-U2j, an X-basis measurement) gives outcome + with probability 21(1+cos2π2jφ); inserting S† before the measurement gives 21(1+sin2π2jφ). Estimating each 2jφmod1 to constant accuracy from O(log(t/δ)) samples and stitching these estimates together recovers φ to t bits with probability 1−δ, using one control qubit and only single-qubit measurements.
Inputs that are not eigenstates. Expand ∣ψ⟩=∑ucu∣u⟩ in eigenstates of U. By linearity the final state is ∑ucu∣φ~u⟩∣u⟩, where ∣φ~u⟩ is the counting-register state for phase φu. Because the ∣u⟩ are orthonormal, the outcome distribution is the mixture ∑u∣cu∣2Pφu(m): you sample an eigenphase with probability ∣cu∣2, and if the phases are resolved the work register collapses onto (approximately) that eigenstate. Order finding uses this with ∣1⟩=r1∑s∣us⟩; 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. On average, how many runs until the ground-state energy appears?
1: phase estimation projects onto the ground state
About 3 (≈10)
About 10
About 100
Show the answer
C. About 10
Each run returns the ground-state phase with probability ∣cg∣2=0.1, independently, so the waiting time is geometric with mean 1/0.1=10. Amplitude amplification could reduce this to about 10, but only with extra coherent machinery (reflections about ∣ψ⟩ and about the ground-state phase), not by plain repetition.
Key takeaways
P(m)=sin2(π2tδ)/(4tsin2(πδ)), a Fejér kernel: exact for t-bit phases, otherwise a main lobe of width ∼2−t with 1/ℓ2 tails.
The nearest estimate has probability at least 4/π2 and the two nearest at least 8/π2; for φ=1/3, P(best)≈0.68 at every t. Precision is not confidence.
t=n+⌈log2(2+2ε1)⌉ qubits give n bits with probability at least 1−ε; alternatively take the median of O(log(1/ε)) runs.
2t−1 uses of U buy precision 2−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 with probability ∣cu∣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+21)/2t. As t→∞, the probability of outcome b tends to
21
4/π2≈0.405
8/π2≈0.81
0, because the outcome spreads over 2t values
Show the answer
B.4/π2≈0.405
P(b)=sin2(π/2)/(M2sin2(π/2M))→1/(M2⋅π2/4M2)=4/π2. The neighbor b+1 gets the same, so the two together carry 8/π2; the remaining ≈0.19 sits in the tails.
Question 2
To learn φ to 20 bits with failure probability at most 41, how many counting qubits does t=n+⌈log2(2+2ε1)⌉ prescribe?
20
21
22
40
Show the answer
C. 22
2+2⋅411=4, log24=2, so t=22.
Question 3
Counting a controlled-U2j as 2j uses of U, how many uses does textbook phase estimation with t counting qubits make?
t
t(t+1)/2
t2t
2t−1
Show the answer
D.2t−1
∑j=0t−12j=2t−1. Precision 2−t for ≈2t uses is the Heisenberg scaling ε∼1/T.
Question 4
Which statement about Kitaev's approach to phase estimation is correct?
It estimates each 2jφmod1 with Hadamard tests on a single control qubit, needs no QFT, and controls the error probability by repetition
It needs 2t counting qubits to reach t bits
It works only when φ has an exact t-bit expansion
It reaches precision ε with O(log(1/ε)) total uses of U
Show the answer
A. It estimates each 2jφmod1 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/δ)) repetitions per power for overall confidence 1−δ.
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).