Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 (Appendix D): force a leading H without changing the body T-count

Open
QAlgorithms.Papers.Independent.Intakenext100.P82.force_leading_h

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

All circuits are single-qubit circuits without ancillas or measurements. Products act from right to left. Let H=i 2−1/2(111−1)H=i\,2^{-1/2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}H=i2−1/2(11​1−1​), T=diag⁡(e−iπ/8,eiπ/8)T=\operatorname{diag}(e^{-i\pi/8},e^{i\pi/8})T=diag(e−iπ/8,eiπ/8), S=T2S=T^2S=T2, and C=⟨H,S⟩⊂PSU⁡(2)C=\langle H,S\rangle\subset\operatorname{PSU}(2)C=⟨H,S⟩⊂PSU(2). The two distinct syllable letters are a=THa=THa=TH and b=SHb=SHb=SH. A normalized word is empty, or ends in aaa with no adjacent bbb letters. A canonical word is normalized and its first four syllables, when present, are all aaa. Write τ(c)\tau(c)τ(c) for the number of aaa letters in ccc; Clifford gates have zero charged cost.

There are a fixed symbolic rewrite procedure AAA and a universal K>0K>0K>0 such that every normalized word ccc yields a normalized word ddd and an actual g∈Cg\in Cg∈C with

[SH TH c]=H[SH TH d]g,τ(d)=τ(c),cost⁡A(c)≤K(τ(c)+1).[SH\,TH\,c]=H[SH\,TH\,d]g,\qquad \tau(d)=\tau(c),\qquad \operatorname{cost}_A(c)\le K(\tau(c)+1).[SHTHc]=H[SHTHd]g,τ(d)=τ(c),costA​(c)≤K(τ(c)+1).

The actual output retains the external HHH, the initial SH THSH\,THSHTH, the body and the Clifford terminal. This forces the required leading HHH without changing the sub-body T-count, including when the sub-body is empty.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P82
Formal statement
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
Source
A Depth-Optimal Canonical Form for Single-qubit Quantum Circuits, arXiv:1206.3223v1, PDF p. 8, Lemma 1 (Appendix D): force a leading H without changing the body T-count
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

Let H=12(111−1)H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}H=2​1​(11​1−1​), S=diag⁡(1,i)S=\operatorname{diag}(1,i)S=diag(1,i), T=diag⁡(1,eiπ/4)T=\operatorname{diag}(1,e^{i\pi/4})T=diag(1,eiπ/4), and let a=THa=THa=TH, b=SHb=SHb=SH be the two syllables. For a syllable list ccc, let V(c)V(c)V(c) be its product in list order, with empty product III, and let Na(c)N_a(c)Na​(c) count its occurrences of aaa. A list is normalized when it is empty, or ends in aaa and has no consecutive bbb's. Define C0,…,C23C_0,\ldots,C_{23}C0​,…,C23​, in order, as

(I,H,HS2H,S2,S,S3,HS2,S2H,SH,S3H,S2HS2H,SHS2H,S3HS2H,HS,HS3,S2HS2,SHS2,S3HS2,HSH,HS3H,HSHS2H,HS3HS2H,S3HS,SHS3).\bigl( I,H,HS^2H,S^2,S,S^3,HS^2,S^2H,SH,S^3H, S^2HS^2H,SHS^2H,S^3HS^2H,HS,HS^3,S^2HS^2, SHS^2,S^3HS^2,HSH,HS^3H,HSHS^2H,HS^3HS^2H,S^3HS,SHS^3 \bigr).(I,H,HS2H,S2,S,S3,HS2,S2H,SH,S3H,S2HS2H,SHS2H,S3HS2H,HS,HS3,S2HS2,SHS2,S3HS2,HSH,HS3H,HSHS2H,HS3HS2H,S3HS,SHS3).

There exist a finite program ppp and a natural number K>0K>0K>0 such that, for every normalized list ccc, including the empty list, there exist a normalized list ddd, an index g∈{0,…,23}g\in\{0,\ldots,23\}g∈{0,…,23}, and a natural number cost\mathrm{cost}cost such that Na(d)=Na(c)N_a(d)=N_a(c)Na​(d)=Na​(c), there exists z∈Cz\in\mathbb Cz∈C with ∣z∣=1|z|=1∣z∣=1 and

V([b,a]+ ⁣ ⁣+c)=z H V([b,a]+ ⁣ ⁣+d) Cg,cost≤K(Na(c)+1).V([b,a]\mathbin{+\!\!+}c) =z\,H\,V([b,a]\mathbin{+\!\!+}d)\,C_g, \qquad \mathrm{cost}\le K(N_a(c)+1).V([b,a]++c)=zHV([b,a]++d)Cg​,cost≤K(Na​(c)+1).

The program has four stacks over symbols 0,…,310,\ldots,310,…,31 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 000, stack 000 contains [b,a]+ ⁣ ⁣+c[b,a]\mathbin{+\!\!+}c[b,a]++c encoded by a↦3a\mapsto3a↦3, b↦4b\mapsto4b↦4, and the other stacks are empty. For some natural number sss, after sss steps the machine is halted and stack 000 is

[30,4,3]+ ⁣ ⁣+encode⁡(d)+ ⁣ ⁣+[5+g].[30,4,3]\mathbin{+\!\!+}\operatorname{encode}(d)\mathbin{+\!\!+}[5+g].[30,4,3]++encode(d)++[5+g].

There is no final condition on the other stacks, and the cost is exactly

cost=(2+∣c∣)+(4+∣d∣)+1+20(∣p∣+1)s,\mathrm{cost}=(2+|c|)+(4+|d|)+1+20(|p|+1)s,cost=(2+∣c∣)+(4+∣d∣)+1+20(∣p∣+1)s,

where ∣p∣|p|∣p∣ is the number of instructions and s=0s=0s=0 is among the quantified possibilities.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me