clifford_t_circuit_t_count_nil
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
- 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_exampleSanity check: the circuit H_0, T_0, T_1 on two qubits has T-count 2.
- Used by 1
- clifford_t_circuit_t_count_appendThe T-count of the concatenation of two Clifford+T circuits is the sum of their T-counts.
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.
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.
uses
clifford_t_circuit_t_count,clifford_t_circuit_t_count_exampleclifford_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.
- The proof is structured as an automated fallback search using `first`. The tactic branches referencing `clifford_t_circuit_t_count_example` are unsuccessful or redundant; the goal is closed entirely because simplifying `clifford_t_circuit_t_count` on the empty list evaluates `List.countP` on `[]` to 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
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 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)