Corollary 1: reduction of optimal approximation to Clifford double cosets
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.approximation_double_cosetsAll circuits are single-qubit circuits without ancillas or measurements. Products act from right to left. Let , , , and . The two distinct syllable letters are and . A normalized word is empty, or ends in with no adjacent letters. A canonical word is normalized and its first four syllables, when present, are all . Write for the number of letters in ; Clifford gates have zero charged cost.
Let be any single-qubit projective gate, , and . Put . Then
The left-hand word is a Clifford/T presentation, so it expresses the minimum charged non-Clifford cost convention of §IV. This reduces bounded-cost approximation to the Clifford double coset; both inequalities are strict.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P82
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P82
open scoped BigOperators
local notation "Mat" => Matrix Bool Bool ℂ
/-- Corollary 1, PDF p.3, §IV metric and charged cost pp.3--4.
Both distance and integer cost cutoffs are strict. -/
theorem approximation_double_cosets (U : Mat) (hU : U ∈ Matrix.unitaryGroup Bool ℂ)
(epsilon : ℝ) (hepsilon : 0 < epsilon) (t : ℕ) :
(∃ w : List CTLetter, chargedT w < t ∧ gateDistance (ctValue w) U < epsilon) ↔
(∃ c : List Syllable, BsCanonical c ∧ bsTCount c < t ∧
∃ g1 g2 : Fin 24,
gateDistance (syllableValue c) (cliffordMatrix g1 * U * cliffordMatrix g2) < epsilon) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P82
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let , , and . For , define , in that order, by the list
For complex matrices define
where is conjugate transpose and the square root is the real square root, which is zero on negative inputs. For every unitary complex matrix , every real , and every natural number , the following are equivalent: there exists a finite word whose letters are or individually indexed matrices , containing strictly fewer than letters of type , whose product satisfies ; and there exists a finite syllable list with syllables and , which is empty or ends in and has no consecutive 's, whose first syllables are all , which contains strictly fewer than occurrences of , together with indices , such that
Here all word products are taken in list order and an empty product is . Letters contribute zero to the count on the first side. Empty words and empty syllable lists are permitted; when , both existential statements are false because a natural-number count cannot be strictly less than zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.