Exact quantum factoring: prescribed probabilities and deferred verification

Source and verification

This article explains family 279 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Exact computation and the gate model

Quantum factoring with bounded error and quantum factoring with certainty are different tasks. Checking an answer detects a failed trial, but retrying until success does not give a polynomial worst-case running time. Likewise, replacing a rotation by a highly accurate approximation does not make its error exactly zero. Family 279 constructs a factoring algorithm with both certainty and a polynomial worst-case bound over one fixed finite gate set. (OpenAI, 2026)

The prerequisites are linear algebra, quantum circuits, elementary modular arithmetic, and bit complexity. A quantum circuit acts unitarily on qubits and obtains classical outputs by measurement. A uniform circuit family has a deterministic classical algorithm that produces the circuit for each input length in polynomial time. The input here is a binary integer $N\ge 2$; the output is its complete sorted prime factorization, including multiplicities.

Manuscript's exact factoring theorem

A polynomial-time uniform family of polynomial-size quantum circuits outputs the complete prime factorization of every $N\ge 2$ with probability exactly one. Both gate count and qubit count have polynomial worst-case bounds. The gates are NOT, CNOT, Toffoli, Hadamard, $S=\mathrm{diag}(1,i)$, their inverses, and their singly controlled versions. (OpenAI, 2026)

This is a fixed finite set of bounded-arity gates. A control on a long Boolean condition is implemented by computing that condition reversibly, controlling one gate, and uncomputing. The large polynomial parameters in the construction are not presented as practical resource improvements.

Set $n=\max \{128,\lfloor {\log }_{2}N\rfloor +1\}$ and $B=2^n$. The cutoff is a constant, so polynomial complexity in $n$ is still polynomial in the input length. Logarithms in bit bounds are base two.

The proof has three layers. An order trial has an exactly prescribed success probability. A factoring process produces auxiliary data that allow its earlier transition probabilities to be computed retrospectively. Finally, exact probability corrections create a preparation with success probability $1/4$, for which one amplification step succeeds with certainty.

🏷️ Dyadic probabilities and retained histories

A dyadic rational is $A/2^T$. When $T$ and the bit length of $A$ are polynomially bounded, it can be sampled exactly: apply Hadamards to $T$ fresh bits to create a uniform integer $u$, then compute the flag $[u<A]$. Keep the random register and work registers.

Throughout the construction, “retain with probability $q$” means appending such a flag and requiring it for eventual success. Unsuccessful branches remain in the quantum state. There is no postselection that discards and renormalizes them.

Classically controlled measurements can also be implemented coherently. Copy each intended basis measurement outcome to an immutable history register, and use it for subsequent controls. Different histories remain orthogonal. Crucially, labels are copied only after the interference that the original procedure intended to perform. Reversible simulation of the polynomially clocked controller gives a polynomial-size unitary circuit, and reversing all gates inverts it, including its retained history.

This convention justifies conditional probability calculations. Given a recorded classical prefix, the next trial uses fresh zero registers and leaves previous quantum work untouched. Its distribution is therefore the specified one even when that old work is entangled with other retained registers.

🏷️ An order trial with a specified mass

For an integer $a$ coprime to $m$, its multiplicative order $r$ is the least positive integer satisfying $a^r\equiv 1(\mathrm{mod}m)$. Let $\phi (d)$ count residues coprime to $d$, with $\phi (1)=1$.

The manuscript constructs a trial that needs neither $r$ nor a factorization as input. It returns either no candidate or an integer $d<B$ that is a positive multiple of $r$, and

$$\begin{array}{c}\mathrm{Pr}(d=r)=\phi (r)\lambda (r),\\ \lambda (d)=2^{-\lceil {\log }_{2}d\rceil -10}.\end{array}$$

The exact mass is more important here than optimizing its size. It will later be computable from verified auxiliary data.

Put $Q=B^{16}=2^{16n}$. Replace the exponential Fourier phase by its piecewise linear interpolation $g$ through the quarter-integers:

$$\begin{array}{rl}g((q+t)/4)& =(1-t)(-i{)}^q\\ & +t(-i{)}^{q+1},\\ q\in \mathbb{Z},& 0\le t\le 1.\end{array}$$

This function is periodic and satisfies $g(z+1/2)=-g(z)$. A phase register in the state

$$|\chi ⟩=Q^{-1/2}\sum _{y=0}^{Q-1}{i}^{\lfloor 4y/Q\rfloor }|y⟩$$

requires only Hadamards and the phases $S,S^2$. If $T_D$ shifts the register forward by $D$ modulo $Q$, counting positions that cross quarter-bin boundaries gives $⟨\chi |T_D|\chi ⟩=g(D/Q)$. In particular, a forward quarter shift has overlap $-i$.

A sequence of Hadamards and controlled modular shifts, followed by testing whether the phase register returns to $|\chi ⟩$, has the unnormalized selected-branch matrix

$$A_{k,x}=Q^{-1/2}g(kx/Q).$$

The bitwise construction accounts for the highest product bits through the Hadamard signs and the lower bits through shifts. It uses only polynomially many reversible additions on $16n$ bits. The test’s actual probability remains part of the experiment; $A$ is not asserted to be a unitary Fourier transform.

Apply this circuit to the usual modular-power state $Q^{-1/2}{\sum }_x|x⟩|a^x\mathrm{mod}m⟩$, with arithmetic scratch uncomputed. For a reduced fraction $j/d$, $0\le j<d<B$, define the nearest bin $k(d,j)=\lfloor jQ/d+1/2\rfloor$. Continued fractions recover its unique label in polynomial time. The large value of $Q$ separates distinct fractions whose denominators are below $B$.

For this bin, abbreviate $k=k(d,j)$ and define the arithmetic quantity

$$\begin{array}{c}P(d,j,t)=\\ {\left|\frac{1}{Q}\sum _{\begin{array}{c}0\le x<Q\\ x\equiv t(\mathrm{mod}d)\end{array}}g(kx/Q)\right|}^2.\end{array}$$

When $d=r$, the probability of that bin together with phase-register success is ${\sum }_{t}P(r,j,t)$. This follows because the modular-power register has identical labels exactly on residue classes modulo $r$, and distinct classes are orthogonal. For $d\ne r$, the definition of $P$ is still useful arithmetic, but no such probability interpretation is assumed.

🏷️ Exact sums and two small corrections

Computing one $P(d,j,t)$ is easy; summing over all $d$ residues could be exponentially expensive in the input length. The manuscript constructs a dyadic upper approximation $U(d,j,u)$ whose total is nevertheless exactly computable in polynomial time:

$$\begin{array}{c}0\le U(d,j,jt\mathrm{mod}d)-P(d,j,t)\\ \le 128/Q,\\ S(d,j)=\frac{1}{2}\sum _{u=0}^{d-1}U(d,j,u),\\ \frac{1}{128d}\le S(d,j)\le 2.\end{array}$$

Here is the mechanism. Write $\eta =k(d,j)-jQ/d$, so $|\eta |\le 1/2$. Along a residue progression, $g(kx/Q)=g(u/d+\eta x/Q)$, with $u=jt\mathrm{mod}d$. Its argument crosses only a bounded number of quarter-bin breakpoints; sums of affine functions therefore compute $P$ exactly.

For the total, approximate the progression sum by $I(u)=d^{-1}{\int }_0^{1}g(u/d+\eta v)dv$. A rectangle-rule estimate gives $|P-|I{|}^2|\le 32/Q$. The primitive of $g$ is piecewise quadratic, so $|I(u){|}^2$ is piecewise polynomial of degree at most four, with a bounded number of pieces. Round each coefficient upward to a sufficiently fine dyadic grid and add $64/Q$. Since $u\ge 0$, upward coefficient rounding increases the value even for negative coefficients. Integer power sums through degree four now compute $S$ without enumerating residues.

Round the desired multiplier downward:

$$\begin{array}{c}c(d,j)=2^{-10n}\lfloor \frac{2^{10n}\lambda (d)}{S(d,j)}\rfloor ,\\ \rho (d,j)=\lambda (d)-c(d,j)S(d,j).\end{array}$$

The bounds give $0\le c\le 1/8$ and $0\le \rho \le 2^{1-10n}$. Three modes then supply the exact mass. With probability $1/2$, run the quantum experiment and retain its valid bin with probability $c$. With probability $1/4$, guess uniform $n$-bit labels $d,j,t$ and retain with probability $2B^3(U-P)c$. With probability $1/4$, guess $d,j$ and retain with probability $4B^2\rho$. Every mode checks the reduced-label conditions and $a^d\equiv 1(\mathrm{mod}m)$ before accepting; the second also checks $t<d$.

All sampled probabilities are valid dyadics. At the true order and a fixed reduced numerator, the first two masses sum to $cS$, because multiplication by $j$ permutes residues modulo $d$. The last adds $\rho$, giving exactly $\lambda (d)$. There are $\phi (r)$ reduced numerators. The modular-power check ensures that every returned candidate, even from an incorrect label, is a multiple of $r$.

🏷️ Auxiliary factorizations and guaranteed progress

The factoring process produces a rooted occurrence tree $\mathcal{D}(N)$. Each node records its label’s prime factorization; for every distinct odd prime $p$ in that factorization, it also contains a child recording $\mathcal{D}(p-1)$. Equal labels under different parents remain separate occurrences. For example, $\mathcal{D}(21)$ has children $\mathcal{D}(2)$ and $\mathcal{D}(6)$, and the latter has its own $\mathcal{D}(2)$ child.

Once this tree is known, one can factor $\phi (m)$ for any subfactor $m$ encountered at a node. Starting from that exponent and removing prime factors whenever modular powering permits computes the exact order of each recorded unit. Thus the tree determines probabilities of earlier transitions. It is generated during the run, not supplied as advice.

The controller first handles primes, even composites, and perfect powers by exact classical procedures. For the remaining odd composite $m$, it generates a list of candidate units and runs order trials for usable entries. If a unit has different powers of two dividing its orders on different prime-power components, its true even order $r$ gives a nontrivial split through $\gcd (a^{r/2}-1,m)$.

For a uniform unit, at most half have matching powers of two across all components. The exact favorable residue count is computable from the factorization data using the counts at each power-of-two level. A canonical favorable residue is $1$ on one prime-power component and $-1$ on the others.

Each randomized transition repeats its basic trial $K=n^5$ times. An order transition returns the smallest nonempty candidate, which is the true order exactly when one trial returns it, since all candidates are positive multiples. The elementary bound $\phi (r)/r\ge 1/(n+1)$ gives a basic success probability at least $1/(2048(n+1))$. Both list and order transitions consequently have good-output probability $s\ge 1-2^{-2n}$. Their exact probabilities and canonical good outputs can be computed from the completed tree.

Every sequence of good outputs completes the tree. Polynomial bounds hold even on bad sequences: only checked gcd splits are accepted, prime leaves are verified, and malformed records abort. At each depth the sum of logarithms of node labels is at most ${\log }_{2}N$; every two descents halve a label. There are $O(n^2)$ occurrences and fewer than $L=n^{10}$ transition slots. Pad completed runs with dummy slots and use a fixed output width $W=n(K+1)$.

The manuscript supplies a deterministic polynomial-time primality test for verifying all prime labels. Its appendix is an explicit polynomial-congruence variant; no factoring oracle is used. The exposition here uses that interface rather than developing the appendix’s finite-field argument.

🏷️ Deferred tests with a known total probability

The key probability correction is elementary. Suppose an ordinary transition has good mass $s$ and a specified good output $y_0$ among $W$-bit strings. Mix that transition with a rare uniform guess of its output, using guess probability $\delta =2^{-t}$. Put $A=(1-\delta )s$ and choose a dyadic target $0<z\le A$. Define

$$\begin{array}{c}E=W+t+2,\\ C=2^{-E}\lfloor 2^{E}z/A\rfloor ,\\ R=z-CA.\end{array}$$

Retain an ordinary good output with probability $C$. Retain a guessed output only when it equals $y_0$, then with probability $R{2}^W/\delta$. Since $0\le R<2^{-E}$, the latter is at most $1/4$. The two masses are $AC$ and $R$, totaling exactly $z$. Division appears only inside an integer floor; the probabilities actually sampled remain dyadic.

Use $\delta =2^{-2n}$ and $z=1-2^{-n}$ at every slot. The high ordinary success bound ensures $A\ge z$. The implementation initially records outputs without knowing their goodness. It attempts to finish and verify $\mathcal{D}(N)$, then computes the predicates, probabilities, canonical outputs, and retention thresholds for every earlier slot. Success requires all these deferred tests to pass.

Why is its probability exactly $z^L$? For analysis, fix the true tree and imagine applying the same tests immediately, on the same recorded outputs and the same fresh random coins. These hypothetical tests only mark an event; they do not change the controller. Given a passing prefix, all previous outputs are good, so the all-good progress property guarantees the next slot. Its conditional passing mass is exactly $z$, independently of old quantum work.

Finally the two events agree on each recorded run. Analytical success forces completion of the true tree, so the deferred tests agree. Implemented success has verified the complete tree, which is uniquely determined, so its tests are the true-data tests. The argument does not condition on eventual completion. It yields the initially known dyadic

$$p_{\ast }=(1-2^{-n}{)}^{n^{10}}>1/2.$$

Dummy slots are included even when the original input is prime or $N=2$. Without this padding, different completion times would have different retained masses.

🏷️ One-quarter preparation and exact amplification

Encode the sorted root factor list uniquely in $J=n^2$ bits by padding with zeros. Exact primality, ordering, and product checks recognize its unique valid encoding.

With probability $1/2$, run the preparation of success $p_{\ast }$ and retain its success with probability

$$c_{\ast }=2^{-(J+2)}\lfloor \frac{2^{J+2}}{2p_{\ast }}\rfloor .$$

Its contribution is $p_{\ast }{c}_{\ast }/2$. With probability $1/2$, guess a uniform $J$-bit string, require the unique correct list, and retain with probability $2^{J+1}e$, where $e=1/4-p_{\ast }{c}_{\ast }/2$. Downward rounding makes this a valid dyadic probability. The guessed branch contributes exactly $e$, so the total is exactly $1/4$.

Let $V_N$ be the coherent preparation, $\psi =V_N|0⟩$, and $g_{\ast }=\Pi \psi$, where $\Pi$ projects onto its success flag. Then $\Vert g_{\ast }{\Vert }^2=1/4$. A success sign flip followed by reflection about $\psi$ gives

$$(2|\psi ⟩⟨\psi |-I)(\psi -2g_{\ast })=2g_{\ast }.$$

Indeed, $⟨\psi ,\psi -2g_{\ast }⟩=1/2$. The result has norm one and lies entirely in the correct-output subspace. The reflection is implemented as $V_N(2|0⟩⟨0|-I)V_N^{-1}$, including all work and history registers while holding the input fixed. Both reflections use exact Boolean-controlled signs. This is where the prescribed quarter-success probability becomes certainty.

The selected source review read the main file, all six principal sections, and the primality appendix. It checks the probability bookkeeping and proof interfaces described here; it is not an independently implemented quantum circuit or a full formal equivalence audit.

Quantum circuit localization provides a contrasting use of explicit circuit models, where depth and gate structure constrain computation. Entangled-game repetition explains why dependence and conditioning must be controlled explicitly; here retained histories and fresh registers justify the successive exact probability calculations.

🏷️ Key steps and proof outlines

The dyadic envelope needs a noncancellation estimate

The interpolation trick must do more than approximate a Fourier phase. If its averaged amplitude could nearly cancel, the required probability correction could become too large. For

$$I(u)=\frac{1}{d}{\int }_0^{1}g(u/d+\eta v)dv,|\eta |\le \frac{1}{2},$$

compare $g$ with the exponential it interpolates. The exact exponential average has modulus

$$\frac{1}{d}\left|\frac{\sin (\pi \eta )}{\pi \eta }\right|\ge \frac{2}{\pi d}.$$

The value at $\eta =0$ is understood by continuity. Linear interpolation over intervals of length $1/4$ has uniform error at most ${\pi }^2/32$, by the second-derivative interpolation remainder. Hence

$$|I(u)|\ge \frac{1}{d}\left(\frac{2}{\pi }-\frac{{\pi }^2}{32}\right)>\frac{1}{8d}.$$

This lower bound survives squaring and summing over $d$ residues, supplying $S(d,j)\ge 1/(128d)$. It is precisely what bounds the thinning coefficient $c$.

There is also a useful bit-complexity point in the primitive formula for $I$. Although it divides by $\eta$, a nonzero value is

$$\eta =\frac{kd-jQ}{d},|\eta |\ge \frac{1}{d}.$$

Thus no arbitrarily tiny unspecified real parameter enters the exact arithmetic. The piece boundaries and coefficients have polynomial bit length. This explains how a calculation written with integrals produces an exact finite dyadic computation. (OpenAI, 2026, p.d yadic majorant lemma)

A decreasing arithmetic budget proves the worst-case clock

A successful probability calculation would not suffice if an unlucky branch could create an exponentially large auxiliary tree. The tree estimate uses the additive budget ${\log }_{2}M$ at a node labeled $M$. Its children satisfy

$$\sum _{\begin{array}{c}p\mid M\\ p>2\end{array}}{\log }_2(p-1)\le \sum _{p\mid M}{\log }_{2}p\le {\log }_{2}M.$$

Therefore the total logarithmic budget at every depth is at most ${\log }_{2}N<n$. Since every node has label at least two, there are at most $n$ occurrences at each depth.

The depth bound needs a second observation. A descent from a prime $M$ may only replace it by $M-1$, which is not a halving. But that child is even. Any subsequent odd prime divisor $p$ of this even child is at most half its label, so the next descendant $p-1$ is smaller still. A descent from a composite label already has the corresponding factor-size reduction. Thus every two descents halve the label, giving fewer than $2n+2$ levels and $O(n^2)$ occurrences.

Checked gcd splits obey the same product budget even on erroneous candidate outputs. Malformed records are rejected at explicit size caps. This is why the eventual coherent circuit can be given a polynomial worst-case clock before its exact success probability is amplified. The three records remain distinct: transition outputs control the next step, the arithmetic tree verifies probabilities retrospectively, and retained quantum history makes the entire preparation invertible. (OpenAI, 2026)

🏷️ Manuscripts and verification scope

• Exact quantum factoring over a fixed finite gate set — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects a polynomial-time uniform circuit family with probability-one complete factorization over one fixed finite set of bounded-arity gates, and polynomial worst-case bounds on gates and qubits. The statement is exact rather than an asymptotic or bounded-error guarantee. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Exact quantum factoring over a fixed finite gate set.