Factoring with no gamble, proved at last?
An AI preprint claims exact quantum factoring over one fixed, finite gate set
Covers result 279 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.
3:16. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
Shor’s algorithm factors integers on a quantum computer in polynomial time, but each run is a gamble: for 21, one run finds the hidden period with probability about 31%. Repeating drives the chance of failure down, but never to zero. Can factoring be done exactly, with probability one, in guaranteed polynomial time? Brassard and Høyer posed this in 1997, and in 2003 Mosca and Zalka called it a challenge that remains. Mosca had sketched a way in 2002, but with gates whose rotation angles are computed during the run. What stayed open was one fixed, finite set of gates. That restriction bites: Hadamard and S alone make only 24 distinct rotations, and these gates offer only 8th roots of unity as phases, so Shor’s fine Fourier phases can be approximated but never made exact.
Result 279 is one OpenAI preprint, 24 pages, dated September 25, 2026. It claims a uniform family of quantum circuits, built only from NOT, CNOT, Toffoli, Hadamard and S gates and their controlled versions, that outputs the complete prime factorization of every integer from 2 up with probability exactly one, with gate and qubit counts polynomial in the input length, and no measurement until the end.
What it doesn’t claim
Practical speed, as the paper says plainly; noise or fault tolerance; or any classical algorithm. At the smallest size the paper allows, our rough count is about 2137 gates, against about 221 for textbook Shor. “Probability one” is for an ideal, noiseless circuit.
Where it stands
- Posted as a preprint
- OpenAI, 24 pages, dated September 25, 2026
- Peer reviewed
- Not yet
- Formalized in Lean
- The theorem, constructing the circuit (docs)
Last checked October 19, 2026. The preprint has not been revised. The theorem is formalized in Lean, about 54,000 lines that construct the circuit itself; our scan finds no unproved steps, but we did not rebuild it. OSVerify has not reviewed it, and we found no comment from specialists.
How the proof goes
- Throw luck away. One step of amplitude amplification turns a success probability of exactly 1/4 into exactly 1; with plain sign flips, 3/4 or 1/2 never get there. So every stage is made exactly predictable, and a final top-up sets the total at exactly 1/4.
- Exact odds, by bookkeeping. The Fourier transform is replaced by one that runs straight between 1, i, −1 and −i, so every probability is a power-of-two fraction. The order trial is deliberately diluted with coin flips so it succeeds with a small probability fixed by an exact formula (exactly 1 in 4,096 in our toy for 21). The run also factors p − 1 for each prime it finds, computes each step’s exact odds afterwards, and filters them all to the same rate.
The numbers in the video
- Ours: textbook Shor for 21 recovers the order with probability 0.308 per run.
- Ours: the paper’s four-point transform rebuilt gate by gate at Q = 64; one amplification step takes exactly 1/4 to exactly 1.
- Ours: a rough count of about 2137 gates at the smallest allowed size.
Read the source
- Exact Quantum Factoring over a Fixed Finite Gate Set (PDF), 24 pages.
- The Lean formalization notes.
- The collection’s catalog, where this is result 279.
The paper
OpenAI groups related papers into one result; this one has a single paper.
Transcript
Read the full script
0:00The question
Shor’s algorithm factors integers on a quantum computer in polynomial time, but each run is a gamble. Our computer simulates it for 21: one run finds the hidden period with probability about 31%. Repeating drives the chance of failure down, but never to zero. Can factoring be done exactly, with probability one, in guaranteed polynomial time? Brassard and Høyer posed this in 1997, and in 2003 Mosca and Zalka called it a challenge that remains. Mosca had sketched a way in 2002, but with gates whose rotation angles are computed during the run. The open question was one fixed, finite set of gates. That restriction bites. Hadamard and the phase gate S alone make only 24 distinct rotations, and these gates offer only 8th roots of unity as phases, so Shor’s fine Fourier phases can be approximated but never made exact.
0:59The claims
Result 279 is one OpenAI preprint, 24 pages, dated September 25, 2026. It claims a uniform family of quantum circuits, built only from NOT, CNOT, Toffoli, Hadamard and S gates and their controlled versions, that outputs the complete prime factorization of every integer from 2 up with probability exactly one, with gate and qubit counts polynomial in the input length, and no measurement until the end. Not claimed: practical speed, as the paper says plainly; noise or fault tolerance; or any classical algorithm. At the smallest size the paper allows, our rough count is about 2¹³⁷ gates, against about 2²¹ for textbook Shor.
1:48How the proof goes
The trick is to throw luck away. One step of amplitude amplification turns a success probability of exactly 1/4 into exactly one; our computer confirms it, while with plain sign flips, 3/4 or 1/2 never get there. So every stage is made exactly predictable, and a final top-up sets the total at exactly 1/4. The Fourier transform is replaced by one that runs straight between 1, i, −1 and −i, so every probability is a power-of-two fraction. The order trial is deliberately diluted with coin flips so it succeeds with a small probability fixed by an exact formula: in our toy for 21, exactly 1 in 4,096. The run also factors p − 1 for each prime it finds, computes each step’s exact odds afterwards, and filters them all to the same rate.
2:43Where it stands
The preprint is unrefereed and unchanged since release. The theorem is formalized in Lean, about 54,000 lines that construct the circuit itself; our scan finds no unproved steps, but we did not rebuild it. OSVerify has not reviewed it, and we found no comment from specialists. If it holds, an ideal quantum computer can factor with no gamble at all, using one fixed set of gates, though this construction’s cost is astronomical.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.