clifford_circuit_score_one_nil
Sanity check: the empty Clifford circuit on 1 qubit has score 3.
Statement
theorem clifford_circuit_score_one_nil : clifford_circuit_score ([] : List (CliffordGate 1)) = 3- Source
- scout/2610-04621-exact-clifford-optimality-for-two-sided-locally-randomized.md:370
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- CliffordGateAn inductive type representing a quantum gate in a k-qubit Clifford circuit: Hadamard h on qubit i : Fin k, phase gate s on qubit i : Fin…
- clifford_circuit_scoreThe integer score S_k(U) of a k-qubit Clifford circuit circ : List (CliffordGate k), defined as the sum over all p in full_support_paulis…
Read back from the Lean
The Clifford circuit score of the empty list of Clifford gates on 1 qubit is equal to 3.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The score of a Clifford circuit on 1 qubit is defined as the sum of $3^{1 - \text{pauli\_size}(p)}$ over all Pauli operators $p$ with full support (size 1). For the empty circuit, each Pauli operator is mapped to itself. There are exactly 3 non-identity Pauli operators on 1 qubit ($X, Y, Z$), and each contributes $3^{1 - 1} = 1$ to the sum, giving 3. The `decide` tactic checks this equality automatically by direct evaluation over the finite domain.
The score of the empty Clifford circuit on 1 qubit is 3. automation
By definition, the score of a circuit on 1 qubit is the sum over all full-support Pauli operators $p$ (operators with size 1) of $3^{1 - \text{pauli\_size}(\text{apply\_clifford\_circuit } \text{circ } p)}$. For the empty circuit, every Pauli is left unchanged. On a single qubit, there are 4 Pauli operators in total ($I, X, Y, Z$), of which exactly 3 have full support (the non-identity Paulis $X, Y, Z$). Each contributes $3^{1 - 1} = 3^0 = 1$ to the sum, yielding $1 + 1 + 1 = 3$. Because the types $\text{Fin } 1$ and $\mathbb{Z}/2$ are finite, the `decide` tactic verifies this finite sum by direct evaluation.
decide
- The proof relies entirely on Lean's kernel computation (`decide`), evaluating the finite sum over the Pauli group on 1 qubit by computational reflection.
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.
/-- Sanity check: the empty Clifford circuit on 1 qubit has score 3. -/theorem clifford_circuit_score_one_nil : clifford_circuit_score ([] : List (CliffordGate 1)) = 3 := by decide