we-solve (beta)

Phys-56 · physics · mathematics · Physics

Exact quantum factoring over one fixed finite gate set

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
Is there a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer $N\geq 2$ with probability one, using a polynomial number of gates and qubits in log N and a single fixed finite gate set containing NOT, CNOT, Toffoli, Hadamard, diag(1,i), their inverses and singly controlled versions?

Short English statement

Is there a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer $N\geq 2$ with probability one, using a polynomial number of gates and qubits in log N and a single fixed finite gate set containing NOT, CNOT, Toffoli, Hadamard, diag(1,i), their inverses and singly controlled versions?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Phys-56-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Phys-56

Uniform polynomial-size circuits over one fixed finite bounded-arity gate set are claimed to output every integer factorization with probability one. The question retains these same parameters and conventions. Within these assumptions, this is a claimed affirmative answer to the stated question.

Exact quantum factoring over one fixed finite gate set

OpenAI's claim

OpenAI presents a proof in the selected manuscript. Uniform polynomial-size circuits over one fixed finite bounded-arity gate set are claimed to output every integer factorization with probability one.

Mathematical statement of the claimed result

Result 1.
There is a polynomial-time uniform quantum circuit family with $\mathbb P(\text{output is the prime factorization of }N)=1$ for every $N\ge2$. Resources grow polynomially in $\lceil\log_2N\rceil$, with separate bounds for gates and qubits. One fixed finite gate set suffices: \[ \mathrm{NOT},\ \mathrm{CNOT},\ \mathrm{Toffoli},\ H,\ \operatorname{diag}(1,i), \] together with inverses and singly controlled versions. This is exact success, rather than merely success approaching one.

Outline of the argument

Order trials are arranged to have prescribed success probabilities while preserving exact classical records. Circuit phase functions and fraction-label recovery replace arbitrary-angle approximations, and exact amplification plus recursive arithmetic gives a worst-case polynomial factorization family.

Formal verification

For family 279, the selected theorem gives exact probability-one factorization by a polynomially uniform circuit family over a fixed finite bounded-arity gate set. The listed Comparator files are ExactQuantumFactoring.lean. The inventory does not supply a named declaration for these Comparator entries. This site has not executed the Lean code. The scope descriptions do not certify the remaining manuscript arguments.

Status caveat

OpenAI attributes these manuscripts to work by an internal model. Its release cautions that arguments without formalization can contain mistakes. This catalogue has not independently checked the proofs; the labels report the mathematical claims attributed to OpenAI.

Sources

Go to contribution →