pauli_size_apply_clifford_gate_s
Single-qubit Phase gate preserves the Pauli size of any Pauli label.
Statement
theorem pauli_size_apply_clifford_gate_s {k : ℕ} (i : Fin k) (p : PauliLabel k) :
pauli_size (apply_clifford_gate (.s 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
- 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…
- pauli_sizeThe weight (support size) of a k-qubit Pauli operator: the number of qubits on which the operator is not the identity.
- 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.
The proof, explained
The Pauli size of a Pauli label is the number of qubits on which the label acts non-trivially (its support). The single-qubit Phase gate at qubit i modifies only the second component at qubit i, replacing b with b + a in ZMod 2 while leaving all other qubits unaffected. The proof shows that this operation preserves the support set qubit by qubit: on qubits j ≠ i the label is unchanged, while on qubit i the condition a ≠ 0 ∨ b + a ≠ 0 is logically equivalent to a ≠ 0 ∨ b ≠ 0. Since the support sets are identical, their cardinalities (the Pauli sizes) are equal.
The action of the single-qubit Phase gate on qubit i updates the second component from p.2 i to p.2 i + p.1 i, leaving all other components unchanged.
By definition of `apply_clifford_gate`, applying the Phase gate S on qubit i leaves p.1 unchanged and replaces p.2 at index i with p.2 i + p.1 i. Rewriting the goal with this definition (`rw [hp]`) reduces the theorem to showing that this update does not affect the Pauli size.
have hp : apply_clifford_gate (CliffordGate.s i) p = (p.1, Function.update p.2 i (p.2 i + p.1 i)) := rfl rw [hp]
Equality of the support sets of the updated and original Pauli labels reduces to pointwise equivalence of their non-triviality conditions for each qubit j.
The Pauli size counts the qubits in the support of the label, defined as the sub-finset of qubits where p.1 j ≠ 0 or p.2 j ≠ 0. By extensionality (`ext j`), the two support sets are equal if and only if each qubit j belongs to the first if and only if it belongs to the second. Simplifying the set-membership conditions using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and` reduces this to the equivalence p.1 j ≠ 0 ∨ (updated p.2) j ≠ 0 ↔ p.1 j ≠ 0 ∨ p.2 j ≠ 0.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave h : (Finset.univ.filter fun j : Fin k => p.1 j ≠ 0 ∨ Function.update p.2 i (p.2 i + p.1 i) j ≠ 0) = (Finset.univ.filter fun j : Fin k => p.1 j ≠ 0 ∨ p.2 j ≠ 0) := by ext j simp only [Finset.mem_filter, Finset.mem_univ, true_and]
On qubit i, the non-triviality condition p.1 i ≠ 0 ∨ p.2 i + p.1 i ≠ 0 is equivalent to p.1 i ≠ 0 ∨ p.2 i ≠ 0.
When j = i, the updated function evaluates to p.2 i + p.1 i by `Function.update_self`. We then case-split on whether p.1 i = 0: if p.1 i = 0, then p.2 i + p.1 i = p.2 i and both disjunctions reduce to p.2 i ≠ 0; if p.1 i ≠ 0, then the first disjunct is true on both sides, so both disjunctions evaluate to true. In either case, the equivalence holds.
uses
Function.update_selfby_cases hj : j = i · -- On qubit i, `a ≠ 0 ∨ b + a ≠ 0 ↔ a ≠ 0 ∨ b ≠ 0` in ZMod 2. rw [hj, Function.update_self] by_cases ha : p.1 i = 0 <;> simp [ha]
On every qubit j ≠ i, the non-triviality condition is identical before and after the gate.
When j ≠ i, `Function.update_of_ne` shows that the updated function evaluates to p.2 j, so the condition p.1 j ≠ 0 ∨ p.2 j ≠ 0 is identical on both sides. Rewriting closes the goal by reflexivity.
uses
Function.update_of_ne· rw [Function.update_of_ne hj]The single-qubit Phase gate preserves the Pauli size of any Pauli label.
Unfolding the definition of `pauli_size` on both sides expresses the sizes as the cardinalities of the respective support sets. Rewriting with the set equality h established in the previous steps makes both sides identical, concluding the proof.
uses
pauli_sizerw [pauli_size, pauli_size, h]
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- The conjunction `True ∧ p` is equivalent to `p`.
Function.update_self- Evaluating a function updated at index `a` with value `v` at `a` yields `v`.
Function.update_of_ne- Evaluating a function updated at index `a'` at a distinct index `a ≠ a'` yields its original value.
pauli_size- The Pauli size of a Pauli label is the number of qubits on which the label acts non-trivially (where at least one component is non-zero).
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 Phase gate preserves the Pauli size of any Pauli label. -/theorem pauli_size_apply_clifford_gate_s {k : ℕ} (i : Fin k) (p : PauliLabel k) : pauli_size (apply_clifford_gate (.s i) p) = pauli_size p := by -- The phase gate acts as (a, b) ↦ (a, b + a) on the qubit i; elsewhere nothing changes. have hp : apply_clifford_gate (CliffordGate.s i) p = (p.1, Function.update p.2 i (p.2 i + p.1 i)) := rfl rw [hp] -- The support predicate agrees pointwise with that of p. have h : (Finset.univ.filter fun j : Fin k => p.1 j ≠ 0 ∨ Function.update p.2 i (p.2 i + p.1 i) j ≠ 0) = (Finset.univ.filter fun j : Fin k => p.1 j ≠ 0 ∨ p.2 j ≠ 0) := by ext j simp only [Finset.mem_filter, Finset.mem_univ, true_and] by_cases hj : j = i · -- On qubit i, `a ≠ 0 ∨ b + a ≠ 0 ↔ a ≠ 0 ∨ b ≠ 0` in ZMod 2. rw [hj, Function.update_self] by_cases ha : p.1 i = 0 <;> simp [ha] · rw [Function.update_of_ne hj] rw [pauli_size, pauli_size, h]