apply_clifford_gate_cnot_involutive
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.
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$.
dsimp [apply_clifford_gate] ext i
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$.
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]
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$.
uses
add_assoc,CharTwo.add_self_eq_zeroby_cases hi : i = t · subst hi simp [add_assoc, CharTwo.add_self_eq_zero]
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$.
uses
Function.update_of_ne· rw [Function.update_of_ne hi, Function.update_of_ne hi]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$.
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]
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$.
uses
add_assoc,CharTwo.add_self_eq_zeroby_cases hi : i = c · subst hi simp [add_assoc, CharTwo.add_self_eq_zero]
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$.
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`.
- In lines 11 and 18, `simp` automatically evaluates updated functions at their modified indices (evaluating `Function.update f a v a` to `v`) in addition to using the supplied lemmas for associativity and characteristic-2 cancellation.
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.
/-- 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]