ForShor

Lean Mathlib License

A formal verification of Shor's algorithm in Lean 4 — including its resource estimation.

The development verifies an implementation of order finding built on fast (Toom-Cook) multiplication, from a high-level gate language down to a low-level abstract machine, and proves that the whole circuit uses only O(n^(2+ε)) gates.

Main results

Correctness (ForShor/ShorVerification/Implementation/Shor/Proofs/NaiveShor/Correctness.lean): the ideal order-finding circuit recovers the multiplicative order with probability Ω(1 / log log N).

theorem Shor_correct (T : ℕ → ℕ) (inst : ShorOrderFindingInstance)
    (ψ0 : qs.State) (hψ0 : ‖ψ0‖ = 1) :
    probability_of_success ... ≥ κ / Real.log ((Nat.log2 inst.N : ℝ) + 1)

Unpacking the five pieces, since the inequality alone does not say much:

  • probability_of_success (Implementation/Shor/Statement.lean) is ∑ o : Fin Q, r_found T verify o Q r * probMeas x o (evalC C ψ) — the probability that the measured outcome, after classical post-processing, is exactly the order r. Not the probability of landing in a good window.
  • r_found (Implementation/Shor/Math/ShorDefinition.lean) is the 0/1 indicator that scanning the first T Q continued-fraction convergents of o/Q, keeping those whose denominator d satisfies a^d ≡ 1 (mod N), returns r.
  • T is any classical budget with continuedFractionSearchBound Q ≤ T Q. It bounds the convergent scan, is not a circuit parameter, and costs no gates.
  • κ = 1/π² ≈ 0.101, which is Shor's per-numerator Fourier constant 4/π² times the 1/4 of the Mertens-type totient bound φ(r)/r ≥ 1/(4 · log(log₂ N + 1)). The bound is Ω(1 / log log N), the classical Rosser–Schoenfeld shape.
  • The exponent register has log₂(2N²) bits and the modulus register log₂(2N), and the input is the ideal IdealOrderFindingInput: all registers clean, exponent register in uniform superposition.

The same bound survives compilation, up to a factor of two, once the per-step precision η is chosen as a function of N (Implementation/Shor/Main.lean):

theorem Shor_correct_approx_lowered (T : ℕ → ℕ) (hT : ContinuedFractionSearchComplete T) :
    ShorCorrectApproxLowered T hT
-- at any η ≤ shorPrecision N x:  probability_of_success ... ≥ κ / (2 * Real.log ((Nat.log2 N : ℝ) + 1))

The lowering itself is exact; the loss is the modular-exponentiation approximation, bounded by 2 · tbits(x) · √(2 · 2048 · η). Holding that to half the ideal bound needs η = Θ(1/(n log n)²), which costs O(log n) extra work bits — well inside the budget the resource estimate allows. At 2048 bits this is η ≈ 2⁻⁵³, about 105 extra work bits; the constant is κ²/65536 and the exponents come from inverting the square root in the per-step error bound. shorPrecision is a closed form — there is no existential constant a circuit builder would have to guess.

Resource estimation (ForShor/ShorVerification/Implementation/GateCount/Shor_GateCount.lean): for every ε > 0 there is a recursion parameter k such that the compiled Shor circuit uses O(n^(2+ε)) elementary gates.

def ExistsShorGateCountBound (qs : QSemantics) (ε : ℝ) : Prop :=
  0 < ε →
    ∃ k : ℕ, ∃ hk : 1 < k, ∃ ops : Prog k,
      PhaseProductProgramOK k hk ops ∧ ShorGateCountBound qs ε k hk ops

theorem exists_shorGateCountBound (qs : QSemantics) ... (ε : ℝ) : ExistsShorGateCountBound qs ε

The bound is not special to the table this repository generates. PhaseProductProgramOK is the four submission conditions C1–C4, so any ShorLoweringSetup — any submission — satisfies it by construction, and the companion theorem applies to it directly:

def ShorGateCountBoundOfSetup (qs : QSemantics) (s : ShorLoweringSetup) (ε : ℝ) : Prop :=
  phaseProductExponent s.k ≤ 1 + ε →
    ShorGateCountBound qs ε s.k s.hk s.ops s.pts s.hpts

theorem shorGateCountBound_of_setup (qs : QSemantics) ... (s : ShorLoweringSetup) (ε : ℝ) :
    ShorGateCountBoundOfSetup qs s ε

The two forms differ in who chooses k. A submitted table fixes its own arity, and with it its own exponent phaseProductExponent k = log(2k−1)/log k — a k = 2 table runs at roughly n^2.585 — so shorGateCountBound_of_setup takes the ε that table supports as a hypothesis. Reaching every positive ε means letting k grow, which is why exists_shorGateCountBound quantifies over k existentially.

Both theorems are about the constant policy: one table used at every width. That is the right statement for an asymptotic exponent, since a finite cascade of tables is eventually the widest one and does not change the exponent — but it is the wrong statement for the score, which is a gate count at n = 2048, where the bands below the top are exactly what a cascade is for. An exact gate count at a fixed size for a general width-indexed policy is separate work, not a corollary of these; it is what the IR for a policy (above) would feed.

Policy.shorGateCountBound is the asymptotic statement for a policy: for any admissible policy whose first band's exponent log(2k−1)/log k is at most 1 + ε, the lowered order-finding circuit has O(n^(2+ε)) gates.

Here ShorGateCountBound says the count of elementary gates in the fully lowered order-finding circuit is at most C · n^(2+ε), where n is the size of the modulus register (typeclass arguments elided):

def ShorGateCountBound (qs : QSemantics) (ε : ℝ) (k : ℕ) (hk : 1 < k) (ops : Prog k) : Prop :=
  ∀ cWork : ℕ, 1 ≤ cWork →
  ∃ C : ℝ, 0 < C ∧
  ∃ n₀ : ℕ, 1 ≤ n₀ ∧
    ∀ (inst : ShorOrderFindingInstance) (x y work scratch : ExtReg) (flag : ℕ) (b0 : qs.Basis) (η : ℝ)
      (hready : LoweredShorReady qs P η inst.a inst.N x y work scratch flag b0)
      (hws : Policy.GateWorkspaceOK P hready.circuit),
      let n := y.width
      n₀ ≤ n →
      algorithm1ExtraBits η ≤ (cWork - 1) * regSize y.active →
      (LowGate.gateCount shorGateCostModel (Policy.lowerGate P hready.circuit hws) : ℝ)
        ≤ C * shorGateRate ε n

Here P is the constant policy of the table. The hypothesis LoweredShorReady and the circuit Policy.lowerGate P hready.circuit hws are those of the correctness theorem, so the bound and the correctness statement are about the same circuit.

The precision η is a parameter of the circuit, not of the bound: fix any work-width budget cWork, and the estimate holds for every η whose prescribed extra bits fit that budget. Shor's own schedule η = δ/n² is one such choice, and shorGateCountBoundShorEta_of_setup specialises to it — that corollary is the only public statement mentioning δ.

The two quantities being compared are honest counts, not abstract measures: LowGate.gateCount shorGateCostModel counts the LowGate operations of the compiled circuit, and shorGateRate ε n is just n^(2+ε).

noncomputable def shorGateRate (ε : ℝ) (n : ℕ) : ℝ :=
  Real.rpow (((max 1 n : ℕ) : ℝ)) (2 + ε)

Status

All components are proved: phase-product compilation, QFT decomposition, continued-fraction recovery, lowering correctness, modular-exponentiation error bounds, and the full resource-estimation stack. No proof in the codebase uses sorry — the one occurrence is a deliberate test that Submission/Audit.lean's axiom check rejects it — and #print axioms on the headline theorems reports only propext, Classical.choice, and Quot.sound.

The reference implementation (ForShor/ShorVerification/Implementation/Reference/) instantiates the whole framework concretely and is fully computable end to end: Shor.Reference.referenceProgramAt lowers to an executable LowGate circuit with no noncomputable interpolation step (the phase-product coefficients are computed via Matrix.cramer, not Matrix.inv). ForShor/Emit/ prints that circuit as JSON (forshor.lowgate/v2 schema); lake exe forshor_emit <k> <a> <N> <m> writes it to stdout.

The reference is not the only implementation the development admits. ForShor/ShorVerification/Framework/ToomCookTable.lean states what makes a Toom-Cook table admissible, and referenceProgramAt is generic in it, so any table passing four decidable side conditions gets the same proved correctness theorem — see Submitting a table.

Repository layout

DirectoryContents
ForShor/ShorVerification/Framework/Semantic core, shared by every implementation: registers (Quantum/), the high-level Gate and low-level LowGate languages (AbstractMachine/), QSemantics and the other semantic classes (Semantics/), the cost model (Gatecount/), general classical math (Math/), the correctness contract (Contract.lean), what makes a submitted Toom-Cook table admissible (ToomCookTable.lean, which imports Mathlib and nothing else), and what makes a submitted policy admissible (Policy.lean: a policy is a list of width-indexed bands, and a table is the one-band policy at threshold 0; it imports ToomCookTable.lean, never the reverse).
ForShor/ShorVerification/Implementation/PhaseProduct/The recursive phase-product compiler: Toom-Cook interpolation, table generation, and compilation/lowering correctness.
ForShor/ShorVerification/Implementation/PhaseTripleProduct/The three-register analogue, exp(iπφ·x·y·z), as a recursive Toom-Cook circuit with 3k−2 points: correctness on clean states, a controlled and an unequal-width version, the O(n^log_k(3k−2)) gate count and the qubit count. Standalone: nothing in order finding uses it. Read Statement.lean and Main.lean.
ForShor/ShorVerification/Implementation/QFT/The QFT split identity and QFT lowering correctness.
ForShor/ShorVerification/Implementation/ModularExponentiation/Modular-multiplication/exponentiation approximation bounds.
ForShor/ShorVerification/Implementation/Shor/Order-finding circuits, the top-level theorem Shor_correct, and whole-program lowering correctness.
ForShor/ShorVerification/Implementation/GateCount/Resource estimation: counting bounds for the phase product, the QFT, and the complete Shor circuit.
ForShor/ShorVerification/Implementation/Reference/The construction that turns an admissible table into a circuit family: fully computable, and generic in the table rather than tied to one.
ForShor/ShorVerification/Submission/The public surface a submissions repo builds against: deciding the four side conditions, auditing the axioms behind them, the certificate, the score, and the template a submitter copies.
ForShor/ShorVerification/Submission/Policies/The sister repositories' policies written as Lean values and kernel-checked: the twelve acceptance policies and rejection controls (RefPp2048, RefPtp2048, the threshold and fault controls), the six PhaseTripleProduct results-board rows (Board/) and the nine PhaseProduct results-board rows (BoardPP/). Their order-finding peaks are kernel-evaluated in Implementation/QubitCount/Proofs/PolicyNumerals*.
ForShor/Emit/JSON printer for a lowered circuit, the symbolic IR extractor, and the forshor_emit executable.
ForShor/ShorVerification/Model/Consistency witnesses: the standard matrix model of the semantic classes, and the headline theorems restated over QuantumLib matrices. Not imported by anything else.
ForShor/ShorVerification/Vendor/Mertens/Mertens' third theorem with an explicit error term, vendored from an unmerged Mathlib pull request under its Apache-2.0 headers; used by the totient bound behind the success constant. See its README for provenance and removal.
docs/An interactive visualization of the proof architecture.
efficient_tables/Separate from the verified circuit. A classical, theoretical companion: exact optimization of the tables PhaseProduct consumes, sparsity barriers and NP-hardness results, with its own Lean projects and toolchains, a Fortran solver, and a paper. Nothing above depends on it. See efficient_tables/README.md.

For a detailed file-by-file guide, see ARCHITECTURE.md. Each folder also has its own README.md.

Proof architecture

The dependency story in one paragraph: Implementation/PhaseProduct/Proofs/Math/Table_Generation produces the symbolic source programs and phase-point structure, and Implementation/PhaseProduct/Proofs/Math/ToomCook.lean supplies the interpolation algebra. Implementation/PhaseProduct/Proofs/ uses both to prove the high-level Toom-Cook phase identity, the correctness of the compiled signed phase-product circuit, and its lowering to LowGate; Implementation/QFT/Proofs/ proves the QFT split identity and its lowering. Together with Implementation/ModularExponentiation/'s approximation bounds, these feed into Implementation/Shor/, which assembles order finding and whole-program lowering correctness, while Implementation/GateCount/ supplies the resource estimates for the compiled circuit. Implementation/Reference/ instantiates all of this concretely into an executable circuit family, which ForShor/Emit/ serializes to JSON.

You can explore the proof graph interactively:

cd docs && python3 -m http.server 8765
# then open http://localhost:8765

Submitting a table

The challenge this repository defines is narrower than "write a Shor circuit", and deliberately so. The one degree of freedom the verified construction exposes is its Toom-Cook table: an arithmetic program ops over k limb registers, plus the interpolation points pts its phaseProduct checkpoints evaluate at. Everything else — the quantum construction, its correctness proof, the precision, the trial count — is fixed here and is the same for every submission.

A submission is therefore a value of Shor.ShorSubmission (Framework/ToomCookTable.lean): the table, plus the submitter's proofs of four conditions.

(The second kind of submission, a Shor.ShorPolicySubmission (Framework/Policy.lean), is a list of such tables indexed by operand width — Toom-6 at the top, Karatsuba near the leaves, the schoolbook leaf below an explicit threshold — each band carrying the same four proofs, plus one decidable field saying the thresholds strictly decrease. A table submission is the one-band policy at threshold 0, so nothing below changes for it.)

conditionproved by
C1pts.length = 2k - 1 — one point per product coefficientrfl
C2det (interpMatrix …) ≠ 0 — the points interpolate a degree-2k-2 polynomialgoodToomCookPoints_of_distinct _ (by decide +kernel)
C3running ops from the start state, the i-th checkpoint holds exactly pts[i]'s row, all points are consumed, and no addScaled has dst = srcby decide +kernel
C4run? ops start = some start — the table uncomputes itselfby decide +kernel

All four are decidable in the kernel, so the kernel checks a submission rather than a parser or the compiled evaluator. C2 would be the exception — its determinant is a sum over (2k-1)! permutations — except that the interpolation matrix is a projective Vandermonde, so Submission/Decide.lean proves C2 equivalent to the points being pairwise distinct as projective points, which is a quadratic scan.

decide +kernel, not native_decide, and that is enforced rather than requested: Submission/Check.lean runs #assert_axioms Submission.setup, which fails the build unless the finished term's axioms lie inside propext, Classical.choice, Quot.sound — so native_decide (its compiled-evaluator axiom), sorry (sorryAx) and a submitter's own axiom are all rejected by name.

Passing C1–C4 is not evidence of admissibility, it is admissibility: Shor.submission_correct is proved once, generic in the table, and applies with no per-submission proof.

Copy ForShor/ShorVerification/Submission/Template.lean — the only file a submitter owns — edit the three definitions it marks (k, pts, ops), prove the four conditions for them, and run:

lake build Submission && lake exe forshor_submission > ir.json

Building is the check. The executable is a printer: it emits the table, the extracted IR a resource estimator reads, the fixed precision, and the trial count the score is multiplied by.

The second kind: a policy

The score is a gate count at one fixed size, not an asymptotic exponent, and at a fixed size the best circuit is generally a cascade of tables rather than one table used at every width: a wide table while the operands are wide, narrower ones as the recursion descends, the schoolbook leaf at the bottom. A policy submission is that cascade — a list of (threshold, table) bands, widest first.

lake build PolicySubmission && lake exe forshor_policy_submission > policy.json

A policy owns Submission/PolicyTemplate.lean instead, and writes per band exactly what a table submitter writes once: k, pts, ops, and C1–C4. The one new obligation is sorted — the thresholds strictly decrease, closed by decide — which is what makes each band's range well defined. There is deliberately no condition that a band's table shrink the width on its own band: the recursion already falls back to the leaf when it does not, so such a band is dead weight rather than unsoundness, and Shor.Policy.bandShrinks reports it as an advisory check.

The certificate is the same theorem. Shor.policy_submission_correct is generic in the policy, and Shor.submission_correct is literally its one-band case at threshold 0 — a table submission is a policy. A policy is scored the same way too: policy.json carries an IR of one dispatcher plus one body template per band. The dispatcher must be exactly the guard chain built from the policy, and that chain picking the same band as ShorLoweringPolicy.choose at every width is proved, not sampled. The band bodies are pinned against the real compiled circuit on a probe copy of the policy — the same tables in the same order at the smallest thresholds where each table shrinks — one level deep per distinct table and at full depth at the widths reaching one, two and three levels of the probe's recursion, so the cost of the check depends on the tables and not on the thresholds.

The negation option. A policy chooses, with one field next to its bands, how a negation is built and priced: negation := .oneQubit (the default if the field is left out: Gidney's one-clean-ancilla increment, about 12 w Toffolis for a w-bit register) or negation := .scratch (the pre-swap Cuccaro negation against a register of ones: w + 1 clean qubits, 2 w - 3 Toffolis). It is a qubits-against-gates choice and not an admissibility condition: the tables, C1–C4, the thresholds and the certificate are the same either way. forshor_policy_submission prints the method as negation in policy.json, and the gate counts and the qubit peaks are stated and proved for both methods (NegationMethod, Framework/NegationMethod.lean). See Submission/README.md.

See Submission/README.md for what the tiers of checking do and do not establish, and for the CI rules a submissions repo should enforce.

Exact widths, the balanced split, and run-time IR

Three additions. None of them changes what a submitter writes, what lake build PolicySubmission checks, or what the default lake exe forshor_policy_submission prints: by default every circuit, IR and number is upstream's.

Exact widths, opt-in. A policy has a width rule (ShorLoweringPolicy.widthRule, Framework/Policy.lean). The default, .scan, is the scan as before: scanNeededWidths and nextSignedWidth are unchanged. With .exact, the compiler grows each level's registers to the least width holding every value the table reaches, over the box of limb values (exactSignedWidthOfWidths, Compiler/ExactWidth.lean). That width is least (exactSignedWidth_le_iff), never above the scan (nextSignedWidthBy_exact_le_scan) and sound for allocation (allocated_widths_sound_exact). The compiler takes the rule from the policy (neededWidthsBy, compileOpsToSignedGateBy). The correctness theorems are generic in the policy, so policy_submission_correct covers both rules with the same hypotheses and bound. PolicyCheck.lean states it for the shipped template on the exact rule (correct_exact). ExactWidthTests.lean pins one instance and its fault challenge: the shipped k = 2 table at width 20 needs 12 bits, and 11 provably do not hold every reachable value.

The balanced split (Implementation/Reference/Balanced/, lean_lib Balanced). A gate-tree pass for unequal operand widths runs ahead of the unchanged equal-width core. With s the smaller width and L the larger, it pads the small operand if 2L ≤ 3s and otherwise cuts the large one into ⌈L/s⌉ blocks, and only where the existing reserves suffice. Policy.lowerGate_balance_correctness and Shor_correct_approx_lowered_balanced_of_modExp_bound are its certificate.

Run-time policy IR. forshor_policy_submission extracts the policy IR itself, at run time, with the extractor PolicyCheck.lean used to run at build time, which hit the heartbeat wall on k ≥ 4 tables. The IR templates do not depend on the width rule; only the width oracles' values do. Flags:

FlagEffect
noneThe policy as submitted, on the scan rule: upstream's document
--exact-widthsThe same bands on the exact rule; the evaluation tier compiles at exact widths, and ir.width_rule carries the rule a consumer evaluates nextWidth with
--balancedImplies --exact-widths; also runs the balanced tier, and prints the balanced document as ir and the policy's own as ir_unbalanced
--probe-exactProbe where the policy's own rule shrinks each table rather than where the scan does: deeper and much slower
--probe-scanAccepted, does nothing (it is the default)
--width-tablePrint the compiler's widths per band; not a submission document

The output's extraction field records the rule and the probe tier.

What to trust, and how far:

  • The IR is checked against the compiled circuit at sampled widths, as before. That is evaluation, not a theorem.
  • exactWidthMemo (@[implemented_by]) speeds up compiled evaluation on the exact rule only. No kernel proof uses it; any native_decide that reaches the exact width runs through it.
  • At run time the extractor memoises registry lookups and bounds each comparison. One that exceeds its budget counts as no match, and the term is translated structurally instead. The count is recorded as extraction.lookup_timeouts, and the evaluation tier checks the result either way. Build-time extraction (extract_ir_doc) is unchanged.

Building

The project uses Lean v4.36.0-rc1 (pinned in lean-toolchain) and depends on mathlib4 at revision 4dc43842a11f257ffba2a611c943a133a65cb4b2, pinned in both lakefile.lean and lake-manifest.json. lake exe cache get fetches the prebuilt oleans for that exact revision, so the pin is what makes the cache usable. With elan installed:

lake exe cache get   # fetch prebuilt mathlib oleans
lake build

To print the reference circuit for an instance (k, a, N, m) as JSON:

lake exe forshor_emit 2 2 15 0

The other build targets:

lake build EmitTests          # the emitter's native_decide acceptance suite
lake build Submission         # checks the table and proofs in Submission/Template.lean
lake exe forshor_submission
lake build PolicySubmission   # the kernel-checked side conditions for Submission/PolicyTemplate.lean
lake exe forshor_policy_submission   # extracts the IR, runs the evaluation tier; prints policy.json only if it passes
lake build ExactWidthTests Balanced  # exact-width instances and fault challenge; the balanced split

The kernel-evaluated order-finding peaks of the policies under Submission/Policies/ (decide +kernel) are heavy, so the ones under the exact width rule are libraries of their own, chained by import so that Lake builds them one at a time:

lake build PolicyNumeralsExact           # the five PhaseProduct acceptance policies with an exact-rule numeral (9-12 GB peak each)
lake build PolicyNumeralsBoardExact      # the five results-board PhaseProduct rows that fit a 16 GB CI runner (up to about 12 GB)
lake build PolicyNumeralsBoardExactHeavy # the other four rows; needs 16 GB or more of free memory, not built in CI

CI builds the first two, each in a step of its own after the main build; the scan-rule numerals and the policies themselves are part of the ForShor umbrella. The peak resident memory of the kernel evaluation is what limits these, which is why the exact ones are not in the umbrella.

License

Released under the Apache License 2.0. See LICENSE. Two files carry code from other projects under their own licenses, each reproduced in the file: ShorVerification/Model/QuantumLib/Vendored.lean (QuantumLib, MIT) and ShorVerification/Implementation/Shor/Proofs/Math/Mertens/ (Apache 2.0, from a Mathlib fork).

Citation

If you use ForShor in your research, please cite it. A machine-readable CITATION.cff is provided (GitHub renders a "Cite this repository" button); a BibTeX entry:

@misc{suresh2026forshor,
  author       = {Anirudh Suresh and Jai Patel and Yudong Cao and Runzhou Tao},
  title        = {{ForShor}: Formal Verification of {Shor}'s Algorithm in {Lean~4}
                  with Verified Resource Estimation},
  year         = {2026},
  howpublished = {\url{https://github.com/VerifiedQC/ForShor}},
  note         = {Apache-2.0 licensed Lean~4 development}
}