Finite-block iid pure-state coding bound
OpenQAlgorithms.Papers.Independent.Intakenext100.P76.finiteBlockCodingLet , its normalized pure outputs, the measurable input law , and the computed average output be as above. For an integer , use the memoryless channel with product pure outputs and the iid input law . For , a finite deterministic code and a joint POVM satisfy
Consequently the same lower bound holds for . This finite-block bound needs no moment or positive-variance hypothesis.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P76
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P76
open MeasureTheory Filter
open QAlgorithms.Papers.Independent.Information100.P63 (logTwo normalCDF normalQuantile)
open QAlgorithms.Papers.Independent.Information100.P54 (thermalEntropy)
open QAlgorithms.Papers.Independent.Dependency50.P39 (coherentCoefficient)
open QAlgorithms.Papers.Independent.Next46.P32 (PositiveKernel)
open scoped BigOperators ENNReal Topology
attribute [local instance] Classical.propDecidable
attribute [local instance] Classical.decEq
/-- PDF p.9, (5.2): finite-block iid specialization. No variance, third moment,
or asymptotic approximation is assumed. The message decoder is joint. -/
theorem finiteBlockCoding {X : Type*} {I : Type} [MeasurableSpace X] [Countable I]
(W : X → I → ℂ) (mu : Measure X) [IsProbabilityMeasure mu]
(hnorm : ∀ x, IsUnitCoefficientVector (W x))
(hmeas : ∀ a b, Measurable (fun x => Matrix.vecMulVec (W x) (star (W x)) a b))
(p : ℕ → ℝ) (hspec : HasSpectralLaw (meanOutput W mu) p)
(n : ℕ) (hn : 1 ≤ n) (epsilon slack : ℝ)
(he : 0 < epsilon) (he1 : epsilon < 1) (hs : 0 < slack) (hse : slack < epsilon) :
let R := spectralInfEntropy (productSpectrum p n) (epsilon - slack) -
logTwo (4 * epsilon / slack ^ 2)
HasFiniteCode (productPureCQChannel W n) epsilon R ∧
(R : EReal) ≤ logMaxCodeSize (productPureCQChannel W n) epsilon := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P76
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a measurable type, a countable type, , and a probability measure on . Assume , with this family summable, for every , and assume is measurable for every . Let be nonnegative and summable with sum , and suppose the matrix has an expansion , where vectors with positive weights have summable squared moduli totaling and distinct such vectors are orthogonal under ; zero-weight vectors are unrestricted. For every natural number and real numbers , , define
for , , and , and put
Then there exist a positive integer , an encoding , and matrices indexed by , each having real nonnegative quadratic forms on every finite set of indices, with , such that
Also, , regarded as an extended real number, is at most the extended-real supremum of over all positive finite codes of this form with average error at most . Repeated codewords are allowed, and is excluded.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.