A map of the Lean proofs for ForShor
What is actually proved about Shor's algorithm here, and where to find it in the code
Feasibility of a quantum algorithm is typically argued
using gate counts as the primary metric. In the case of factoring a 2048-bit modulus to
break RSA, Shor's algorithm for order-finding is exceedingly popular, being taught in most
introductory quantum computing courses and has an often-quoted gate count to evidence its
practicality. Every instance of a gate count is an estimate coming from a cost model, a circuit
design in a paper, or a spreadsheet explicitly accounting for each subroutine. ForShor
develops the estimation from formally stated theorems, being a Lean 4 repository proving that
a specific, fully compiled order-finding circuit is correct. It also proves the asymptotic gate scaling to be
\(O(n^{2+\varepsilon})\) elementary gates when substituting fast-multiplication from Kahanamoku-Meyer and
Yao (2024) into the modular exponentiation subroutine. By using high-level gate languages
mapping to low-level abstractions, both proofs can be checked in the same kernel, with no sorry and no axioms beyond Lean's own three.#print axioms on the headline theorems reports only propext, Classical.choice and Quot.sound. Decidable side conditions are closed by decide +kernel, never native_decide. The one sorry in the repository is a test that the axiom audit rejects it.
When treated independently, verifying correctness for an idealized circuit is not hard, nor is estimating the cost of a realistic circuit. Coupling these two actions is critically important as the world looks toward a fault-tolerant future, ensuring the resource bound and the correctness proof consider the same quantum algorithm. This way, a circuit with a bounded success probability has its gates explicitly counted, maximizing clarity and confidence as quantum algorithms like Shor’s order-finding, giving efficient solutions to classically hard problems, come into the scope of realizability.
Here, we will describe Shor’s order-finding algorithm as it is written in Lean. We detail the stepwise process from modulus to solution using quantum algorithmic subroutines, with interactive displays to allow the reader to freely traverse the argument. By pairing the proof in words to the Lean code, we aim to build a mathematical foundation both for Lean experts and for those who may be new to formal verification. Interactive nodes in the graphs below link back to the Lean code in the GitHub repository, letting a researcher easily locate where statements are proven. This site primarily focuses on how fast multiplication is integrated with Shor's order-finding algorithm. To learn more about Toom-Cook multiplication and how fast multiplication is brought into controlled modular multiplication, as well as how QFTs can use fast multiplication via Cooley-Tukey decomposition, we recommend reading Appendix A of the paper (link given at the bottom of this page).
We start with three theorems. Shor_correct says the ideal order-finding circuit,
after classical continued-fraction post-processing, returns exactly the order \(r\)
with probability at least \(\kappa / \log(\log_2 N + 1)\), that is \(\Omega(1 / \log\log N)\).\(\kappa = 1/\pi^2 \approx 0.101\): Shor's per-numerator Fourier constant \(4/\pi^2\) times the \(1/4\) of the totient bound \(\varphi(r)/r \ge 1/(4 \log(\log_2 N + 1))\). The exponent register has \(\log_2(2N^2)\) bits, the modulus register \(\log_2(2N)\). The classical budget \(T\) bounds the convergent scan and costs no gates. This is the probability of getting \(r\) itself, not of landing in a good window.
Shor_correct_approx_lowered says the same bound survives compilation, up to a
factor of two, once the per-step precision \(\eta\) is set by a closed form in
\(N\).The lowering itself is exact; the only loss is the modular-exponentiation approximation. Holding it to half the ideal bound costs \(O(\log n)\) extra work bits; at 2048 bits \(\eta \approx 2^{-53}\), about 105 extra work bits. shorPrecision is a closed form, so there is no existential constant a circuit builder would have to guess.
Finally, exists_shorGateCountBound says that for every \(\varepsilon > 0\) there is a
Toom-Cook arity \(k\) at which the compiled circuit uses at most
\(C \cdot n^{2+\varepsilon}\) gates, \(n\) the size of the modulus register. That count is
derived from LowGate operations under an explicitly stated cost model, containing
common primitives like ripple-carry addition and bit-shifting.The quantity bounded is LowGate.gateCount shorGateCostModel of orderFindingApproxLow, the compiled circuit, and the rate is \(n^{2+\varepsilon}\). A companion theorem, shorGateCountBound_of_setup, gives any admissible Toom-Cook table the bound at its own exponent \(\log(2k-1)/\log k\); a \(k = 2\) table runs at about \(n^{2.585}\). Both theorems are about one table used at every width, which is the right statement for an exponent and not a gate count at \(n = 2048\).
Shor's algorithm, as stated in Lean
Shor's algorithm has large classical components, which we will discuss first. To factor a modulus \(N\),
we must first pick a random base \(a\). The quantum computing target is to find the order \(r\)
of \(a\) modulo \(N\). Once found, if \(r\) is even and \(a^{r/2}\)
is not \(-1\), then \(\gcd(a^{r/2} \pm 1, N)\) is a factor. Narrowing further, the quantum
algorithm can be cast as a single circuit composed of four steps (shown below), followed by measurement
and a classical continued-fraction scan.Every block is a definition or theorem in the repository; click it to see the Lean source, verbatim, with a link to the line. The blue row is orderFindingIdeal, the circuit the correctness theorem is about. The circuit that is compiled and counted has the same four steps, with the verified approximate modular exponentiation in third place.
Composing this in Lean, we state the full loop as one theorem, Shor_end_to_end_factoring: at
least half of the bases are good, and for each good one the circuit and the scan return \(r\) with probability at least
\(\kappa / \log(\log_2 N + 1)\), after which the gcd step gives a factor.
Uniform superposition, preparing a data register, and even the inverse QFT are relatively cheap when compared to the modular exponentiation block \(y \leftarrow a^x \bmod N\). We expand this block in the next diagram, building from QFT arithmetic, QFT using phase products, and the phase product itself, further detailing the optimization problem occurring within scheduling operations for the PhaseProduct primitive.
The proof, layer by layer
We recommend reading the development of this proof from top-to-bottom, since that is the order in which the proof goes. The whole scheme is six layers deep. The specification comes first: this is the vocabulary every statement is written in, and the contract the final object has to meet. The three subroutines follow, each verified on its own and resting on the one before it, and a compiler lowers them to elementary gates. Assembling these routines gives a proof that Shor's algorithm is correct, together with a theorem stating the cost of that assembled circuit. The last layer fills in every remaining choice, hands the framework a concrete instance, and counts the qubits it needs.Every arrow is a real import between these folders, read from the Lean sources. The solid labelled arrows are the ones that carry the argument, and the label is the theorem or the vocabulary that crosses it; thin grey arrows are real structure that is not part of the story. Click a layer to open it.
Each panel shows the folder's role in the argument, its forward and backward dependencies, and
a verbatim statement that carries it. The Lean statements are deliberately shown, instance arguments and all:
the Toom-Cook table is given from parameters \(k\) and
ops, appearing in every subroutine theorem and is the reason why one proof serves every
admissible table. We will see everywhere the semantics qs where the theorems are generic.
Inside PhaseProduct: one table, applied recursively
The layer graph shows folder dependencies, but not how expensive blocks are built. As a brief recap, the phase product \(\mathrm{PP}(\varphi x z)\) applies \(\exp(i \varphi x z)\) to two \(n\)-bit registers. Doing it directly costs about \(n^2\) gates. ForShor formalizes the Toom-Cook method for integer multiplication, splitting \(x\) and \(z\) into \(k\) chunks, evaluating both chunk polynomials at \(2k - 1\) points, taking one smaller phase product per point, and recursing. Each layer of the recursion can have its own table and \(k\). The left panel of the figure shows a policy that does this: the table \(T^{(1)}\) (\(k = 3\)) is used while the width is at least \(\underline{w}_1 = 40\), the table \(T^{(2)}\) (\(k = 2\)) from there down to \(\underline{w}_2 = 14\), and a naive phase product below that.
A table is a straight-line program on \(k\) registers, each
holding a combination of the chunks. It may add, negate, and shift, composing into the ability to move
between interpolation points. When one or more of the interpolation points are reached, it may take a
phase product of whatever a register then holds.Every box in the figure is clickable and opens the Lean source; the register contents in the middle panel are computed by running the table, not typed in. The program type is Prog k, a list of valid_ops k: addScaled, negate, shiftL, shiftR, phaseProduct. A point is Point, where frac 0 is the point at infinity. The table drawn is one admissible \(k = 3\) table, chosen because it reads well; the reference table in refOps uses the points genInterpolationPoints 3 = \(0, -1, 1, -2, 2\) on a single register.
A table is admissible when the points are distinct, each phase product sees exactly the chunk polynomial
evaluated at the next point, and the program ends where it started, so the registers are returned
clean. These are four decidable conditions, checked by the kernel; nothing else about the table is trusted.
One recursion level is shown in the middle panel. For the table \(T^{(1)}\), with \(k = 3\), the operations
\(\Pi^{(0)}\) put \(x_0\), \(x_0 + x_1 + x_2\) and \(x_2\) into the three registers,
the values at \(0\), \(1\) and \(\infty\); three phase products are taken;
\(\Pi^{(1)}\) moves the registers to the values at \(-2\) and \(-1\) for two more
phase product operations; and
\(\Pi^{(2)}\) reverses the additions, negations, and shifts. This leaves the measurement-basis back
where it started, with the multiplication correctly applied in phase space. Succinctly, applying
five smaller phase products on chunks roughly a third of the total circuit width replaces one
phase product at the full width.The phases of the five products are not the product's own: the angle for each point is an interpolation coefficient, so that the five phases multiply out to \(\exp(i \varphi x z)\). That is the algebra in PhaseProduct/Math, and lowerSignedPhaseProduct_correct is the theorem that the lowered circuit is correct for any admissible table.
Recursion is emphasized on the right panel, where each of the five terms
(for \(k = 3\)) can also be given as a recursive phase product, lowering with a table until the
width stops shrinking. When stopped, the circuit will use a naive phase product. The width at the next
level is about a \(k\)-th of the current one, plus a constant number of padding bits, and the
register arithmetic at a node is linear in its width. Summing over the tree gives
\(O(n^{\log_k(2k-1)})\) gates: \(n^{1.585}\) at \(k = 2\),
\(n^{1.465}\) at \(k = 3\), approaching \(n\) as \(k\) grows.The recursion is Policy.signedPlanOf, which recurses only while nextSignedWidth is smaller than the input width, so it terminates by construction. The three facts the count needs are prog_balanced_nextSignedWidth (next width at most \(\lceil w/k \rceil + c\)), phaseProgramOverhead_linear (overhead at most \(A w + B\)) and balanced_phaseProduct_recurrence_solution; the exponent is phaseProductExponent k and the bound is PhaseProductGateCountBound.
Applying \(O(n)\) of these controlled modular multiplications composes one modular
exponentiation, giving rise to the headline \(n^{2+\varepsilon}\) scaling.
Back to the PhaseProduct layer in the graph above.
Why PhaseProduct optimization is nontrivial
A policy \(P = ((\underline{w}_1, T^{(1)}), (\underline{w}_2, T^{(2)}), \ldots)\) is a short list of instructions where at each width, there will be a table to use (the left panel above). Finding the best policy is not easy because three things couple together. Inside a table, the program of additions, negations and shifts may visit the evaluation points in any order and keep partial sums, so each step's cost depends on what earlier steps left in the registers. Between a table and the levels below it, a table is judged by the whole recursion it triggers. In this way, saving an addition can widen the registers and make every product below more expensive. Across widths, the same table is reused wherever its arity appears, and the remainder of the width modulo \(k\) enters the child width, so one more input bit can help one arity and not another. With arities up to 3 the optimum uses \(k = 2\) at \(n = 60\), \(k = 3\) at \(n = 62\) and \(k = 2\) again at \(n = 64\). Even the trade-off at arity 2 is sensitive, wherein at \(n = 40\), stopping costs 92,800 T gates and one split with a charge-4 table costs 92,750, a saving of 50, while a second split loses.
What we can prove. A table matters only through three integers, its arithmetic charge and two width offsets, so the search over programs becomes a search over profiles. Given the cheapest table of each arity, choosing the recursion is an integer program with one unknown per distinct arity, solvable by Lenstra–Kannan in time polynomial in \(n\). So the whole problem has an exact algorithm running in \(2^{O(K^4 \log K)} \cdot \mathrm{poly}(n)\), where \(K\) is the largest arity and \(n\) is in unary.This bound is proved on paper; Lean does not check the running time or the shift bound, and Kannan's theorem is imported. All the difficulty is in finding the cheapest table of a given arity: we search exhaustively inside a proven but enormous bound on the shifts, \(2^{O(k^2 \log k)}\) (about \(2^{576}\) for arity 3). We know of no faster method and prove no lower bound; a faster method would have to exploit the arithmetic inside the tables.
What we have not proven: For the problem as posed, finding the best table cannot be NP-hard unless \(\mathrm{P} = \mathrm{NP}\): the best structural score grows only polynomially in \(k\), so the yes-instances form a sparse set, and Mahaney's theorem forbids a sparse NP-hard set. Both we check in Lean. For the full T-count problem the same barrier holds if the optimum is polynomially bounded, a hypothesis we supply. Once the evaluation points are part of the input, the problem is NP-hard already at arity 2, by reduction from SAT through Hamiltonian cycle, also checked in Lean. That applies to the structural score, not to the T count, and not to the points the challenge uses; it shows that point ordering alone carries combinatorial difficulty.
In our implementation, we built the exact algorithm in Fortran 90; every table it returned was replayed independently, and each distinct table was compiled in Lean against the benchmark's contract. With arity 2 the answer is immediate up to \(n = 2048\). With arity 3 the search took 2.6 s at \(n = 52\), 19 s at 60, 89 s at 62 and 511 s at 64, and at arity 4 the run at \(n = 56\) stopped with no answer after 24 hours with a footprint of 130–140 GiB.One machine (Apple M5 Pro, 24 GiB), whole-process wall time, interim snapshot. These are measurements, not a scaling law. In every run that finished the optimal policy was a single level of recursion. The cryptographic target is \(n = 2048\), where exact search at arity 3 or higher is out of reach, so the objective is explicit, every candidate can be checked, and the exact optimum is not known, founding the ForShor Challenge. Any search method is welcome, and a cheaper policy on the leaderboard is a real result.
What this site is
The proof is about 180 Lean files and 3,500 declarations in eight folders, which is more
than anyone wants to read top to bottom. This page is a guide to it. The layer graph above is
the outline: each block is a top-level folder, each arrow is an import between folders, and
opening a block shows what that folder is for, what it rests on and what it feeds, and its key
statements quoted from the source with a link to the file and line on GitHub. It is meant to
answer questions like “where is Shor_correct stated, and what does it rest on?”
without cloning the repository.
The mathematics and the design are in our paper,
Formally verified harness for Shor's order
finding algorithm in \(O(n^{2+\varepsilon})\) gate cost (Suresh, Courtney, Tao, and Cao, 2026).
The paper describes the estimation procedure and results, with the layer graph its outline in the
code.The arrows are the imports between top-level folders, read from the Lean sources by scripts/gen_docs_graph.py. The quoted statements are verbatim copies of the declarations at the file and line shown.
Where to start.
Shor_correct
and Shor_correct_approx_lowered
for correctness;
exists_shorGateCountBound
for the gate count; Policy.orderFinding_peak_formula for the peak number of live qubits (QubitCount); Framework if you want
to know what the statements mean before reading the proofs; and
Reference for the computable instance, the
one lake exe forshor_emit prints as JSON.
A companion page
PhaseTripleProduct is the three-register analogue of the PhaseProduct primitive above, \(\exp(i\pi\varphi\,xyz)\), with a verified recursive circuit, its gate and qubit counts, and a policy checker, and its own interactive map. It is not used by the order-finding circuit, and nothing on it changes the theorems on this page.
Checking it yourself
The project pins Lean v4.36.0-rc1 and a fixed Mathlib revision, so the prebuilt cache
applies. With elan installed:
lake exe cache get # prebuilt Mathlib oleans
lake build # the whole development
lake exe forshor_emit 2 2 15 0 # the reference circuit for (k, a, N, m), as JSON
The construction is generic for a policy: any table or policy that passes four decidable side conditions inherits the correctness theorem and the gate-count bound at its own exponent. The README's Submitting a table explains how such a table or policy is stated and checked.
Citing ForShor
A machine-readable CITATION.cff
is in the repository.
@misc{suresh2026forshor,
author = {Anirudh Suresh and Joshua M. Courtney and Runzhou Tao and Yudong Cao},
title = {Formally verified harness for Shor's order finding algorithm in $O(n^{2+\epsilon})$ gate cost},
year = {2026},
howpublished = {arXiv preprint},
note = {Apache-2.0 licensed Lean~4 development}
}
Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao · Apache License 2.0 · README · ARCHITECTURE.md · GitHub