Unnumbered §V: worst-case recursive T-count growth
OpenQAlgorithms.Papers.Independent.Intakenext100.P82.recursive_t_count_growthAll 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.
Supply a depth- recursion tree using the five-factor composition 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 . Then the exact recursively composed gate has both a Clifford/T presentation and a canonical presentation satisfying
This explicit bound implies the advertised worst-case growth. Auxiliary recursive choices are supplied as data; this statement concerns T-cost growth and supplies no additional approximation-accuracy claim.
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.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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For all natural numbers , including zero, and every tree of depth whose depth-zero nodes carry triples with and a finite word in the symbols , suppose that every leaf word is either empty or ends in , contains no adjacent pair , has all of its first symbols equal to , and contains at most occurrences of . Here let , , and , with rows and columns ordered as false, true, and define the twenty-four matrices by
For a syllable word , let be the product, in its listed order, obtained by replacing with and with , with the empty product equal to . Assign a leaf the matrix ; each node of positive depth has three ordered children of the same depth and is assigned the matrix , where denotes conjugate transpose. Writing for the resulting matrix of the whole tree, both of the following exist: a finite word whose letters are either or a labelled choice with , such that its matrix product equals for some complex number with , and the number of its explicit letters is at most ; and a triple , with , such that is either empty or ends in , contains no adjacent pair , has its first symbols all equal to , and satisfies for some complex number with , while the number of occurrences of in is at most . The first count charges only explicit letters, and the second counts only syllables. At depth the bound is ; when , the first output word has no explicit letters and the second output has an empty syllable word.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.