AFTD Auto-Formalizing Theoretical Domains

clifford_circuit_score_one_nil

theoremverified

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.

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

    line 3

      decide

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

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