clifford_circuit_score
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
- clifford_circuit_score_one_nilSanity check: the empty Clifford circuit on 1 qubit has score 3.
- op_757_cnot_two_existsFor k = 2, there exists a Clifford circuit circ : List (CliffordGate 2) satisfying is_1d_chain_circuit circ and clifford_circuit_score…
- op_757_all_to_all_cnot_three_existsFor k = 3 with all-to-all connectivity, there exists a Clifford circuit circ : List (CliffordGate 3) achieving clifford_circuit_score circ…
- op_757_1d_chain_cnot_three_le_fiveFor k = 3 with 1D nearest-neighbor chain connectivity, there exists a Clifford circuit circ : List (CliffordGate 3) satisfying…
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))