Remark 25: finite universal compression construction
OpenQAlgorithms.Papers.Independent.Intakenext100.P54.finite_universal_compressionLet and . There is a universal visible quantum-classical compression code whose quantum code space has exactly
dimensions and whose fixed classical message support has size satisfying
Alice's quantum codeword is a normalized pure state in the -dimensional space, and each message decoder is CPTP and fixed independently of the target. The cost bound is the printed number of cbits, rather than its logarithm. Padding gives the stated exact code dimension, with an identity code when .
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P54
noncomputable section
open scoped BigOperators Matrix ComplexConjugate ComplexOrder NNReal ENNReal
open MeasureTheory ProbabilityTheory
namespace QAlgorithms.Papers.Independent.Intakenext100.P54
open QAlgorithms.Papers.Independent.Information100.P03 (PureEnsemble)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)
open QAlgorithms.Papers.Independent.Claimed50.P08 (classicalEntropy)
open QAlgorithms.Papers.Independent.Claimed50.P38 (tensorSuperop)
/-- Remark 25, PDF pp.16–17: the source's ceil(1/eps) CBITS bound, not its logarithm.
Pad the code to exactly ceil((1-eps/2)D); when that equals D, use the identity code. -/
theorem finite_universal_compression (D : ℕ) (hD : 0 < D)
(eps : ℝ) (heps : 0 < eps) (hepsOne : eps ≤ 1) :
∃ P : VisibleCode D, P.S = ⌈(1 - eps / 2) * D⌉₊ ∧
Real.logb 2 P.K ≤ (⌈eps⁻¹⌉₊ : ℝ) ∧
∀ psi : RSPVector (Fin D), (1 - eps) ^ 2 ≤
(pureDensity psi.val * P.output psi).trace.re := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P54
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number and every real number , there exist positive natural numbers , a function assigning to each unit vector a unit vector , a function assigning to each such a label , and maps from complex matrices to complex matrices, one for each label , such that
Each has a finite Kraus representation: there are a natural number and complex matrices , indexed by , satisfying
For every unit vector , the output obtained from its assigned vector and label satisfies
where denotes the matrix with entries . The quantifiers include and ; at , the asserted lower bound is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.