Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Order Finding & Continued Fractions

Turning a noisy measurement into an exact period.

Phase estimation hands you a binary fraction like 0.00101010110.0010101011. Hidden inside it is an exact rational s/rs/r whose denominator is the period you need. This lesson proves why 2L+12L+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 aa yields a factor with probability at least 1−2−(m−1)1-2^{-(m-1)}, and explain why prime powers must be handled classically.
  • Bound the information lost when gcd⁡(s,r)>1\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<2N2N^2\le Q<2N^2 without the extra log⁡(1/ε)\log(1/\varepsilon) qubits. For each ss, the outcome yy with ∣ry mod Q∣≤r/2\abs{ry\bmod Q}\le r/2 (residue taken in (−Q/2,Q/2](-Q/2,Q/2]) has probability at least about 4/(π2r)4/(\pi^2r), so some such "good" yy appears with probability about 4/π24/\pi^2, and every good yy satisfies ∣y/Q−s/r∣≤12Q<12r2\abs{y/Q-s/r}\le\tfrac1{2Q}<\tfrac1{2r^2}.

Continued fractions and Legendre's theorem

DerivationProof of Legendre's theorem
  1. x=pnqn+δ2qn2,∣δ∣<1x=\frac{p_n}{q_n}+\frac{\delta}{2q_n^2},\qquad\abs\delta<1

    Reduce s/rs/r to lowest terms (this only weakens the hypothesis' denominator) and expand it as [a0;…,an][a_0;\dots,a_n] with convergents pk/qkp_k/q_k, so pn/qn=s/rp_n/q_n=s/r. A rational has two expansions, […,an]=[…,an−1,1][\dots,a_n]=[\dots,a_n-1,1], so the parity of nn is yours to choose. Define δ\delta as above; if δ=0\delta=0 there is nothing to prove.

  2. x=λpn+pn−1λqn+qn−1 ⟹ (−1)nqn(λqn+qn−1)=δ2qn2 ⟹ λ=2(−1)nδ−qn−1qnx=\frac{\lambda p_n+p_{n-1}}{\lambda q_n+q_{n-1}}\ \Longrightarrow\ \frac{(-1)^n}{q_n(\lambda q_n+q_{n-1})}=\frac{\delta}{2q_n^2}\ \Longrightarrow\ \lambda=\frac{2(-1)^n}{\delta}-\frac{q_{n-1}}{q_n}

    Define λ\lambda by x=[a0;…,an,λ]x=[a_0;\dots,a_n,\lambda]. Subtract pn/qnp_n/q_n and use qnpn−1−pnqn−1=(−1)nq_np_{n-1}-p_nq_{n-1}=(-1)^n.

  3. λ=2∣δ∣−qn−1qn > 2−1=1\lambda=\frac{2}{\abs\delta}-\frac{q_{n-1}}{q_n}\ >\ 2-1=1

    Choose the parity of nn so that (−1)n(-1)^n has the sign of δ\delta. Use ∣δ∣<1\abs\delta<1 and qn−1≤qnq_{n-1}\le q_n.

  4. x=[a0;a1,…,an,b0,b1,… ],b0≥1x=[a_0;a_1,\dots,a_n,b_0,b_1,\dots],\qquad b_0\ge1

    A real λ>1\lambda>1 has a continued fraction [b0;b1,… ][b_0;b_1,\dots] with b0≥1b_0\ge1, so this is a valid expansion of xx, and pn/qn=s/rp_n/q_n=s/r is its nn-th convergent. ■\blacksquare

Complexity. For x=m/2tx=m/2^t the expansion is Euclid's algorithm on (m,2t)(m,2^t): O(t)\order{t} division steps on tt-bit numbers, O(t3)\order{t^3} bit operations naively. In practice you keep the last convergent with denominator below NN and test aq≡1(modN)a^{q}\equiv1\pmod N for it and a few small multiples.

Check your understanding

Phase estimation returns xx. For which xx does Legendre's theorem guarantee that 2/72/7 appears among the convergents?

  1. x=0.2500x=0.2500
  2. x=0.2700x=0.2700
  3. x=0.2900x=0.2900
  4. x=0.3000x=0.3000
Show the answer

C. x=0.2900x=0.2900

The condition is ∣x−2/7∣<1/(2⋅72)=1/98≈0.0102\abs{x-2/7}<1/(2\cdot7^2)=1/98\approx0.0102, and 2/7≈0.28572/7\approx0.2857. Only ∣0.29−0.2857∣≈0.0043\abs{0.29-0.2857}\approx0.0043 qualifies. Indeed 0.29=29/100=[0;3,2,4,3]0.29=29/100=[0;3,2,4,3] has convergents 0,13,27,931,291000,\tfrac13,\tfrac27,\tfrac9{31},\tfrac{29}{100}.

When does a random a work?

DerivationProof
  1. r=lcm⁡(r1,…,rm),2dj ∥ rjr=\operatorname{lcm}(r_1,\dots,r_m),\qquad 2^{d_j}\,\|\,r_j

    By the Chinese remainder theorem, aa corresponds to independent uniform aj∈Zpjαj∗a_j\in\Z^*_{p_j^{\alpha_j}}, and each of these groups is cyclic of even order φ(pjαj)=pjαj−1(pj−1)\varphi(p_j^{\alpha_j})=p_j^{\alpha_j-1}(p_j-1). Let rjr_j be the order of aja_j and djd_j the exact power of 2 dividing it.

  2. failure ⟹ d1=d2=⋯=dm\text{failure}\ \Longrightarrow\ d_1=d_2=\cdots=d_m

    If rr is odd, every dj=0d_j=0. If rr is even and ar/2≡−1a^{r/2}\equiv-1, then ajr/2≡−1≢1a_j^{r/2}\equiv-1\not\equiv1 modulo every pjαjp_j^{\alpha_j}, so rj∤r/2r_j\nmid r/2 although rj∣rr_j\mid r: every djd_j equals the power of 2 in rr.

  3. Pr⁡[dj=Dj]=12,Pr⁡[dj=d]≤12  for every d\Pr[d_j=D_j]=\tfrac12,\qquad\Pr[d_j=d]\le\tfrac12\ \ \text{for every } d

    In a cyclic group ⟨g⟩\langle g\rangle of order 2Du2^{D}u (uu odd, D≥1D\ge1), the order of gkg^k is 2Du/gcd⁡(2Du,k)2^{D}u/\gcd(2^{D}u,k), whose power of 2 is exactly 2D2^{D} iff kk is odd: half of the elements.

  4. Pr⁡[failure] ≤ Pr⁡[d2=d1,…,dm=d1] ≤ (12)m−1■\Pr[\text{failure}]\ \le\ \Pr[d_2=d_1,\dots,d_m=d_1]\ \le\ \Bigl(\tfrac12\Bigr)^{m-1}\qquad\blacksquare

    Condition on a1a_1; the remaining aja_j are independent of it.

The bound is tight. For N=21=3⋅7N=21=3\cdot7, both Z3∗\Z_3^* (order 2) and Z7∗\Z_7^* (order 6) have exactly one factor of 2 in their order, so each djd_j is 0 or 1 with probability 12\tfrac12, and exactly half of the 12 elements of Z21∗\Z_{21}^* work. The proof also explains the classical pre-check for prime powers: Zpα∗\Z^*_{p^\alpha} is cyclic and its only element of order 2 is −1-1, so whenever rr is even, ar/2≡−1a^{r/2}\equiv-1 and the reduction always fails.

Predict before you look

What fraction of the 20 elements of Z33∗\Z_{33}^* satisfy "rr even and ar/2≢−1a^{r/2}\not\equiv-1"?

Show the answer

50 %

Z3∗\Z_3^* has order 2 and Z11∗\Z_{11}^* has order 10, each with a single factor of 2, so d1,d2∈{0,1}d_1,d_2\in\{0,1\} independently with probability 12\tfrac12 each. Failure means d1=d2d_1=d_2, probability 12\tfrac12: exactly 10 of the 20 elements work, the theorem's bound for m=2m=2.

Reversible modular exponentiation

Each controlled-UbU_b, with b=a2j mod Nb=a^{2^j}\bmod N, must multiply in place, ∣y⟩↦∣by mod N⟩\ket y\mapsto\ket{by\bmod N}, without leaving garbage: scratch data correlated with yy 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
  1. ∣y⟩∣0⟩ ⟼ ∣y⟩∣by mod N⟩\ket{y}\ket{0}\ \longmapsto\ \ket{y}\ket{by\bmod N}

    Out-of-place multiply–accumulate: LL controlled modular additions of the classical constants b 2i mod Nb\,2^i\bmod N, one for each bit yiy_i.

  2. ⟼ ∣by mod N⟩∣y⟩\longmapsto\ \ket{by\bmod N}\ket{y}

    Swap the two registers.

  3. ⟼ ∣by mod N⟩∣y−b−1(by) mod N⟩=∣by mod N⟩∣0⟩\longmapsto\ \ket{by\bmod N}\ket{y-b^{-1}(by)\bmod N}=\ket{by\bmod N}\ket{0}

    Run the multiply–accumulate in subtract mode with the constant b−1 mod Nb^{-1}\bmod N, which exists because gcd⁡(b,N)=1\gcd(b,N)=1 and is found classically by the extended Euclidean algorithm.

  4. controlled version: control the additions and the swap;O(L2) gates\text{controlled version: control the additions and the swap};\qquad\order{L^2}\ \text{gates}

    If the control is ∣0⟩\ket0 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)\order{L} gates, one multiplication O(L2)\order{L^2}, and the t≈2Lt\approx2L multiplications O(L3)\order{L^3}; fast multiplication lowers this to O(L2log⁡Llog⁡log⁡L)\order{L^2\log L\log\log L}.

Space-efficient designs bring the total to 2L+32L+3 qubits (Beauregard 2003, with Fourier-space adders and one recycled control qubit) or 2L+22L+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+⌈log⁡2(2+12ε)⌉t=2L+1+\lceil\log_2(2+\tfrac1{2\varepsilon})\rceil counting qubits, phase estimation of UaU_a on ∣1⟩\ket1 lands within 2−(2L+1)<1/(2r2)2^{-(2L+1)}<1/(2r^2) of s/rs/r for a uniform ss, with probability at least 1−ε1-\varepsilon.
  • Legendre: ∣x−s/r∣<1/(2r2)\abs{x-s/r}<1/(2r^2) forces s/rs/r to be a convergent of xx; Euclid's algorithm finds it in O(L3)\order{L^3} bit operations.
  • gcd⁡(s,r)>1\gcd(s,r)>1 hides a factor of rr; the lcm of two runs recovers rr with probability above 0.540.54.
  • A random aa works with probability at least 1−2−(m−1)1-2^{-(m-1)}, tight for N=21N=21 and N=33N=33; prime powers always fail and are handled classically.
  • Reversible in-place multiplication uses compute, swap, uncompute with b−1b^{-1}: O(L2)\order{L^2} gates each, O(L3)\order{L^3} in total, in 2L+O(1)2L+\order1 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 xx with ∣x−s/r∣<1/(2r2)\abs{x-s/r}<1/(2r^2). Which conclusion is guaranteed?

  1. x=s/rx=s/r exactly
  2. s/rs/r, in lowest terms, is a convergent of the continued fraction of xx
  3. The last convergent of xx is s/rs/r
  4. rr is the denominator of xx in lowest terms
Show the answer

B. s/rs/r, in lowest terms, is a convergent of the continued fraction of xx

That is Legendre's theorem. Note that you obtain s/rs/r in lowest terms, so the denominator is r/gcd⁡(s,r)r/\gcd(s,r).

Question 2

Why must N=pαN=p^\alpha (odd prime power) be detected and handled classically?

  1. Because UaU_a is not unitary when NN is a prime power
  2. Because order finding cannot be done modulo a prime power
  3. Because a prime power has no square roots of 1
  4. Because Zpα∗\Z_{p^\alpha}^* is cyclic, its only element of order 2 is −1-1, so even rr always gives ar/2≡−1a^{r/2}\equiv-1
Show the answer

D. Because Zpα∗\Z_{p^\alpha}^* is cyclic, its only element of order 2 is −1-1, so even rr always gives ar/2≡−1a^{r/2}\equiv-1

In a cyclic group, ar/2a^{r/2} has order exactly 2 when rr is even, and the unique such element is −1-1. Every aa fails, but prime powers are detected classically by testing integer roots.

Question 3

Two runs for the same aa return convergent denominators r1=2r_1=2 and r2=3r_2=3, and neither satisfies ari≡1(modN)a^{r_i}\equiv1\pmod N. What should you try next?

  1. lcm⁡(2,3)=6\operatorname{lcm}(2,3)=6: check whether a6≡1a^6\equiv1
  2. r=5r=5, the sum of the two denominators
  3. r=gcd⁡(2,3)=1r=\gcd(2,3)=1
  4. Discard both runs and start over with a new aa
Show the answer

A. lcm⁡(2,3)=6\operatorname{lcm}(2,3)=6: check whether a6≡1a^6\equiv1

Each denominator is r/gcd⁡(si,r)r/\gcd(s_i,r), a divisor of rr, so rr is a common multiple of 2 and 3. The lcm equals rr unless s1,s2s_1,s_2 share a prime factor with each other and with rr.

Question 4

In-place modular multiplication runs a second multiply–accumulate with b−1 mod Nb^{-1}\bmod N. Why?

  1. To compute b−1b^{-1}, which the controlled powers need
  2. To double the success probability of phase estimation
  3. To return the scratch register to ∣0⟩\ket0, so that no garbage stays entangled with yy and spoils the interference
  4. To reduce the gate count from O(L3)\order{L^3} to O(L2)\order{L^2}
Show the answer

C. To return the scratch register to ∣0⟩\ket0, so that no garbage stays entangled with yy and spoils the interference

After the first pass and the swap, the scratch register holds yy. Subtracting b−1⋅(by)=yb^{-1}\cdot(by)=y clears it, leaving the clean in-place map ∣y⟩↦∣by mod N⟩\ket y\mapsto\ket{by\bmod N}.

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).