pauli_size_apply_clifford_gate_cnot_le
Applying a CNOT gate increases the Pauli size by at most 1.
Statement
theorem pauli_size_apply_clifford_gate_cnot_le {k : ℕ} (c t : Fin k) (hct : c ≠ t) (p : PauliLabel k) :
pauli_size (apply_clifford_gate (.cnot c t hct) p) ≤ pauli_size p + 1- 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 operator is the cardinality of its support, the set of qubit indices where at least one of its components is non-zero. A CNOT gate with control $c$ and target $t$ modifies only the first component at $t$ and the second component at $c$, leaving all other qubit positions unchanged. By case analysis on whether the target index $t$ belongs to the initial support $A$, we show that the support of the resulting operator is contained in $A \cup \{c\}$ if $t \in A$, or in $A \cup \{t\}$ if $t \notin A$ (because in the latter case $p_2(t) = 0$, so no new non-zero entry is created at $c$). In either case, at most one new index is added to the support, so its cardinality increases by at most 1.
Let $A$ be the support of $p$; then the Pauli size of $p$ equals $|A|$, and $i \in A$ if and only if $p_1(i) \neq 0$ or $p_2(i) \neq 0$.
We define $A$ to be the set of qubit indices $i$ where at least one Pauli component $p_1(i)$ or $p_2(i)$ is non-zero. Unfolding the definition of `pauli_size`, the Pauli size of $p$ is precisely the cardinality of $A$, and membership in $A$ is equivalent to satisfying this non-zero condition.
uses
pauli_sizeclassical set A : Finset (Fin k) := Finset.univ.filter (fun i => p.1 i ≠ 0 ∨ p.2 i ≠ 0) with hA have hsize : pauli_size p = A.card := by rw [pauli_size, ← hA] have hmem : ∀ i : Fin k, (i ∈ A ↔ (p.1 i ≠ 0 ∨ p.2 i ≠ 0)) := by intro i; rw [hA]; simp
Let $q$ be the result of applying the CNOT gate to $p$; its components differ from $p$ only at the target $t$ and control $c$, and its Pauli size is the cardinality of its support.
By definition of `apply_clifford_gate` on a CNOT gate with control $c$ and target $t$, the first component $q_1$ updates $p_1$ only at index $t$ by adding $p_1(c)$, while the second component $q_2$ updates $p_2$ only at index $c$ by adding $p_2(t)$. The Pauli size of $q$ is definitionally the cardinality of the set of indices where $q_1(i) \neq 0$ or $q_2(i) \neq 0$.
set q := apply_clifford_gate (CliffordGate.cnot c t hct) p with hq have hq1 : q.1 = Function.update p.1 t (p.1 t + p.1 c) := by rw [hq]; rfl have hq2 : q.2 = Function.update p.2 c (p.2 c + p.2 t) := by rw [hq]; rfl have hqsize : pauli_size q = (Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0)).card := rfl
In the case where $t \in A$, the support of $q$ is a subset of $A \cup \{c\}$.
We split into cases on whether $t \in A$. Assuming $t \in A$, let $i$ be any index in the support of $q$. If $i = c$, then $i \in A \cup \{c\}$ directly by `Or.inl`. If $i \neq c$, then either $i = t$ (in which case $i \in A$ because $t \in A$) or $i \neq t$. If $i$ is neither $c$ nor $t$, neither component was updated, so $q_1(i) = p_1(i)$ and $q_2(i) = p_2(i)$ by `Function.update_of_ne`, which implies $i \in A$. Hence, every element in the support of $q$ belongs to $A \cup \{c\}$.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_insert,Or.inl,Function.update_of_neby_cases ht : t ∈ A · have hsub : Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0) ⊆ insert c A := by intro i hi simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi rw [Finset.mem_insert] by_cases hic : i = c · exact Or.inl hic · right by_cases hit : i = t · rw [hit]; exact ht · have e1 : q.1 i = p.1 i := by rw [hq1, Function.update_of_ne hit] have e2 : q.2 i = p.2 i := by rw [hq2, Function.update_of_ne hic] rw [e1, e2] at hi exact (hmem i).mpr hi
If $t \in A$, then $\text{pauli\_size}(q) \le \text{pauli\_size}(p) + 1$.
Because the support of $q$ is contained in $A \cup \{c\}$, its cardinality is at most $|A \cup \{c\}|$ by `Finset.card_le_card`. Inserting an element into a finite set increases its cardinality by at most 1 by `Finset.card_insert_le`, giving $|A \cup \{c\}| \le |A| + 1 = \text{pauli\_size}(p) + 1$.
uses
Finset.card_le_card,Finset.card_insert_lecalc pauli_size q = (Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0)).card := hqsize _ ≤ (insert c A).card := Finset.card_le_card hsub _ ≤ A.card + 1 := Finset.card_insert_le c A _ = pauli_size p + 1 := by rw [hsize]
If $t \notin A$, then $p_1(t) = 0$ and $p_2(t) = 0$.
If either $p_1(t) \neq 0$ or $p_2(t) \neq 0$, then $t$ would satisfy the membership condition for $A$ (via `Or.inl` or `Or.inr`), which contradicts $t \notin A$.
uses
Or.inl,Or.inr· have ht1 : p.1 t = 0 := by by_contra h exact ht ((hmem t).mpr (Or.inl h)) have ht2 : p.2 t = 0 := by by_contra h exact ht ((hmem t).mpr (Or.inr h))
In the case where $t \notin A$, the support of $q$ is a subset of $A \cup \{t\}$.
Let $i$ be any index in the support of $q$. If $i = t$, then $i \in A \cup \{t\}$ by `Or.inl`. If $i \neq t$, consider whether $i = c$: since $c \neq t$, the first component is unchanged ($q_1(c) = p_1(c)$), and since $p_2(t) = 0$, the updated second component satisfies $q_2(c) = p_2(c) + p_2(t) = p_2(c)$; thus $i = c \in A$. If instead $i \neq t$ and $i \neq c$, both components are untouched by `Function.update_of_ne`, so $i \in A$. In all subcases, $i \in A \cup \{t\}$.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_insert,Or.inl,Function.update_of_nehave hsub : Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0) ⊆ insert t A := by intro i hi simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi rw [Finset.mem_insert] by_cases hit : i = t · exact Or.inl hit · right by_cases hic : i = c · rw [hic] at hi ⊢ have e1 : q.1 c = p.1 c := by rw [hq1, Function.update_of_ne hct] have e2 : q.2 c = p.2 c := by rw [hq2]; simp [ht2] rw [e1, e2] at hi exact (hmem c).mpr hi · have e1 : q.1 i = p.1 i := by rw [hq1, Function.update_of_ne hit] have e2 : q.2 i = p.2 i := by rw [hq2, Function.update_of_ne hic] rw [e1, e2] at hi exact (hmem i).mpr hi
If $t \notin A$, then $\text{pauli\_size}(q) \le \text{pauli\_size}(p) + 1$.
Because the support of $q$ is contained in $A \cup \{t\}$, its cardinality is at most $|A \cup \{t\}| \le |A| + 1 = \text{pauli\_size}(p) + 1$ by `Finset.card_le_card` and `Finset.card_insert_le`.
uses
Finset.card_le_card,Finset.card_insert_lecalc pauli_size q = (Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0)).card := hqsize _ ≤ (insert t A).card := Finset.card_le_card hsub _ ≤ A.card + 1 := Finset.card_insert_le t A _ = pauli_size p + 1 := by rw [hsize]
pauli_size- The Pauli size of a Pauli operator is defined as the number of qubit indices where at least one of its two components is non-zero.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the parent finset and satisfies the filter predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- The logical conjunction `True ∧ p` simplifies to `p`.
Finset.mem_insert- An element belongs to `insert b s` if and only if it equals `b` or belongs to `s`.
Or.inl- Proves the disjunction `a ∨ b` from a proof of `a`.
Or.inr- Proves the disjunction `a ∨ b` from a proof of `b`.
Function.update_of_ne- A function updated at an argument `a'` retains its original value when evaluated at any distinct argument `a ≠ a'`.
Finset.card_le_card- If `s ⊆ t` for finite sets `s` and `t`, then `|s| ≤ |t|`.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1: `|insert a s| ≤ |s| + 1`.
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.
/-- Applying a CNOT gate increases the Pauli size by at most 1. -/theorem pauli_size_apply_clifford_gate_cnot_le {k : ℕ} (c t : Fin k) (hct : c ≠ t) (p : PauliLabel k) : pauli_size (apply_clifford_gate (.cnot c t hct) p) ≤ pauli_size p + 1 := by classical set A : Finset (Fin k) := Finset.univ.filter (fun i => p.1 i ≠ 0 ∨ p.2 i ≠ 0) with hA have hsize : pauli_size p = A.card := by rw [pauli_size, ← hA] have hmem : ∀ i : Fin k, (i ∈ A ↔ (p.1 i ≠ 0 ∨ p.2 i ≠ 0)) := by intro i; rw [hA]; simp set q := apply_clifford_gate (CliffordGate.cnot c t hct) p with hq have hq1 : q.1 = Function.update p.1 t (p.1 t + p.1 c) := by rw [hq]; rfl have hq2 : q.2 = Function.update p.2 c (p.2 c + p.2 t) := by rw [hq]; rfl have hqsize : pauli_size q = (Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0)).card := rfl by_cases ht : t ∈ A · have hsub : Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0) ⊆ insert c A := by intro i hi simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi rw [Finset.mem_insert] by_cases hic : i = c · exact Or.inl hic · right by_cases hit : i = t · rw [hit]; exact ht · have e1 : q.1 i = p.1 i := by rw [hq1, Function.update_of_ne hit] have e2 : q.2 i = p.2 i := by rw [hq2, Function.update_of_ne hic] rw [e1, e2] at hi exact (hmem i).mpr hi calc pauli_size q = (Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0)).card := hqsize _ ≤ (insert c A).card := Finset.card_le_card hsub _ ≤ A.card + 1 := Finset.card_insert_le c A _ = pauli_size p + 1 := by rw [hsize] · have ht1 : p.1 t = 0 := by by_contra h exact ht ((hmem t).mpr (Or.inl h)) have ht2 : p.2 t = 0 := by by_contra h exact ht ((hmem t).mpr (Or.inr h)) have hsub : Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0) ⊆ insert t A := by intro i hi simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi rw [Finset.mem_insert] by_cases hit : i = t · exact Or.inl hit · right by_cases hic : i = c · rw [hic] at hi ⊢ have e1 : q.1 c = p.1 c := by rw [hq1, Function.update_of_ne hct] have e2 : q.2 c = p.2 c := by rw [hq2]; simp [ht2] rw [e1, e2] at hi exact (hmem c).mpr hi · have e1 : q.1 i = p.1 i := by rw [hq1, Function.update_of_ne hit] have e2 : q.2 i = p.2 i := by rw [hq2, Function.update_of_ne hic] rw [e1, e2] at hi exact (hmem i).mpr hi calc pauli_size q = (Finset.univ.filter (fun i : Fin k => q.1 i ≠ 0 ∨ q.2 i ≠ 0)).card := hqsize _ ≤ (insert t A).card := Finset.card_le_card hsub _ ≤ A.card + 1 := Finset.card_insert_le t A _ = pauli_size p + 1 := by rw [hsize]