Exact quantum factoring
A polynomial-time uniform family of quantum circuits over one fixed finite gate set (NOT, CNOT, Toffoli, the Hadamard gate and the phase gate S, with their inverses and singly controlled versions) outputs the complete prime factorization of every integer N ≥ 2 with probability one. A transform with a piecewise-linear phase replaces the Fourier transform of order finding; exact power sums and classical corrections make the probability of the true order explicit; a factoring process produces, with the factorization, verifiable factorizations of p − 1 from which the probabilities of all its steps are computed after the run; filters computed afterwards make the success probability exactly one quarter, and one step of amplitude amplification gives certainty. The course is an exposition of OpenAI's construction (2026), with a deterministic primality test of Agrawal–Kayal–Saxena type.
Six lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.
- Exact circuits and dyadic probabilities
- A transform with a piecewise-linear phase
- An order trial with prescribed probability
- A deterministic primality test
- Factoring with verifiable auxiliary data
- Certain output from deferred filters
Theorems and assumptions · Reader and editable sources · Course record
Prerequisites
- Finite-dimensional complex inner product spaces: unitary maps, orthogonal projections and tensor products.
- Lagrange's theorem, units modulo m, the Chinese remainder theorem, polynomials over fields and finite fields (core courses Abstract Algebra I and II).