AFTD Auto-Formalizing Theoretical Domains

pauli_size_apply_clifford_gate_h

theoremverified

Single-qubit Hadamard gate preserves the Pauli size of any Pauli label.

Statement

theorem pauli_size_apply_clifford_gate_h {k : ℕ} (i : Fin k) (p : PauliLabel k) :
    pauli_size (apply_clifford_gate (.h 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
  • 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.
  • pauli_sizeThe weight (support size) of a k-qubit Pauli operator: the number of qubits on which the operator is not the identity.
  • 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 Pauli size of a Pauli label is the number of qubits on which at least one of its components is non-zero. A single-qubit Hadamard gate at index i acts by swapping the X and Z components at qubit i while leaving all other qubits unchanged. Since swapping the two components does not affect their disjunction being non-zero, each qubit is non-trivial after the gate if and only if it was non-trivial before, preserving the overall Pauli size.

  1. It suffices to show that for every qubit j, the non-triviality condition under the transformed Pauli label is equivalent to that under the original label.

    By definition, the Pauli size is the number of qubits where at least one of the X or Z components is non-zero (pauli_size). Applying congr 1 reduces the equality of sizes (cardinalities) to the equality of the two underlying filtered sets, and Finset.filter_congr reduces that to showing that for an arbitrary qubit j, the filtering conditions before and after the gate are logically equivalent.

    lines 4–7

    uses Finset.filter_congr

      unfold pauli_size apply_clifford_gate
      congr 1
      apply Finset.filter_congr
      intro j _
  2. At the target qubit i, the non-triviality condition is preserved because the Hadamard gate swaps the two components.

    We split into cases on whether j = i (by_cases). In the case j = i, substituting j for i (subst), the Hadamard gate replaces the first component p.1 i with p.2 i and the second component p.2 i with p.1 i by Function.update_self. The condition p.2 i ≠ 0 ∨ p.1 i ≠ 0 is equivalent to p.1 i ≠ 0 ∨ p.2 i ≠ 0 by commutativity of disjunction (or_comm).

    lines 8–10

    uses Function.update_self, or_comm

      by_cases hji : j = i
      · subst hji
        simp [Function.update_self, or_comm]
  3. At any qubit j ≠ i, the condition is preserved because the gate leaves the components unchanged.

    In the remaining case j ≠ i, Function.update_of_ne shows that evaluating the updated components at j yields the original components p.1 j and p.2 j, so the filtering condition is identical.

    line 11

    uses Function.update_of_ne

      · simp [Function.update_of_ne hji]
Finset.filter_congr
Two subsets obtained by filtering the same set are equal if their defining predicates are equivalent for every element of the set.
Function.update_self
Updating a function at a point and then evaluating at that same point returns the new value.
or_comm
Disjunction is commutative: a ∨ b is equivalent to b ∨ a.
Function.update_of_ne
Updating a function at a point a' and evaluating at a different point a leaves the function value unchanged.

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

/-- Single-qubit Hadamard gate preserves the Pauli size of any Pauli label. -/theorem pauli_size_apply_clifford_gate_h {k : ℕ} (i : Fin k) (p : PauliLabel k) :    pauli_size (apply_clifford_gate (.h i) p) = pauli_size p := by  unfold pauli_size apply_clifford_gate  congr 1  apply Finset.filter_congr  intro j _  by_cases hji : j = i  · subst hji    simp [Function.update_self, or_comm]  · simp [Function.update_of_ne hji]
See it in the graphDiscuss this resultChallenge it