Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Appendix A (A1)–(A3): symmetry reduction coefficients

Open
QAlgorithms.Papers.Independent.Support50.P11.symmetry_reduction_coefficients

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

prove2quantum

Let d≥2d\ge2d≥2, n,K≥1n,K\ge1n,K≥1, and 0≤α≤10\le\alpha\le10≤α≤1. On the nnn input–output pairs let EjE_jEj​ sum all products with exactly jjj antisymmetric projectors and n−jn-jn−j symmetric projectors. Let Υi\Upsilon_iΥi​ sum products with exactly iii normalized Bell projectors and n−in-in−i complements. The EjE_jEj​ are orthogonal idempotents summing to the identity. For real x0,…,xnx_0,\ldots,x_nx0​,…,xn​ and Λ(x)=∑jxjEj\Lambda(x)=\sum_jx_jE_jΛ(x)=∑j​xj​Ej​,

ΓB(Λ(x))=∑iΥi∑jMijxj,Tr⁡BEj=gjIA′,\Gamma_B(\Lambda(x))=\sum_i\Upsilon_i\sum_jM_{ij}x_j,\qquad\operatorname{Tr}_BE_j=g_jI_{A'},ΓB​(Λ(x))=i∑​Υi​j∑​Mij​xj​,TrB​Ej​=gj​IA′​,

where

Mij=2−n∑k=max⁡(0,j−(n−i))min⁡(i,j)(n−ij−k)(ik)(1+d)i−k(1−d)k,gj=2−n(nj)(d+1)n−j(d−1)j.M_{ij}=2^{-n}\sum_{k=\max(0,j-(n-i))}^{\min(i,j)}\binom{n-i}{j-k}\binom ik(1+d)^{i-k}(1-d)^k,\quad g_j=2^{-n}\binom nj(d+1)^{n-j}(d-1)^j.Mij​=2−nk=max(0,j−(n−i))∑min(i,j)​(j−kn−i​)(ki​)(1+d)i−k(1−d)k,gj​=2−n(jn​)(d+1)n−j(d−1)j.

For any selected NS/PPTp flags, every primal feasible (ρ,Λ)(\rho,\Lambda)(ρ,Λ) for (W(d,α))⊗n(\mathcal W^{(d,\alpha)})^{\otimes n}(W(d,α))⊗n has a feasible pair (I/dn,Λ(x))(I/d^n,\Lambda(x))(I/dn,Λ(x)) with the identical full-transpose Choi objective. This is the lossless symmetry reduction, with the remaining identity on the input system.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P11
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder ENNReal

namespace QAlgorithms.Papers.Independent.Support50.P11

open QAlgorithms.Papers.Independent.Information100.P34 (choi dephasing permutationMatrix)

open QAlgorithms.Papers.Independent.Information100.P21 (pt)

open QAlgorithms.Papers.Independent.Dependency50.P09 (tensorAction)

open QAlgorithms.Papers.Independent.Information100.P76 (swapMatrix)

open QAlgorithms.Papers.Independent.Information100.P69 (replacer)

open QAlgorithms.Papers.Independent.Gap20.P19 (wernerIsometry)

attribute [local instance] Classical.propDecidable

attribute [local instance] Classical.decEq

/-- PDF pp.13--14, (A1)--(A3): sector orthogonality, exact partial transpose and
partial trace, and lossless averaging to rho=I/d^n and the real wernerSector ansatz.
The printed remaining-system identity is corrected from I_B to I_input. -/
theorem symmetry_reduction_coefficients
    (d n K : ℕ) (hd : 2 ≤ d) (hn : 0 < n) (hK : 0 < K)
    (alpha : ℝ) (ha0 : 0 ≤ alpha) (ha1 : alpha ≤ 1) (s p : Bool) :
    (∀ j : Fin (n + 1), sectorSum d n j * sectorSum d n j = sectorSum d n j) ∧
    (∀ i j : Fin (n + 1), i ≠ j → sectorSum d n i * sectorSum d n j = 0) ∧
    (∑ j : Fin (n + 1), sectorSum d n j) = 1 ∧
    (∀ x : Fin (n + 1) → ℝ,
      pt (ansatz d n x) = ∑ i : Fin (n + 1),
        ((∑ j, coeffM d n i j * x j : ℝ) : ℂ) • bellSectorSum d n i (by omega)) ∧
    (∀ j : Fin (n + 1), traceRight (sectorSum d n j) = (coeffG d n j : ℂ) • 1) ∧
    (∀ rho L, Primal K s p rho L →
      ∃ x : Fin (n + 1) → ℝ,
        Primal K s p (((d : ℂ)^n)⁻¹ • 1) (ansatz d n x) ∧
        primalObjective (piSuperop (fun _ : Fin n => wernerHolevoChannel d alpha)) L =
          primalObjective (piSuperop (fun _ : Fin n => wernerHolevoChannel d alpha)) (ansatz d n x)) := by sorry

end QAlgorithms.Papers.Independent.Support50.P11

end
Source
On the power of PPT-preserving and non-signalling codes, arXiv:1406.7142v2, PDF p. 13, Appendix A (A1)–(A3): symmetry reduction coefficients
Read-back

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

For all natural numbers d,n,Kd,n,Kd,n,K with d≥2d\ge2d≥2, n>0n>0n>0, and K>0K>0K>0, every real α∈[0,1]\alpha\in[0,1]α∈[0,1], and either Boolean value of each of s,ps,ps,p, make the following definitions. Let H={0,…,d−1}{0,…,n−1}H=\{0,\ldots,d-1\}^{\{0,\ldots,n-1\}}H={0,…,d−1}{0,…,n−1}, let S∣a,b⟩=∣b,a⟩S|a,b\rangle=|b,a\rangleS∣a,b⟩=∣b,a⟩, put P0=(I+S)/2P_0=(I+S)/2P0​=(I+S)/2, P1=(I−S)/2P_1=(I-S)/2P1​=(I−S)/2, and let B=∣Ωd⟩⟨Ωd∣B=|\Omega_d\rangle\langle\Omega_d|B=∣Ωd​⟩⟨Ωd​∣, where ∣Ωd⟩=d−1/2∑a∣a,a⟩|\Omega_d\rangle=d^{-1/2}\sum_a|a,a\rangle∣Ωd​⟩=d−1/2∑a​∣a,a⟩. For 0≤j≤n0\le j\le n0≤j≤n, define

Qj=∑t∈{0,1}n∣t∣=j⊠ℓ=0n−1Ptℓ,Rj=∑t∈{0,1}n∣t∣=j⊠ℓ=0n−1(tℓB+(1−tℓ)(I−B)),A(x)=∑j=0nxjQj,Q_j=\sum_{\substack{t\in\{0,1\}^n\\|t|=j}}\boxtimes_{\ell=0}^{n-1}P_{t_\ell}, \qquad R_j=\sum_{\substack{t\in\{0,1\}^n\\|t|=j}} \boxtimes_{\ell=0}^{n-1}(t_\ell B+(1-t_\ell)(I-B)), \qquad A(x)=\sum_{j=0}^{n}x_jQ_j,Qj​=t∈{0,1}n∣t∣=j​∑​⊠ℓ=0n−1​Ptℓ​​,Rj​=t∈{0,1}n∣t∣=j​∑​⊠ℓ=0n−1​(tℓ​B+(1−tℓ​)(I−B)),A(x)=j=0∑n​xj​Qj​,

where ∣t∣|t|∣t∣ counts the entries equal to 111, and (⊠ℓTℓ)(a,b),(a′,b′)=∏ℓ(Tℓ)(aℓ,bℓ),(aℓ′,bℓ′)(\boxtimes_\ell T_\ell)_{(a,b),(a',b')}=\prod_\ell(T_\ell)_{(a_\ell,b_\ell),(a'_\ell,b'_\ell)}(⊠ℓ​Tℓ​)(a,b),(a′,b′)​=∏ℓ​(Tℓ​)(aℓ​,bℓ​),(aℓ′​,bℓ′​)​. Define

Mij=2−n∑k=0min⁡(i,j){(n−ij−k)(ik)(1+d)i−k(1−d)k,j−k≤n−i,0,otherwise,Gj=2−n(nj)(d+1)n−j(d−1)j.M_{ij}=2^{-n}\sum_{k=0}^{\min(i,j)} \begin{cases} \displaystyle\binom{n-i}{j-k}\binom{i}{k}(1+d)^{i-k}(1-d)^k, &j-k\le n-i,\\ 0,&\text{otherwise}, \end{cases} \qquad G_j=2^{-n}\binom nj(d+1)^{n-j}(d-1)^j.Mij​=2−nk=0∑min(i,j)​⎩⎨⎧​(j−kn−i​)(ki​)(1+d)i−k(1−d)k,0,​j−k≤n−i,otherwise,​Gj​=2−n(jn​)(d+1)n−j(d−1)j.

All integer subtractions in these definitions are natural-number subtraction, truncated at zero. Write (ΓX)(a,b),(a′,b′)=X(a,b′),(a′,b)(\Gamma X)_{(a,b),(a',b')}=X_{(a,b'),(a',b)}(ΓX)(a,b),(a′,b′)​=X(a,b′),(a′,b)​, and let Nα=Wα⊗nN_\alpha=W_\alpha^{\otimes n}Nα​=Wα⊗n​, where

Wα(X)=1−αd+1(tr⁡(X)I+XT)+αd−1(tr⁡(X)I−XT);W_\alpha(X)=\frac{1-\alpha}{d+1}(\operatorname{tr}(X)I+X^{\mathsf T}) +\frac{\alpha}{d-1}(\operatorname{tr}(X)I-X^{\mathsf T});Wα​(X)=d+11−α​(tr(X)I+XT)+d−1α​(tr(X)I−XT);

the tensor map is specified on matrix units by Nα(Eaa′)bb′=∏ℓWα(Eaℓaℓ′)bℓbℓ′N_\alpha(E_{aa'})_{bb'}=\prod_\ell W_\alpha(E_{a_\ell a'_\ell})_{b_\ell b'_\ell}Nα​(Eaa′​)bb′​=∏ℓ​Wα​(Eaℓ​aℓ′​​)bℓ​bℓ′​​. Then every QjQ_jQj​ is idempotent, QiQj=0Q_iQ_j=0Qi​Qj​=0 whenever i≠ji\ne ji=j, ∑jQj=I\sum_jQ_j=I∑j​Qj​=I, and, for every real vector x=(x0,…,xn)x=(x_0,\ldots,x_n)x=(x0​,…,xn​),

ΓA(x)=∑i=0n(∑j=0nMijxj)Ri,tr⁡2Qj=GjI.\Gamma A(x)=\sum_{i=0}^{n}\left(\sum_{j=0}^{n}M_{ij}x_j\right)R_i, \qquad \operatorname{tr}_2Q_j=G_jI.ΓA(x)=i=0∑n​(j=0∑n​Mij​xj​)Ri​,tr2​Qj​=Gj​I.

Moreover, for every pair of complex matrices ρ\rhoρ on HHH and LLL on H×HH\times HH×H, suppose ρ\rhoρ is positive semidefinite with trace 111, 0≤L≤ρ⊗I0\le L\le\rho\otimes I0≤L≤ρ⊗I, and the following conditional requirements hold: if sss is true, tr⁡1L=K−2I\operatorname{tr}_1L=K^{-2}Itr1​L=K−2I; if ppp is true, −K−1ρ⊗I≤ΓL≤K−1ρ⊗I-K^{-1}\rho\otimes I\le\Gamma L\le K^{-1}\rho\otimes I−K−1ρ⊗I≤ΓL≤K−1ρ⊗I. There then exists a real vector xxx for which the same requirements hold with ρ\rhoρ replaced by d−nId^{-n}Id−nI and LLL replaced by A(x)A(x)A(x), and

Re⁡tr⁡(JNαTL)=Re⁡tr⁡(JNαTA(x)),(JNα)(a,b),(a′,b′)=Nα(Eaa′)bb′.\operatorname{Re}\operatorname{tr}(J_{N_\alpha}^{\mathsf T}L) =\operatorname{Re}\operatorname{tr}(J_{N_\alpha}^{\mathsf T}A(x)), \qquad (J_{N_\alpha})_{(a,b),(a',b')}=N_\alpha(E_{aa'})_{bb'}.Retr(JNα​T​L)=Retr(JNα​T​A(x)),(JNα​​)(a,b),(a′,b′)​=Nα​(Eaa′​)bb′​.

Each matrix inequality means positive semidefiniteness of the difference; when a flag is false, its associated conditional requirement imposes no restriction.

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