∑math20

Mathematical physics · Result 279

Exact quantum factoring over a fixed finite gate set

1 paperLean

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.

Watch

▶Introduction: the problem and why it mattersin preparation
▶The presented solutionin preparation

Papers 1

First page of Exact quantum factoring over a fixed finite gate set

Exact quantum factoring over a fixed finite gate set

OpenAI · September 25, 2026

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.

Read PDF Download Source

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}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

The formalization constructs a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer \(N\ge2\) with probability exactly one. The circuits use one fixed finite set of bounded-arity gates, and both the gate count and number of qubits have polynomial worst-case bounds in the bit length of \(N\). The probability-one conclusion is exact, rather than an asymptotic or bounded-error guarantee.

Comparator links

ResultComparator statement
Exact quantum factoring over a fixed finite gate setExactQuantumFactoring.lean

Scope note on GitHub →