Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3: quantum Marton inner bound without a common message

Open
QAlgorithms.Papers.Independent.Support50.P26.marton_inner_bound

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

prove2quantum

Let x↦ρxB1B2x\mapsto\rho_x^{B_1B_2}x↦ρxB1​B2​​ be a finite classical–quantum broadcast channel, with nonempty input alphabet XXX and nonzero finite output dimensions. Choose any finite nonempty auxiliary alphabets U1,U2U_1,U_2U1​,U2​, any joint probability law p(u1,u2)p(u_1,u_2)p(u1​,u2​), and any deterministic function f:U1×U2→Xf:U_1\times U_2\to Xf:U1​×U2​→X. Compute the information quantities in bits from the actual state

θU1U2B1B2=∑u1,u2p(u1,u2)∣u1⟩⟨u1∣⊗∣u2⟩⟨u2∣⊗ρf(u1,u2)B1B2.\theta^{U_1U_2B_1B_2}=\sum_{u_1,u_2}p(u_1,u_2)|u_1\rangle\langle u_1|\otimes|u_2\rangle\langle u_2|\otimes\rho_{f(u_1,u_2)}^{B_1B_2}.θU1​U2​B1​B2​=u1​,u2​∑​p(u1​,u2​)∣u1​⟩⟨u1​∣⊗∣u2​⟩⟨u2​∣⊗ρf(u1​,u2​)B1​B2​​.

Let M(p,f)\mathcal M(p,f)M(p,f) consist of the nonnegative pairs obeying

R1≤I(U1;B1)θ,R2≤I(U2;B2)θ,R1+R2≤I(U1;B1)θ+I(U2;B2)θ−I(U1;U2)θ.R_1\le I(U_1;B_1)_\theta,\quad R_2\le I(U_2;B_2)_\theta,\quad R_1+R_2\le I(U_1;B_1)_\theta+I(U_2;B_2)_\theta-I(U_1;U_2)_\theta.R1​≤I(U1​;B1​)θ​,R2​≤I(U2​;B2​)θ​,R1​+R2​≤I(U1​;B1​)θ​+I(U2​;B2​)θ​−I(U1​;U2​)θ​.

Every pair in the unrestricted union of these regions is operationally achievable: for every ϵ,δ>0\epsilon,\delta>0ϵ,δ>0, all sufficiently large positive block lengths admit a deterministic code with rates at least Ri−δR_i-\deltaRi​−δ and average joint decoding error at most ϵ\epsilonϵ, using independent uniform messages and separate collective receiver POVMs. Furthermore,

⋃U1,U2,p,fM(p,f)=⋃∣U1∣,∣U2∣≤∣X∣, p,fM(p,f).\bigcup_{U_1,U_2,p,f}\mathcal M(p,f)=\bigcup_{|U_1|,|U_2|\le |X|,\,p,f}\mathcal M(p,f).U1​,U2​,p,f⋃​M(p,f)=∣U1​∣,∣U2​∣≤∣X∣,p,f⋃​M(p,f).

This is a two-private-message inner bound with a correlation penalty, together with both cardinality conclusions; it is not a capacity equality.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P26
Formal statement
noncomputable section

open scoped BigOperators Matrix ComplexConjugate ComplexOrder

namespace QAlgorithms.Papers.Independent.Support50.P26

attribute [local instance] Classical.propDecidable Classical.decEq

-- Exact primitives from pinned accepted modules, under the independent-paper override.
-- No coding theorem or other paper's channel model is reused.

open QAlgorithms.Papers.Independent.Information100.P22 (Op quantumMI)

open QAlgorithms.Papers.Independent.Information100.P27 (shannon)

open QAlgorithms.Papers.Independent.Claimed50.P08 (cqBlocks)

open QAlgorithms.Papers.Independent.Dependency50.P47 (Law)

variable {X B1 B2 W U V A B : Type}

variable [Fintype X] [Fintype B1] [Fintype B2] [Fintype W] [Fintype U] [Fintype V]

variable [Fintype A] [Fintype B]

variable [DecidableEq X] [DecidableEq B1] [DecidableEq B2] [DecidableEq W]

variable [DecidableEq U] [DecidableEq V] [DecidableEq A] [DecidableEq B]

/-- Theorem 3, PDF p.8, proved pp.8–14: Marton inner inclusion and both auxiliary
cardinality conclusions, expressed as equality of unions. Only two private messages occur. -/
theorem marton_inner_bound (C : BroadcastChannel X B1 B2) :
    (martonUnion C none ⊆ {r | AverageJointAchievable C r}) ∧
    martonUnion C none = martonUnion C (some (Fintype.card X)) := by sorry

end QAlgorithms.Papers.Independent.Support50.P26

end
Source
Classical codes for quantum broadcast channels, arXiv:1111.3645v4, PDF p. 8, Theorem 3: quantum Marton inner bound without a common message
Read-back

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

For every CCC assigning density matrices ρx\rho_xρx​ on finite, nonempty output types B1×B2B_1\times B_2B1​×B2​ to a finite, nonempty input type XXX, with decidable equality where required, the following two assertions hold. Define R\mathcal RR by taking all nonempty finite auxiliary alphabets U,VU,VU,V, all probability mass functions ppp on U×VU\times VU×V, and all functions f:U×V→Xf:U\times V\to Xf:U×V→X, and including the nonnegative real pairs satisfying

r1≤I(J1),r2≤I(J2),r1+r2≤I(J1)+I(J2)−H(pU)−H(pV)+H(p),r_1\le\mathcal I(J_1),\qquad r_2\le\mathcal I(J_2),\qquad r_1+r_2\le\mathcal I(J_1)+\mathcal I(J_2)-H(p_U)-H(p_V)+H(p),r1​≤I(J1​),r2​≤I(J2​),r1​+r2​≤I(J1​)+I(J2​)−H(pU​)−H(pV​)+H(p),

where

J1=⨁u∑vp(u,v)Tr⁡B2ρf(u,v),J2=⨁v∑up(u,v)Tr⁡B1ρf(u,v).J_1=\bigoplus_u\sum_vp(u,v)\operatorname{Tr}_{B_2}\rho_{f(u,v)},\qquad J_2=\bigoplus_v\sum_up(u,v)\operatorname{Tr}_{B_1}\rho_{f(u,v)}.J1​=u⨁​v∑​p(u,v)TrB2​​ρf(u,v)​,J2​=v⨁​u∑​p(u,v)TrB1​​ρf(u,v)​.

Here I(J)=S(Tr⁡2J)+S(Tr⁡1J)−S(J)\mathcal I(J)=S(\operatorname{Tr}_2J)+S(\operatorname{Tr}_1J)-S(J)I(J)=S(Tr2​J)+S(Tr1​J)−S(J), H(q)=−∑zq(z)log⁡2q(z)H(q)=-\sum_zq(z)\log_2q(z)H(q)=−∑z​q(z)log2​q(z), and S(A)=−Re⁡Tr⁡(h(A))S(A)=-\operatorname{Re}\operatorname{Tr}(h(A))S(A)=−ReTr(h(A)) is defined by continuous functional calculus with h(t)=tlog⁡2th(t)=t\log_2th(t)=tlog2​t. First, every r∈Rr\in\mathcal Rr∈R has this property: for every ϵ>0\epsilon>0ϵ>0 and δ>0\delta>0δ>0, there is a positive integer NNN such that for every integer n≥Nn\ge Nn≥N there exist positive message counts M1,M2M_1,M_2M1​,M2​, a deterministic encoding xn(m1,m2)∈Xnx^n(m_1,m_2)\in X^nxn(m1​,m2​)∈Xn, and POVMs (Am1)(A_{m_1})(Am1​​) on B1nB_1^nB1n​ and (Bm2)(B_{m_2})(Bm2​​) on B2nB_2^nB2n​, satisfying

r1−δ≤log⁡2M1n,r2−δ≤log⁡2M2n,1M1M2∑m1,m2[1−Re⁡Tr⁡ ⁣((Am1⊗Bm2)⨂i=0n−1ρxi(m1,m2))]≤ϵ.r_1-\delta\le\frac{\log_2M_1}{n},\qquad r_2-\delta\le\frac{\log_2M_2}{n},\qquad \frac1{M_1M_2}\sum_{m_1,m_2} \left[1-\operatorname{Re}\operatorname{Tr}\!\left( (A_{m_1}\otimes B_{m_2}) \bigotimes_{i=0}^{n-1}\rho_{x_i(m_1,m_2)} \right)\right]\le\epsilon.r1​−δ≤nlog2​M1​​,r2​−δ≤nlog2​M2​​,M1​M2​1​m1​,m2​∑​[1−ReTr((Am1​​⊗Bm2​​)i=0⨂n−1​ρxi​(m1​,m2​)​)]≤ϵ.

Each POVM consists of positive semidefinite matrices summing to the identity. Second, R\mathcal RR is unchanged when both auxiliary alphabet sizes are required to be at most ∣X∣|X|∣X∣. The first assertion is an inclusion, while the second is an equality of sets.

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