Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Unnumbered §V: worst-case recursive T-count growth

Open
QAlgorithms.Papers.Independent.Intakenext100.P82.recursive_t_count_growth

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.

Supply a depth-nnn recursion tree using the five-factor composition VWV†W†UVWV^\dagger W^\dagger UVWV†W†U at every internal node, with all three child subtrees at the previous depth. Suppose every leaf is a canonical presentation of T-count at most t∈Nt\in\mathbb Nt∈N. Then the exact recursively composed gate has both a Clifford/T presentation and a canonical presentation satisfying

cost⁡T≤t 5n.\operatorname{cost}_T\le t\,5^n.costT​≤t5n.

This explicit bound implies the advertised worst-case O(t5n)O(t5^n)O(t5n) growth. Auxiliary recursive choices are supplied as data; this statement concerns T-cost growth and supplies no additional approximation-accuracy claim.

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 ℂ

/-- Unnumbered §V, PDF p.5, five-factor recurrence Eq.(1).
The explicit uniform upper bound implies the advertised O(t*5^n).
Inverses have available charged cost equal to that of their input, and
canonical reduction cannot increase the minimum exact charged cost. -/
theorem recursive_t_count_growth (t n : ℕ) (tree : RecursionTree n)
    (hbase : LeavesBounded t tree) :
    (∃ w : List CTLetter,
      SameGate (ctValue w) (recursionValue tree) ∧ chargedT w ≤ t * 5 ^ n) ∧
    (∃ c : CanonicalOutput,
      BsCanonical c.body ∧ SameGate (canonicalValue c) (recursionValue tree) ∧
        bsTCount c.body ≤ t * 5 ^ n) := 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. 5, Unnumbered §V: worst-case recursive T-count growth
Read-back

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

For all natural numbers t,nt,nt,n, including zero, and every tree of depth nnn whose depth-zero nodes carry triples (ℓ,b,r)(\ell,b,r)(ℓ,b,r) with ℓ,r∈{0,…,23}\ell,r\in\{0,\ldots,23\}ℓ,r∈{0,…,23} and bbb a finite word in the symbols th,sh\mathrm{th},\mathrm{sh}th,sh, suppose that every leaf word bbb is either empty or ends in th\mathrm{th}th, contains no adjacent pair sh,sh\mathrm{sh},\mathrm{sh}sh,sh, has all of its first min⁡(4,∣b∣)\min(4,|b|)min(4,∣b∣) symbols equal to th\mathrm{th}th, and contains at most ttt occurrences of th\mathrm{th}th. Here 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, and define the twenty-four matrices (C0,…,C23)(C_0,\ldots,C_{23})(C0​,…,C23​) by

(I,H,HS2H,S2,S,S3,HS2,S2H,SH,S3H,S2HS2H,SHS2H,S3HS2H,HS,HS3,S2HS2,SHS2,S3HS2,HSH,HS3H,HSHS2H,HS3HS2H,S3HS,SHS3).(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).(I,H,HS2H,S2,S,S3,HS2,S2H,SH,S3H,S2HS2H,SHS2H,S3HS2H,HS,HS3,S2HS2,SHS2,S3HS2,HSH,HS3H,HSHS2H,HS3HS2H,S3HS,SHS3).

For a syllable word bbb, let P(b)P(b)P(b) be the product, in its listed order, obtained by replacing th\mathrm{th}th with THTHTH and sh\mathrm{sh}sh with SHSHSH, with the empty product equal to III. Assign a leaf (ℓ,b,r)(\ell,b,r)(ℓ,b,r) the matrix CℓP(b)CrC_\ell P(b)C_rCℓ​P(b)Cr​; each node of positive depth has three ordered children v,w,uv,w,uv,w,u of the same depth and is assigned the matrix V(v)V(w)V(v)∗V(w)∗V(u)V(v)V(w)V(v)^*V(w)^*V(u)V(v)V(w)V(v)∗V(w)∗V(u), where ∗^*∗ denotes conjugate transpose. Writing VVV for the resulting matrix of the whole tree, both of the following exist: a finite word qqq whose letters are either TTT or a labelled choice CgC_gCg​ with 0≤g<240\le g<240≤g<24, such that its matrix product equals zVzVzV for some complex number zzz with ∣z∣=1|z|=1∣z∣=1, and the number of its explicit TTT letters is at most t 5nt\,5^nt5n; and a triple (ℓ′,b′,r′)(\ell',b',r')(ℓ′,b′,r′), with ℓ′,r′∈{0,…,23}\ell',r'\in\{0,\ldots,23\}ℓ′,r′∈{0,…,23}, such that b′b'b′ is either empty or ends in th\mathrm{th}th, contains no adjacent pair sh,sh\mathrm{sh},\mathrm{sh}sh,sh, has its first min⁡(4,∣b′∣)\min(4,|b'|)min(4,∣b′∣) symbols all equal to th\mathrm{th}th, and satisfies Cℓ′P(b′)Cr′=z′VC_{\ell'}P(b')C_{r'}=z'VCℓ′​P(b′)Cr′​=z′V for some complex number z′z'z′ with ∣z′∣=1|z'|=1∣z′∣=1, while the number of occurrences of th\mathrm{th}th in b′b'b′ is at most t 5nt\,5^nt5n. The first count charges only explicit TTT letters, and the second counts only th\mathrm{th}th syllables. At depth n=0n=0n=0 the bound is ttt; when t=0t=0t=0, the first output word has no explicit TTT letters and the second output has an empty syllable word.

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