AFTD Auto-Formalizing Theoretical Domains

clifford_circuit_score

def

The 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 k of 3^(k - pauli_size (apply_clifford_circuit circ p)).

Statement

def clifford_circuit_score {k : ℕ} (circ : List (CliffordGate k)) : ℕ
Defined in
scout/2610-04621-exact-clifford-optimality-for-two-sided-locally-randomized.md:370
Verified
31 Oct 2026
Axioms
none listed
Built on 5
  • 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…
  • PauliLabelA binary symplectic Pauli label on k qubits, given as a pair of binary vectors (x, z) in (ZMod 2)^k x (ZMod 2)^k.
  • pauli_sizeThe weight (support size) of a k-qubit Pauli operator: the number of qubits on which the operator is not the identity.
  • full_support_paulisThe set of full-support Pauli operators on k qubits, acting non-trivially on every qubit.
  • apply_clifford_circuitThe symplectic action of a Clifford circuit circ : List (CliffordGate k) on a PauliLabel k, obtained by folding apply_clifford_gate across…
Used by 4

Read back from the Lean

Definition of clifford_circuit_score: given a natural number k and a list circ of Clifford gates on k qubits (List (CliffordGate k)), it computes the natural number obtained by summing $3^{k - \text{pauli\_size}(p')}$ over all Pauli operators $p$ on $k$ qubits that have full support (i.e., $\text{pauli\_size}(p) = k$), where $p'$ is the Pauli operator obtained by sequentially applying the gates in circ to $p$ (via List.foldl), and $\text{pauli\_size}(p')$ is the number of qubits $i \in \text{Fin } k$ on which the Pauli label has a non-zero component in either coordinate.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The integer score S_k(U) of a k-qubit Clifford circuit. -/
def clifford_circuit_score {k : ℕ} (circ : List (CliffordGate k)) : ℕ := ∑ p ∈ full_support_paulis k, 3 ^ (k - pauli_size (apply_clifford_circuit circ p))
See it in the graphDiscuss this resultChallenge it