Theorem 1: exact multiqubit Clifford+T synthesis with one clean ancilla
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.exactSynthesisLet be a unitary operator on qubits, where , and put . Use exactly the elementary generators , with available as a scalar gate. A clean ancilla starts and ends in for every input vector. Then
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.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number and every unitary complex matrix indexed by Boolean strings of length , the following two assertions hold together: there exist a natural number and a circuit on wires that sends exactly to for every complex vector on wires if and only if every entry of belongs to the smallest complex subring containing and ; and, whenever every entry belongs to that subring, such a circuit exists with . In both assertions the permitted gates are Hadamard, , , controlled-NOT, and a zero-wire gate whose scalar entry is . 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 . The auxiliary wires occupy the final positions, start at zero, and return exactly to zero for every input vector, including unnormalized vectors. The assertion includes , when is a unitary matrix, and it allows .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.