AFTD Auto-Formalizing Theoretical Domains

pauli_size_apply_clifford_gate_s

theoremverified

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

Statement

theorem pauli_size_apply_clifford_gate_s {k : ℕ} (i : Fin k) (p : PauliLabel k) :
    pauli_size (apply_clifford_gate (.s 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
  • 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 label is the number of qubits on which the label acts non-trivially (its support). The single-qubit Phase gate at qubit i modifies only the second component at qubit i, replacing b with b + a in ZMod 2 while leaving all other qubits unaffected. The proof shows that this operation preserves the support set qubit by qubit: on qubits j ≠ i the label is unchanged, while on qubit i the condition a ≠ 0 ∨ b + a ≠ 0 is logically equivalent to a ≠ 0 ∨ b ≠ 0. Since the support sets are identical, their cardinalities (the Pauli sizes) are equal.

  1. The action of the single-qubit Phase gate on qubit i updates the second component from p.2 i to p.2 i + p.1 i, leaving all other components unchanged.

    By definition of `apply_clifford_gate`, applying the Phase gate S on qubit i leaves p.1 unchanged and replaces p.2 at index i with p.2 i + p.1 i. Rewriting the goal with this definition (`rw [hp]`) reduces the theorem to showing that this update does not affect the Pauli size.

    lines 5–7

      have hp : apply_clifford_gate (CliffordGate.s i) p
          = (p.1, Function.update p.2 i (p.2 i + p.1 i)) := rfl
      rw [hp]
  2. Equality of the support sets of the updated and original Pauli labels reduces to pointwise equivalence of their non-triviality conditions for each qubit j.

    The Pauli size counts the qubits in the support of the label, defined as the sub-finset of qubits where p.1 j ≠ 0 or p.2 j ≠ 0. By extensionality (`ext j`), the two support sets are equal if and only if each qubit j belongs to the first if and only if it belongs to the second. Simplifying the set-membership conditions using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and` reduces this to the equivalence p.1 j ≠ 0 ∨ (updated p.2) j ≠ 0 ↔ p.1 j ≠ 0 ∨ p.2 j ≠ 0.

    lines 9–13

    uses Finset.mem_filter, Finset.mem_univ, true_and

      have h : (Finset.univ.filter fun j : Fin k =>
            p.1 j ≠ 0 ∨ Function.update p.2 i (p.2 i + p.1 i) j ≠ 0)
          = (Finset.univ.filter fun j : Fin k => p.1 j ≠ 0 ∨ p.2 j ≠ 0) := by
        ext j
        simp only [Finset.mem_filter, Finset.mem_univ, true_and]
  3. On qubit i, the non-triviality condition p.1 i ≠ 0 ∨ p.2 i + p.1 i ≠ 0 is equivalent to p.1 i ≠ 0 ∨ p.2 i ≠ 0.

    When j = i, the updated function evaluates to p.2 i + p.1 i by `Function.update_self`. We then case-split on whether p.1 i = 0: if p.1 i = 0, then p.2 i + p.1 i = p.2 i and both disjunctions reduce to p.2 i ≠ 0; if p.1 i ≠ 0, then the first disjunct is true on both sides, so both disjunctions evaluate to true. In either case, the equivalence holds.

    lines 14–17

    uses Function.update_self

        by_cases hj : j = i
        · -- On qubit i, `a ≠ 0 ∨ b + a ≠ 0 ↔ a ≠ 0 ∨ b ≠ 0` in ZMod 2.
          rw [hj, Function.update_self]
          by_cases ha : p.1 i = 0 <;> simp [ha]
  4. On every qubit j ≠ i, the non-triviality condition is identical before and after the gate.

    When j ≠ i, `Function.update_of_ne` shows that the updated function evaluates to p.2 j, so the condition p.1 j ≠ 0 ∨ p.2 j ≠ 0 is identical on both sides. Rewriting closes the goal by reflexivity.

    line 18

    uses Function.update_of_ne

        · rw [Function.update_of_ne hj]
  5. The single-qubit Phase gate preserves the Pauli size of any Pauli label.

    Unfolding the definition of `pauli_size` on both sides expresses the sizes as the cardinalities of the respective support sets. Rewriting with the set equality h established in the previous steps makes both sides identical, concluding the proof.

    line 19

    uses pauli_size

      rw [pauli_size, pauli_size, h]
Finset.mem_filter
An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and
The conjunction `True ∧ p` is equivalent to `p`.
Function.update_self
Evaluating a function updated at index `a` with value `v` at `a` yields `v`.
Function.update_of_ne
Evaluating a function updated at index `a'` at a distinct index `a ≠ a'` yields its original value.
pauli_size
The Pauli size of a Pauli label is the number of qubits on which the label acts non-trivially (where at least one component is non-zero).

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 Phase gate preserves the Pauli size of any Pauli label. -/theorem pauli_size_apply_clifford_gate_s {k : ℕ} (i : Fin k) (p : PauliLabel k) :    pauli_size (apply_clifford_gate (.s i) p) = pauli_size p := by  -- The phase gate acts as (a, b) ↦ (a, b + a) on the qubit i; elsewhere nothing changes.  have hp : apply_clifford_gate (CliffordGate.s i) p      = (p.1, Function.update p.2 i (p.2 i + p.1 i)) := rfl  rw [hp]  -- The support predicate agrees pointwise with that of p.  have h : (Finset.univ.filter fun j : Fin k =>        p.1 j ≠ 0 ∨ Function.update p.2 i (p.2 i + p.1 i) j ≠ 0)      = (Finset.univ.filter fun j : Fin k => p.1 j ≠ 0 ∨ p.2 j ≠ 0) := by    ext j    simp only [Finset.mem_filter, Finset.mem_univ, true_and]    by_cases hj : j = i    · -- On qubit i, `a ≠ 0 ∨ b + a ≠ 0 ↔ a ≠ 0 ∨ b ≠ 0` in ZMod 2.      rw [hj, Function.update_self]      by_cases ha : p.1 i = 0 <;> simp [ha]    · rw [Function.update_of_ne hj]  rw [pauli_size, pauli_size, h]
See it in the graphDiscuss this resultChallenge it