Browse › Mathematical physics › 279 Exact quantum factoring over a fixed finite gate set
Exact quantum factoring over a fixed finite gate set
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We give a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer N ≥ 2 with probability one. A fixed finite set of bounded-arity gates suffices, and both the gate count and the number of qubits have polynomial worst-case bounds in the input length.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release / oai-math-revised, Lean scope notes for family 279 (lean/docs/279.md, 2026). The release's scope document describes the formalization as a uniform circuit family over a fixed finite gate set that outputs the complete prime factorization with probability exactly one, with polynomial-time uniformity and polynomial worst-case gate and qubit bounds.
- OpenAI, ExactQuantumFactoring.lean (comparator challenge statement) (github.com/openai/math, 2026). Lean statement
exact_quantum_factoring : MainTheoremwith 20 fixed gate names (NOT, CNOT, Toffoli, Hadamard, phase, with inverse and single-control flags), TM2-based polynomial-time uniformity, polynomial qubit and instruction bounds, and success probability exactly 1; the proof in this challenge file issorryby design. - OpenAI, OAI/Computability/QuantumFactoring/Main.lean (solution module) (github.com/openai/math, 2026). Proves
exact_quantum_factoringby assemblingPhysicalTree.finalCircuitwith its uniformity, resource and correctness lemmas from imported files.
Related prior literature mentioned by others
- M. Mosca and C. Zalka, Exact quantum Fourier transforms and discrete logarithm algorithms (arXiv:quant-ph/0301093, 2003; Int. J. Quantum Inf. 2004). Azmat's Binary Verse AI exposition names their exact algorithms with computed gate parameters as background to the paper's fixed-finite-gate claim; the work is also cited in the paper as [MZ].
Possibly relevant literature (found by the agent, not checked)
- M. Imran, Exact quantum splitting and the structure of finite algebras (arXiv:2608.30340, v1 31 Aug 2026, v2 16 Oct 2026). Exact quantum polynomial splitting over finite fields using one exact Grover iteration with an input-dependent rotation after a test with known success probability; compare with the paper's exact amplification from success probability exactly 1/4 using fixed gates only.
- M. Imran and G. Ivanyos, An exact quantum hidden subgroup algorithm and applications to solvable groups (arXiv:2202.04047, 2022). Exact HSP algorithm using the Mosca–Zalka exact QFT, an example of exact algorithms in parameterized-gate models, which the paper's introduction (Section 1.1) contrasts with its fixed finite gate set.
- J.-Y. Cai, Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise (arXiv:2306.10072, 2023; Sci. China Inf. Sci. 2024). Shows that Shor's factoring fails under vanishing random noise in controlled-rotation gates; relevant to the paper's statement that approximating arbitrary-angle rotations does not yield probability-one correctness.
- J.-Y. Cai and B. Young, Quantum Algorithms for Discrete Log Require Precise Rotations (arXiv:2412.17269, 2024; ACM Trans. Quantum Comput. 2025). Extends Cai's noise result to Shor's discrete-log algorithm; concerns the precision of the rotations that the paper's construction avoids.
Digests and expositions
- Azmat, Exact Quantum Factoring: How OpenAI’s Fixed-Gate Proof Turns 25% Into Certainty (Binary Verse AI, 2026-10-17). Paper-specific exposition of the four-phase order trial, dyadic probability corrections, auxiliary factorizations, deferred filters and final amplitude-amplification step, distinguishing the claimed circuit bounds from practical hardware estimates.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 279
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026,
author = {{OpenAI}},
title = {{Exact quantum factoring over a fixed finite gate set}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf}{OAI:Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/279.md. The Lean statements have not been checked by people against the paper's claims.
Family 279: Exact quantum factoring over a fixed finite gate set
Gives a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer with probability one. Both gate count and qubit count are polynomial in the input length, and one fixed finite gate set suffices.
This is the only paper in this family.