AFTD Auto-Formalizing Theoretical Domains

pauli_size_apply_clifford_gate_cnot_le

theoremverified

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.

  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.

    lines 4–8

    uses pauli_size

      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
  2. 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$.

    lines 9–12

      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
  3. 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\}$.

    lines 13–26

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Or.inl, Function.update_of_ne

      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
  4. 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$.

    lines 27–30

    uses Finset.card_le_card, Finset.card_insert_le

        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]
  5. 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$.

    lines 31–36

    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))
  6. 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\}$.

    lines 37–53

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Or.inl, Function.update_of_ne

        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
  7. 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`.

    lines 54–57

    uses Finset.card_le_card, Finset.card_insert_le

        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]
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

/-- 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]
See it in the graphDiscuss this resultChallenge it