Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Optimal state merging has signed cost S(A|B)

Open
QAlgorithms.Papers.Independent.Gap20.P11.optimalMerging

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

prove2quantum

Let ρAB\rho_{AB}ρAB​ be a density operator on finite, nonzero-dimensional complex registers AAA and BBB. Entropies are measured in bits. Consider independent copies of this source, local operations and unlimited classical communication, and codes that depend only on ρAB\rho_{AB}ρAB​. The inaccessible purifying reference is left untouched. If a block protocol receives knk_nkn​ Bell pairs and returns ℓn\ell_nℓn​ Bell pairs, its signed entanglement cost is the real difference kn−ℓnk_n-\ell_nkn​−ℓn​. The joint output, including those returned pairs, must converge in trace norm to the reconstructed pure source at Bob tensored with the Bell resource.

A real rate eee is achievable when every positive error tolerance and rate slack can be met at every sufficiently large positive blocklength with net cost at most n(e+δ)n(e+\delta)n(e+δ). Then

e is achievable⟺e≥S(A∣B)ρ=S(ρAB)−S(ρB).e\text{ is achievable}\quad\Longleftrightarrow\quad e\ge S(A\mid B)_\rho=S(\rho_{AB})-S(\rho_B).e is achievable⟺e≥S(A∣B)ρ​=S(ρAB​)−S(ρB​).

There is a one-way construction attaining this threshold. For arbitrarily small positive slack it consumes at most n(max⁡{S(A∣B),0}+δ)n(\max\{S(A\mid B),0\}+\delta)n(max{S(A∣B),0}+δ) pairs and returns at least n(max⁡{−S(A∣B),0}−δ)n(\max\{-S(A\mid B),0\}-\delta)n(max{−S(A∣B),0}−δ) pairs, with the same net-cost bound. If S(A∣B)<0S(A\mid B)<0S(A∣B)<0, no initial Bell pairs are required. Consumed pairs may be distributed by sending qubits, and teleportation converts them into source transfer using the allowed classical communication.

This gives the operational meaning of negative conditional entropy: merging can transfer the source while producing entanglement for future communication.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Gap20_P11
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Gap20.P11

open scoped Matrix ComplexConjugate

open QAlgorithms.Papers.Independent.Gap48.P20 (Copies)

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

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF pp.1–3, main result and (1): the optimal LOCC merging cost is precisely
S(A|B), including its negative part. The second conjunct gives an actual one-way
construction, with no seed entanglement in the strictly negative regime.
Source-sketch discrepancies (p.3): the printed S(A)>S(AB) is replaced by
S(B)>S(AB), as follows directly from (1); exactly S(A|B) added ebits
would give zero conditional entropy, so the coding assertion uses positive
rate slack instead of the sketch's strict inequality at equality. -/
theorem optimalMerging {A B : Type} [Fintype A] [Fintype B]
    [Nonempty A] [Nonempty B]
    (rho : Matrix (A × B) (A × B) ℂ) (hrho : IsDensityMatrix rho) :
    (∀ rate : ℝ, MergingAchievable rho rate ↔ conditionalEntropy rho ≤ rate) ∧
    (∃ c : ℝ, MergingConstruction rho c (conditionalEntropy rho)) := by sorry

end QAlgorithms.Papers.Independent.Gap20.P11

end
Source
Quantum information can be negative, arXiv:quant-ph/0505062v1, PDF p. 2, Unnumbered main result: optimal quantum state merging and negative information
Read-back

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

For any nonempty finite types A,BA,BA,B and any positive semidefinite complex matrix ρ\rhoρ on A×BA\times BA×B with trace 111, define H(σ)=−Re⁡tr⁡f(σ)H(\sigma)=-\operatorname{Re}\operatorname{tr}f(\sigma)H(σ)=−Retrf(σ), where f(x)=xlog⁡2xf(x)=x\log_2xf(x)=xlog2​x is applied by continuous functional calculus, and put h=H(ρ)−H(Tr⁡Aρ)h=H(\rho)-H(\operatorname{Tr}_A\rho)h=H(ρ)−H(TrA​ρ). For every real rate rrr, the inequality h≤rh\le rh≤r holds if and only if the following is possible: for every ε,δ>0\varepsilon,\delta>0ε,δ>0, all sufficiently large positive integers nnn admit natural numbers k,lk,lk,l and an operation from (An×{0,1}k)×(Bn×{0,1}k)(A^n\times\{0,1\}^k)\times(B^n\times\{0,1\}^k)(An×{0,1}k)×(Bn×{0,1}k) to {0,1}l×((An×Bn)×{0,1}l)\{0,1\}^l\times((A^n\times B^n)\times\{0,1\}^l){0,1}l×((An×Bn)×{0,1}l), obtainable, after enumerating the finite bases, from the identity by finitely many recursively composed local Kraus measurements and outcome-dependent continuations, with each local Kraus family satisfying ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I, such that k−l≤n(r+δ)k-l\le n(r+\delta)k−l≤n(r+δ) and reconstruction has trace norm error at most ε\varepsilonε for every unit-vector purification of ρ\rhoρ with reference A×BA\times BA×B. Reconstruction means preserving the nnn source copies and their reference while replacing the initial shared vector 2−k/2∑u∣u,u⟩2^{-k/2}\sum_u|u,u\rangle2−k/2∑u​∣u,u⟩ by 2−l/2∑v∣v,v⟩2^{-l/2}\sum_v|v,v\rangle2−l/2∑v​∣v,v⟩, with the source’s AnA^nAn registers moved to Bob’s output; the trace norm of a matrix ZZZ is Re⁡tr⁡Z†Z\operatorname{Re}\operatorname{tr}\sqrt{Z^\dagger Z}RetrZ†Z​. Moreover, there exists a real ccc such that, for every ε,δ>0\varepsilon,\delta>0ε,δ>0, all sufficiently large positive nnn admit such reconstruction by an operation ∑s<o(As⊗Bs)\sum_{s<o}(\mathcal A_s\otimes\mathcal B_s)∑s<o​(As​⊗Bs​), where o>0o>0o>0, As(X)=∑t<h0As,tXAs,t†\mathcal A_s(X)=\sum_{t<h_0}A_{s,t}XA_{s,t}^{\dagger}As​(X)=∑t<h0​​As,t​XAs,t†​, ∑s,tAs,t†As,t=I\sum_{s,t}A_{s,t}^{\dagger}A_{s,t}=I∑s,t​As,t†​As,t​=I, and every Bs\mathcal B_sBs​ has a finite Kraus representation with completeness sum III, satisfying

log⁡2o≤n(c+δ),k−l≤n(h+δ),k≤n(max⁡(h,0)+δ),n(max⁡(−h,0)−δ)≤l,h<0⟹k=0.\log_2o\le n(c+\delta),\quad k-l\le n(h+\delta),\quad k\le n(\max(h,0)+\delta),\quad n(\max(-h,0)-\delta)\le l,\quad h<0\Longrightarrow k=0.log2​o≤n(c+δ),k−l≤n(h+δ),k≤n(max(h,0)+δ),n(max(−h,0)−δ)≤l,h<0⟹k=0.

The tensor products of maps act on matrix units componentwise and extend linearly; all auxiliary dimensions are natural numbers, and the existentially quantified ccc has no explicit sign restriction.

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).

  • Endorsed by Gohan · Oct 29, 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