sum_pow_pauli_size
Weight enumerator of Pauli labels: summed over all 4^k labels, x^(k - pauli_size p) equals (x+3)^k. Per qubit the four Pauli choices contribute x (identity), 1, 1, 1 (X, Y, Z).
Statement
theorem sum_pow_pauli_size (k x : ℕ) : ∑ p : PauliLabel k, x ^ (k - pauli_size p) = (x + 3) ^ k- Source
- step towards op_757_all_to_all_cnot_lower_bound
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- pauli_sizeThe weight (support size) of a k-qubit Pauli operator: the number of qubits on which the operator is not the identity.
- 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 theorem evaluates the Pauli weight enumerator by factoring each term into a per-qubit product and interchanging summation and multiplication. First, each label's weight x^(k - pauli_size p) is shown to factor into a product over the k qubits, contributing x at qubits where the label is identity and 1 elsewhere. Using the canonical equivalence between Pauli labels and functions Fin k → ℤ₂ × ℤ₂, the generalized distributive law (Fintype.prod_sum) swaps the sum and product into a product of k independent single-qubit sums. Finally, each single-qubit sum over the four Pauli choices evaluates to x + 1 + 1 + 1 = x + 3, yielding the total (x + 3)^k.
k - pauli_size p is equal to the number of qubits where both components of p are zero.
By definition, `pauli_size p` counts the qubits where at least one component of p is non-zero. Splitting the universe of k qubits into those satisfying this non-zero condition and those satisfying its negation (`Finset.card_filter_add_card_filter_not`), and simplifying the negation using De Morgan's laws (`Finset.filter_congr`), shows that the complement consists of the qubits where both components vanish. Since the total number of qubits is k (`card_univ`, `Fintype.card_fin`), linear arithmetic (`omega`) deduces that k - pauli_size p is the size of this complement. Rewriting with this equality replaces the exponent.
uses
Finset.card_filter_add_card_filter_not,Finset.filter_congr,card_univ,Fintype.card_finlemma sum_pow_pauli_size_prod_per_qubit {k x : ℕ} (p : PauliLabel k) : x ^ (k - pauli_size p) = ∏ i : Fin k, (if p.1 i = 0 then (if p.2 i = 0 then x else 1) else 1) := by have hcard : k - pauli_size p = (univ.filter (fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0)).card := by show k - (univ.filter (fun i : Fin k => p.1 i ≠ 0 ∨ p.2 i ≠ 0)).card = _ have h2 := Finset.card_filter_add_card_filter_not (s := (univ : Finset (Fin k))) (p := fun i => p.1 i ≠ 0 ∨ p.2 i ≠ 0) have h3 : (univ.filter (fun i : Fin k => ¬ (p.1 i ≠ 0 ∨ p.2 i ≠ 0))) = univ.filter (fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0) := by apply Finset.filter_congr intro i _ simp rw [h3, card_univ, Fintype.card_fin] at h2 omega rw [hcard]
x^(k - pauli_size p) equals the product over all qubits of the factor testing whether both components of p are zero.
Case analysis on whether each component of p(i) is zero simplifies the nested conditionals into a single condition testing both components (`Finset.prod_congr`). Rewriting with `Finset.prod_filter` transforms the product of this indicator into a product of the constant x over the set of qubits where p acts as the identity. Finally, `Finset.prod_const` evaluates this product as x raised to the number of identity qubits, completing the proof of the helper lemma.
uses
Finset.prod_congr,Finset.prod_filter,Finset.prod_consthave hstep : (∏ i : Fin k, (if p.1 i = 0 then (if p.2 i = 0 then x else 1) else 1)) = ∏ i : Fin k, (if (p.1 i = 0 ∧ p.2 i = 0) then x else 1) := by apply Finset.prod_congr rfl intro i _ by_cases h1 : p.1 i = 0 <;> by_cases h2 : p.2 i = 0 <;> simp [h1, h2] rw [hstep] rw [← Finset.prod_filter (s := univ) (p := fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0) (f := fun _ => x)] rw [Finset.prod_const]
For a single qubit, the sum of the Pauli factor over all four choices in ℤ₂ × ℤ₂ equals x + 3. automation
The universe ℤ₂ × ℤ₂ is explicitly shown by finite decision (`decide`) to equal {(0, 0), (0, 1), (1, 0), (1, 1)}. Substituting this explicit four-element set and simplifying the sum evaluates the conditional on each pair: (0, 0) gives x, while (0, 1), (1, 0), and (1, 1) each give 1, summing to x + 1 + 1 + 1 = x + 3.
lemma sum_pow_pauli_size_sum_zmod2_sq (x : ℕ) : (∑ c : ZMod 2 × ZMod 2, (if c.1 = 0 then (if c.2 = 0 then x else 1) else 1)) = x + 3 := by have hu : (univ : Finset (ZMod 2 × ZMod 2)) = {(0, 0), (0, 1), (1, 0), (1, 1)} := by decide rw [hu] simp
The sum of x^(k - pauli_size p) over all Pauli labels is reindexed to a sum over functions g : Fin k → ℤ₂ × ℤ₂ of a per-qubit product.
Using the per-qubit product lemma `sum_pow_pauli_size_prod_per_qubit`, each term in the sum is expressed as a product over qubits. The sum over Pauli labels (Fin k → ℤ₂) × (Fin k → ℤ₂) is then reindexed into a sum over functions g : Fin k → ℤ₂ × ℤ₂ using `Equiv.sum_comp` with the canonical bijection `sum_pow_pauli_size_equiv`. Definitional equality (`rfl`) simplifies the components of the reindexed functions so that the factor at qubit i depends directly on g(i).
uses
sum_pow_pauli_size_prod_per_qubit,Equiv.sum_comp,sum_pow_pauli_size_equiv/-- Weight enumerator of Pauli labels: `∑ p, x^(k - pauli_size p) = (x+3)^k`. -/ theorem sum_pow_pauli_size (k x : ℕ) : ∑ p : PauliLabel k, x ^ (k - pauli_size p) = (x + 3) ^ k := by simp_rw [sum_pow_pauli_size_prod_per_qubit] rw [← Equiv.sum_comp (sum_pow_pauli_size_equiv k)] have h_prod : (∑ g : Fin k → ZMod 2 × ZMod 2, ∏ i : Fin k, (if (sum_pow_pauli_size_equiv k g).1 i = 0 then (if (sum_pow_pauli_size_equiv k g).2 i = 0 then x else 1) else 1)) = (∑ g : Fin k → ZMod 2 × ZMod 2, ∏ i : Fin k, (if (g i).1 = 0 then (if (g i).2 = 0 then x else 1) else 1)) := by rfl rw [h_prod]
Exchanging the summation over functions with the product over qubits yields a product of single-qubit sums.
By the generalized distributive law `Fintype.prod_sum` applied in reverse, the sum over all functions g : Fin k → ℤ₂ × ℤ₂ of the product over qubits equals the product over all qubits i of the sum over all choices c ∈ ℤ₂ × ℤ₂.
uses
Fintype.prod_sumhave h_swap := (@Fintype.prod_sum (Fin k) ℕ _ _ _ (fun _ => ZMod 2 × ZMod 2) _ (fun _ c => if c.1 = 0 then if c.2 = 0 then x else 1 else 1)).symm rw [h_swap]
The weight enumerator evaluates to (x + 3)^k.
Each single-qubit sum is replaced by x + 3 using `sum_pow_pauli_size_sum_zmod2_sq`. The product of this constant over the k qubits of Fin k evaluates to (x + 3)^k via `prod_const`, `card_univ`, and `Fintype.card_fin`.
uses
sum_pow_pauli_size_sum_zmod2_sq,prod_const,card_univ,Fintype.card_finsimp_rw [sum_pow_pauli_size_sum_zmod2_sq] rw [prod_const, card_univ, Fintype.card_fin]
Finset.card_filter_add_card_filter_not- For any finite set s and decidable predicate p, the number of elements in s satisfying p plus the number of elements satisfying ¬p equals the total cardinality of s.
Finset.filter_congr- Two predicates that are logically equivalent on every element of a finite set s select the same filtered subset of s.
card_univ- The cardinality of the universal finset `univ` of a finite type α equals the cardinality of the type α.
Fintype.card_fin- The cardinality of the standard finite set Fin n is n.
Finset.prod_congr- If two finite sets are equal and two functions agree on every element of the set, their products over that set are equal.
Finset.prod_filter- The product of f(a) over elements of s satisfying predicate p equals the product over all elements of s of the conditional expression taking f(a) when p(a) holds and 1 otherwise.
Finset.prod_const- The product of a constant value b over a finite set s equals b raised to the cardinality of s.
sum_pow_pauli_size_prod_per_qubit- The weight enumerator term x^(k - pauli_size p) for a Pauli label p equals the product over all qubits i of the conditional factor that yields x if both components of p at qubit i are zero and 1 otherwise.
Equiv.sum_comp- Summing a function over a finite type is invariant under precomposition with an equivalence of finite types (reindexing a sum).
sum_pow_pauli_size_equiv- The canonical equivalence between functions from Fin k to ℤ₂ × ℤ₂ and Pauli labels (Fin k → ℤ₂) × (Fin k → ℤ₂).
Fintype.prod_sum- The generalized distributive law: the product over i of sums over j of f(i, j) equals the sum over all choice functions x of the product over i of f(i, x(i)).
sum_pow_pauli_size_sum_zmod2_sq- The sum of the single-qubit factor over all four pairs in ℤ₂ × ℤ₂ equals x + 3.
prod_const- The product of a constant value over a finite set equals that constant raised to the cardinality of the set.
- In Step 3 (line 32), the four elements of ℤ₂ × ℤ₂ are enumerated by the `decide` tactic, which verifies the equality by computational exhaustion of the finite type.
- In Step 4 (lines 39–45), Lean requires the explicit type equivalence `sum_pow_pauli_size_equiv` between (Fin k → ℤ₂) × (Fin k → ℤ₂) and Fin k → (ℤ₂ × ℤ₂) in order to apply the generalized distributive law `Fintype.prod_sum`.
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.
open Finsetdef sum_pow_pauli_size_equiv (k : ℕ) : (Fin k → ZMod 2 × ZMod 2) ≃ PauliLabel k := Equiv.arrowProdEquivProdArrow (Fin k) (fun _ => ZMod 2) (fun _ => ZMod 2)lemma sum_pow_pauli_size_prod_per_qubit {k x : ℕ} (p : PauliLabel k) : x ^ (k - pauli_size p) = ∏ i : Fin k, (if p.1 i = 0 then (if p.2 i = 0 then x else 1) else 1) := by have hcard : k - pauli_size p = (univ.filter (fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0)).card := by show k - (univ.filter (fun i : Fin k => p.1 i ≠ 0 ∨ p.2 i ≠ 0)).card = _ have h2 := Finset.card_filter_add_card_filter_not (s := (univ : Finset (Fin k))) (p := fun i => p.1 i ≠ 0 ∨ p.2 i ≠ 0) have h3 : (univ.filter (fun i : Fin k => ¬ (p.1 i ≠ 0 ∨ p.2 i ≠ 0))) = univ.filter (fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0) := by apply Finset.filter_congr intro i _ simp rw [h3, card_univ, Fintype.card_fin] at h2 omega rw [hcard] have hstep : (∏ i : Fin k, (if p.1 i = 0 then (if p.2 i = 0 then x else 1) else 1)) = ∏ i : Fin k, (if (p.1 i = 0 ∧ p.2 i = 0) then x else 1) := by apply Finset.prod_congr rfl intro i _ by_cases h1 : p.1 i = 0 <;> by_cases h2 : p.2 i = 0 <;> simp [h1, h2] rw [hstep] rw [← Finset.prod_filter (s := univ) (p := fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0) (f := fun _ => x)] rw [Finset.prod_const]lemma sum_pow_pauli_size_sum_zmod2_sq (x : ℕ) : (∑ c : ZMod 2 × ZMod 2, (if c.1 = 0 then (if c.2 = 0 then x else 1) else 1)) = x + 3 := by have hu : (univ : Finset (ZMod 2 × ZMod 2)) = {(0, 0), (0, 1), (1, 0), (1, 1)} := by decide rw [hu] simp/-- Weight enumerator of Pauli labels: `∑ p, x^(k - pauli_size p) = (x+3)^k`. -/theorem sum_pow_pauli_size (k x : ℕ) : ∑ p : PauliLabel k, x ^ (k - pauli_size p) = (x + 3) ^ k := by simp_rw [sum_pow_pauli_size_prod_per_qubit] rw [← Equiv.sum_comp (sum_pow_pauli_size_equiv k)] have h_prod : (∑ g : Fin k → ZMod 2 × ZMod 2, ∏ i : Fin k, (if (sum_pow_pauli_size_equiv k g).1 i = 0 then (if (sum_pow_pauli_size_equiv k g).2 i = 0 then x else 1) else 1)) = (∑ g : Fin k → ZMod 2 × ZMod 2, ∏ i : Fin k, (if (g i).1 = 0 then (if (g i).2 = 0 then x else 1) else 1)) := by rfl rw [h_prod] have h_swap := (@Fintype.prod_sum (Fin k) ℕ _ _ _ (fun _ => ZMod 2 × ZMod 2) _ (fun _ c => if c.1 = 0 then if c.2 = 0 then x else 1 else 1)).symm rw [h_swap] simp_rw [sum_pow_pauli_size_sum_zmod2_sq] rw [prod_const, card_univ, Fintype.card_fin]