Corollary 10: classical communication lower bound
OpenQAlgorithms.Papers.Independent.Intakenext100.P61.classical_communication_lowerLet be normalized bipartite pure states. A deterministic finite LOCC protocol, optionally supplied with any finite number of EPR pairs, produces an unconditional output with squared fidelity at least to , where . If its worst-case classical communication is bits, and , then
Here is joint eigenvalue-subset smoothing of the spectral spread. The formal model counts log-alphabet message sizes and includes binary messages. This is the factor-two improvement over quantum communication.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P61
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P61
open scoped Matrix ComplexConjugate
open QAlgorithms.Papers.Independent.Information100.P63 (logTwo)
open QAlgorithms.Papers.Independent.Dependency50.P35 (supportRank)
open QAlgorithms.Papers.Independent.Bridge50.P40 (entropyInfinity)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
attribute [local instance] Classical.propDecidable
section Operational
variable {A B C D : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
[Fintype C] [DecidableEq C] [Fintype D] [DecidableEq D]
/-- PDF p.5, Corollary 10: classical-only communication improves the factor two;
arbitrary finite EPR supplementation is allowed, including k=0. -/
theorem classical_communication_lower (phi : EuclideanSpace ℂ (A × B))
(psi : EuclideanSpace ℂ (C × D)) (hphi : ‖phi‖ = 1) (hpsi : ‖psi‖ = 1)
(k : ℕ) (epsilon cost : ℝ) (hzero : 0 ≤ epsilon) (hsmall : epsilon < 1 / 4)
(hprotocol : ClassicalPrepares (tensorPureStates phi (eprPairs k)) psi epsilon cost) :
cost ≥ smoothSpread (aliceDensity psi) (smoothingError epsilon) -
spread (aliceDensity phi) + 2 * logTwo (1 - smoothingError epsilon) := by sorry
end Operational
end QAlgorithms.Papers.Independent.Intakenext100.P61
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For finite register types , unit vectors on and on , every natural number , and real numbers and , let be the vector on with amplitude when the two added indices agree and zero otherwise. Suppose a classical execution of cost exactly takes to some matrix with
After finite-register relabeling, classical executions are generated by identity and trace-preserving local Kraus maps at zero cost, local measurements with outcomes followed by outcome-dependent classical executions, and finite composition. Measurement matrices satisfy ; if continuation costs are all at most a real budget , the measurement step and continuations cost , with output the sum of their unnormalized branch outputs. Composition adds costs. Put , , and . Define , and define as the logarithm of the minimum of over subsets of the positive eigenvalues, counted with multiplicity, whose total weight is at least , without renormalization. Then
The statement includes and .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.