Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5: normalized inverse and linear construction

Open
QAlgorithms.Papers.Independent.Intakenext100.P82.normalized_inverse_linear

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 procedure AAA and a universal K>0K>0K>0 such that every normalized word ccc yields an actual normalized word ddd and a choice s∈{0,1}s\in\{0,1\}s∈{0,1} with

[c]−1=H[d]H(S3)s,cost⁡A(c)≤K(∣c∣+1).[c]^{-1}=H[d]H(S^3)^s,\qquad \operatorname{cost}_A(c)\le K(|c|+1).[c]−1=H[d]H(S3)s,costA​(c)≤K(∣c∣+1).

Here ∣c∣|c|∣c∣ is syllable depth, within a fixed factor of the displayed elementary depth. The empty word is included via HIH=IH I H=IHIH=I projectively. The proposition supplies the two inverse presentations and their linear construction.

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 ℂ

/-- Proposition 5, PDF p.3. The last factor is S cubed, not G3.
No equality of T-counts is asserted; empty c is allowed. -/
theorem normalized_inverse_linear :
    ∃ p : Program, ∃ K : ℕ, 0 < K ∧
      ∀ c : List Syllable, BsNormalized c →
        ∃ d : List Syllable, ∃ hasS3 : Bool, ∃ cost : ℕ,
          BsNormalized d ∧
          SameGate (star (syllableValue c))
            (QAlgorithms.hadamard * syllableValue d * QAlgorithms.hadamard *
              (if hasS3 then QAlgorithms.phaseS ^ 3 else 1)) ∧
          BsExecutes p (syllableSymbols c)
            ([if hasS3 then 30 else 29] ++ syllableSymbols d) cost ∧
          cost ≤ K * (c.length + 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. 3, Proposition 5: normalized inverse and linear construction
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), and T=diag⁡(1,eiπ/4)T=\operatorname{diag}(1,e^{i\pi/4})T=diag(1,eiπ/4), with rows and columns ordered as false, true. A syllable is either a=THa=THa=TH or b=SHb=SHb=SH; for a syllable list ccc, let V(c)V(c)V(c) be its matrix product in list order, with V([])=IV([])=IV([])=I. Call a list normalized when it is empty, or ends in aaa and has no two consecutive bbb's. Write X∼YX\sim YX∼Y when there exists z∈Cz\in\mathbb Cz∈C with ∣z∣=1|z|=1∣z∣=1 and X=zYX=zYX=zY. There exist a finite program ppp and a natural number K>0K>0K>0 such that, for every normalized syllable list ccc, including the empty list, there exist a normalized syllable list ddd, a Boolean hhh, and a natural number cost\mathrm{cost}cost satisfying

V(c)∗∼H V(d) H{S3,h=true,I,h=false,cost≤K(∣c∣+1).V(c)^*\sim H\,V(d)\,H \begin{cases} S^3,&h=\mathrm{true},\\ I,&h=\mathrm{false}, \end{cases} \qquad \mathrm{cost}\le K(|c|+1).V(c)∗∼HV(d)H{S3,I,​h=true,h=false,​cost≤K(∣c∣+1).

Here ∗^*∗ denotes conjugate transpose. The program operates on four stacks whose symbols are the integers 0,…,310,\ldots,310,…,31, with a natural-number control state or a halted state. Each instruction specifies a control state, the exact four stack heads, an action on each stack—keep, remove its first symbol, or prepend a specified symbol—and a next control state or halt. Removing a symbol from an empty stack leaves it empty. Each step uses the first matching instruction in program order; if none matches, it halts without changing the stacks, and halted configurations remain unchanged. Initially the control state is 000, stack 000 contains ccc 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 contains the symbol 303030 if hhh is true, or 292929 otherwise, followed by the encoding of ddd; no final condition is imposed on the other stacks. The asserted cost is exactly

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

where ∣p∣|p|∣p∣ is the number of instructions; s=0s=0s=0 is included 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