Unnumbered §V: normalization preserves the gate and minimizes T-cost
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.normalized_t_optimalAll 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 a normalized presentation. For every competing Clifford/T word representing the same projective gate,
If is an -approximation of a unitary target , with , the exactly equivalent presentation still satisfies . Thus normalization minimizes charged T-cost within an exact gate-equivalence class; optimization among distinct nearby gates is a separate problem.
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 ℂ
/-- Unnumbered §V, PDF p.6. Every normalized presentation has minimum
charged T-cost among all exact Clifford/T presentations of the same gate.
The epsilon clause preserves approximation and asserts no optimum over neighbors. -/
theorem normalized_t_optimal (o : NormalOutput) (hc : BsNormalized o.body) :
(∀ w : List CTLetter, SameGate (ctValue w) (bsNormalValue o) →
bsTCount o.body ≤ chargedT w) ∧
(∀ (U : Mat), U ∈ Matrix.unitaryGroup Bool ℂ → ∀ epsilon : ℝ, 0 < epsilon →
∀ w : List CTLetter, SameGate (ctValue w) (bsNormalValue o) →
gateDistance (ctValue w) U < epsilon → gateDistance (bsNormalValue o) U < 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 define , in order, by
For matrices write when for some complex with , and define , using conjugate transpose and the real square root, which is zero on negative inputs. Consider any output consisting of a Boolean , a finite body of syllables or , and an index . Assume is empty, or ends in and contains no consecutive 's. Let count its occurrences of , let be its list-order product with empty product , and put
Then both of the following hold: for every finite word with letters or indexed letters , if its product satisfies , then is at most the number of -letters in ; and, for every unitary complex matrix , every real , and every such word , if and , then . Words may be empty, and only letters explicitly of type contribute to their count.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.