Exact Quantum Factoring: How OpenAI’s Fixed-Gate Proof Turns 25% Into Certainty

A factoring algorithm that almost always works is not the same as one that cannot fail. That distinction drives exact quantum factoring, the subject of OpenAI’s September 25, 2026 preprint. Its claimed advance is a polynomial-time-uniform family of quantum circuits that returns the complete prime factorization of every integer at least two with probability exactly one, using only a fixed finite gate set and polynomial worst-case numbers of gates and qubits. This is a mathematical circuit-existence result, not a working RSA-breaking machine or a measured hardware speedup. The surprising part is how the proof replaces uncertain sampling with a precisely engineered success probability, then eliminates the remaining failure in one amplification step.

1. What Exact Quantum Factoring Actually Establishes

The headline statement appears as Theorem 1.1 in the 24-page original manuscript. For any binary input, the proposed circuit outputs its prime factors in nondecreasing order, including repeats. For instance, a complete factorization of 72 is 2, 2, 2, 3, 3, not merely the discovery that 8 divides 72. The guarantee concerns ideal circuits.

Uniformity means one efficient classical generator produces a circuit for each length, handling every input of that length. OpenAI listed the work in its October 6 mathematics release, alongside papers with different formalization and verification records. As with AI-produced mathematical claims, identifying exactly what has been proved is more useful than counting headlines.

2. Exact Quantum Factoring vs Shor’s Algorithm

Shor’s algorithm already established that a quantum computer can factor integers in polynomial time with bounded error. Its order-finding step uses interference to learn useful periodic information, followed by classical arithmetic that turns an even multiplicative order into a divisor. Success is highly probable after suitable repetitions, but not logically guaranteed after any specified finite batch.

Checking an answer is easy: multiply the proposed primes and verify their primality. But repeating until verification succeeds can take longer than every fixed polynomial limit on an unlucky run. More precise quantum rotations also do not automatically make the error literally zero.

Earlier exact quantum algorithms did exist, including work by Mosca and Zalka allowing computed gate parameters and order-finding methods with additional input information. The novelty claimed here is the combination of input-only complete factoring, exact output, worst-case polynomial bounds and one fixed finite gate library. The model distinction echoes OpenAI’s unitary synthesis problem, whose oracle assumptions concern a different computational setting.

3. Why the Fixed Finite Gate Set Changes the Proof

An “exact rotation by a chosen angle” can hide substantial computational work when the angle depends on unknown data or unlimited precision. The new paper avoids that ambiguity by specifying NOT, CNOT, Toffoli, Hadamard and the phase gate S with diagonal entries 1 and i, plus inverses and singly controlled versions.

A Toffoli gate performs reversible Boolean arithmetic. Hadamard creates equal-amplitude branches; S supplies an exact quarter-turn phase. Larger logical controls are synthesized by computing Boolean conditions into scratch qubits, applying a permitted controlled operation, and reversing the scratch computation. The paper tracks that workspace within its polynomial accounting. For background on why reversible arithmetic can dominate cost, see our Claude quantum circuits analysis.

Logical gates are not necessarily cheap, noise-free physical operations. Fault-tolerant compilation may add significant overhead. The explicit gate alphabet makes the theorem’s assumptions auditable.

4. How the Quantum Order Trial Finds Useful Periods

For an integer m and a number a coprime to m, the multiplicative order r is the smallest positive exponent for which a raised to r leaves remainder one modulo m. Consider $m=15,\quad a=2$: powers of two modulo 15 cycle through 2, 4, 8, 1, so $r=4$. Finding such orders is the quantum part of the familiar factoring reduction.

The paper interpolates the complex exponential using four quarter-turn phases. A Hadamard-and-S phase register responds to controlled modular shifts; testing its return creates an unnormalized selected transform. The test’s acceptance probability is retained, not silently reset to one.

Continued fractions recover candidate rational labels from measured bins. The construction filters candidates by modular exponentiation, retaining only a positive d for which raising a to d returns one modulo m. Therefore every nonempty answer is a multiple of the true order. Crucially, the circuit does not know r in advance. Its deliberately engineered probability of returning exactly r is the feature used in the next stage.

Here φ is Euler’s totient function, the count of positive integers no larger than r that are coprime to r. The probability is small but exact. Proposition 3.1 also guarantees polynomial circuit cost. Its proof implements this law without ideal arbitrary rotations.

5. Engineering Exact Probabilities Without Knowing the Order

The later amplification needs an exactly computable acceptance probability. Yet phase-bin weights are complicated, and enumerating every residue can cost exponentially many operations.

OpenAI’s solution decomposes those probabilities into piecewise polynomials. The four-phase interpolation makes sums over residue classes accessible by rational arithmetic. A dyadic majorant, an upper bound whose denominator is a power of two, can be evaluated using low-degree power sums instead of visiting every residue. Two auxiliary sampling modes correct the difference between the original bin weights and the chosen target.

Why powers of two? A polynomial number of Hadamards produces uniformly weighted bit strings. A reversible integer comparison can then accept exactly a chosen number of those strings, realizing a dyadic acceptance probability without approximation. Thus even correction branches can be implemented with the permitted gates. This is mathematics, not a hardware benchmark.

The order trial’s final rule only asks that modular exponentiation agree with a candidate. Knowledge of the true order enters the mathematical analysis of its success probability, not the input to the quantum trial. The answer is not assumed as input.

6. Turning Order Candidates Into Complete Factorization

Once the multiplicative order is known, standard number theory provides a split. For an appropriate even order r, compute the greatest common divisor of m with one less than a raised to r/2. In our small example, $m=15,\quad a=2$ give $r=4$; the relevant power is four, and $\gcd(4-1,15)=3$. The complementary factor is five.

Not every order is useful, and an arbitrary multiple of the true order can fail to split a number. The paper therefore distinguishes finding any compatible exponent from obtaining the true order. It selects lists of candidate bases whose local orders at different odd prime-power factors have unequal powers of two. That inequality guarantees a nontrivial square root of unity and hence a proper gcd split.

Primes, even composites and perfect powers are handled deterministically. The order mechanism tackles odd composites with multiple distinct prime divisors. Every split is checked, and recursion continues through repeated factors until the entire prime list is complete.

Unlike the Haldane gap proof, this proof must certify an algorithm’s output and stopping bound.

7. Auxiliary Factorizations Make Hidden Orders Verifiable

A particularly clever move is to collect extra arithmetic information while factoring. For each odd prime p appearing in the factorization, the algorithm also factors $p-1$ and repeats that operation for prime factors found below it. The resulting finite occurrence tree contains much more than the requested root answer.

For N = 21, the root has factors three and seven, so the tree includes factorizations of two and six. The seven branch also leads to the factors of six, including a new occurrence of two. Repeated values are recorded as distinct tree occurrences where needed. The manuscript proves that this auxiliary structure has polynomially many nodes and can be checked deterministically using a polynomial-time primality algorithm.

Why store such apparently unnecessary data? Factorizations of $p-1$ allow the factorization of Euler’s totient for composite moduli. With that information, a verifier can compute the multiplicative order of a recorded base retrospectively: start with the known totient and remove prime factors while modular powers still equal one. Earlier transition success probabilities, previously unknowable to the running procedure, then become exact arithmetic quantities.

The tree is generated, not supplied as advice. Every all-good execution must complete it, and invalid trees fail verification. Only then can later filters use the newly discovered information.

8. Deferred Filters Turn A Random Run Into A Known Probability

The proof gives every randomized transition a very high probability of producing a good output. It then mixes an ordinary transition with an exceptionally rare uniform guess, retaining selected outputs using exactly computed dyadic probabilities. A correction term makes the chance of passing each such filter equal to the same constant, even though individual transitions have different success rates.

Here n is the input bit length padded to at least 128, K is the number of trials inside a transition, L is the fixed number of transition slots, and W is the encoded width of a transition output. Unused slots are deterministic dummies. These are theoretical parameters, not optimized gate counts.

The subtle argument is that filtering after completion is equivalent to a hypothetical sequence of tests against the true auxiliary data. Passing all hypothetical tests forces completion; a completed accepted record must agree with that true data. The two tests select the same runs, without giving the algorithm advance knowledge.

Proposition 5.2 proves this dyadic probability exactly, not as an empirical estimate. The strict lower bound follows for the padded input lengths used in the construction. It is the known starting point needed for the final correction.

9. Why One Amplitude-Amplification Step Reaches 100 Percent

The last preparation mixes the verified factoring run with a rare uniform guess of the complete encoded answer. Exact rounding and another dyadic retention test tune the success probability to one quarter. Every flagged output is correct; unsuccessful branches may contain anything. Guessing only fills a small probability gap.

The first identity gives an amplitude angle of 30 degrees. Ordinary Grover-style amplification triples it to 90 degrees after one iteration, moving the entire state into the successful subspace. Algebraically, the paper uses a sign flip on success followed by a reflection around the prepared state. Both are compiled from the same finite gate set; no success-dependent arbitrary-angle rotation appears.

Ordinary amplitude amplification can overshoot when the initial probability is unknown. Here that probability is engineered exactly. The ideal measurement is certain, and the preparation, inverse and reflection retain polynomial worst-case resources.

10. What OpenAI’s Lean Comparator Does and Does Not Prove

OpenAI’s Lean formalization scope note describes the target theorem: a polynomial-time-uniform fixed-gate circuit family with probability-one complete factoring and polynomial gate and qubit bounds. The public comparator theorem formalizes that target through gate matrices, circuit semantics, output encoding, uniform generation and a final theorem declaration.

There is a critical distinction: the comparator source shown in the repository ends its theorem with sorry. In Lean, that is an admitted proof obligation, not evidence of a completed proof. This file documents what should be shown; it does not, by itself, provide a finished machine-checked derivation. The scope note’s wording cannot substitute for examining and successfully building a separate completed solution, if one is available.

The article therefore treats the mathematical argument as a published preprint claim and the comparator as a formal statement, not a separately reproduced Lean certification. The distinction also appears in our Fermat’s Last Theorem formalization explainer, where the difference between discovering mathematics and checking a formal proof matters just as much. Our percolation Lean case study shows why the final theorem statement and its checked implementation both matter. Reviewers should also audit the dyadic sums, completion lemma and exact reflections.

11. RSA-2048, Hardware Reality and the Research Outlook

Does exact quantum factoring mean RSA-2048 can now be broken? No. The theorem assumes ideal qubits and exact gates and proves that some polynomial bound exists. Its deliberately large exponents, including the fixed slot count, are not an optimized cost model for a 2,048-bit modulus. No RSA-2048 execution, physical qubit count, fault-tolerant schedule or experimentally validated runtime is supplied. Even an exact logical circuit must overcome errors, connectivity limits and error-correction overhead on real machines.

For designers, exactness, gate implementability, worst-case resources and reversible memory must be accounted for together. Related questions arise in quantum computing and AI systems, even though this paper itself does not benchmark AI-assisted quantum hardware.

Other recent OpenAI papers address different barriers, including the 2D area law, the Laughlin spectral gap and integer multiplication below n log n. None should be mistaken for a shortcut from abstract complexity to usable hardware. Their resource models and theorem assumptions remain distinct.

The strongest reading of exact quantum factoring is therefore a proposed theoretical closure of the failure-probability gap under unusually explicit circuit rules, not a new attack deployment. The next valuable work is independent proof scrutiny, reproducible formal verification and tighter resource estimates. Follow Binary Verse AI for research-first explainers that keep those three tasks distinct.