Exact (zero-error) polynomial-time quantum factoring over a fixed finite gate set
Shor's algorithm factors integers in quantum polynomial time with bounded error. Exact versions were known for the quantum Fourier transform and discrete logarithms of known order (Mosca-Zalka, using computed gate angles), for order finding when a multiple of the order is supplied (Imran), and for factoring only in a generalized model with gate parameters computed during the run (Mosca). Mosca and Zalka (2003) noted that it is not clear how to make Shor's factoring exact, 'a challenge that remains', and Imran (2022) called derandomizing it a difficult open question. Is there a polynomial-time uniform family of polynomial-size quantum circuits over a fixed finite gate set that outputs the prime factorization of every with probability exactly one?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Quantum algorithms; exact quantum computation
- Posed by
- Michele Mosca and Christof Zalka, Exact quantum Fourier transforms and discrete logarithm algorithms (2003), Section 5.2
- Year posed
- 2003
- Years open
- 23y
- Solved
- 2026-09-25
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 25 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: a polynomial-time uniform family of polynomial-size quantum circuits over NOT, CNOT, Toffoli, Hadamard, , their inverses and singly controlled versions outputs the complete prime factorization of every with probability one, with gate and qubit counts polynomial in the bit length. The construction makes the true-order mass of an order trial an exact dyadic rational, then uses one amplitude-amplification step, and handles auxiliary factorizations of recursively with a deterministic primality test. Not shown: practical resource bounds (the polynomials are large) or any classical algorithm.
What the AI did
The release README says every result was produced by an unreleased internal OpenAI model with a fixed procedure of roughly three hours of ChatGPT Pro thinking compute per result. This family is not among the README's exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region, whose write-up was human-edited). The manuscripts are authored 'OpenAI' and name no human author. The family is a single manuscript dated September 25, 2026.
Verification
No independent mathematician has checked this yet. Checked here: the introduction and Theorem 1.1 were read against Mosca-Zalka Section 5.2 and Imran's statement, both read here. Lean: lean/ComparatorChallenges/ExactQuantumFactoring.lean (solution module OAI.Computability.QuantumFactoring.Main, present at the pinned commit) is not in the formalization catalogue; it was found through lean/docs/279.md. Its statement exact_quantum_factoring was read: there is a circuit family over 20 fixed gates (NOT, CNOT, Toffoli, Hadamard, diag(1,i), inverses and singly controlled versions), generated by a polynomial-time TM2 machine from the input length, with polynomially many qubits and gates, whose Born probability of the correct padded nondecreasing prime factorization is exactly 1 for every N >= 2. That is the headline claim. Not rebuilt here. The paper claims no classical factoring speedup and no practical resource gains.