Optimal state merging has signed cost S(A|B)
OpenQAlgorithms.Papers.Independent.Gap20.P11.optimalMergingLet be a density operator on finite, nonzero-dimensional complex registers and . Entropies are measured in bits. Consider independent copies of this source, local operations and unlimited classical communication, and codes that depend only on . The inaccessible purifying reference is left untouched. If a block protocol receives Bell pairs and returns Bell pairs, its signed entanglement cost is the real difference . 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 is achievable when every positive error tolerance and rate slack can be met at every sufficiently large positive blocklength with net cost at most . Then
There is a one-way construction attaining this threshold. For arbitrarily small positive slack it consumes at most pairs and returns at least pairs, with the same net-cost bound. If , 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.
import Definitions.Def_QAlgorithms_Papers_Independent_Gap20_P11
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For any nonempty finite types and any positive semidefinite complex matrix on with trace , define , where is applied by continuous functional calculus, and put . For every real rate , the inequality holds if and only if the following is possible: for every , all sufficiently large positive integers admit natural numbers and an operation from to , 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 , such that and reconstruction has trace norm error at most for every unit-vector purification of with reference . Reconstruction means preserving the source copies and their reference while replacing the initial shared vector by , with the source’s registers moved to Bob’s output; the trace norm of a matrix is . Moreover, there exists a real such that, for every , all sufficiently large positive admit such reconstruction by an operation , where , , , and every has a finite Kraus representation with completeness sum , satisfying
The tensor products of maps act on matrix units componentwise and extend linearly; all auxiliary dimensions are natural numbers, and the existentially quantified has no explicit sign restriction.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.