Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Coset weight polynomials and Shor–Laflamme enumerators

Proved
QAlgorithms.Papers.Independent.Support50.P40.shorLaflamme_relation

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

prove2quantum

Let p≥0p\ge0p≥0 and let CCC be a finite set of canonical Hermitian ppp-qubit Pauli labels, with scalar phases discarded. Write w(e)w(e)w(e) for the number of nonidentity factors, g=(1−f)/3g=(1-f)/3g=(1−f)/3 for f∈[0,1]f\in[0,1]f∈[0,1], and Pf(C)=∑e∈Cfp−w(e)gw(e)P_f(C)=\sum_{e\in C}f^{p-w(e)}g^{w(e)}Pf​(C)=∑e∈C​fp−w(e)gw(e). Using ordinary matrix traces, define Ad(O1,O2)=∑w(u)=dtr⁡(uO1)tr⁡(uO2)A_d(O_1,O_2)=\sum_{w(u)=d}\operatorname{tr}(uO_1)\operatorname{tr}(uO_2)Ad​(O1​,O2​)=∑w(u)=d​tr(uO1​)tr(uO2​) and A(z,O1,O2)=∑d=0pAd(O1,O2)zdA(z,O_1,O_2)=\sum_{d=0}^p A_d(O_1,O_2)z^dA(z,O1​,O2​)=∑d=0p​Ad​(O1​,O2​)zd.

Then, for every Pauli label eee and nonnegative integer ddd,

Ad(e,e)=4p1{w(e)=d},Pf(C)=4−p∑e∈C∑d=0pAd(e,e)fp−dgd.A_d(e,e)=4^p\mathbf1_{\{w(e)=d\}},\qquad P_f(C)=4^{-p}\sum_{e\in C}\sum_{d=0}^p A_d(e,e)f^{p-d}g^d.Ad​(e,e)=4p1{w(e)=d}​,Pf​(C)=4−pe∈C∑​d=0∑p​Ad​(e,e)fp−dgd.

For f>0f>0f>0 one also has

Pf(C)=fp4p∑e∈CA(g/f,e,e)=(f4)p∑e∈CA(1−f3f,e,e).P_f(C)=\frac{f^p}{4^p}\sum_{e\in C}A(g/f,e,e) =\left(\frac f4\right)^p\sum_{e\in C}A\left(\frac{1-f}{3f},e,e\right).Pf​(C)=4pfp​e∈C∑​A(g/f,e,e)=(4f​)pe∈C∑​A(3f1−f​,e,e).

This identifies the probability polynomials with the earlier enumerators. The division-free formula remains valid at f=0f=0f=0.

Formalization Note The first double sum in printed Eq. (6) omits 4−p4^{-p}4−p. The statement includes the normalization forced by Eq. (5) and both right-hand expressions; independent moderation of this correction remains required.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P40
Formal statement
namespace QAlgorithms.Papers.Independent.Support50.P40

open QAlgorithms QAlgorithms.Stabilizer

open scoped ComplexConjugate Matrix

noncomputable section

/-- PDF p.7, Eqs.(5)--(6). Source correction: the first double sum in
printed Eq.(6) omits `4^(-p)`; Eq.(5) and both right-hand expressions force
this factor. The polynomial identity includes f=0; only the ratio form
requires f>0. No quantum-state hypothesis is needed for matrix enumerators. -/
theorem shorLaflamme_relation (p : ℕ) (C : Finset (ErrorLabel p))
    (f : ℝ) (hf0 : 0 ≤ f) (hf1 : f ≤ 1) :
    (∀ (e : ErrorLabel p) (d : ℕ),
      slWeight d (pauliOps e) (pauliOps e) =
        if opsWeight e = d then (4 : ℂ) ^ p else 0) ∧
    ((weightPolynomial f C : ℂ) = ((4 : ℂ) ^ p)⁻¹ *
      ∑ e ∈ C, ∑ d ∈ Finset.range (p + 1),
        slWeight d (pauliOps e) (pauliOps e) * (f : ℂ) ^ (p - d) * (noiseG f : ℂ) ^ d) ∧
    (0 < f →
      (weightPolynomial f C : ℂ) = (f : ℂ) ^ p / (4 : ℂ) ^ p *
        ∑ e ∈ C, slEnumerator ((noiseG f : ℂ) / (f : ℂ)) (pauliOps e) (pauliOps e) ∧
      (weightPolynomial f C : ℂ) = ((f : ℂ) / 4) ^ p *
        ∑ e ∈ C, slEnumerator (((1 - f) / (3 * f) : ℝ) : ℂ) (pauliOps e) (pauliOps e)) := by sorry

end

end QAlgorithms.Papers.Independent.Support50.P40
Source
Quantum Channel Capacity of Very Noisy Channels, arXiv:quant-ph/9706061v3, PDF p. 7, Section II, Eqs. (5)-(6): relation to Shor-Laflamme enumerators
Read-back

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

For every natural number ppp, every finite set CCC of length-ppp strings over {I,X,Y,Z}\{I,X,Y,Z\}{I,X,Y,Z}, and every real fff satisfying 0≤f≤10\le f\le10≤f≤1, set g=(1−f)/3g=(1-f)/3g=(1−f)/3. Order the Boolean basis as 0,10,10,1, and use the Pauli matrices

I=(1001),X=(0110),Y=(0−ii0),Z=(100−1).I=\begin{pmatrix}1&0\\0&1\end{pmatrix},\quad X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad Y=\begin{pmatrix}0&-\mathrm i\\ \mathrm i&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.I=(10​01​),X=(01​10​),Y=(0i​−i0​),Z=(10​0−1​).

For a label string eee, write Pe=⨂q=0p−1eqP_e=\bigotimes_{q=0}^{p-1}e_qPe​=⨂q=0p−1​eq​ and let w(e)w(e)w(e) count its nonidentity labels. Define

Wf(C)=∑e∈Cfp−w(e)gw(e),Ld(A,B)=∑u∈{I,X,Y,Z}pw(u)=dtr⁡(PuA)tr⁡(PuB),L(z;A,B)=∑d=0pLd(A,B)zd.W_f(C)=\sum_{e\in C}f^{p-w(e)}g^{w(e)},\qquad L_d(A,B)=\sum_{\substack{u\in\{I,X,Y,Z\}^{p}\\w(u)=d}} \operatorname{tr}(P_uA)\operatorname{tr}(P_uB), \qquad L(z;A,B)=\sum_{d=0}^{p}L_d(A,B)z^d.Wf​(C)=e∈C∑​fp−w(e)gw(e),Ld​(A,B)=u∈{I,X,Y,Z}pw(u)=d​∑​tr(Pu​A)tr(Pu​B),L(z;A,B)=d=0∑p​Ld​(A,B)zd.

The traces in LdL_dLd​ are multiplied without complex conjugation. The theorem asserts all of the following equalities:

∀e∈{I,X,Y,Z}p ∀d∈N,Ld(Pe,Pe)={4p,w(e)=d,0,w(e)≠d,Wf(C)=4−p∑e∈C∑d=0pLd(Pe,Pe)fp−dgd,\begin{gathered} \forall e\in\{I,X,Y,Z\}^{p}\ \forall d\in\mathbb N,\qquad L_d(P_e,P_e)= \begin{cases} 4^p,&w(e)=d,\\ 0,&w(e)\ne d, \end{cases}\\ W_f(C)=4^{-p}\sum_{e\in C}\sum_{d=0}^{p} L_d(P_e,P_e)f^{p-d}g^d, \end{gathered}∀e∈{I,X,Y,Z}p ∀d∈N,Ld​(Pe​,Pe​)={4p,0,​w(e)=d,w(e)=d,​Wf​(C)=4−pe∈C∑​d=0∑p​Ld​(Pe​,Pe​)fp−dgd,​

where the real quantity on the left is embedded into C\mathbb CC; moreover, if f>0f>0f>0, it asserts both

Wf(C)=fp4p∑e∈CL(g/f;Pe,Pe)andWf(C)=(f4)p∑e∈CL(1−f3f;Pe,Pe).W_f(C)=\frac{f^p}{4^p}\sum_{e\in C}L(g/f;P_e,P_e) \quad\text{and}\quad W_f(C)=\left(\frac f4\right)^p \sum_{e\in C}L\left(\frac{1-f}{3f};P_e,P_e\right).Wf​(C)=4pfp​e∈C∑​L(g/f;Pe​,Pe​)andWf​(C)=(4f​)pe∈C∑​L(3f1−f​;Pe​,Pe​).

The parameter ddd in the first assertion is unrestricted, including d>pd>pd>p, when its defining sum is empty. The theorem includes C=∅C=\varnothingC=∅, p=0p=0p=0, and the endpoints f=0,1f=0,1f=0,1; the final two equalities are required only under the additional hypothesis f>0f>0f>0. At p=0p=0p=0, the tensor product is the scalar identity on the unique empty Boolean string, and all zero-exponent powers equal 111.

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