Phase estimation hands you a binary fraction like 0.0010101011. Hidden inside it is an exact rational s/r whose denominator is the period you need. This lesson proves why 2L+1 bits of precision are exactly enough for continued fractions to find it, quantifies every way a run can fail, and makes modular exponentiation reversible.
What you’ll learn
State and prove Legendre's theorem and apply it to the output of phase estimation.
Prove that a random a yields a factor with probability at least 1−2−(m−1), and explain why prime powers must be handled classically.
Bound the information lost when gcd(s,r)>1 and show that two runs suffice with constant probability.
Construct reversible controlled modular multiplication with uncomputation, and count its cost.
The order-finding theorem
Shor's own analysis uses N2≤Q<2N2 without the extra log(1/ε) qubits. For each s, the outcome y with ∣rymodQ∣≤r/2 (residue taken in (−Q/2,Q/2]) has probability at least about 4/(π2r), so some such "good" y appears with probability about 4/π2, and every good y satisfies ∣y/Q−s/r∣≤2Q1<2r21.
Continued fractions and Legendre's theorem
DerivationProof of Legendre's theorem
x=qnpn+2qn2δ,∣δ∣<1
Reduce s/r to lowest terms (this only weakens the hypothesis' denominator) and expand it as [a0;…,an] with convergents pk/qk, so pn/qn=s/r. A rational has two expansions, […,an]=[…,an−1,1], so the parity of n is yours to choose. Define δ as above; if δ=0 there is nothing to prove.
Define λ by x=[a0;…,an,λ]. Subtract pn/qn and use qnpn−1−pnqn−1=(−1)n.
λ=∣δ∣2−qnqn−1>2−1=1
Choose the parity of n so that (−1)n has the sign of δ. Use ∣δ∣<1 and qn−1≤qn.
x=[a0;a1,…,an,b0,b1,…],b0≥1
A real λ>1 has a continued fraction [b0;b1,…] with b0≥1, so this is a valid expansion of x, and pn/qn=s/r is its n-th convergent. ■
Complexity. For x=m/2t the expansion is Euclid's algorithm on (m,2t): O(t) division steps on t-bit numbers, O(t3) bit operations naively. In practice you keep the last convergent with denominator below N and test aq≡1(modN) for it and a few small multiples.
Check your understanding
Phase estimation returns x. For which x does Legendre's theorem guarantee that 2/7 appears among the convergents?
x=0.2500
x=0.2700
x=0.2900
x=0.3000
Show the answer
C.x=0.2900
The condition is ∣x−2/7∣<1/(2⋅72)=1/98≈0.0102, and 2/7≈0.2857. Only ∣0.29−0.2857∣≈0.0043 qualifies. Indeed 0.29=29/100=[0;3,2,4,3] has convergents 0,31,72,319,10029.
When does a random a work?
DerivationProof
r=lcm(r1,…,rm),2dj∥rj
By the Chinese remainder theorem, a corresponds to independent uniform aj∈Zpjαj∗, and each of these groups is cyclic of even order φ(pjαj)=pjαj−1(pj−1). Let rj be the order of aj and dj the exact power of 2 dividing it.
failure⟹d1=d2=⋯=dm
If r is odd, every dj=0. If r is even and ar/2≡−1, then ajr/2≡−1≡1 modulo every pjαj, so rj∤r/2 although rj∣r: every dj equals the power of 2 in r.
Pr[dj=Dj]=21,Pr[dj=d]≤21for every d
In a cyclic group ⟨g⟩ of order 2Du (u odd, D≥1), the order of gk is 2Du/gcd(2Du,k), whose power of 2 is exactly 2D iff k is odd: half of the elements.
Pr[failure]≤Pr[d2=d1,…,dm=d1]≤(21)m−1■
Condition on a1; the remaining aj are independent of it.
The bound is tight. For N=21=3⋅7, both Z3∗ (order 2) and Z7∗ (order 6) have exactly one factor of 2 in their order, so each dj is 0 or 1 with probability 21, and exactly half of the 12 elements of Z21∗ work. The proof also explains the classical pre-check for prime powers: Zpα∗ is cyclic and its only element of order 2 is −1, so whenever r is even, ar/2≡−1 and the reduction always fails.
Predict before you look
What fraction of the 20 elements of Z33∗ satisfy "r even and ar/2≡−1"?
Show the answer
50 %
Z3∗ has order 2 and Z11∗ has order 10, each with a single factor of 2, so d1,d2∈{0,1} independently with probability 21 each. Failure means d1=d2, probability 21: exactly 10 of the 20 elements work, the theorem's bound for m=2.
Reversible modular exponentiation
Each controlled-Ub, with b=a2jmodN, must multiply in place, ∣y⟩↦∣bymodN⟩, without leaving garbage: scratch data correlated with y would stay entangled with the counting register and destroy the interference phase estimation relies on (see uncomputation). The standard construction runs an out-of-place multiplier twice.
DerivationIn-place modular multiplication
∣y⟩∣0⟩⟼∣y⟩∣bymodN⟩
Out-of-place multiply–accumulate: L controlled modular additions of the classical constants b2imodN, one for each bit yi.
⟼∣bymodN⟩∣y⟩
Swap the two registers.
⟼∣bymodN⟩∣y−b−1(by)modN⟩=∣bymodN⟩∣0⟩
Run the multiply–accumulate in subtract mode with the constant b−1modN, which exists because gcd(b,N)=1 and is found classically by the extended Euclidean algorithm.
controlled version: control the additions and the swap;O(L2)gates
If the control is ∣0⟩ nothing must happen, so the additions, subtractions and the register swap (a row of Fredkin gates) are all controlled. Each modular addition costs O(L) gates, one multiplication O(L2), and the t≈2L multiplications O(L3); fast multiplication lowers this to O(L2logLloglogL).
Space-efficient designs bring the total to 2L+3 qubits (Beauregard 2003, with Fourier-space adders and one recycled control qubit) or 2L+2 (Häner, Roetteler & Svore 2017, with Toffoli-based arithmetic). Large-scale estimates add further tricks, such as windowing and coset representations, covered in Breaking RSA: Resource Estimates.
Key takeaways
With t=2L+1+⌈log2(2+2ε1)⌉ counting qubits, phase estimation of Ua on ∣1⟩ lands within 2−(2L+1)<1/(2r2) of s/r for a uniform s, with probability at least 1−ε.
Legendre: ∣x−s/r∣<1/(2r2) forces s/r to be a convergent of x; Euclid's algorithm finds it in O(L3) bit operations.
gcd(s,r)>1 hides a factor of r; the lcm of two runs recovers r with probability above 0.54.
A random a works with probability at least 1−2−(m−1), tight for N=21 and N=33; prime powers always fail and are handled classically.
Reversible in-place multiplication uses compute, swap, uncompute with b−1: O(L2) gates each, O(L3) in total, in 2L+O(1) qubits.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Question 1
Phase estimation gives x with ∣x−s/r∣<1/(2r2). Which conclusion is guaranteed?
x=s/r exactly
s/r, in lowest terms, is a convergent of the continued fraction of x
The last convergent of x is s/r
r is the denominator of x in lowest terms
Show the answer
B.s/r, in lowest terms, is a convergent of the continued fraction of x
That is Legendre's theorem. Note that you obtain s/r in lowest terms, so the denominator is r/gcd(s,r).
Question 2
Why must N=pα (odd prime power) be detected and handled classically?
Because Ua is not unitary when N is a prime power
Because order finding cannot be done modulo a prime power
Because a prime power has no square roots of 1
Because Zpα∗ is cyclic, its only element of order 2 is −1, so even r always gives ar/2≡−1
Show the answer
D. Because Zpα∗ is cyclic, its only element of order 2 is −1, so even r always gives ar/2≡−1
In a cyclic group, ar/2 has order exactly 2 when r is even, and the unique such element is −1. Every a fails, but prime powers are detected classically by testing integer roots.
Question 3
Two runs for the same a return convergent denominators r1=2 and r2=3, and neither satisfies ari≡1(modN). What should you try next?
lcm(2,3)=6: check whether a6≡1
r=5, the sum of the two denominators
r=gcd(2,3)=1
Discard both runs and start over with a new a
Show the answer
A.lcm(2,3)=6: check whether a6≡1
Each denominator is r/gcd(si,r), a divisor of r, so r is a common multiple of 2 and 3. The lcm equals r unless s1,s2 share a prime factor with each other and with r.
Question 4
In-place modular multiplication runs a second multiply–accumulate with b−1modN. Why?
To compute b−1, which the controlled powers need
To double the success probability of phase estimation
To return the scratch register to ∣0⟩, so that no garbage stays entangled with y and spoils the interference
To reduce the gate count from O(L3) to O(L2)
Show the answer
C. To return the scratch register to ∣0⟩, so that no garbage stays entangled with y and spoils the interference
After the first pass and the swap, the scratch register holds y. Subtracting b−1⋅(by)=y clears it, leaving the clean in-place map ∣y⟩↦∣bymodN⟩.
Further reading
P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM J. Comput. 26, 1484 (1997); conference version in Proc. 35th IEEE FOCS (1994).
M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §5.3 and Appendix 4 (Cambridge, 10th anniv. ed., 2010).
G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., revised by D. R. Heath-Brown & J. H. Silverman (Oxford, 2008), chapter on continued fractions.
S. Beauregard, "Circuit for Shor's algorithm using 2n+3 qubits", Quantum Inf. Comput. 3, 175 (2003).
O. Regev, "An efficient quantum factoring algorithm", arXiv:2308.06572 (2023).