clifford_t_circuit_t_count_append
The T-count of the concatenation of two Clifford+T circuits is the sum of their T-counts.
Statement
theorem clifford_t_circuit_t_count_append {N : ℕ} (gs1 gs2 : List (CliffordTGate N)) :
clifford_t_circuit_t_count (gs1 ++ gs2) = clifford_t_circuit_t_count gs1 + clifford_t_circuit_t_count gs2- Source
- step towards ccz_layer_t_count_below_6m_plus_1_with_hadamards
- Verified
- 07 Nov 2026
- Axioms
propext- Built on 3
- clifford_t_circuit_t_countThe T-count of a Clifford+T circuit: the number of T gates in its gate list.
- CliffordTGateA gate of a Clifford+T circuit on N qubits: a Hadamard H on qubit i, a phase gate S on qubit i, a CNOT with control c and target t (c…
- clifford_t_circuit_t_count_nilThe empty Clifford+T circuit has T-count 0.
The proof, explained
The T-count of a Clifford+T circuit is defined as the count of T gates in the list of gates via `List.countP`. Unfolding the definition reveals that the theorem is an instance of the general fact that counting elements satisfying a predicate in a concatenated list equals the sum of the counts in each list (`List.countP_append`). The simplifier applies this list property automatically to close the goal.
The T-count of the concatenation gs1 ++ gs2 is the sum of the T-counts of gs1 and gs2. automation
The T-count of a circuit is defined as `List.countP` of the predicate that selects T-gates. Unfolding this definition with `simp only` reduces the goal to showing that counting elements satisfying a predicate distributes over list concatenation, which `simpa` closes automatically via the library lemma `List.countP_append`.
uses
clifford_t_circuit_t_count_nilclifford_t_circuit_t_count (gs1 ++ gs2) = clifford_t_circuit_t_count gs1 + clifford_t_circuit_t_count gs2 := by first | exact clifford_t_circuit_t_count_nil | (apply clifford_t_circuit_t_count_nil <;> assumption) | (apply clifford_t_circuit_t_count_nil <;> simp_all) | simpa using clifford_t_circuit_t_count_nil | (simp only [CliffordTGate, clifford_t_circuit_t_count] at *; first | exact clifford_t_circuit_t_count_nil | (apply clifford_t_circuit_t_count_nil <;> assumption) | (apply clifford_t_circuit_t_count_nil <;> simp_all) | simpa using clifford_t_circuit_t_count_nil)
clifford_t_circuit_t_count_nil- The T-count of the empty circuit (the empty list of gates) is 0.
- The proof script uses a brute-force `first | ...` tactic combinator to try several candidate tactics. The winning branch unfolds `clifford_t_circuit_t_count` and invokes `simpa using clifford_t_circuit_t_count_nil`, where `simpa` solves the goal using the standard library lemma `List.countP_append` without actually needing `clifford_t_circuit_t_count_nil`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The T-count of the concatenation of two Clifford+T circuits is the sum of their T-counts. -/theorem clifford_t_circuit_t_count_append {N : ℕ} (gs1 gs2 : List (CliffordTGate N)) : clifford_t_circuit_t_count (gs1 ++ gs2) = clifford_t_circuit_t_count gs1 + clifford_t_circuit_t_count gs2 := by first | exact clifford_t_circuit_t_count_nil | (apply clifford_t_circuit_t_count_nil <;> assumption) | (apply clifford_t_circuit_t_count_nil <;> simp_all) | simpa using clifford_t_circuit_t_count_nil | (simp only [CliffordTGate, clifford_t_circuit_t_count] at *; first | exact clifford_t_circuit_t_count_nil | (apply clifford_t_circuit_t_count_nil <;> assumption) | (apply clifford_t_circuit_t_count_nil <;> simp_all) | simpa using clifford_t_circuit_t_count_nil)