Lemma 6: entanglement-assisted compression cannot beat dimension ratio
ProvedQAlgorithms.Papers.Independent.Gap48.P38.lemma6_assistedCompressionLet be arbitrary nonempty finite complex registers. Let be any unit vector, and let and be arbitrary CPTP maps. Define the attempted identity simulation by the actual composition
For the normalized fixed-basis maximally entangled state , where is a copy of , its squared entanglement fidelity satisfies
Assistance dimensions and local channels are unrestricted. The only transmitted register is ; no additional classical or backward channel is free. The statement also covers , when its upper bound may exceed one.
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P38
noncomputable section
open MeasureTheory
open scoped Matrix ComplexConjugate ComplexOrder Matrix.Norms.Elementwise
attribute [local instance] Classical.propDecidable Classical.decEq
namespace QAlgorithms.Papers.Independent.Gap48.P38
/-- Lemma 6, PDF p.9, eq.(20): arbitrary finite-dimensional assistance and arbitrary
encoding/decoding CPTP maps; the fidelity is the overlap with a normalized Bell target.
No restriction |Y|<=|X| is imposed by the source. -/
theorem lemma6_assistedCompression
(X Y L Lprime : Type) [Fintype X] [Fintype Y] [Fintype L] [Fintype Lprime]
[DecidableEq X] [DecidableEq Y] [DecidableEq L] [DecidableEq Lprime]
[Nonempty X] [Nonempty Y] [Nonempty L] [Nonempty Lprime]
(psi : EuclideanSpace ℂ (L × Lprime)) (hpsi : ‖psi‖ = 1)
(E : Superop (X × L) Y) (hE : IsChannel E)
(D : Superop (Y × Lprime) X) (hD : IsChannel D) :
effectProb (pureDensity (finiteMaxEntangled X))
(idTensorSuperop (R := X) (assistedChannel E D (pureDensity psi))
(pureDensity (finiteMaxEntangled X))) ≤ (Fintype.card Y : ℝ) / Fintype.card X := by sorry
end QAlgorithms.Papers.Independent.Gap48.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For finite, nonempty types , all with decidable equality, let have norm one. Let map matrices on to matrices on , and let map matrices on to matrices on . Assume each is a channel in the explicit sense that it has a finite Kraus representation: with , and with . Put , and define , where
Writing , define when and zero otherwise, and . Extend to matrices on by
Then
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.