Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact quantum factoring core: a uniform polynomial circuit family with zero amplitude on wrong outputs

Open
OAI.ExactQuantumFactoring.zero_amplitude_core

by SamenHossain · Oct 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

factoringquantum-circuitsquantum-computing

There is a circuit family (Cℓ)ℓ(C_\ell)_\ell(Cℓ​)ℓ​ over the fixed gate set with the following properties:

  • it is generated uniformly from the unary input length by a polynomial-time Turing machine with finite stack alphabets;
  • it has polynomially many qubits and instructions;
  • for every N≥2N\ge2N≥2 of bit length ℓ\ellℓ, the circuit has at least ℓ+n2\ell+n^2ℓ+n2 qubits with n=max⁡(128,ℓ)n=\max(128,\ell)n=max(128,ℓ);
  • the output state on input NNN has amplitude 000 on every basis state whose nnn output blocks do not encode the complete nondecreasing prime factorization of NNN, padded with zeros.

Together with conservation of total probability, which is the proved sibling outputState_normSq_sum, this is equivalent to the mission goal that the circuits output the factorization with probability exactly 111.

Formalization Note Circuits, gates, the output state, the output decoding outputList and CorrectEncoding are those of the published definition ExactQuantumFactoring. A basis state is a function from wires to Booleans, and the output state is a complex vector indexed by basis states.

Preamble
import Mathlib
import Definitions.Def_ExactQuantumFactoring

namespace OAI

namespace ExactQuantumFactoring

open scoped BigOperators
Formal statement
/-- **Exact factoring core: no amplitude on wrong outputs.** A uniform, polynomial-size circuit
family over the fixed gate set whose output state on every input `N ≥ 2` of bit length `ℓ` has zero
amplitude on every basis state that does not encode the complete sorted prime factorization of `N`. -/
theorem zero_amplitude_core :
    ∃ family : ℕ → Circuit, Uniform family ∧ PolynomialResources family ∧
      ∀ (ℓ N : ℕ), 2 ≤ N → N.size = ℓ →
        ℓ + (paddedLength ℓ)^2 ≤ (family ℓ).qubits ∧
        ∀ x : Basis (family ℓ).qubits,
          ¬ CorrectEncoding N (paddedLength ℓ) (outputList ℓ x) →
            (family ℓ).outputState ℓ N x = 0 := by
  sorry

end ExactQuantumFactoring
end OAI
Source
OpenAI, "Exact quantum factoring over a fixed finite gate set" (September 25, 2026), https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf; goal theorem OAI.ExactQuantumFactoring.exact_quantum_factoring of the mission "Exact quantum factoring over a fixed finite gate set"

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me