AFTD Auto-Formalizing Theoretical Domains

apply_clifford_gate_cnot_involutive

theoremverified

The CNOT gate action on Pauli labels is an involution.

Statement

theorem apply_clifford_gate_cnot_involutive {k : ℕ} (c t : Fin k) (hct : c ≠ t) (p : PauliLabel k) :
    apply_clifford_gate (.cnot c t hct) (apply_clifford_gate (.cnot c t hct) p) = p
Source
step towards op_757_all_to_all_cnot_lower_bound
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • 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 proof proceeds by extensionality on both components of the Pauli label at an arbitrary qubit index $i$. A CNOT gate with control $c$ and target $t$ acts on the first component by adding the control coordinate to the target coordinate, and on the second component by adding the target coordinate to the control coordinate. Since the control and target indices are distinct ($c \neq t$), applying the gate a second time adds the control (respectively, target) coordinate's value twice to the target (respectively, control) position. Because arithmetic is in $\mathbb{Z}/2\mathbb{Z}$ where $x + x = 0$, both additions cancel and leave the Pauli label unchanged.

  1. It suffices to show that applying the CNOT gate twice preserves both components of the Pauli label at every coordinate index $i$.

    Unfolding the definition of `apply_clifford_gate` and applying extensionality (`ext i`) reduces equality of the Pauli label pairs to checking equality of their first and second components pointwise at an arbitrary index $i$.

    lines 4–5

      dsimp [apply_clifford_gate]
      ext i
  2. In the first component, the value at the control qubit $c$ is unchanged by the update at the target qubit $t$.

    Projecting onto the first component, helper lemma `h1` establishes that updating at $t$ leaves index $c$ intact using `Function.update_of_ne` with the hypothesis $c \neq t$. Rewriting with `h1` simplifies the second update's argument from the updated function evaluated at $c$ to the original value $p.1\ c$.

    lines 6–8

    uses Function.update_of_ne

      · dsimp only
        have h1 : Function.update p.1 t (p.1 t + p.1 c) c = p.1 c := Function.update_of_ne hct (p.1 t + p.1 c) p.1
        rw [h1]
  3. When $i = t$, the first component after two applications equals $p.1\ t$. automation

    We split into cases on whether $i = t$. In the positive case, substituting $t$ for $i$ makes the double update evaluate to $(p.1\ t + p.1\ c) + p.1\ c$. By associativity (`add_assoc`) and the fact that $x + x = 0$ in characteristic 2 (`CharTwo.add_self_eq_zero`), the two $p.1\ c$ terms cancel, leaving $p.1\ t$.

    lines 9–11

    uses add_assoc, CharTwo.add_self_eq_zero

        by_cases hi : i = t
        · subst hi
          simp [add_assoc, CharTwo.add_self_eq_zero]
  4. When $i \neq t$, the first component after two applications equals $p.1\ i$.

    Because $i \neq t$, rewriting twice with `Function.update_of_ne` shows that neither the inner nor outer update at index $t$ modifies the value at index $i$, leaving it as $p.1\ i$.

    line 12

    uses Function.update_of_ne

        · rw [Function.update_of_ne hi, Function.update_of_ne hi]
  5. In the second component, the value at the target qubit $t$ is unchanged by the update at the control qubit $c$.

    Projecting onto the second component, helper lemma `h2` uses `Function.update_of_ne` with $t \neq c$ (the symmetry of $c \neq t$) to show that updating at $c$ leaves index $t$ intact. Rewriting with `h2` simplifies the second update's argument to the original value $p.2\ t$.

    lines 13–15

    uses Function.update_of_ne

      · dsimp only
        have h2 : Function.update p.2 c (p.2 c + p.2 t) t = p.2 t := Function.update_of_ne hct.symm (p.2 c + p.2 t) p.2
        rw [h2]
  6. When $i = c$, the second component after two applications equals $p.2\ c$. automation

    We split into cases on whether $i = c$. In the positive case, substituting $c$ for $i$ makes the double update evaluate to $(p.2\ c + p.2\ t) + p.2\ t$. By associativity (`add_assoc`) and characteristic-2 cancellation (`CharTwo.add_self_eq_zero`), the two $p.2\ t$ terms cancel to zero, leaving $p.2\ c$.

    lines 16–18

    uses add_assoc, CharTwo.add_self_eq_zero

        by_cases hi : i = c
        · subst hi
          simp [add_assoc, CharTwo.add_self_eq_zero]
  7. When $i \neq c$, the second component after two applications equals $p.2\ i$.

    Because $i \neq c$, rewriting twice with `Function.update_of_ne` shows that neither update at index $c$ modifies coordinate $i$, leaving it as $p.2\ i$.

    line 19

    uses Function.update_of_ne

        · rw [Function.update_of_ne hi, Function.update_of_ne hi]
Function.update_of_ne
Evaluating a function updated at index `a'` at a distinct index `a` (with `a ≠ a'`) returns the function's original value at `a`.
add_assoc
Addition in an additive semigroup is associative: `(a + b) + c = a + (b + c)`.
CharTwo.add_self_eq_zero
In a semiring of characteristic 2, adding any element to itself gives zero: `x + x = 0`.

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

/-- The CNOT gate action on Pauli labels is an involution. -/theorem apply_clifford_gate_cnot_involutive {k : ℕ} (c t : Fin k) (hct : c ≠ t) (p : PauliLabel k) :    apply_clifford_gate (.cnot c t hct) (apply_clifford_gate (.cnot c t hct) p) = p := by  dsimp [apply_clifford_gate]  ext i  · dsimp only    have h1 : Function.update p.1 t (p.1 t + p.1 c) c = p.1 c := Function.update_of_ne hct (p.1 t + p.1 c) p.1    rw [h1]    by_cases hi : i = t    · subst hi      simp [add_assoc, CharTwo.add_self_eq_zero]    · rw [Function.update_of_ne hi, Function.update_of_ne hi]  · dsimp only    have h2 : Function.update p.2 c (p.2 c + p.2 t) t = p.2 t := Function.update_of_ne hct.symm (p.2 c + p.2 t) p.2    rw [h2]    by_cases hi : i = c    · subst hi      simp [add_assoc, CharTwo.add_self_eq_zero]    · rw [Function.update_of_ne hi, Function.update_of_ne hi]
See it in the graphDiscuss this resultChallenge it