AFTD Auto-Formalizing Theoretical Domains

clifford_t_circuit_t_count_nil

theoremverified

The empty Clifford+T circuit has T-count 0.

Statement

theorem clifford_t_circuit_t_count_nil {N : ℕ} :
    clifford_t_circuit_t_count ([] : List (CliffordTGate N)) = 0
Source
step towards ccz_layer_t_count_below_6m_plus_1_with_hadamards
Verified
07 Nov 2026
Axioms
propext
Built on 3
Used by 1

The proof, explained

The empty Clifford+T circuit has no gates, so its T-count is 0 by definition. The formal proof unfolds the definition of `clifford_t_circuit_t_count` via `simp`, reducing the goal to evaluating `List.countP` on an empty list, which simplifies immediately to 0.

  1. The empty circuit has T-count 0. automation

    The proof attempts several tactic strategies via `first`. Unfolding the definition of `clifford_t_circuit_t_count` rewrites the expression into counting the number of T gates in the empty list `[]` using `List.countP`. Simplification then reduces `List.countP p []` to `0`, closing the goal `0 = 0`. The lemma `clifford_t_circuit_t_count_example` supplied to `simpa` is unused by the simplifier.

    line 3

    uses clifford_t_circuit_t_count, clifford_t_circuit_t_count_example

        clifford_t_circuit_t_count ([] : List (CliffordTGate N)) = 0 := by first | exact clifford_t_circuit_t_count_example | (apply clifford_t_circuit_t_count_example <;> assumption) | (apply clifford_t_circuit_t_count_example <;> simp_all) | simpa using clifford_t_circuit_t_count_example | (simp only [CliffordTGate, clifford_t_circuit_t_count] at *; first | exact clifford_t_circuit_t_count_example | (apply clifford_t_circuit_t_count_example <;> assumption) | (apply clifford_t_circuit_t_count_example <;> simp_all) | simpa using clifford_t_circuit_t_count_example)
clifford_t_circuit_t_count
The T-count of a Clifford+T circuit is defined as the number of T gates in its list of gates.
clifford_t_circuit_t_count_example
A specific example stating that the circuit [H, T, T] on 2 qubits has T-count 2.

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 empty Clifford+T circuit has T-count 0. -/theorem clifford_t_circuit_t_count_nil {N : ℕ} :    clifford_t_circuit_t_count ([] : List (CliffordTGate N)) = 0 := by first | exact clifford_t_circuit_t_count_example | (apply clifford_t_circuit_t_count_example <;> assumption) | (apply clifford_t_circuit_t_count_example <;> simp_all) | simpa using clifford_t_circuit_t_count_example | (simp only [CliffordTGate, clifford_t_circuit_t_count] at *; first | exact clifford_t_circuit_t_count_example | (apply clifford_t_circuit_t_count_example <;> assumption) | (apply clifford_t_circuit_t_count_example <;> simp_all) | simpa using clifford_t_circuit_t_count_example)
See it in the graphDiscuss this resultChallenge it