Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Full noisy-entanglement-assisted capacity with the unassisted baseline

Open
QAlgorithms.Papers.Independent.Support50.P39.fullCapacity

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

prove2quantum

Let ρAB\rho_{AB}ρAB​ be a positive semidefinite density operator of trace one on two nonzero finite dimensional complex registers AAA and BBB, whose dimensions may differ. Alice and Bob receive arbitrarily many independent copies of this one fixed state for free. Alice may send quantum systems to Bob through a noiseless channel; there is no free classical communication or feedback. Arbitrary local CPTP encodings, ancillas, disposal, and joint decoding are allowed. Entropies use logarithms to base two.

Write Csd(ρ)C_{\rm sd}(\rho)Csd​(ρ) for the operational supremum of classical bits per transmitted qubit: first choose integers d≥2d\ge2d≥2 and n≥1n\ge1n≥1; a block of kkk channel uses sends a system of dimension dkd^kdk and consumes nknknk copies. For each error tolerance and rate slack, all sufficiently large positive kkk admit encoders for all mmm-bit messages and one common decoder whose success is at least 1−ϵ1-\epsilon1−ϵ for every message. The normalized rate is m/(klog⁡2d)m/(k\log_2d)m/(klog2​d), with vanishing error and arbitrarily small rate slack.

For every positive integer nnn and every CPTP map Λ:A⊗n→A′\Lambda:A^{\otimes n}\to A'Λ:A⊗n→A′ with arbitrary positive finite output dimension, put σ=(Λ⊗idB⊗n)(ρ⊗n)\sigma=(\Lambda\otimes\mathrm{id}_{B^{\otimes n}})(\rho^{\otimes n})σ=(Λ⊗idB⊗n​)(ρ⊗n). Write SA(σ)=S(σA′)S_A(\sigma)=S(\sigma_{A'})SA​(σ)=S(σA′​), IM(σ)=S(σA′)+S(σB⊗n)−S(σ)I_M(\sigma)=S(\sigma_{A'})+S(\sigma_{B^{\otimes n}})-S(\sigma)IM​(σ)=S(σA′​)+S(σB⊗n​)−S(σ), and IB(σ)=max⁡{S(σB⊗n)−S(σ),0}I^B(\sigma)=\max\{S(\sigma_{B^{\otimes n}})-S(\sigma),0\}IB(σ)=max{S(σB⊗n​)−S(σ),0}. Quotients below range only over outputs with SA(σ)>0S_A(\sigma)>0SA​(σ)>0.

Let M(ρ)\mathcal M(\rho)M(ρ) be the set of all these positive-entropy mutual-information quotients. Then

Csd(ρ)=max⁡{1,sup⁡M(ρ)},M(ρ)={IM(σ)SA(σ)},1≤Csd(ρ)≤2.C_{\rm sd}(\rho)=\max\left\{1,\sup\mathcal M(\rho)\right\},\qquad \mathcal M(\rho)=\left\{\frac{I_M(\sigma)}{S_A(\sigma)}\right\},\qquad 1\le C_{\rm sd}(\rho)\le2.Csd​(ρ)=max{1,supM(ρ)},M(ρ)={SA​(σ)IM​(σ)​},1≤Csd​(ρ)≤2.

The set M(ρ)\mathcal M(\rho)M(ρ) is nonempty and lies in [0,2][0,2][0,2], and the operational rate set is nonempty and bounded above. Every nonnegative rate strictly below the displayed value is achievable with some fixed finite d,nd,nd,n chosen before the error and rate-slack limits. Conversely, for any fixed d≥2,n≥1d\ge2,n\ge1d≥2,n≥1, every family of worst-message block codes with errors tending to zero has normalized rate eventually at most max⁡{1,sup⁡M(ρ)}+δ\max\{1,\sup\mathcal M(\rho)\}+\deltamax{1,supM(ρ)}+δ for each δ>0\delta>0δ>0, even when its rates do not converge.

This is an operational capacity identity with finite near-optimal protocols; no maximizing block length or output dimension is required.

Formalization Note This is an explicit source correction. The baseline and exclusion of zero denominators repair Eqs. (3),(4) using the unassisted strategy and the compression argument in Eqs. (13),(15).

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P39
Formal statement
namespace QAlgorithms.Papers.Independent.Support50.P39

noncomputable section

open QAlgorithms

open Filter Topology

open scoped Matrix ComplexConjugate ComplexOrder

attribute [local instance] Classical.propDecidable Classical.decEq

/-- arXiv:quant-ph/0106080v3, PDF pp.1--3,6--8, Eqs. (3),(4),(6),(15).
Full operational noisy-entanglement-assisted capacity, with achievability below
the supremum and a converse for every reliable fixed-(d,n) block family.
CORRECTION: the printed Eq. (3) omits the unassisted baseline 1, and Eq. (4)
is undefined at S(A)=0. We optimize only positive-entropy quotients and take
max with 1. Product resources have ratio 0 and operational capacity 1.
No global optimizer in n or output dimension is asserted or assumed. -/
theorem fullCapacity {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] [Nonempty A] [Nonempty B]
    (rho : Matrix (A × B) (A × B) ℂ) (hrho : IsDensityMatrix rho) :
    (mutualRatios rho).Nonempty ∧ BddAbove (mutualRatios rho) ∧
    (∀ r ∈ mutualRatios rho, 0 ≤ r ∧ r ≤ 2) ∧
    (operationalRates rho).Nonempty ∧ BddAbove (operationalRates rho) ∧
    denseCodingCapacity rho = max 1 (sSup (mutualRatios rho)) ∧
    1 ≤ denseCodingCapacity rho ∧ denseCodingCapacity rho ≤ 2 ∧
    (∀ R : ℝ, 0 ≤ R → R < max 1 (sSup (mutualRatios rho)) →
      ∃ d n : ℕ, 2 ≤ d ∧ 0 < n ∧ FixedRate rho d n R) ∧
    (∀ d n : ℕ, 2 ≤ d → 0 < n →
      ∀ (m : ℕ → ℕ) (epsilon : ℕ → ℝ), ReliableFamily rho d n m epsilon →
      ∀ delta : ℝ, 0 < delta → ∃ K : ℕ, ∀ k : ℕ, K ≤ k → 0 < k →
        (m k : ℝ) / ((k : ℝ)*Real.logb 2 d) ≤
          max 1 (sSup (mutualRatios rho)) + delta) := by sorry

end

end QAlgorithms.Papers.Independent.Support50.P39
Source
Classical capacity of a noiseless quantum channel assisted by noisy entanglement, arXiv:quant-ph/0106080v3, PDF p. 2, Eqs. (3),(4),(6),(15); abstract
Read-back

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

Let AAA and BBB be finite, nonempty types with decidable equality, and let ρ\rhoρ be a complex matrix on A×BA\times BA×B that is positive semidefinite and has trace 111. For any matrix XXX, write S(X)=−Re⁡tr⁡(f(X))S(X)=-\operatorname{Re}\operatorname{tr}(f(X))S(X)=−Retr(f(X)), where f(t)=tlog⁡2tf(t)=t\log_2 tf(t)=tlog2​t is applied by continuous functional calculus; write XAX_AXA​ and XBX_BXB​ for its partial traces over Bob and Alice, respectively. A channel from an index type III to an index type JJJ means a map on matrices admitting a finite representation Φ(X)=∑j=0q−1EjXEj†\Phi(X)=\sum_{j=0}^{q-1}E_jXE_j^\daggerΦ(X)=∑j=0q−1​Ej​XEj†​, with ∑jEj†Ej=I\sum_jE_j^\dagger E_j=I∑j​Ej†​Ej​=I. For s∈Ns\in\mathbb Ns∈N, let ρ[s]\rho^{[s]}ρ[s] be the matrix on As×BsA^s\times B^sAs×Bs whose entries are ∏t=0s−1ρ(at,bt),(at′,bt′)\prod_{t=0}^{s-1}\rho_{(a_t,b_t),(a'_t,b'_t)}∏t=0s−1​ρ(at​,bt​),(at′​,bt′​)​; applying a channel on Alice means applying it to each Alice matrix block with Bob's row and column fixed. Let Mρ\mathcal M_\rhoMρ​ be the set of all numbers

S(ωA)+S(ωB)−S(ω)S(ωA),ω=(Φ⊗id)(ρ[s]),\frac{S(\omega_A)+S(\omega_B)-S(\omega)}{S(\omega_A)}, \qquad \omega=(\Phi\otimes\mathrm{id})(\rho^{[s]}),S(ωA​)S(ωA​)+S(ωB​)−S(ω)​,ω=(Φ⊗id)(ρ[s]),

where sss and the output dimension DDD are positive natural numbers, Φ:As→{0,…,D−1}\Phi:A^s\to\{0,\ldots,D-1\}Φ:As→{0,…,D−1} is a channel in the preceding matrix sense, and S(ωA)>0S(\omega_A)>0S(ωA​)>0. To define the operational quantities, a block code with parameters d,n,k,m∈Nd,n,k,m\in\mathbb Nd,n,k,m∈N and error ϵ∈R\epsilon\in\mathbb Rϵ∈R consists of a channel Ex:Ank→{0,…,dk−1}\mathcal E_x:A^{nk}\to\{0,\ldots,d^k-1\}Ex​:Ank→{0,…,dk−1} for each mmm-bit string xxx, and positive semidefinite matrices MxM_xMx​ on {0,…,dk−1}×Bnk\{0,\ldots,d^k-1\}\times B^{nk}{0,…,dk−1}×Bnk satisfying ∑xMx=I\sum_xM_x=I∑x​Mx​=I, such that

Re⁡tr⁡ ⁣(Mx(Ex⊗id)(ρ[nk]))≥1−ϵfor every x.\operatorname{Re}\operatorname{tr}\!\left(M_x(\mathcal E_x\otimes\mathrm{id})(\rho^{[nk]})\right)\ge 1-\epsilon \quad\text{for every }x.Retr(Mx​(Ex​⊗id)(ρ[nk]))≥1−ϵfor every x.

Say that RRR is a fixed rate for d,nd,nd,n if R≥0R\ge0R≥0 and, for every 0<ϵ<10<\epsilon<10<ϵ<1 and every δ>0\delta>0δ>0, there is K∈NK\in\mathbb NK∈N such that every k≥Kk\ge Kk≥K with k>0k>0k>0 admits an m∈Nm\in\mathbb Nm∈N and such a block code satisfying m≥(R−δ)klog⁡2dm\ge(R-\delta)k\log_2dm≥(R−δ)klog2​d. Let Rρ\mathcal R_\rhoRρ​ consist of those RRR that are fixed rates for some d≥2d\ge2d≥2 and n>0n>0n>0, and put Cρ=sup⁡RρC_\rho=\sup\mathcal R_\rhoCρ​=supRρ​, with the supremum taken in R\mathbb RR. The declaration asserts that Mρ\mathcal M_\rhoMρ​ is nonempty and bounded above, every r∈Mρr\in\mathcal M_\rhor∈Mρ​ satisfies 0≤r≤20\le r\le20≤r≤2, Rρ\mathcal R_\rhoRρ​ is nonempty and bounded above, and

Cρ=max⁡{1,sup⁡Mρ},1≤Cρ≤2.C_\rho=\max\{1,\sup\mathcal M_\rho\}, \qquad 1\le C_\rho\le2.Cρ​=max{1,supMρ​},1≤Cρ​≤2.

Moreover, every real RRR with 0≤R<max⁡{1,sup⁡Mρ}0\le R<\max\{1,\sup\mathcal M_\rho\}0≤R<max{1,supMρ​} is a fixed rate for some d≥2,n>0d\ge2,n>0d≥2,n>0. Finally, for every d≥2,n>0d\ge2,n>0d≥2,n>0, every pair of functions m:N→Nm:\mathbb N\to\mathbb Nm:N→N and ϵ:N→R\epsilon:\mathbb N\to\mathbb Rϵ:N→R such that, for each positive kkk, 0≤ϵ(k)≤10\le\epsilon(k)\le10≤ϵ(k)≤1 and a block code with parameters d,n,k,m(k)d,n,k,m(k)d,n,k,m(k) and error ϵ(k)\epsilon(k)ϵ(k) exists, and such that ϵ(k)→0\epsilon(k)\to0ϵ(k)→0, every δ>0\delta>0δ>0 admits K∈NK\in\mathbb NK∈N for which

m(k)klog⁡2d≤max⁡{1,sup⁡Mρ}+δwhenever k≥K, k>0.\frac{m(k)}{k\log_2d}\le\max\{1,\sup\mathcal M_\rho\}+\delta \quad\text{whenever }k\ge K,\ k>0.klog2​dm(k)​≤max{1,supMρ​}+δwhenever k≥K, k>0.

Message length m=0m=0m=0 is allowed; the code conditions on these functions impose no requirement at k=0k=0k=0, and the positive-entropy condition excludes preprocessings with zero Alice entropy.

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