Lemma 1 (Appendix D): force a leading H without changing the body T-count
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.force_leading_hAll 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.
There are a fixed symbolic rewrite procedure and a universal such that every normalized word yields a normalized word and an actual with
The actual output retains the external , the initial , the body and the Clifford terminal. This forces the required leading without changing the sub-body T-count, including when the sub-body is empty.
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 ℂ
/-- Lemma 1 of Appendix D, PDF pp.8--9. The entire output still begins
with external H followed by SH.TH; only the sub-body is replaced. -/
theorem force_leading_h :
∃ p : Program, ∃ K : ℕ, 0 < K ∧
∀ c : List Syllable, BsNormalized c →
∃ d : List Syllable, ∃ g : Fin 24, ∃ cost : ℕ,
BsNormalized d ∧ bsTCount d = bsTCount c ∧
SameGate (syllableValue (.sh :: .th :: c))
(QAlgorithms.hadamard * syllableValue (.sh :: .th :: d) * cliffordMatrix g) ∧
BsExecutes p (syllableSymbols (.sh :: .th :: c))
(normalSymbols ⟨true, .sh :: .th :: d, g⟩) cost ∧
cost ≤ K * (bsTCount c + 1) := 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 let , be the two syllables. For a syllable list , let be its product in list order, with empty product , and let count its occurrences of . A list is normalized when it is empty, or ends in and has no consecutive 's. Define , in order, as
There exist a finite program and a natural number such that, for every normalized list , including the empty list, there exist a normalized list , an index , and a natural number such that , there exists with and
The program has four stacks over symbols and a control state that is a natural number or halt. Each instruction specifies a control state, the exact heads of all four stacks, an action on each stack—keep, remove the first symbol, or prepend a specified symbol—and a next state or halt. Removing from an empty stack leaves it empty. A step uses the first matching instruction in program order; if none matches it halts without changing the stacks, and a halted configuration stays unchanged. Initially the control state is , stack contains encoded by , , and the other stacks are empty. For some natural number , after steps the machine is halted and stack is
There is no final condition on the other stacks, and the cost is exactly
where is the number of instructions and is among the quantified possibilities.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.