Quantum factoring with certainty and a fixed finite gate set

← All digests

Family 279 · Mathematical physics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-25

1. The question

Shor’s algorithm made integer factorization a landmark example of quantum speedup. Its standard guarantee is bounded error: a polynomial-time run succeeds with sufficiently high probability, and repetition reduces the chance of failure.

Can one instead demand the complete prime factorization with probability exactly one, while retaining polynomial worst-case resources and using one fixed finite collection of gates? Each qualification matters. Retrying until success may have unbounded worst-case duration. Approximating a rotation extremely accurately does not make it exact. Supplying information about an unknown order can change the input problem.

Family 279 reports a positive answer to this stricter question. The manuscript constructs a uniform circuit family that factors every integer using a finite set of bounded-arity gates, with polynomial gate and qubit counts. Its central device is to arrange an exactly known success probability and then amplify it to certainty.

2. Background and essential definitions

What the algorithm must output

The input is a binary integer $N\geq2$, with length approximately $\log_2N$. The output is its complete nondecreasing list of prime factors, including multiplicities. For example, factoring $72$ means producing $2,2,2,3,3$, not merely finding one divisor.

A polynomial-time uniform circuit family has a deterministic classical algorithm that generates the circuit for each input length in polynomial time. The circuit then works for every integer of that length. This rules out hiding a separate factorization in a circuit chosen for each individual input.

Worst-case polynomial resources mean fixed polynomial bounds on gates and qubits for every input and every computational history. Probability-one correctness refers to the distribution obtained from ideal exact gates and the final measurement.

Orders and factorization

If $a$ is coprime to $m$, its multiplicative order $r$ is the least positive integer with

$$a^r\equiv1\pmod m.$$

When $r$ is even and $a^{r/2}$ is a nontrivial square root of one modulo a composite $m$, greatest common divisors of $a^{r/2}-1$ or $a^{r/2}+1$ with $m$ yield nontrivial factors. This is the familiar arithmetic bridge from order information to factoring. A recursive procedure must also handle primes, prime powers and unsuccessful choices.

A dyadic rational is a number $A/2^T$ with integer numerator and power-of-two denominator. Such probabilities can be generated exactly with Hadamard gates: prepare a uniform $T$-bit string $u$, then reversibly test whether $u<A$. Exactly $A$ of the $2^T$ labels pass.

Exact amplitude amplification

Suppose a unitary preparation has a marked successful component of squared norm $\sin^2\theta$. Ordinary amplitude amplification uses reflections about the initial state and the successful subspace; one iteration changes the success probability to $\sin^2(3\theta)$.

If the initial probability is exactly $1/4$, then $\theta=\pi/6$, and one iteration reaches probability one. The challenge is therefore to create that exact probability with efficiently implementable gates and a success predicate that really certifies a complete factorization.

3. Development history and previous partial results

Shor established polynomial-time quantum factoring and discrete logarithms with bounded error. The order-based arithmetic reduction builds on Miller’s earlier work. A proposed factorization is efficiently checkable, but checking and retrying does not by itself produce a polynomial worst-case exact algorithm.

Exact quantum algorithms exist in several gate models. Mosca and Zalka developed exact Fourier transforms using computed rotations and exact discrete-logarithm procedures with known group orders. Their discussion also records an exact factoring algorithm in a generalized model allowing gate parameters obtained during computation. Imran’s exact order-finding procedure receives a suitable multiple of the unknown order. That extra information is not initially supplied by the ordinary factoring problem.

Approximate universality of a finite gate set does not bridge these distinctions. It allows approximation of a desired transformation, with a nonzero error, while the present target is exact success. Work of Nishimura and Ozawa formalizes the significance of finitely generated uniform circuit models.

More recent algorithms of Regev, with unconditional correctness results for modified constructions by Pilatte, address resource efficiency. Their success guarantees retain a nonzero failure probability. The present manuscript pursues certainty in a specified gate model and explicitly does not present its large polynomial parameters as a practical resource improvement.

The final amplification step is established machinery, originating in quantum search and amplitude amplification. Brassard and Høyer used exact probability engineering for Simon’s problem; Mosca and Zalka explicitly used probability $1/4$ followed by one ordinary amplification step. The claimed novelty here lies in constructing the required exact factoring success law without unknown-order advice or input-dependent rotation gates.

4. What the new manuscript claims

For every integer $N\geq2$, the manuscript claims a polynomial-time uniform quantum circuit that outputs its complete prime factorization with probability one. Both gate count and number of qubits are bounded by fixed polynomials in the bit length.

One fixed finite gate set suffices: NOT, CNOT, Toffoli, Hadamard, the phase gate $\operatorname{diag}(1,i)$, their inverses and their singly controlled versions. Each gate acts on only a bounded number of qubits. Additional controls are implemented through reversible Boolean computations, rather than supplied as gates of growing arity.

A central intermediate trial has a more specific guarantee. With $n$ at least the input bit length and a fixed constant cutoff, put $B=2^n$. For a unit $a$ modulo $2\leq m<B$, of unknown order $r$, the trial returns either no candidate or an integer $d$ satisfying

$$1\leq d<B, \qquad r\mid d.$$

Its probability of returning the true order is exactly

$$\Pr[d=r]=\varphi(r)\,2^{-\lceil\log_2r\rceil-10},$$

where $\varphi(r)$ counts residues coprime to $r$, with $\varphi(1)=1$. Neither $r$ nor its factorization is supplied to the trial.

The theorem receives only the integer to be factored. It does not assume a supplied multiple of an order, a factorization oracle or continuously adjustable exact rotations. Its final success flag is coherently amplified; intermediate selected events retain their actual probabilities rather than being treated as free postselection.

5. Why the advance matters

Importance: 4/5, provisional. Exact factoring in a fixed finite gate model would sharpen a central quantum algorithmic result and clarify the role of randomness, gate precision and worst-case complexity.

The gain is conceptual certainty under stricter computational rules. It is not a new classical factoring algorithm or a claim that practical quantum factoring suddenly needs fewer resources. The manuscript’s construction deliberately accepts large polynomial overheads to make every relevant probability exactly controllable.

The broader technique also separates two issues often conflated in randomized constructions: producing useful outcomes with some probability, and knowing that probability exactly enough to eliminate failure. Here auxiliary arithmetic data generated during a successful run allow deferred verification of earlier transitions. The importance score concerns these claims if correct, not independent verification.

6. The main idea

Engineer an exact order-trial probability

Standard order sampling uses phases associated with a Fourier transform. The manuscript instead employs a four-phase step register and a piecewise-linear interpolation of the complex exponential. Controlled modular shifts implement the selected branch with its actual, unnormalized amplitude.

The resulting residue probabilities admit dyadic majorants. Their sums are evaluated exactly using finitely many polynomial pieces and power sums. Two correction branches then adjust the mass at each reduced fraction so that the true order has precisely the displayed probability.

This does not require knowing the true order during execution. The formula describes the trial’s behavior; later arithmetic data make its relevant probabilities evaluable on completed runs.

Generate the data needed for deferred tests

The factoring process also recursively factors $p-1$ for prime factors $p>2$ that arise. This creates an auxiliary occurrence tree of polynomial size. Its shape resembles Pratt’s primality certificates, but its role is to determine orders and transition probabilities. Prime labels are checked by an exact deterministic primality procedure based on the Agrawal–Kayal–Saxena polynomial-congruence method.

Ordinary transitions are mixed with uniform guesses, and filters computed from completed data make every accepted transition retain the same exact mass. A key logical point is that the deferred tests mark exactly the same recorded runs as a hypothetical sequence using true data from the start. Passing those tests itself forces the run to generate the required data. Thus the analysis does not smuggle that information into the algorithm as advice.

Keep all branches, then amplify

Adaptive classical choices can be simulated reversibly. Instead of measuring and forgetting a history, the circuit copies the intended basis outcomes into history qubits and uses them as controls. Different histories remain orthogonal. A fixed polynomial clock and retained work registers allow the entire preparation and its inverse to be compiled uniformly.

A further dyadic correction makes the preparation’s complete-success probability exactly $1/4$. The established pair of sign reflections then gives probability one after a single amplification iteration. Boolean success predicates and reflections are implemented exactly using the stated finite gates.

Retaining unsuccessful branches is essential. Renormalizing a selected branch without paying its probability would amount to postselection and would describe a different computational model.

7. Scope, limitations, and open questions

The result is an ideal exact-circuit statement. Physical gate noise and approximate implementations are outside that mathematical guarantee. Replacing a specified gate by an approximation does not preserve literal probability-one success.

The theorem supplies polynomial upper bounds, not competitive practical resource estimates. It makes no claim of deterministic classical polynomial-time factoring, nor does it automatically extend to every order-finding or discrete-logarithm formulation without checking their inputs and gate requirements.

The auxiliary data and exact probability calculations are central to the construction. Whether similar techniques can produce simpler exact algorithms or improve resource exponents is a further question. The current claim is the combination of certainty, uniformity, a fixed finite gate set and polynomial worst-case bounds.

8. Sources and further reading

Shor’s algorithm and Mosca–Zalka’s exact-transform work are linked above. For the amplification framework, see Brassard, Høyer, Mosca and Tapp, Quantum amplitude amplification and estimation. The source below gives the prescribed-probability order trial, deferred tests and exact circuit construction, reported as stated.

Source manuscripts

• M1. OpenAI, Exact quantum factoring over a fixed finite gate set (September 25, 2026).

Sources consulted on 25 October 2026 at repository revision 1581d4c. Download the manuscript citations.