Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Attainable fixed-inner coset-entropy concatenation rate

Open
QAlgorithms.Papers.Independent.Support50.P40.cosetEntropy_rate

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

prove2quantum

Fix a normalized additive [p,1,d][p,1,d][p,1,d] inner code, p≥1p\ge1p≥1, and complete syndrome and logical-Pauli coset representatives. Its phase-inclusive commuting stabilizer excludes −I-I−I and has p−1p-1p−1 independent generators. For independent depolarization with f∈[0,1]f\in[0,1]f∈[0,1], define ai=Pf(eiSˉ⊥)a_i=P_f(e_i\bar S^\perp)ai​=Pf​(ei​Sˉ⊥) and bij=Pf(eisjSˉ)b_{ij}=P_f(e_i s_j\bar S)bij​=Pf​(ei​sj​Sˉ), where jjj ranges over the four logical Paulis and iii over 2p−12^{p-1}2p−1 syndromes. Write HHH for finite entropy in bits, with 0log⁡20=00\log_2 0=00log2​0=0, and set SX2=∑i:ai>0aiH((bij/ai)j)S_{X2}=\sum_{i:a_i>0}a_iH((b_{ij}/a_i)_j)SX2​=∑i:ai​>0​ai​H((bij​/ai​)j​).

The signed yield satisfies

qC(f)=1+H((ai)i)−H((bij)i,j)p=1−SX2p.q_C(f)=\frac{1+H((a_i)_i)-H((b_{ij})_{i,j})}{p} =\frac{1-S_{X2}}p.qC​(f)=p1+H((ai​)i​)−H((bij​)i,j​)​=p1−SX2​​.

If qC(f)>0q_C(f)>0qC​(f)>0, it is attainable by keeping this inner code fixed and increasing the additive outer block size. Precisely, for every ϵ,δ>0\epsilon,\delta>0ϵ,δ>0, all sufficiently large outer sizes nnn admit kkk logical qubits, an additive outer isometric encoder, and a local CPTP decoder such that k≥(qC(f)−δ)pnk\ge(q_C(f)-\delta)pnk≥(qC​(f)−δ)pn. One choice of encoder and decoder works for every normalized unknown input with fidelity at least 1−ϵ1-\epsilon1−ϵ, and has entanglement fidelity at least 1−ϵ1-\epsilon1−ϵ. The scheme uses pnpnpn physical noisy channel calls and no preshared entanglement or side communication.

Attainability is attributed by the paper to Shor–Smolin [14]; the compact coset formula is the present paper's derivation. Negative signed yields are not negative capacities.

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 pp.11--13, Eqs.(13)--(20), Fig.4 p.28. Attainability of the
concatenation scheme is attributed on p.11 to Shor--Smolin [14],
quant-ph/9604006; this paper derives its coset-entropy expression. The
positive signed yield is attained by this fixed-inner scheme, not merely
bounded by an unrelated capacity parameter. -/
theorem cosetEntropy_rate {m : ℕ} (C : InnerCode m) (T : CosetChoices C)
    (f : ℝ) (hf0 : 0 ≤ f) (hf1 : f ≤ 1) :
    signedYield C T f = (1 - conditionalBellEntropy C T f) / (m + 1) ∧
    (0 < signedYield C T f → FixedInnerAchievable C f (signedYield C T f)) := by sorry

end

end QAlgorithms.Papers.Independent.Support50.P40
Source
Quantum Channel Capacity of Very Noisy Channels, arXiv:quant-ph/9706061v3, PDF p. 11, Section III, Eqs. (13)-(20): attainable coset-entropy concatenation rate
Read-back

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

Let mmm be any natural number, put r=m+1r=m+1r=m+1, and write Qa={0,1}aQ_a=\{0,1\}^aQa​={0,1}a. For a Pauli label string eee, let PeP_ePe​ be its tensor product of the usual matrices I,X,Y,ZI,X,Y,ZI,X,Y,Z, with Y0,1=−iY_{0,1}=-\mathrm iY0,1​=−i, and let w(e)w(e)w(e) count its nonidentity entries. Write Pa\mathcal P_aPa​ for the subgroup of unitary matrices generated by all icPe\mathrm i^cP_eicPe​ on aaa qubits, where c∈{0,1,2,3}c\in\{0,1,2,3\}c∈{0,1,2,3}. The inner-code data consist of an abelian subgroup S≤PrS\le\mathcal P_rS≤Pr​ containing no −I-I−I, and orthonormal vectors v0,v1v_0,v_1v0​,v1​ spanning exactly the common fixed space of SSS. Define the label sets

A={e:∃U∈S, ∃c∈{0,1,2,3}, Pe=icU},B={e:∀U∈S, PeU=UPe},A=\{e:\exists U\in S,\ \exists c\in\{0,1,2,3\},\ P_e=\mathrm i^cU\}, \qquad B=\{e:\forall U\in S,\ P_eU=UP_e\},A={e:∃U∈S, ∃c∈{0,1,2,3}, Pe​=icU},B={e:∀U∈S, Pe​U=UPe​},

and require ∣A∣=2m|A|=2^m∣A∣=2m. Let VVV be the matrix with columns v0,v1v_0,v_1v0​,v1​. Multiplication ⊙\odot⊙ of labels discards Pauli phases, equivalently adding modulo 222 the pairs I=(0,0)I=(0,0)I=(0,0), X=(1,0)X=(1,0)X=(1,0), Y=(1,1)Y=(1,1)Y=(1,1), Z=(0,1)Z=(0,1)Z=(0,1) at each coordinate. The representative data are strings sis_isi​, indexed by i∈Qmi\in Q_mi∈Qm​, and ℓj\ell_jℓj​, indexed by Pauli labels jjj, such that s0=ℓIs_0=\ell_Is0​=ℓI​ is the all-identity string, every label string belongs to exactly one set si⊙Bs_i\odot Bsi​⊙B, every ℓj∈B\ell_j\in Bℓj​∈B, every element of BBB belongs to exactly one set ℓj⊙A\ell_j\odot Aℓj​⊙A, and PℓjVρV†Pℓj†=Vjρj†V†P_{\ell_j}V\rho V^\dagger P_{\ell_j}^\dagger=Vj\rho j^\dagger V^\daggerPℓj​​VρV†Pℓj​†​=Vjρj†V† for every complex 2×22\times22×2 matrix ρ\rhoρ. For every real fff satisfying 0≤f≤10\le f\le10≤f≤1, define

νf(e)=fr−w(e)(1−f3)w(e),sf(i)=∑e∈si⊙Bνf(e),jf(i,j)=∑e∈(si⊙ℓj)⊙Aνf(e),H(a)=−∑xaxlog⁡2(ax),Y=1+H(sf)−H((jf(i,j))i,j)r,Hcond=∑i∈Qm{0,sf(i)=0,sf(i) H((jf(i,j)/sf(i))j∈{I,X,Y,Z}),sf(i)≠0.\begin{gathered} \nu_f(e)=f^{r-w(e)}\left(\frac{1-f}{3}\right)^{w(e)},\qquad s_f(i)=\sum_{e\in s_i\odot B}\nu_f(e),\qquad j_f(i,j)=\sum_{e\in(s_i\odot\ell_j)\odot A}\nu_f(e),\\ H(a)=-\sum_xa_x\log_2(a_x),\qquad Y=\frac{1+H(s_f)-H((j_f(i,j))_{i,j})}{r},\\ H_{\mathrm{cond}}= \sum_{i\in Q_m} \begin{cases} 0,&s_f(i)=0,\\ s_f(i)\,H\bigl((j_f(i,j)/s_f(i))_{j\in\{I,X,Y,Z\}}\bigr),&s_f(i)\ne0. \end{cases} \end{gathered}νf​(e)=fr−w(e)(31−f​)w(e),sf​(i)=e∈si​⊙B∑​νf​(e),jf​(i,j)=e∈(si​⊙ℓj​)⊙A∑​νf​(e),H(a)=−x∑​ax​log2​(ax​),Y=r1+H(sf​)−H((jf​(i,j))i,j​)​,Hcond​=i∈Qm​∑​{0,sf​(i)H((jf​(i,j)/sf​(i))j∈{I,X,Y,Z}​),​sf​(i)=0,sf​(i)=0.​​

The total real logarithm gives a zero contribution at a zero entry. The theorem asserts

Y=1−Hcondr,Y=\frac{1-H_{\mathrm{cond}}}{r},Y=r1−Hcond​​,

and further asserts the following implication if Y>0Y>0Y>0. For every ϵ>0\epsilon>0ϵ>0 and δ>0\delta>0δ>0, there is a natural number n0n_0n0​ such that, for every natural number n≥n0n\ge n_0n≥n0​, there exist a natural number kkk, an encoder matrix E:CQk→CQnE:\mathbb C^{Q_k}\to\mathbb C^{Q_n}E:CQk​→CQn​, and a decoding map DDD from matrices on CQrn\mathbb C^{Q_r^n}CQrn​ to matrices on CQk\mathbb C^{Q_k}CQk​, with

(Y−δ)rn≤k,k≤n,E†E=I.(Y-\delta)rn\le k,\qquad k\le n,\qquad E^\dagger E=I.(Y−δ)rn≤k,k≤n,E†E=I.

The range of EEE must be the common fixed space of some abelian subgroup S′≤PnS'\le\mathcal P_nS′≤Pn​ containing no −I-I−I. The map DDD must admit a finite Kraus representation D(X)=∑aLaXLa†D(X)=\sum_aL_aXL_a^\daggerD(X)=∑a​La​XLa†​ with ∑aLa†La=I\sum_aL_a^\dagger L_a=I∑a​La†​La​=I. Define

Γf(X)=∑e∈{I,X,Y,Z}rνf(e)PeXPe†,(Bn)y,x=∏t=0n−1vxt(yt),\Gamma_f(X)=\sum_{e\in\{I,X,Y,Z\}^{r}}\nu_f(e)P_eXP_e^\dagger,\qquad (B_n)_{y,x}=\prod_{t=0}^{n-1}v_{x_t}(y_t),Γf​(X)=e∈{I,X,Y,Z}r∑​νf​(e)Pe​XPe†​,(Bn​)y,x​=t=0∏n−1​vxt​​(yt​),

where x∈Qnx\in Q_nx∈Qn​ and y∈Qrny\in Q_r^ny∈Qrn​, and define the transmission map

T=D∘Γf⊗n∘(X↦BnXBn†)∘(X↦EXE†).\mathcal T =D\circ\Gamma_f^{\otimes n}\circ(X\mapsto B_nXB_n^\dagger) \circ(X\mapsto EXE^\dagger).T=D∘Γf⊗n​∘(X↦Bn​XBn†​)∘(X↦EXE†).

Here Γf⊗n\Gamma_f^{\otimes n}Γf⊗n​ is the linear tensor product map, applying Γf\Gamma_fΓf​ to each matrix factor. For

∣Φk⟩=2−k/2∑x∈Qk∣x,x⟩,|\Phi_k\rangle=2^{-k/2}\sum_{x\in Q_k}|x,x\rangle,∣Φk​⟩=2−k/2x∈Qk​∑​∣x,x⟩,

the required conclusions are

1−ϵ≤Re⁡⟨Φk∣(id⊗T)(∣Φk⟩⟨Φk∣)∣Φk⟩1-\epsilon\le \operatorname{Re}\langle\Phi_k| (\mathrm{id}\otimes\mathcal T)(|\Phi_k\rangle\langle\Phi_k|) |\Phi_k\rangle1−ϵ≤Re⟨Φk​∣(id⊗T)(∣Φk​⟩⟨Φk​∣)∣Φk​⟩

and, for every vector ψ∈CQk\psi\in\mathbb C^{Q_k}ψ∈CQk​ with ∥ψ∥=1\|\psi\|=1∥ψ∥=1,

1−ϵ≤Re⁡tr⁡(∣ψ⟩⟨ψ∣ T(∣ψ⟩⟨ψ∣)).1-\epsilon\le \operatorname{Re}\operatorname{tr} \bigl(|\psi\rangle\langle\psi|\, \mathcal T(|\psi\rangle\langle\psi|)\bigr).1−ϵ≤Retr(∣ψ⟩⟨ψ∣T(∣ψ⟩⟨ψ∣)).

The statement allows m=0m=0m=0, f=0,1f=0,1f=0,1, and k=0k=0k=0; empty tensor products have value 111. When Y≤0Y\le0Y≤0, the achievability implication imposes no requirement.

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