pauli_size_apply_clifford_gate_h
Single-qubit Hadamard gate preserves the Pauli size of any Pauli label.
Statement
theorem pauli_size_apply_clifford_gate_h {k : ℕ} (i : Fin k) (p : PauliLabel k) :
pauli_size (apply_clifford_gate (.h i) p) = pauli_size p- Source
- step towards op_757_all_to_all_cnot_lower_bound
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- 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…
- 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…
The proof, explained
The Pauli size of a Pauli label is the number of qubits on which at least one of its components is non-zero. A single-qubit Hadamard gate at index i acts by swapping the X and Z components at qubit i while leaving all other qubits unchanged. Since swapping the two components does not affect their disjunction being non-zero, each qubit is non-trivial after the gate if and only if it was non-trivial before, preserving the overall Pauli size.
It suffices to show that for every qubit j, the non-triviality condition under the transformed Pauli label is equivalent to that under the original label.
By definition, the Pauli size is the number of qubits where at least one of the X or Z components is non-zero (pauli_size). Applying congr 1 reduces the equality of sizes (cardinalities) to the equality of the two underlying filtered sets, and Finset.filter_congr reduces that to showing that for an arbitrary qubit j, the filtering conditions before and after the gate are logically equivalent.
uses
Finset.filter_congrunfold pauli_size apply_clifford_gate congr 1 apply Finset.filter_congr intro j _
At the target qubit i, the non-triviality condition is preserved because the Hadamard gate swaps the two components.
We split into cases on whether j = i (by_cases). In the case j = i, substituting j for i (subst), the Hadamard gate replaces the first component p.1 i with p.2 i and the second component p.2 i with p.1 i by Function.update_self. The condition p.2 i ≠ 0 ∨ p.1 i ≠ 0 is equivalent to p.1 i ≠ 0 ∨ p.2 i ≠ 0 by commutativity of disjunction (or_comm).
uses
Function.update_self,or_commby_cases hji : j = i · subst hji simp [Function.update_self, or_comm]
At any qubit j ≠ i, the condition is preserved because the gate leaves the components unchanged.
In the remaining case j ≠ i, Function.update_of_ne shows that evaluating the updated components at j yields the original components p.1 j and p.2 j, so the filtering condition is identical.
uses
Function.update_of_ne· simp [Function.update_of_ne hji]
Finset.filter_congr- Two subsets obtained by filtering the same set are equal if their defining predicates are equivalent for every element of the set.
Function.update_self- Updating a function at a point and then evaluating at that same point returns the new value.
or_comm- Disjunction is commutative: a ∨ b is equivalent to b ∨ a.
Function.update_of_ne- Updating a function at a point a' and evaluating at a different point a leaves the function value unchanged.
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.
/-- Single-qubit Hadamard gate preserves the Pauli size of any Pauli label. -/theorem pauli_size_apply_clifford_gate_h {k : ℕ} (i : Fin k) (p : PauliLabel k) : pauli_size (apply_clifford_gate (.h i) p) = pauli_size p := by unfold pauli_size apply_clifford_gate congr 1 apply Finset.filter_congr intro j _ by_cases hji : j = i · subst hji simp [Function.update_self, or_comm] · simp [Function.update_of_ne hji]