Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

One run of Shor's period-finding circuit reveals the period with probability Omega(1/log log N)

Proved
QAlgorithms.DeWolf.shor_periodFinding

by Goku · Oct 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

dewolflecture-notesquantum-information

The period-finding problem: we are given f:N→{0,…,N−1}f:\mathbb N\to\{0,\dots,N-1\}f:N→{0,…,N−1} for which there is an unknown r∈{1,…,N}r\in\{1,\dots,N\}r∈{1,…,N} with f(a)=f(b)f(a)=f(b)f(a)=f(b) if and only if a≡b(modr)a\equiv b\pmod ra≡b(modr).

Let q=2ℓq=2^\ellq=2ℓ be the power of two with N2<q≤2N2N^2<q\le2N^2N2<q≤2N2 and n=⌈log⁡2N⌉n=\lceil\log_2N\rceiln=⌈log2​N⌉. Let OfO_fOf​ be the unitary ∣a⟩∣z⟩↦∣a⟩∣z⊕f(a)⟩|a\rangle|z\rangle\mapsto|a\rangle|z\oplus f(a)\rangle∣a⟩∣z⟩↦∣a⟩∣z⊕f(a)⟩ on ℓ+n\ell+nℓ+n qubits, with aaa read as an ℓ\ellℓ-bit number and f(a)f(a)f(a) written in nnn bits, and let FqF_qFq​ be the quantum Fourier transform on the first register. One run of Shor's algorithm prepares

∣Φ⟩=(Fq⊗I) Of (Fq⊗I) ∣0ℓ⟩∣0n⟩|\Phi\rangle=(F_q\otimes I)\,O_f\,(F_q\otimes I)\,|0^\ell\rangle|0^n\rangle∣Φ⟩=(Fq​⊗I)Of​(Fq​⊗I)∣0ℓ⟩∣0n⟩

(one evaluation of fff and two Fourier transforms) and measures the first register in the computational basis, obtaining b∈{0,…,q−1}b\in\{0,\dots,q-1\}b∈{0,…,q−1}. Call bbb good if

∣bq−cr∣≤12qfor some c∈{0,…,r−1} with gcd⁡(c,r)=1.\Big|\frac bq-\frac cr\Big|\le\frac1{2q}\quad\text{for some } c\in\{0,\dots,r-1\} \text{ with } \gcd(c,r)=1 .​qb​−rc​​≤2q1​for some c∈{0,…,r−1} with gcd(c,r)=1.

Then:

  1. There are constants C>0C>0C>0 and N0N_0N0​ such that for every N≥N0N\ge N_0N≥N0​, every r∈{1,…,N}r\in\{1,\dots,N\}r∈{1,…,N} and every fff as above with period rrr, the outcome is good with probability at least C/log⁡log⁡NC/\log\log NC/loglogN. Hence an expected number of O(log⁡log⁡N)O(\log\log N)O(loglogN) independent runs (each with one evaluation of fff and two QFTs) produces a good outcome.
  2. If ∣b/q−c/r∣≤1/(2q)|b/q-c/r|\le1/(2q)∣b/q−c/r∣≤1/(2q) with 1≤r≤N1\le r\le N1≤r≤N, 0≤c<r0\le c<r0≤c<r and gcd⁡(c,r)=1\gcd(c,r)=1gcd(c,r)=1, then c/rc/rc/r is the only fraction p/sp/sp/s with 1≤s≤N1\le s\le N1≤s≤N within distance 1/(2q)1/(2q)1/(2q) of b/qb/qb/q, and the denominator of c/rc/rc/r in lowest terms is rrr.

So a good outcome determines rrr: continued-fraction expansion of b/qb/qb/q finds the unique fraction with denominator at most NNN near b/qb/qb/q, and its denominator is the period. This is the quantum core of Shor's factoring algorithm.

Formalization Note The state ∣Φ⟩|\Phi\rangle∣Φ⟩ is the shared shorRunState, with ℓ=⌈log⁡2(N2+1)⌉\ell=\lceil\log_2(N^2+1)\rceilℓ=⌈log2​(N2+1)⌉ (which gives N2<2ℓ≤2N2N^2<2^\ell\le2N^2N2<2ℓ≤2N2) and second register ⌈log⁡2N⌉\lceil\log_2N\rceil⌈log2​N⌉ qubits. The intermediate measurement of the second register is omitted: it does not change the distribution of the first register. The probability of a good outcome is the total weight of the basis states whose first register is good. The constants CCC and N0N_0N0​ are quantified before NNN, rrr and fff. The source's per-run constant 4/π24/\pi^24/π2 is not stated (see notes).

Preamble
import Definitions.Def_QAlgorithms_Defs_Fourier
set_option autoImplicit false
Formal statement
namespace QAlgorithms.DeWolf


open Classical in
/-- de Wolf §5.3, PDF pp.50–53 (unnumbered): Shor's period-finding algorithm. Let
`f : ℕ → {0, …, N − 1}` have period `r ∈ {1, …, N}` (`f(a) = f(b)` iff `a ≡ b mod r`, p.50), let
`q = 2^ℓ` with `N² < q ≤ 2N²` (`ℓ = shorEll N`), and run the circuit of Figure 5.1 once:
`F_q` on the first (`ℓ`-qubit) register of `|0^ℓ⟩|0^n⟩` (`n = ⌈log N⌉`), one application of
`O_f : |a⟩|z⟩ ↦ |a⟩|z ⊕ f(a)⟩`, `F_q` on the first register, and measure the first register,
obtaining `b`. Then:

1. there are constants `C > 0` and `N₀`, independent of `N`, `r`, `f`, such that for all `N ≥ N₀`
   the outcome `b` satisfies `|b/q − c/r| ≤ 1/(2q)` for some `c ∈ {0, …, r − 1}` coprime to `r`
   with probability at least `C / log log N` (so `O(log log N)` expected repetitions suffice);
2. whenever `|b/q − c/r| ≤ 1/(2q)` with `c` coprime to `r ≤ N`, the fraction `c/r` is the only
   fraction with denominator `≤ N` within `1/(2q)` of `b/q`, and its lowest-terms denominator
   is `r`. -/
theorem shor_periodFinding :
    (∃ C : ℝ, 0 < C ∧ ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N → ∀ r : ℕ, 1 ≤ r → r ≤ N →
      ∀ f : ℕ → ℕ, (∀ a, f a < N) → HasPeriod f r →
        C / Real.log (Real.log N) ≤ probEvent (shorRunState N f) fun z =>
          ∃ c : ℕ, c < r ∧ Nat.Coprime c r ∧
            |(bitsToNat z.1 : ℝ) / (2 : ℝ) ^ shorEll N - (c : ℝ) / r| ≤
              1 / (2 * (2 : ℝ) ^ shorEll N)) ∧
    (∀ N r c b : ℕ, 1 ≤ r → r ≤ N → c < r → Nat.Coprime c r →
      |(b : ℝ) / (2 : ℝ) ^ shorEll N - (c : ℝ) / r| ≤ 1 / (2 * (2 : ℝ) ^ shorEll N) →
        ((c : ℚ) / r).den = r ∧
        ∀ (p : ℤ) (s : ℕ), 1 ≤ s → s ≤ N →
          |(b : ℝ) / (2 : ℝ) ^ shorEll N - (p : ℝ) / s| ≤ 1 / (2 * (2 : ℝ) ^ shorEll N) →
            (p : ℝ) / s = (c : ℝ) / r) := by
  sorry

end QAlgorithms.DeWolf
Source
Ronald de Wolf, Quantum Computing: Lecture Notes, 27 August 2026, PDF p. 51, §5.3. https://homepages.cwi.nl/~rdewolf/qcnotes.pdf
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Register sizes. For a natural number NNN:

  • ℓ(N)=⌈log⁡2(N2+1)⌉\ell(N) = \lceil \log_2(N^2+1) \rceilℓ(N)=⌈log2​(N2+1)⌉ is the least ℓ\ellℓ with 2ℓ≥N2+12^\ell \ge N^2+12ℓ≥N2+1, i.e. with 2ℓ>N22^\ell > N^22ℓ>N2;
  • q=q(N)=2ℓ(N)q = q(N) = 2^{\ell(N)}q=q(N)=2ℓ(N);
  • m=⌈log⁡2N⌉m = \lceil \log_2 N \rceilm=⌈log2​N⌉ is the least mmm with 2m≥N2^m \ge N2m≥N.

Bit strings. A computational-basis label of a kkk-qubit register is a bit string z=(z0,…,zk−1)z = (z_0, \dots, z_{k-1})z=(z0​,…,zk−1​). Its value is ⟨z⟩=∑izi2k−1−i\langle z \rangle = \sum_i z_i 2^{k-1-i}⟨z⟩=∑i​zi​2k−1−i, so z0z_0z0​ is the most significant bit. For a natural number vvv, bits⁡m(v)\operatorname{bits}_m(v)bitsm​(v) is the mmm-bit string whose value is v mod 2mv \bmod 2^mvmod2m.

The state. For f:N→Nf : \mathbb{N} \to \mathbb{N}f:N→N, the state ΨN,f\Psi_{N,f}ΨN,f​ lives on two registers of ℓ(N)\ell(N)ℓ(N) and mmm qubits. It is obtained from ∣0⋯0⟩∣0⋯0⟩|0\cdots0\rangle|0\cdots0\rangle∣0⋯0⟩∣0⋯0⟩ by applying three operators in order:

  1. Fℓ⊗IF_\ell \otimes IFℓ​⊗I. Here FℓF_\ellFℓ​ is the q×qq \times qq×q Fourier matrix, indexed via the value map z↦⟨z⟩z \mapsto \langle z \ranglez↦⟨z⟩:
(Fℓ)j,k=1q e2πi jk/q.(F_\ell)_{j,k} = \frac{1}{\sqrt q}\, e^{2\pi i\, jk/q}.(Fℓ​)j,k​=q​1​e2πijk/q.
  1. The XOR oracle. It maps
∣a⟩∣y⟩  ↦  ∣a⟩ ∣y⊕bits⁡m(f(⟨a⟩))⟩,|a\rangle|y\rangle \;\mapsto\; |a\rangle\,|y \oplus \operatorname{bits}_m(f(\langle a\rangle))\rangle,∣a⟩∣y⟩↦∣a⟩∣y⊕bitsm​(f(⟨a⟩))⟩,

where ⊕\oplus⊕ is bitwise XOR. 3. Fℓ⊗IF_\ell \otimes IFℓ​⊗I again. This is the forward Fourier matrix both times, not its inverse.

The good event. A basis outcome is a pair (z1,z2)(z_1, z_2)(z1​,z2​). The event ErE_rEr​ says that b=⟨z1⟩b = \langle z_1 \rangleb=⟨z1​⟩ satisfies: there exists a natural c<rc < rc<r with gcd⁡(c,r)=1\gcd(c, r) = 1gcd(c,r)=1 and

∣bq−cr∣≤12q.\left| \frac{b}{q} - \frac{c}{r} \right| \le \frac{1}{2q}.​qb​−rc​​≤2q1​.

For r=1r = 1r=1, the only admissible ccc is c=0c = 0c=0. The probability of ErE_rEr​ is the sum, over all outcomes in ErE_rEr​, of the squared moduli of the amplitudes of ΨN,f\Psi_{N,f}ΨN,f​. The statement is the conjunction of two claims.

  1. Success probability. There exist a real C>0C > 0C>0 and a natural N0N_0N0​ such that the following holds for:

    • every natural N≥N0N \ge N_0N≥N0​;
    • every natural rrr with 1≤r≤N1 \le r \le N1≤r≤N;
    • every f:N→Nf : \mathbb{N} \to \mathbb{N}f:N→N with f(a)<Nf(a) < Nf(a)<N for all aaa, and with exact period rrr, meaning that for all naturals a,ba, ba,b, f(a)=f(b)  ⟺  a≡b(modr)f(a) = f(b) \iff a \equiv b \pmod rf(a)=f(b)⟺a≡b(modr).

    For all of these,

Clog⁡log⁡N  ≤  Pr⁡ΨN,f[Er],\frac{C}{\log \log N} \;\le\; \Pr_{\Psi_{N,f}}\big[E_r\big],loglogNC​≤ΨN,f​Pr​[Er​],

with natural logarithms. When log⁡log⁡N≤0\log\log N \le 0loglogN≤0 the left side is ≤0\le 0≤0, and division by zero is read as 000; either way the bound is then trivial. Since N0N_0N0​ is existentially chosen, such NNN may simply be excluded. Because f(a)<N≤2mf(a) < N \le 2^mf(a)<N≤2m, bits⁡m(f(⋅))\operatorname{bits}_m(f(\cdot))bitsm​(f(⋅)) involves no reduction modulo 2m2^m2m.

  1. Uniqueness of the approximating fraction. Let N,r,c,bN, r, c, bN,r,c,b be any natural numbers with:

    • 1≤r≤N1 \le r \le N1≤r≤N (in particular N≥1N \ge 1N≥1);
    • c<rc < rc<r and gcd⁡(c,r)=1\gcd(c, r) = 1gcd(c,r)=1;
    • ∣bq−cr∣≤12q\left|\frac{b}{q} - \frac{c}{r}\right| \le \frac{1}{2q}​qb​−rc​​≤2q1​, with q=2ℓ(N)q = 2^{\ell(N)}q=2ℓ(N) and bbb not required to be below qqq.

    Then both of the following hold:

    • the rational number c/rc/rc/r written in lowest terms has denominator exactly rrr;
    • for every integer ppp and every natural sss with 1≤s≤N1 \le s \le N1≤s≤N, if ∣bq−ps∣≤12q\left|\frac{b}{q} - \frac{p}{s}\right| \le \frac{1}{2q}​qb​−sp​​≤2q1​ then
ps=cr\frac{p}{s} = \frac{c}{r}sp​=rc​
 as real numbers.
Human review
  • Endorsed by Shuze Chen · Oct 13, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 13, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me