CliffordGate
An 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 k, or controlled-NOT gate cnot with distinct control and target qubits c t : Fin k (with a proof c ≠ t).
Statement
inductive CliffordGate (k : ℕ)- Defined in
- scout/2610-04621-exact-clifford-optimality-for-two-sided-locally-randomized.md:1610
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Used by 13
- pauli_size_apply_clifford_gate_cnot_leApplying a CNOT gate increases the Pauli size by at most 1.
- clifford_circuit_score_one_nilSanity check: the empty Clifford circuit on 1 qubit has score 3.
- apply_clifford_gate_cnot_involutiveThe CNOT gate action on Pauli labels is an involution.
- apply_clifford_gateThe symplectic action of a Clifford gate g : CliffordGate k on a PauliLabel k: h i swaps the x and z components at qubit i; s i updates…
- 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…
- pauli_size_apply_clifford_gate_hSingle-qubit Hadamard gate preserves the Pauli size of any Pauli label.
- pauli_size_apply_clifford_gate_sSingle-qubit Phase gate preserves the Pauli size of any Pauli label.
- apply_clifford_circuitThe symplectic action of a Clifford circuit circ : List (CliffordGate k) on a PauliLabel k, obtained by folding apply_clifford_gate across…
- clifford_cnot_countThe CNOT count of a k-qubit Clifford circuit, defined as the number of cnot gates in the list circ : List (CliffordGate k).
- 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…
- is_1d_chain_circuitA Clifford circuit circ : List (CliffordGate k) satisfies the 1D nearest-neighbor chain connectivity condition if every cnot gate with…
- 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
An inductive type CliffordGate (k : ℕ) representing elementary Clifford gates on k qubits, with three constructors:
1. h (i : Fin k): a Hadamard gate acting on qubit i.
2. s (i : Fin k): a phase gate (S gate) acting on qubit i.
3. cnot (c t : Fin k) (h : c ≠ t): a controlled-NOT (CNOT) gate with control qubit c and target qubit t, requiring a proof that c ≠ t.
The type also derives decidable equality (DecidableEq).
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
/-- A quantum gate in a k-qubit Clifford circuit: H on qubit i, S on qubit i, or CNOT with distinct control c and target t. -/ inductive CliffordGate (k : ℕ) where | h : Fin k → CliffordGate k | s : Fin k → CliffordGate k | cnot : (c t : Fin k) → c ≠ t → CliffordGate k deriving DecidableEq