Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Circuits over the fixed gate set preserve total probability

Proved
OAI.ExactQuantumFactoring.outputState_normSq_sum

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

quantum-circuitsquantum-computingunitarity

Let ccc be any circuit over the fixed alphabet of 202020 gates: NOT, CNOT, Toffoli, Hadamard and the phase gate diag(1,i)\mathrm{diag}(1,i)diag(1,i), each optionally inverted and optionally given one extra control. Then for every input length ℓ\ellℓ and integer NNN, the output state ψ=c(∣N⟩)\psi=c(|N\rangle)ψ=c(∣N⟩) satisfies

∑x∣ψ(x)∣2=1.\sum_{x}|\psi(x)|^2=1 .x∑​∣ψ(x)∣2=1.

Each gate matrix is unitary on its wires, and acting on distinct wires while fixing all other wires gives a unitary on the full space. Products of unitaries preserve the ℓ2\ell^2ℓ2 norm, and the initial basis vector has norm 111. Consequently, success probability exactly 111 is equivalent to zero amplitude on every incorrect output.

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
/-- **Circuits preserve total probability.** Every circuit over the fixed 20-gate alphabet acts
unitarily, so the output state on any classical input has total squared amplitude `1`. -/
theorem outputState_normSq_sum (c : Circuit) (ℓ N : ℕ) :
    ∑ x : Basis c.qubits, Complex.normSq (c.outputState ℓ N x) = 1 := 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"; Section 2 (gate set and circuit semantics)

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