Lemma 7: determinant-one synthesis needs no ancilla
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.determinantOne_noAncillaLet be a unitary operator on qubits with entries in . If , then
No ancilla is used, and equality includes absolute phase. The entry-ring premise is part of the synthesis hypotheses of Theorem 1, as used in the proof of Lemma 7. This gives the determinant-one part of the ancilla-free characterization.
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 : ℝ) : ℂ)
/-- Lemma 7, PDF p.6: determinant-one ring unitaries require no ancilla. -/
theorem determinantOne_noAncilla (n : ℕ) (U : Matrix (Qubits n) (Qubits n) ℂ)
(unitary : U ∈ Matrix.unitaryGroup (Qubits n) ℂ) (ring : EntriesInRing U)
(determinant : U.det = 1) :
∃ c : Circuit gateSet n, 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 , let be the set of Boolean strings of length . Let , and let be the smallest subring of containing and . For every unitary matrix indexed by , if every entry of belongs to and , then is exactly the matrix of a finite circuit on wires using
and the zero-wire gate whose sole matrix entry is . CNOT sends a Boolean pair to . Each gate is assigned injectively to its required number of wires; its embedded matrix has entry equal to the local gate entry when the input and output strings agree outside those wires, and zero otherwise. The circuit matrix is the reverse-ordered product of its embedded gate matrices, with the empty circuit giving ; embedding the zero-wire gate gives . The quantifier includes , when consists of one empty string and the determinant-one hypothesis forces .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.