AFTD Auto-Formalizing Theoretical Domains

clifford_t_circuit_t_count_append

theoremverified

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

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.

  1. 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`.

    line 3

    uses clifford_t_circuit_t_count_nil

        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)
clifford_t_circuit_t_count_nil
The T-count of the empty circuit (the empty list of gates) is 0.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it