Theorem 1: exact transformation communication lower bound
OpenQAlgorithms.Papers.Independent.Intakenext100.P61.exact_communication_lowerLet and be normalized finite-dimensional bipartite pure vectors, with Alice reductions and defined similarly. Write . Every deterministic protocol transforming exactly into , using local operations, local ancillas and quantum transfers of dimensions , has cost satisfying
Local disposal is allowed and the tested final output is the unconditional pure target. This bound counts communication in either direction.
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.3, Theorem 1: exact deterministic transformation lower bound. -/
theorem exact_communication_lower (phi : EuclideanSpace ℂ (A × B))
(psi : EuclideanSpace ℂ (C × D)) (hphi : ‖phi‖ = 1) (hpsi : ‖psi‖ = 1)
(cost : ℝ) (hprotocol : Quantum (pureDensity phi) (pureDensity psi) cost) :
cost ≥ (spread (aliceDensity psi) - spread (aliceDensity phi)) / 2 := 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 , and a real number , suppose there is a quantum execution taking exactly to with cost exactly . Such executions, after relabeling the registers by consecutive integers, are generated by identity steps, arbitrary local maps with , transfers in either direction of a tensor factor of any positive integer dimension , and finite composition. Identity and local-map steps cost zero, each transfer costs , and composition adds costs. Let and , where . For a density matrix , set . Then
Zero cost is included; the right-hand side is not required to be positive.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.