# Exact quantum factoring over a fixed finite gate set

> Proves polynomial-size quantum circuits over a fixed gate set factor every integer with probability exactly one.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-279/
Last updated: 2026-10-14

**Proves polynomial-size quantum circuits over a fixed gate set factor every integer with probability exactly one.**

**Trust:** Formal proof listed · **Papers:** 1 · **First paper:** September 25, 2026 · **Field:** Mathematical physics · **Entry:** 279

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

Shor's 1994 quantum algorithm factors whole numbers quickly, but it can fail and must sometimes be rerun. This paper builds quantum circuits that output the full prime factorization of every number with probability exactly one. They use one fixed, small set of gates and stay polynomial in size. Lean checks the main theorem; the circuits are far too large to be practical.

## At a glance

- **First step:** 1994 (Shor, polynomial-time quantum factoring with bounded error)
- **Significance:** Solid. It removes the failure probability from quantum factoring while keeping one fixed finite gate set and polynomial worst-case size.
- **Trust:** Formal proof listed
- **Field:** Mathematical physics (1 paper)

## The explanation

Factor N = 15 the quantum way. Pick a = 7 and look at its powers modulo 15. They run 7, 4, 13, 1, so the order of 7 is r = 4. The order is the least power that gives 1. Half the order gives 7² ≡ 4, a square root of 1 that is not ±1. Then gcd(4 − 1, 15) = 3 and gcd(4 + 1, 15) = 5. So 15 = 3 × 5.

Shor's algorithm finds orders quickly with a quantum computer. It factors in polynomial time with bounded error[1]. Bounded error means each run can fail with some small chance. Checking a proposed answer makes reruns reliable. But a procedure that retries until success need not have a polynomial worst-case running time[2]. Exact versions existed only in stronger models. Mosca's exact algorithm allowed gate settings computed during the run[3]. The obstacle with a fixed gate set is that rotations by arbitrary angles cannot be built exactly. Approximating them ever more finely does not give probability-one answers[4].

The paper proves a uniform family of polynomial-size quantum circuits[5]. Uniform means an ordinary computer can write out each circuit in polynomial time. The circuits output the complete prime factorization of every N ≥ 2 with probability one[5]. One fixed finite gate set suffices: NOT, CNOT, Toffoli, Hadamard, diag(1, i), their inverses and singly controlled versions[6]. The gate and qubit counts are bounded by a fixed polynomial in the bit length of N[7].

The key trick ends with amplitude amplification, a step that boosts the chance of a good outcome. Suppose a good outcome has probability exactly 1/4. Write this as sin²θ = 1/4, so θ = 30°. One amplification step turns the probability into sin²(3θ) = sin²(90°) = 1. So the whole difficulty is making the success probability exactly 1/4[8]. The paper does this with dyadic numbers, fractions whose denominators are powers of two. Its order trial hits the true order with an exact dyadic probability[9]. Along the way, each run also factors p − 1 for its primes p, recursively. A deterministic primality test, adapted from Agrawal, Kayal and Saxena, checks the prime labels[10].

The constructions are not meant to save resources. Their large polynomial sizes are not offered as practical improvements[11]. The paper makes no claim of a classical polynomial-time factoring algorithm[12].

How sure is this? Lean, a computer proof checker, has a formal proof of the main theorem. It covers the uniform polynomial-size circuit family, the fixed gate set and the exact probability one. No specialist review of the paper has been published.

**What it doesn't show.** This does not give a practical speed-up, a classical factoring method, or circuits small enough for any foreseeable quantum computer.

## Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

## Hype check

Solid. Lean covers the main theorem; the circuits are polynomial but very large and are not a practical improvement. No specialist review is published.

## Words used

- **Order:** For a modulo m, the least positive r with a^r ≡ 1 (mod m).
- **Bounded error:** Each run is right with probability at least some fixed amount, such as 2/3, but may fail.
- **Gate set:** The fixed list of basic operations a quantum circuit is allowed to use.
- **Uniform circuit family:** One circuit for each input length, all written out by a single efficient ordinary program.
- **Amplitude amplification:** A quantum step that raises the probability of a marked outcome, generalizing Grover's search.
- **Dyadic rational:** A fraction whose denominator is a power of two, such as 3/8.
- **Polynomial size:** The number of gates and qubits grows at most like a fixed power of the number of input digits.

## The original paper

- [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf) - September 25, 2026

- [Lean notes](https://github.com/openai/math/blob/main/lean/docs/279.md)

## Quoted lines from the paper (12)

[1] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> Shor's quantum algorithms established polynomial-time factorization and discrete logarithms with bounded error.

[2] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> Verifying a proposed factorization makes repetition reliable, but a procedure that retries until success need not have a polynomial worst-case running time.

[3] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> Their discussion also reports Mosca's exact factoring algorithm in a generalized model permitting gate parameters obtained during the computation; see also.

[4] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> Approximating an arbitrary-angle rotation to increasingly high precision likewise does not by itself yield probability-one correctness over a fixed finite gate set.

[5] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> There is a polynomial-time uniform family of polynomial-size quantum circuits that outputs the complete prime factorization of every input integer $N\ge2$ with probability one.

[6] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> One fixed finite gate set suffices: NOT, CNOT, Toffoli, Hadamard, $\operatorname{diag}(1,i)$, their inverses, and their singly controlled versions.

[7] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> The number of gates and qubits is bounded by a fixed polynomial in the bit length of $N$.

[8] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> Here the preceding construction makes that probability exactly $1/4$ using dyadic arithmetic and the fixed gates, so the established pair of sign reflections suffices.

[9] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> First, it constructs an order trial whose mass on the true order is a prescribed dyadic rational, meaning a rational with a power-of-two denominator.

[10] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> The appendix adapts the polynomial-congruence method of Agrawal, Kayal, and Saxena, with its constants and auxiliary-prime choice established directly.

[11] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> Its large polynomial parameters are not intended as practical resource improvements.

[12] From [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/main/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf):

> It makes no claim of a classical deterministic or randomized polynomial-time factoring algorithm.

## Other sources

- [openai/math, Lean scope note for family 279](https://github.com/openai/math/blob/main/lean/docs/279.md): “The probability-one conclusion is exact, rather than an asymptotic or bounded-error guarantee.”
- [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model”

## Related

- [Parity is not in QAC 0](https://closedform.nishachay.tech/e/openai-math-2026-274/) - Mathematical physics
- [Classical capacity of generalized amplitude damping](https://closedform.nishachay.tech/e/openai-math-2026-276/) - Mathematical physics
- [Polynomial-time unitary synthesis from a Boolean oracle](https://closedform.nishachay.tech/e/openai-math-2026-283/) - Mathematical physics
- [The optimal quartic separation between randomized and quantum queries](https://closedform.nishachay.tech/e/openai-math-2026-284/) - Mathematical physics
- [Bloch's law, its lattice correction, and the spherical magnetization law](https://closedform.nishachay.tech/e/openai-math-2026-271/) - Mathematical physics
- [Mathematical physics](https://closedform.nishachay.tech/science/mathematics/mathematical-physics/) - Field · 25 results
- [Quantum theory](https://closedform.nishachay.tech/topic/quantum/) - Topic · 9 results
- [Open since the 1990s](https://closedform.nishachay.tech/open-since/1990s/) - Era · 55 results
- [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results
- [Solid results](https://closedform.nishachay.tech/significance/solid/) - Significance · 50 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20279%5D%20)