Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1: exact multiqubit Clifford+T synthesis with one clean ancilla

Open
QAlgorithms.Papers.Independent.Intakethird100.P85.exactSynthesis

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let UUU be a unitary operator on nnn qubits, where n≥0n\ge0n≥0, and put R=Z[1/2,i]R=\mathbb Z[1/\sqrt2,i]R=Z[1/2​,i]. Use exactly the elementary generators H,S,CNOT,T,ωH,S,\mathrm{CNOT},T,\omegaH,S,CNOT,T,ω, with ω=eiπ/4\omega=e^{i\pi/4}ω=eiπ/4 available as a scalar gate. A clean ancilla starts and ends in ∣0⟩|0\rangle∣0⟩ for every input vector. Then

U has an exact circuit with finitely many clean ancillas  ⟺  (∀x,y, Uxy∈R).U\text{ has an exact circuit with finitely many clean ancillas} \iff (\forall x,y,\ U_{xy}\in R).U has an exact circuit with finitely many clean ancillas⟺(∀x,y, Uxy​∈R).

Whenever the entry condition holds, an exact circuit using at most one clean ancilla exists. Equality includes absolute phase. The circuit is chosen for the operator and works for every input vector.

This characterizes the matrices admitting exact multiqubit Clifford+T synthesis.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P85

open scoped Classical BigOperators

open QAlgorithms

open QAlgorithms.Papers.Independent.Gap48.P10
  (InZomega InDomega Residue bits residue residueMultiply Reducible)

open QAlgorithms.Papers.Independent.Support21.P13
  (synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)

local notation "omega" => QAlgorithms.gateT true true

local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)

/-- Theorem 1, PDF pp.1,5: ring iff exact synthesis, with at most one clean ancilla. -/
theorem exactSynthesis (n : ℕ) (U : Matrix (Qubits n) (Qubits n) ℂ)
    (unitary : U ∈ Matrix.unitaryGroup (Qubits n) ℂ) :
    ((∃ a : ℕ, ∃ c : Circuit gateSet (n + a), ImplementsWithCleanAncillas c.unitary U) ↔
      EntriesInRing U) ∧
    (EntriesInRing U → ∃ a : ℕ, a ≤ 1 ∧ ∃ c : Circuit gateSet (n + a),
      ImplementsWithCleanAncillas c.unitary U) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P85

end
Source
Exact synthesis of multiqubit Clifford+T circuits, arXiv:1212.0506v3, PDF p. 1, Theorem 1: exact multiqubit Clifford+T synthesis with one clean ancilla
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every natural number nnn and every unitary complex matrix UUU indexed by Boolean strings of length nnn, the following two assertions hold together: there exist a natural number aaa and a circuit on n+an+an+a wires that sends ψ⊗∣0a⟩\psi\otimes|0^a\rangleψ⊗∣0a⟩ exactly to Uψ⊗∣0a⟩U\psi\otimes|0^a\rangleUψ⊗∣0a⟩ for every complex vector ψ\psiψ on nnn wires if and only if every entry of UUU belongs to the smallest complex subring containing 1/21/\sqrt21/2​ and iii; and, whenever every entry belongs to that subring, such a circuit exists with a≤1a\le1a≤1. In both assertions the permitted gates are Hadamard, S=diag⁡(1,i)S=\operatorname{diag}(1,i)S=diag(1,i), T=diag⁡(1,eiπ/4)T=\operatorname{diag}(1,e^{i\pi/4})T=diag(1,eiπ/4), controlled-NOT, and a zero-wire gate whose scalar entry is eiπ/4e^{i\pi/4}eiπ/4. A circuit is a finite list of these gates placed on injectively chosen ordered wires; each embedded gate fixes the other wires, and the circuit matrix is their product in reverse list order, with empty product III. The auxiliary wires occupy the final aaa positions, start at zero, and return exactly to zero for every input vector, including unnormalized vectors. The assertion includes n=0n=0n=0, when UUU is a unitary 1×11\times11×1 matrix, and it allows a=0a=0a=0.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

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