Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§II unnumbered result: superposition need not regularize to capacity

Proved
QAlgorithms.Papers.Independent.Gap48.P39.superposition_not_complete

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

prove2quantum

Consider the explicit binary cq broadcast channel x↦∣0⟩⟨0∣B⊗∣x⟩⟨x∣Cx\mapsto|0\rangle\langle0|^B\otimes|x\rangle\langle x|^Cx↦∣0⟩⟨0∣B⊗∣x⟩⟨x∣C, with a singleton Bob system and noiseless binary Charlie. Let Rsup∞(W)=⋃n≥11nRsup(W⊗n)\mathcal R_{\mathrm{sup}}^\infty(W)=\bigcup_{n\ge1}\frac1n\mathcal R_{\mathrm{sup}}(W^{\otimes n})Rsup∞​(W)=⋃n≥1​n1​Rsup​(W⊗n) be the raw block-regularized, oriented three-inequality superposition region. Then

Rsup∞(W)⊊C(W),(0,0,1) is achievable,\mathcal R_{\mathrm{sup}}^\infty(W)\subsetneq\mathcal C(W),\qquad (0,0,1)\text{ is achievable},Rsup∞​(W)⊊C(W),(0,0,1) is achievable,

and every triple in the raw superposition union has R+RB+RC=0R+R_B+R_C=0R+RB​+RC​=0. In fact, for every positive blocklength there are deterministic words and separate POVMs sending ⌊2n⌋\lfloor2^n\rfloor⌊2n⌋ Charlie-only messages with zero joint decoding error. The capacities use bits per channel use. This realizes the paper's explicit limitation: superposition in the stated Bob/Charlie orientation need not become complete under regularization.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P39
Formal statement
noncomputable section

open scoped BigOperators Matrix ComplexConjugate

namespace QAlgorithms.Papers.Independent.Gap48.P39

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

open QAlgorithms.Papers.Independent.Information100.P03 (PureEnsemble)

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

open QAlgorithms.Papers.Independent.Dependency50.P19 (both epr mutualInformation marginalRA marginalRB)

open QAlgorithms.Papers.Independent.Information100.P58 (Distribution)

open QAlgorithms.Papers.Independent.Information100.P67 (squaredFidelity conditionalEntropy groupedChannelPower)

attribute [local instance] Classical.propDecidable Classical.decEq

variable {A B C X T E : Type}

variable [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]

variable [Fintype C] [DecidableEq C] [Fintype X] [DecidableEq X]

variable [Fintype T] [DecidableEq T] [Fintype E] [DecidableEq E]

/-- §II p.4 explicit nonregularization limitation (supporting the seed target).
The oriented superposition union is strictly smaller than capacity: every member
has zero total rate, while Charlie alone receives one bit per use with zero error. -/
theorem superposition_not_complete :
    rawRegularizedSuperposition binaryExample ⊂ cqBroadcastCapacity binaryExample ∧
    (∀ r ∈ rawRegularizedSuperposition binaryExample, r.1 + r.2.1 + r.2.2 = 0) ∧
    cqBroadcastAchievable binaryExample (0, 0, 1) ∧
    (∀ n : ℕ, 0 < n → ∃ D : CQBroadcastCode Bool Unit Bool n 1 1 (rank n 1),
      D.Good binaryExample 0) := by sorry

end QAlgorithms.Papers.Independent.Gap48.P39

end
Source
Quantum broadcast channels, arXiv:quant-ph/0603098v2, PDF p. 4, §II unnumbered result: superposition need not regularize to capacity
Read-back

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

Let WWW be the Boolean input channel with a one element Bob register and Boolean Charlie register whose output at xxx is the basis density matrix at (∗,x)(\ast,x)(∗,x). The assertion is the conjunction of four statements: its raw regularized superposition set is a proper subset of its broadcast capacity set; every triple (r0,rB,rC)(r_0,r_B,r_C)(r0​,rB​,rC​) in that raw set satisfies r0+rB+rC=0r_0+r_B+r_C=0r0​+rB​+rC​=0; the triple (0,0,1)(0,0,1)(0,0,1) is broadcast achievable; and for every natural n>0n>0n>0, there is a length nnn broadcast code with one common label, one Bob label, and ⌊2n⌋N\lfloor2^n\rfloor_{\mathbb N}⌊2n⌋N​ Charlie labels whose success probability is at least 111 for every label combination. Here a broadcast code assigns an input word xs,i,j∈{false,true}nx_{s,i,j}\in\{\mathrm{false},\mathrm{true}\}^nxs,i,j​∈{false,true}n to each common, Bob, and Charlie label and has Bob measurement matrices Ps,iP_{s,i}Ps,i​ and Charlie measurement matrices Qs,jQ_{s,j}Qs,j​, each family consisting of positive semidefinite matrices summing to the identity; its success for (s,i,j)(s,i,j)(s,i,j) is Re⁡Tr⁡((Ps,i⊗Qs,j)Wxs,i,j[n])\operatorname{Re}\operatorname{Tr}((P_{s,i}\otimes Q_{s,j})W^{[n]}_{x_{s,i,j}})ReTr((Ps,i​⊗Qs,j​)Wxs,i,j​[n]​), where the word output has entries equal to the product of the corresponding single letter output entries. A nonnegative rate triple is broadcast achievable when, for every ε>0\varepsilon>0ε>0, all sufficiently large positive block lengths admit such codes with label counts ⌊2nr0⌋N,⌊2nrB⌋N,⌊2nrC⌋N\lfloor2^{nr_0}\rfloor_{\mathbb N},\lfloor2^{nr_B}\rfloor_{\mathbb N},\lfloor2^{nr_C}\rfloor_{\mathbb N}⌊2nr0​⌋N​,⌊2nrB​⌋N​,⌊2nrC​⌋N​ and success at least 1−ε1-\varepsilon1−ε for every label combination; the broadcast capacity set is the closure of these achievable triples. The raw set consists of nonnegative triples for which some n,t>0n,t>0n,t>0, with t≤min⁡{∣Xn∣,∣Bn∣2+∣Cn∣2−1}t\le\min\{|X^n|,|B^n|^2+|C^n|^2-1\}t≤min{∣Xn∣,∣Bn∣2+∣Cn∣2−1}, and some probability distribution p(s,x)p(s,x)p(s,x) on Fin⁡t×Xn\operatorname{Fin}t\times X^nFint×Xn satisfy

nrB≤H(TB)−H(diag⁡(pS))−∑s,xp(s,x)H(ωxB),n(r0+rC)≤H(Tr⁡CnTC)+H(Tr⁡Fin⁡tTC)−H(TC),n(r0+rB+rC)≤H ⁣(∑xpX(x)ωxB)−∑xpX(x)H(ωxB),\begin{aligned} nr_B&\le H(T_B)-H(\operatorname{diag}(p_S))-\sum_{s,x}p(s,x)H(\omega^B_x),\\ n(r_0+r_C)&\le H(\operatorname{Tr}_{C^n}T_C)+H(\operatorname{Tr}_{\operatorname{Fin}t}T_C)-H(T_C),\\ n(r_0+r_B+r_C)&\le H\!\left(\sum_xp_X(x)\omega^B_x\right)-\sum_xp_X(x)H(\omega^B_x), \end{aligned}nrB​n(r0​+rC​)n(r0​+rB​+rC​)​≤H(TB​)−H(diag(pS​))−s,x∑​p(s,x)H(ωxB​),≤H(TrCn​TC​)+H(TrFint​TC​)−H(TC​),≤H(x∑​pX​(x)ωxB​)−x∑​pX​(x)H(ωxB​),​

where X={false,true}X=\{\mathrm{false},\mathrm{true}\}X={false,true}, B={∗}B=\{\ast\}B={∗}, C={false,true}C=\{\mathrm{false},\mathrm{true}\}C={false,true}, ωxB,ωxC\omega^B_x,\omega^C_xωxB​,ωxC​ are the marginals of Wx[n]W^{[n]}_xWx[n]​, TB,TCT_B,T_CTB​,TC​ are block diagonal with blocks ∑xp(s,x)ωxB\sum_xp(s,x)\omega^B_x∑x​p(s,x)ωxB​ and ∑xp(s,x)ωxC\sum_xp(s,x)\omega^C_x∑x​p(s,x)ωxC​, pS,pXp_S,p_XpS​,pX​ are the two marginals of ppp, partial traces sum diagonal entries over the removed register, and H(M)=−Re⁡Tr⁡(f(M))H(M)=-\operatorname{Re}\operatorname{Tr}(f(M))H(M)=−ReTr(f(M)) for f(u)=ulog⁡2uf(u)=u\log_2uf(u)=ulog2​u applied by continuous functional calculus. Proper inclusion requires both inclusion and inequality of the two sets; the final finite block assertion excludes n=0n=0n=0.

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

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 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