Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Unnumbered generalization of Theorem 2 to k-local Pauli sums

Open
QAlgorithms.Papers.Independent.Support50.P30.kLocalPauli_formulas

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Fix 0≤k≤n0\le k\le n0≤k≤n, one Pauli matrix χ∈{X,Y,Z}\chi\in\{X,Y,Z\}χ∈{X,Y,Z}, and let Aχ(k)A_\chi^{(k)}Aχ(k)​ be the sum of the corresponding Pauli string over each kkk-element subset of qubits exactly once. Put Kk(w;n)=∑l=0k(n−wk−l)(wl)(−1)lK_k(w;n)=\sum_{l=0}^k\binom{n-w}{k-l}\binom wl(-1)^lKk​(w;n)=∑l=0k​(k−ln−w​)(lw​)(−1)l. In the computational basis for χ=Z\chi=Zχ=Z,

AZ(k)∣z⟩=Kk(w(z);n)∣z⟩.A_Z^{(k)}|z\rangle=K_k(w(z);n)|z\rangle.AZ(k)​∣z⟩=Kk​(w(z);n)∣z⟩.

For the common block in any fixed Schur sector λ=(n−m,m)\lambda=(n-m,m)λ=(n−m,m), with dλ=n−2m+1d_\lambda=n-2m+1dλ​=n−2m+1, all three choices of χ\chiχ satisfy

Tr⁡Aχ,λ(k)=∑w=mn−mKk(w;n),Tr⁡((Aχ,λ(k))2)=∑w=mn−mKk(w;n)2,\operatorname{Tr}A_{\chi,\lambda}^{(k)}=\sum_{w=m}^{n-m}K_k(w;n),\qquad \operatorname{Tr}\bigl((A_{\chi,\lambda}^{(k)})^2\bigr)=\sum_{w=m}^{n-m}K_k(w;n)^2,TrAχ,λ(k)​=w=m∑n−m​Kk​(w;n),Tr((Aχ,λ(k)​)2)=w=m∑n−m​Kk​(w;n)2, Δ(Aχ,λ(k))=∑w=mn−mKk(w;n)2−(∑w=mn−mKk(w;n))2dλ.\Delta(A_{\chi,\lambda}^{(k)})=\sum_{w=m}^{n-m}K_k(w;n)^2-\frac{\bigl(\sum_{w=m}^{n-m}K_k(w;n)\bigr)^2}{d_\lambda}.Δ(Aχ,λ(k)​)=w=m∑n−m​Kk​(w;n)2−dλ​(∑w=mn−m​Kk​(w;n))2​.

At k=0k=0k=0 the operator is the identity and its centered statistic is zero. The formulas extend the three special families of Theorem 2.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P30
Formal statement
noncomputable section

open MeasureTheory

open scoped BigOperators ComplexConjugate Matrix.Norms.L2Operator NNReal ENNReal

namespace QAlgorithms.Papers.Independent.Support50.P30

attribute [local instance] LieRing.ofAssociativeRing

/-- PDF p.29, Eqs.(61)-(65): computational eigenvalue, trace, squared trace,
and Delta. The weight range m,...,n-m has exactly d_lambda entries. -/
theorem kLocalPauli_formulas {n : ℕ} (k : ℕ) (hk : k ≤ n)
    (S : SchurFrame n) (m : Sector n)
    (chi : Matrix Bool Bool ℂ) (hchi : chi ∈ ({pauliX, pauliY, pauliZ} : Set _)) :
    (∀ z : Qubits n, act (collective n pauliZ k) (ket z) =
      (krawtchouk n k (hammingWeight z) : ℂ) • ket z) ∧
    (commonBlock S m (collective n chi k)).trace.re =
      ∑ j : Fin (blockDim n m), krawtchouk n k (m.val + j.val) ∧
    ((commonBlock S m (collective n chi k)) ^ 2).trace.re =
      ∑ j : Fin (blockDim n m), (krawtchouk n k (m.val + j.val)) ^ 2 ∧
    centeredDelta (commonBlock S m (collective n chi k)) =
      (∑ j : Fin (blockDim n m), (krawtchouk n k (m.val + j.val)) ^ 2) -
      (∑ j : Fin (blockDim n m), krawtchouk n k (m.val + j.val)) ^ 2 /
        (blockDim n m : ℝ) := by sorry

end QAlgorithms.Papers.Independent.Support50.P30

end
Source
Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks, arXiv:2210.09974v3, PDF p. 29, Unnumbered generalization of Theorem 2 to k-local Pauli sums
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every natural number nnn, every natural number k≤nk\le nk≤n, every Schur frame SSS described below, every sector 0≤m≤⌊n/2⌋0\le m\le\lfloor n/2\rfloor0≤m≤⌊n/2⌋, and every χ\chiχ belonging to {X,Y,Z}\{X,Y,Z\}{X,Y,Z}, where X=(0110)X=\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)X=(01​10​), Y=(0−ii0)Y=\left(\begin{smallmatrix}0&-\mathrm i\\\mathrm i&0\end{smallmatrix}\right)Y=(0i​−i0​), and Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), the following four assertions hold. Define Cχ,kC_{\chi,k}Cχ,k​ as the sum of tensor products applying χ\chiχ on each kkk-element subset of qubit positions and identity elsewhere, and put

K(n,k,w)=∑ℓ=0k(n−wk−ℓ)(wℓ)(−1)ℓ,dh=n−2h+1,rh=(nh)−{0,h=0,(nh−1),h>0.K(n,k,w)=\sum_{\ell=0}^k\binom{n-w}{k-\ell}\binom w\ell(-1)^\ell,\qquad d_h=n-2h+1,\qquad r_h=\binom nh-\begin{cases}0,&h=0,\\\binom n{h-1},&h>0.\end{cases}K(n,k,w)=ℓ=0∑k​(k−ℓn−w​)(ℓw​)(−1)ℓ,dh​=n−2h+1,rh​=(hn​)−{0,(h−1n​),​h=0,h>0.​

Natural-number subtraction in these definitions is truncated at zero. A Schur frame is a matrix SSS with columns indexed by nnn-bit strings and rows indexed by (h,ν,j)(h,\nu,j)(h,ν,j) for 0≤h≤⌊n/2⌋0\le h\le\lfloor n/2\rfloor0≤h≤⌊n/2⌋, 0≤ν<rh0\le\nu<r_h0≤ν<rh​, and 0≤j<dh0\le j<d_h0≤j<dh​, satisfying SS†=S†S=ISS^\dagger=S^\dagger S=ISS†=S†S=I; every matrix commuting with all permutations ∣x⟩↦∣x∘p−1⟩|x\rangle\mapsto|x\circ p^{-1}\rangle∣x⟩↦∣x∘p−1⟩ becomes, upon conjugation by SSS, block diagonal with rhr_hrh​ identical dh×dhd_h\times d_hdh​×dh​ blocks in sector hhh. Also, S(CX,12+CY,12+CZ,12)S†S(C_{X,1}^2+C_{Y,1}^2+C_{Z,1}^2)S^\daggerS(CX,12​+CY,12​+CZ,12​)S† has repeated sector-hhh block (n−2h)(n−2h+2)Idh(n-2h)(n-2h+2)I_{d_h}(n−2h)(n−2h+2)Idh​​. Let Rm,νR_{m,\nu}Rm,ν​ be the rows of SSS belonging to (m,ν)(m,\nu)(m,ν), write Bm(A)=rm−1∑νRm,νARm,ν†B_m(A)=r_m^{-1}\sum_\nu R_{m,\nu}AR_{m,\nu}^\daggerBm​(A)=rm−1​∑ν​Rm,ν​ARm,ν†​, and define

Δ(B)=Re⁡(tr⁡(B2)−(tr⁡B)2dm)for B∈Cdm×dm.\Delta(B)=\operatorname{Re}\left(\operatorname{tr}(B^2)-\frac{(\operatorname{tr}B)^2}{d_m}\right) \quad\text{for }B\in\mathbb C^{d_m\times d_m}.Δ(B)=Re(tr(B2)−dm​(trB)2​)for B∈Cdm​×dm​.

Then, writing w(z)w(z)w(z) for the number of true bits of zzz and ∣z⟩|z\rangle∣z⟩ for its coordinate basis vector,

CZ,k∣z⟩=K(n,k,w(z))∣z⟩for every n-bit string z,Re⁡tr⁡(Bm(Cχ,k))=∑j=0dm−1K(n,k,m+j),Re⁡tr⁡(Bm(Cχ,k)2)=∑j=0dm−1K(n,k,m+j)2,Δ(Bm(Cχ,k))=∑j=0dm−1K(n,k,m+j)2−(∑j=0dm−1K(n,k,m+j))2dm.\begin{aligned} C_{Z,k}|z\rangle&=K(n,k,w(z))|z\rangle &&\text{for every }n\text{-bit string }z,\\ \operatorname{Re}\operatorname{tr}\bigl(B_m(C_{\chi,k})\bigr) &=\sum_{j=0}^{d_m-1}K(n,k,m+j),\\ \operatorname{Re}\operatorname{tr}\bigl(B_m(C_{\chi,k})^2\bigr) &=\sum_{j=0}^{d_m-1}K(n,k,m+j)^2,\\ \Delta\bigl(B_m(C_{\chi,k})\bigr) &=\sum_{j=0}^{d_m-1}K(n,k,m+j)^2 -\frac{\left(\sum_{j=0}^{d_m-1}K(n,k,m+j)\right)^2}{d_m}. \end{aligned}CZ,k​∣z⟩Retr(Bm​(Cχ,k​))Retr(Bm​(Cχ,k​)2)Δ(Bm​(Cχ,k​))​=K(n,k,w(z))∣z⟩=j=0∑dm​−1​K(n,k,m+j),=j=0∑dm​−1​K(n,k,m+j)2,=j=0∑dm​−1​K(n,k,m+j)2−dm​(∑j=0dm​−1​K(n,k,m+j))2​.​for every n-bit string z,

These assertions include k=0k=0k=0, when Cχ,0=IC_{\chi,0}=ICχ,0​=I and K(n,0,w)=1K(n,0,w)=1K(n,0,w)=1, and include n=0n=0n=0 with its sole sector m=0m=0m=0.

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me