Exact quantum factoring
From OpenAI Aftermath
Exact quantum factoring asks whether integers can be factored by a quantum algorithm that never fails: one that outputs the factorization with probability exactly one and within a polynomial worst-case bound on its size. A manuscript dated 25 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claims such an algorithm over one fixed finite gate set. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- Shor's quantum algorithms factor integers and compute discrete logarithms in polynomial time with bounded error. Checking a proposed factorization makes repetition reliable, but a procedure that retries until success need not have a polynomial worst-case running time, and approximating arbitrary-angle rotations ever more precisely does not by itself give probability-one correctness over a fixed finite gate set.
- Mosca and Zalka constructed exact quantum Fourier transforms using computed rotations and obtained exact discrete-logarithm algorithms for known group orders; their paper also reports Mosca's exact factoring algorithm in a generalized model that permits gate parameters obtained during the computation. Imran's exact order-finding algorithm takes a supplied multiple of the unknown order as additional input. Nishimura and Ozawa studied exact computation by finitely generated uniform circuit families.
- Recent factoring algorithms of Regev and of Pilatte address resource costs; their success guarantees keep a nonzero failure probability.
The original result
- Claim. Theorem 1.1 of Exact quantum factoring over a fixed finite gate set states that there is a polynomial-time uniform family of polynomial-size quantum circuits that outputs the complete prime factorization of every input integer N ≥ 2 with probability one. The numbers of gates and qubits are bounded by a fixed polynomial in the bit length of N, and one fixed finite gate set suffices: NOT, CNOT, Toffoli, Hadamard, the phase gate diag(1, i), their inverses and their singly controlled versions. The manuscript states that its large polynomial parameters are not intended as practical resource improvements and that it makes no claim of a classical polynomial-time factoring algorithm.
- Method, as described: an order trial whose probability of returning the true multiplicative order is a prescribed dyadic rational, built from a four-phase step state that interpolates the complex exponential piecewise linearly, exact power sums and two small correction branches; a factoring run that also generates, recursively, the prime factorizations of p − 1 for its prime factors p > 2, with prime labels checked by a deterministic primality test of Agrawal–Kayal–Saxena type proved in an appendix; filters computed from these completed data, which give every transition the same exact retained mass and make the success probability of the whole preparation exactly 1/4; and one step of amplitude amplification with two sign reflections, which turns probability 1/4 into 1.
- Source (openai/math repository, commit
7ef5c0c): Exact quantum factoring over a fixed finite gate set, dated 25 September 2026. - Formalization, as described by the repository. The scope note lean/docs/279.md states that the formalization constructs a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer N ≥ 2 with probability exactly one, over one fixed finite set of bounded-arity gates and with polynomial worst-case bounds on the numbers of gates and qubits, and that the probability-one conclusion is exact rather than an asymptotic or bounded-error guarantee. It links the Comparator statement
ExactQuantumFactoring.lean.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 29 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | Exact quantum factoring: prescribed probabilities and deferred verification, an article of the Latent Seminar blog at lowrank.github.io | Reading (exposition) | Explains the difference between bounded-error and exact factoring over a fixed gate set and the manuscript's route: dyadic probabilities and retained histories, an order trial with a specified mass, exact sums with two small corrections, auxiliary factorizations that guarantee progress, deferred tests with a known total probability, and a one-quarter preparation followed by exact amplification. It also outlines why a decreasing arithmetic budget gives the circuit a polynomial worst-case clock. | Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs, and that no Lean build, axiom audit or check of the formal statement against the manuscript was performed for these notes. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit 94c6630, 28 October 2026) |
Review (fidelity of the formal statement) | Rates the family's one challenge "full": the formal statement matches the summary, with exact success probability, polynomial numbers of gates and qubits and a fixed finite gate set. It records a sandboxed Comparator pass on 8 October 2026 with the standard axioms only, and lists as definitions to check that the circuit model and the quantum gate semantics are written by hand, while the polynomial-time notion is Mathlib's. | MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K, run 38051470892 | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the ExactQuantumFactoring solution, in 1,384 s. The project reports two-kernel certification of 398 of 416 challenges of the collection. |
Repository. |
| 2026-10-10 to 2026-10-14 | con-leche development journal (task #348) | Verification (second kernel) | In its run over all Comparator challenges of the collection at commit fd4aeeb, the journal's table of exceptions does not list this family's challenge, so it was accepted by con-leche and by Lean's official kernel. |
Development journal. |
| 2026-10-15 | Exact quantum factoring, a course on Open Mathematics Courses (kokunoyumeto/open-math-courses-public) | Reading (exposition) | Six lessons: exact circuits and dyadic probabilities, a transform with a piecewise-linear phase, an order trial with prescribed probability, a deterministic primality test, factoring with verifiable auxiliary data, and certain output from deferred filters. | The course states that it was written and self-checked by Claude Opus 5.5 (Anthropic) and that independent review is not complete. |
| 2026-10-17 | Azmat, Exact Quantum Factoring: How OpenAI’s Fixed-Gate Proof Turns 25% Into Certainty, Binary Verse AI | Reading (exposition) | Explains the four-phase order trial, the exact probability corrections, the auxiliary factorizations, the deferred filters and the final amplitude-amplification step, and stresses that the result concerns ideal circuits: it is not an RSA-2048 attack, a hardware resource estimate or a classical algorithm. It notes that the public Comparator challenge file ends its theorem with sorry, and treats that file as a formal statement rather than as a reproduced Lean certification. | Blog article. |
| 2026-10-18 | AI Proved What?, episode 279 Factoring with no gamble, proved at last?, remade version of 23 October 2026 | Reading (exposition) | Video explainer of the claim of exact factoring with gates from NOT, CNOT, Toffoli, Hadamard and S and their controlled versions. It recounts that Brassard and Høyer posed the question in 1997 and that Mosca and Zalka called it a remaining challenge in 2003. It states that practical speed, noise or fault tolerance and any classical algorithm are not claimed, and that by its own rough count the construction needs about 2137 gates at the smallest size the paper allows, against about 221 for textbook Shor. | Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as a preprint: OpenAI, 24 pages, dated September 25, 2026; under expert review: not yet; peer reviewed: not yet; checked in Lean: the theorem, constructing the circuit. The page also states that the site scanned the formalization, about 54,000 lines, without rebuilding it and found no unproved steps, that OSVerify has not reviewed it, and that it found no comment from specialists. |
Notes
- The background summarizes the manuscript's own account of earlier work.
- The Binary Verse AI article was found through the agent-collected notes of the community revision mathcommunity/oai-math-revised and was read at its source.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
