Definitions for Compression of sources of probability distributions and density operators
DefinitionQAlgorithms_Papers_Independent_Support50_P38The objects the formalized statements of Compression of sources of probability distributions and density operators (arXiv:quant-ph/0208131) are stated in. Each was checked against the paper by a blind read-back and a moderator.
SourceWord: PDF p.1: a length-n word, with the original letter order retained.wordMass: PDF pp.1–2: the memoryless product probability.wordChannel: PDF p.1: the memoryless conditional output distribution.sourceOutputMarginal: PDF p.3: the output marginal PW.sourceConditionalEntropyBits: PDF p.3: conditional entropy H(W|P), in bits.sourceInformationBits: PDF p.3: I(P;W) = H(PW) - H(W|P).tv: PDF p.1, (4): total variation is half the full l1 distance.DistributionCompressionCode: PDF p.1, (3): visible code, finite nonempty message alphabet, stochastic encoder and stochastic decoder. Their private randomness is independent: composition multiplies kernels.DistributionCompressionCode.output: PDF p.1: the composed output distribution of an ordinary code.sourceAverageBlockError: PDF p.1, (4): P^n-average block total variation, not empirical distortion.minimumSize: PDF p.1: M(n,lambda) is the minimum alphabet cardinality. Exact sending of the label makes this set nonempty for lambda >= 0. Theorems only use that domain.sizeRate: PDF p.3: the positive-blocklength normalized communication cost. Using n+1 gives exactly the same asymptotic limits while excluding division by zero.occurrences: PDF p.3, (8): number of occurrences of a letter in a word.VarianceTypicalWord: PDF p.3, (8): variance-normalized typical words, including zero-probability letters.SharedCode: PDF pp.3–6: the seed law is chosen independently of the input; private kernels factor conditional on it. A single common message alphabet is used for every seed.SharedCode.output: PDF p.3: averaging the composed channels over the independent shared seed.SharedCode.Uniform: PDF p.3: Theorem 9 uses a uniform seed.SharedCode.PassiveFeedback: PDF pp.5–6: passive feedback is an actual output word computed from seed and message. The encoder can recover the receiver's identical word; independent decoder noise is absent.QuestionFour: PDF p.3, Question 4: an assertion, not an assumed answer to the open question.QuestionFourPrime: PDF p.3, Question 4': global all-instance assertion, with a code fixed before every input. It includes the average criterion (4) and the extra typical-word condition.ExactType: PDF p.4: an exact n-type is an integer histogram of total n. Results use n >= 1.typeWords: PDF p.4: the full type class of the histogram, not just an arbitrary support subset.typeUniform: PDF p.4: uniform probability on a type class, zero outside the class.ExactType.left: PDF p.4: the X marginal of a joint type.ExactType.right: PDF p.4: the Y marginal of a joint type.JointTypeWordsCompatible: PDF p.4: membership of the paired word in a joint type class.forwardFiber: PDF p.4: conditional exact type T(x).reverseFiber: PDF p.4: conditional exact type T(y).typeForward: PDF p.4: W_T^n, a uniform channel on each nonempty conditional type class. Its totalized value outside the X type class is zero and never used as a probability law.typeReverse: PDF p.4: V_T^n, uniform on the reverse conditional type class.sourceBayesReverse: PDF p.4: Bayes transpose V on positive output mass. On a zero-mass column use P; this arbitrary stochastic completion never affects positive conditional events.positionMarginal: PDF p.2, (5): the single-position output marginal.letterError: PDF p.7: average of the positionwise total variations, with averaging outside the norm.DistributionCompressionCode.Exact: PDF pp.1,7–8: exact reconstruction for every visible label word.DistributionCompressionCode.messageLaw: PDF pp.1,7–8: distribution of the encoder's message under the source.exactEntropy: PDF pp.1,7: optimized encoder entropy S(n), not minimum log-cardinality. Exact label transmission is feasible and entropy is nonnegative, so this real infimum is nonempty and bounded.exactEntropyRate: PDF pp.1–2,7: Gamma is defined as the infimum of normalized positive-length S(n). The limit identity is a theorem, not a presupposition in this definition.FeedbackRates: PDF p.6: operational rates for simulation on every word, with passive feedback. An asymptotic error bound is allowed; arbitrary positive error and rate slack include the boundary of the region (including vanishing error at error = 0).generatedPairs: PDF pp.8–9: independent local channels applied to one uniform shared seed, with no communication. The resulting law is on pairs of ordered words.jointWordLaw: PDF pp.8–9: the i.i.d. joint law of input and channel output, on paired words.VisibleDensityCompressionCode: PDF p.10, (15): visible quantum encoder and CPTP decoder, without a shared seed.quantumWord: PDF p.10: target tensor product in the original letter order.quantumError: PDF p.10, (16): average half trace norm.minimumQuantumSize: PDF p.10: M is a dimension, not its logarithm; all code dimensions are positive.quantumSizeRate: PDF pp.10–11: normalized log dimension on positive lengths.diagonalIn: PDF p.10: classical law as a diagonal density operator in a common eigenbasis U.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_Ensemble
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P56
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P27
import Definitions.Def_QAlgorithms_Papers_Independent_Frontier30_P12
/-!
Winter, Compression of sources of probability distributions and density operators,
arXiv:quant-ph/0208131v1. Local definitions model this paper only.
Probability laws, stochastic kernels, bit-valued Shannon entropy, and bit-valued
Holevo information reuse the pinned accepted library. Distinct source-compression
objects have specific names to distinguish unrelated accepted objects.
All logarithms and entropies are in bits. Empty alphabets are excluded in results.
-/
noncomputable section
namespace QAlgorithms.Papers.Independent.Support50.P38
open scoped BigOperators Matrix ComplexConjugate
open Filter
open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)
open QAlgorithms.Papers.Independent.Frontier30.P12 (IsStochastic)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon labelInformation)
attribute [local instance] Classical.propDecidable
/-- PDF p.1: a length-n word, with the original letter order retained. -/
abbrev SourceWord (A : Type) (n : ℕ) := Fin n → A
/-- PDF pp.1–2: the memoryless product probability. -/
def wordMass {A : Type} {n : ℕ} (p : A → ℝ) (x : SourceWord A n) : ℝ :=
∏ i, p (x i)
/-- PDF p.1: the memoryless conditional output distribution. -/
def wordChannel {A B : Type} {n : ℕ} (w : A → B → ℝ)
(x : SourceWord A n) (y : SourceWord B n) : ℝ := ∏ i, w (x i) (y i)
/-- PDF p.3: the output marginal PW. -/
def sourceOutputMarginal {A B : Type} [Fintype A] (p : A → ℝ) (w : A → B → ℝ) : B → ℝ :=
fun b => ∑ a, p a * w a b
/-- PDF p.3: conditional entropy H(W|P), in bits. -/
def sourceConditionalEntropyBits {A B : Type} [Fintype A] [Fintype B]
(p : A → ℝ) (w : A → B → ℝ) : ℝ := ∑ a, p a * shannon (w a)
/-- PDF p.3: I(P;W) = H(PW) - H(W|P). -/
def sourceInformationBits {A B : Type} [Fintype A] [Fintype B]
(p : A → ℝ) (w : A → B → ℝ) : ℝ :=
shannon (sourceOutputMarginal p w) - sourceConditionalEntropyBits p w
/-- PDF p.1, (4): total variation is half the full l1 distance. -/
def tv {A : Type} [Fintype A] (p q : A → ℝ) : ℝ :=
(∑ a, |p a - q a|) / 2
/-- PDF p.1, (3): visible code, finite nonempty message alphabet, stochastic encoder and
stochastic decoder. Their private randomness is independent: composition multiplies kernels. -/
structure DistributionCompressionCode (A B : Type) [Fintype B] (n : ℕ) where
size : ℕ
size_pos : 0 < size
enc : SourceWord A n → Fin size → ℝ
enc_law : IsStochastic enc
dec : Fin size → SourceWord B n → ℝ
dec_law : IsStochastic dec
/-- PDF p.1: the composed output distribution of an ordinary code. -/
def DistributionCompressionCode.output {A B : Type} [Fintype B] {n : ℕ} (c : DistributionCompressionCode A B n)
(x : SourceWord A n) (y : SourceWord B n) : ℝ := ∑ m, c.enc x m * c.dec m y
/-- PDF p.1, (4): P^n-average block total variation, not empirical distortion. -/
def sourceAverageBlockError {A B : Type} [Fintype A] [Fintype B] {n : ℕ}
(p : A → ℝ) (w : A → B → ℝ) (v : SourceWord A n → SourceWord B n → ℝ) : ℝ :=
∑ x, wordMass p x * tv (wordChannel w x) (v x)
/-- PDF p.1: M(n,lambda) is the minimum alphabet cardinality. Exact sending of the label
makes this set nonempty for lambda >= 0. Theorems only use that domain. -/
def minimumSize {A B : Type} [Fintype A] [Fintype B]
(p : A → ℝ) (w : A → B → ℝ) (n : ℕ) (error : ℝ) : ℕ :=
sInf {m | ∃ c : DistributionCompressionCode A B n, c.size = m ∧ sourceAverageBlockError p w c.output ≤ error}
/-- PDF p.3: the positive-blocklength normalized communication cost. Using n+1 gives
exactly the same asymptotic limits while excluding division by zero. -/
def sizeRate {A B : Type} [Fintype A] [Fintype B]
(p : A → ℝ) (w : A → B → ℝ) (error : ℝ) (n : ℕ) : ℝ :=
Real.logb 2 (minimumSize p w (n + 1) error : ℝ) / (n + 1 : ℝ)
/-- PDF p.3, (8): number of occurrences of a letter in a word. -/
def occurrences {A : Type} [DecidableEq A] {n : ℕ} (x : SourceWord A n) (a : A) : ℕ :=
(Finset.univ.filter fun i => x i = a).card
/-- PDF p.3, (8): variance-normalized typical words, including zero-probability letters. -/
def VarianceTypicalWord {A : Type} [DecidableEq A] {n : ℕ} (p : A → ℝ) (width : ℝ)
(x : SourceWord A n) : Prop :=
∀ a, |(occurrences x a : ℝ) - n * p a| ≤
width * Real.sqrt n * Real.sqrt (p a * (1 - p a))
/-- PDF pp.3–6: the seed law is chosen independently of the input; private kernels
factor conditional on it. A single common message alphabet is used for every seed. -/
structure SharedCode (A B : Type) [Fintype B] (n : ℕ) where
size : ℕ
size_pos : 0 < size
seeds : ℕ
seeds_pos : 0 < seeds
seed : Fin seeds → ℝ
seed_law : IsLaw seed
enc : Fin seeds → SourceWord A n → Fin size → ℝ
enc_law : ∀ s, IsStochastic (enc s)
dec : Fin seeds → Fin size → SourceWord B n → ℝ
dec_law : ∀ s, IsStochastic (dec s)
/-- PDF p.3: averaging the composed channels over the independent shared seed. -/
def SharedCode.output {A B : Type} [Fintype B] {n : ℕ}
(c : SharedCode A B n) (x : SourceWord A n) (y : SourceWord B n) : ℝ :=
∑ s, c.seed s * ∑ m, c.enc s x m * c.dec s m y
/-- PDF p.3: Theorem 9 uses a uniform seed. -/
def SharedCode.Uniform {A B : Type} [Fintype B] {n : ℕ} (c : SharedCode A B n) : Prop :=
∀ s, c.seed s = 1 / (c.seeds : ℝ)
/-- PDF pp.5–6: passive feedback is an actual output word computed from seed and message.
The encoder can recover the receiver's identical word; independent decoder noise is absent. -/
def SharedCode.PassiveFeedback {A B : Type} [Fintype B] [DecidableEq B] {n : ℕ}
(c : SharedCode A B n) : Prop :=
∃ out : Fin c.seeds → Fin c.size → SourceWord B n,
∀ s m y, c.dec s m y = if y = out s m then 1 else 0
/-- PDF p.3, Question 4: an assertion, not an assumed answer to the open question. -/
def QuestionFour : Prop :=
∀ (a b : ℕ), 0 < a → 0 < b →
∀ (p : Fin a → ℝ) (w : Fin a → Fin b → ℝ), IsLaw p → IsStochastic w →
∀ error : ℝ, 0 < error → error < 1 →
Tendsto (sizeRate p w error) atTop (nhds (sourceInformationBits p w))
/-- PDF p.3, Question 4': global all-instance assertion, with a code fixed before every
input. It includes the average criterion (4) and the extra typical-word condition. -/
def QuestionFourPrime : Prop :=
∀ (a b : ℕ), 0 < a → 0 < b →
∀ (p : Fin a → ℝ) (w : Fin a → Fin b → ℝ), IsLaw p → IsStochastic w →
∀ error : ℝ, 0 < error → error < 1 →
∀ slack : ℝ, 0 < slack → ∀ width : ℝ, 0 < width →
∃ threshold : ℕ, ∀ n ≥ threshold, 0 < n →
∃ c : DistributionCompressionCode (Fin a) (Fin b) n,
Real.logb 2 (c.size : ℝ) / n ≤ sourceInformationBits p w + slack ∧
sourceAverageBlockError p w c.output ≤ error ∧
∀ x, VarianceTypicalWord p width x → tv (wordChannel w x) (c.output x) ≤ error
/-- PDF p.4: an exact n-type is an integer histogram of total n. Results use n >= 1. -/
structure ExactType (A : Type) [Fintype A] (n : ℕ) where
count : A → ℕ
total : ∑ a, count a = n
/-- PDF p.4: the full type class of the histogram, not just an arbitrary support subset. -/
def typeWords {A : Type} [Fintype A] [DecidableEq A] {n : ℕ} (t : ExactType A n) :
Finset (SourceWord A n) := Finset.univ.filter fun x => ∀ a, occurrences x a = t.count a
/-- PDF p.4: uniform probability on a type class, zero outside the class. -/
def typeUniform {A : Type} [Fintype A] [DecidableEq A] {n : ℕ}
(t : ExactType A n) (x : SourceWord A n) : ℝ :=
if x ∈ typeWords t then 1 / ((typeWords t).card : ℝ) else 0
/-- PDF p.4: the X marginal of a joint type. -/
def ExactType.left {A B : Type} [Fintype A] [Fintype B] {n : ℕ}
(t : ExactType (A × B) n) : ExactType A n where
count a := ∑ b, t.count (a, b)
total := by simpa only [Fintype.sum_prod_type] using t.total
/-- PDF p.4: the Y marginal of a joint type. -/
def ExactType.right {A B : Type} [Fintype A] [Fintype B] {n : ℕ}
(t : ExactType (A × B) n) : ExactType B n where
count b := ∑ a, t.count (a, b)
total := by rw [Finset.sum_comm]; simpa only [Fintype.sum_prod_type] using t.total
/-- PDF p.4: membership of the paired word in a joint type class. -/
def JointTypeWordsCompatible {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
{n : ℕ} (t : ExactType (A × B) n) (x : SourceWord A n) (y : SourceWord B n) : Prop :=
(fun i => (x i, y i)) ∈ typeWords t
/-- PDF p.4: conditional exact type T(x). -/
def forwardFiber {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
{n : ℕ} (t : ExactType (A × B) n) (x : SourceWord A n) : Finset (SourceWord B n) :=
Finset.univ.filter fun y => JointTypeWordsCompatible t x y
/-- PDF p.4: conditional exact type T(y). -/
def reverseFiber {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
{n : ℕ} (t : ExactType (A × B) n) (y : SourceWord B n) : Finset (SourceWord A n) :=
Finset.univ.filter fun x => JointTypeWordsCompatible t x y
/-- PDF p.4: W_T^n, a uniform channel on each nonempty conditional type class.
Its totalized value outside the X type class is zero and never used as a probability law. -/
def typeForward {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
{n : ℕ} (t : ExactType (A × B) n) (x : SourceWord A n) (y : SourceWord B n) : ℝ :=
if JointTypeWordsCompatible t x y then 1 / ((forwardFiber t x).card : ℝ) else 0
/-- PDF p.4: V_T^n, uniform on the reverse conditional type class. -/
def typeReverse {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
{n : ℕ} (t : ExactType (A × B) n) (y : SourceWord B n) (x : SourceWord A n) : ℝ :=
if JointTypeWordsCompatible t x y then 1 / ((reverseFiber t y).card : ℝ) else 0
/-- PDF p.4: Bayes transpose V on positive output mass. On a zero-mass column use P;
this arbitrary stochastic completion never affects positive conditional events. -/
def sourceBayesReverse {A B : Type} [Fintype A] (p : A → ℝ) (w : A → B → ℝ) (b : B) (a : A) : ℝ :=
if 0 < sourceOutputMarginal p w b then p a * w a b / sourceOutputMarginal p w b else p a
/-- PDF p.2, (5): the single-position output marginal. -/
def positionMarginal {B : Type} [Fintype B] [DecidableEq B] {n : ℕ}
(v : SourceWord B n → ℝ) (i : Fin n) (b : B) : ℝ :=
∑ y, if y i = b then v y else 0
/-- PDF p.7: average of the positionwise total variations, with averaging outside the norm. -/
def letterError {A B : Type} [Fintype A] [Fintype B] [DecidableEq B] {n : ℕ}
(p : A → ℝ) (w : A → B → ℝ) (c : DistributionCompressionCode A B n) : ℝ :=
∑ x, wordMass p x * ((∑ i, tv (w (x i)) (positionMarginal (c.output x) i)) / n)
/-- PDF pp.1,7–8: exact reconstruction for every visible label word. -/
def DistributionCompressionCode.Exact {A B : Type} [Fintype B] {n : ℕ} (c : DistributionCompressionCode A B n) (w : A → B → ℝ) : Prop :=
∀ x y, c.output x y = wordChannel w x y
/-- PDF pp.1,7–8: distribution of the encoder's message under the source. -/
def DistributionCompressionCode.messageLaw {A B : Type} [Fintype A] [Fintype B] {n : ℕ}
(c : DistributionCompressionCode A B n) (p : A → ℝ) (m : Fin c.size) : ℝ := ∑ x, wordMass p x * c.enc x m
/-- PDF pp.1,7: optimized encoder entropy S(n), not minimum log-cardinality. Exact label
transmission is feasible and entropy is nonnegative, so this real infimum is nonempty and bounded. -/
def exactEntropy {A B : Type} [Fintype A] [Fintype B]
(p : A → ℝ) (w : A → B → ℝ) (n : ℕ) : ℝ :=
sInf {r | ∃ c : DistributionCompressionCode A B n, c.Exact w ∧ shannon (c.messageLaw p) = r}
/-- PDF pp.1–2,7: Gamma is defined as the infimum of normalized positive-length S(n).
The limit identity is a theorem, not a presupposition in this definition. -/
def exactEntropyRate {A B : Type} [Fintype A] [Fintype B]
(p : A → ℝ) (w : A → B → ℝ) : ℝ :=
sInf {r | ∃ n : ℕ, 0 < n ∧ exactEntropy p w n / n = r}
/-- PDF p.6: operational rates for simulation on every word, with passive feedback.
An asymptotic error bound is allowed; arbitrary positive error and rate slack include the
boundary of the region (including vanishing error at error = 0). -/
def FeedbackRates {A B : Type} [Fintype A] [Fintype B] [DecidableEq B]
(w : A → B → ℝ) (error communication randomness : ℝ) : Prop :=
∀ tolerance > (0 : ℝ), ∀ slack > (0 : ℝ),
∃ threshold : ℕ, ∀ n ≥ threshold, 0 < n →
∃ c : SharedCode A B n, c.PassiveFeedback ∧
Real.logb 2 (c.size : ℝ) / n ≤ communication + slack ∧
Real.logb 2 (c.seeds : ℝ) / n ≤ randomness + slack ∧
∀ x, tv (wordChannel w x) (c.output x) ≤ error + tolerance
/-- PDF pp.8–9: independent local channels applied to one uniform shared seed,
with no communication. The resulting law is on pairs of ordered words. -/
def generatedPairs {A B : Type} {n seeds : ℕ}
(a : Fin seeds → SourceWord A n → ℝ) (b : Fin seeds → SourceWord B n → ℝ)
(xy : SourceWord A n × SourceWord B n) : ℝ :=
(∑ s, a s xy.1 * b s xy.2) / seeds
/-- PDF pp.8–9: the i.i.d. joint law of input and channel output, on paired words. -/
def jointWordLaw {A B : Type} {n : ℕ} (p : A → ℝ) (w : A → B → ℝ)
(xy : SourceWord A n × SourceWord B n) : ℝ := wordMass p xy.1 * wordChannel w xy.1 xy.2
/-- PDF p.10, (15): visible quantum encoder and CPTP decoder, without a shared seed. -/
structure VisibleDensityCompressionCode (A B : Type) [Fintype B] [DecidableEq B] (n : ℕ) where
size : ℕ
size_pos : 0 < size
enc : SourceWord A n → Matrix (Fin size) (Fin size) ℂ
enc_state : ∀ x, QAlgorithms.IsDensityMatrix (enc x)
dec : QAlgorithms.Superop (Fin size) (SourceWord B n)
dec_channel : QAlgorithms.IsChannel dec
/-- PDF p.10: target tensor product in the original letter order. -/
def quantumWord {A B : Type} {n : ℕ} (rho : A → Matrix B B ℂ)
(x : SourceWord A n) : Matrix (SourceWord B n) (SourceWord B n) ℂ :=
fun y z => ∏ i, rho (x i) (y i) (z i)
/-- PDF p.10, (16): average half trace norm. -/
def quantumError {A B : Type} [Fintype A] [Fintype B] [DecidableEq B] {n : ℕ}
(p : A → ℝ) (rho : A → Matrix B B ℂ) (c : VisibleDensityCompressionCode A B n) : ℝ :=
∑ x, wordMass p x * (QAlgorithms.traceNorm (quantumWord rho x - c.dec (c.enc x)) / 2)
/-- PDF p.10: M is a dimension, not its logarithm; all code dimensions are positive. -/
def minimumQuantumSize {A B : Type} [Fintype A] [Fintype B] [DecidableEq B]
(p : A → ℝ) (rho : A → Matrix B B ℂ) (n : ℕ) (error : ℝ) : ℕ :=
sInf {m | ∃ c : VisibleDensityCompressionCode A B n, c.size = m ∧ quantumError p rho c ≤ error}
/-- PDF pp.10–11: normalized log dimension on positive lengths. -/
def quantumSizeRate {A B : Type} [Fintype A] [Fintype B] [DecidableEq B]
(p : A → ℝ) (rho : A → Matrix B B ℂ) (error : ℝ) (n : ℕ) : ℝ :=
Real.logb 2 (minimumQuantumSize p rho (n + 1) error : ℝ) / (n + 1 : ℝ)
/-- PDF p.10: classical law as a diagonal density operator in a common eigenbasis U. -/
def diagonalIn {B : Type} [Fintype B] [DecidableEq B]
(u : Matrix B B ℂ) (p : B → ℝ) : Matrix B B ℂ :=
u * Matrix.diagonal (fun b => (p b : ℂ)) * uᴴ
/-- Sanity: the empty product is a unit point mass, rather than a zero state. -/
example {A : Type} (p : A → ℝ) (x : SourceWord A 0) : wordMass p x = 1 := by
simp [wordMass]
/-- Sanity: total variation between identical laws is zero. -/
example {A : Type} [Fintype A] (p : A → ℝ) : tv p p = 0 := by
simp [tv]
/-- Sanity: a deterministic code on a singleton message/output has a normalized kernel. -/
example : IsStochastic (fun (_ : Unit) (_ : Unit) => (1 : ℝ)) := by
intro a
constructor
· intro b; norm_num
· simp
/-- Sanity: zero-probability output columns of the Bayes completion return P. -/
example {A B : Type} [Fintype A] (p : A → ℝ) (w : A → B → ℝ) (b : B)
(h : sourceOutputMarginal p w b = 0) : sourceBayesReverse p w b = p := by
funext a
simp [sourceBayesReverse, h]
/-- Sanity: the quantum tensor product of zero letters is the 1-by-1 identity entry. -/
example {A B : Type} (rho : A → Matrix B B ℂ) (x : SourceWord A 0) (y z : SourceWord B 0) :
quantumWord rho x y z = 1 := by
simp [quantumWord]
/-- Sanity: a one-symbol law and channel have zero mutual information. -/
example : sourceInformationBits (fun (_ : Unit) => (1 : ℝ))
(fun (_ _ : Unit) => (1 : ℝ)) = 0 := by
simp [sourceInformationBits, sourceOutputMarginal, sourceConditionalEntropyBits, shannon]
/-- Sanity: incompatible words have zero conditional-type probability, not a normalized
0/0 probability. -/
example {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
{n : ℕ} (t : ExactType (A × B) n) (x : SourceWord A n) (y : SourceWord B n)
(h : ¬ JointTypeWordsCompatible t x y) : typeForward t x y = 0 := by
simp [typeForward, h]
/-- Sanity: the corrected optimal-alphabet bound is one at the singleton corner. -/
example : max 1 (Fintype.card Unit * Fintype.card Unit - 1) = 1 := by
simp
end QAlgorithms.Papers.Independent.Support50.P38
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Support50.P38.DistributionCompressionCode.Exact
For an arbitrary type , a finite type , a natural number , a distribution compression code , and an arbitrary real-valued function , this predicate requires
Here is the code’s message count, each encoder row is nonnegative and sums to one over messages, and each decoder row is nonnegative and sums to one over output words. No stochasticity assumption is made on . At , the product is one and the predicate holds for every such code; if there are no input words, its universal requirement is vacuous.
QAlgorithms.Papers.Independent.Support50.P38.DistributionCompressionCode
For any type , finite type , and natural number , a distribution compression code consists of a natural number , an encoder , and a decoder , where and denote words indexed by . For every input word , all are nonnegative and ; for every message , all are nonnegative and . No accuracy condition is part of this structure. When , each word space contains its unique empty word. When is empty and , no such code exists, since the decoder normalization would require an empty sum to equal .
QAlgorithms.Papers.Independent.Support50.P38.DistributionCompressionCode.messageLaw
For finite types , a natural number , a distribution compression code , an arbitrary function , and a message , this definition returns
Here is the code’s message count, and for each input word ; the code also has decoder rows that are nonnegative probability distributions on . No nonnegativity or normalization is assumed of , so the resulting function of need not be a probability law. At , the value is the encoder weight of for the unique empty input word.
QAlgorithms.Papers.Independent.Support50.P38.DistributionCompressionCode.output
For any type , finite type , natural number , and distribution compression code with positive message count , encoder probabilities , and decoder probabilities , define its output on input word and output word by
Each encoder row and decoder row is nonnegative and sums to , as required by the code structure. Words are functions on , including the unique empty words when ; in that case this output value equals .
QAlgorithms.Papers.Independent.Support50.P38.ExactType.left
For any finite types , natural number , and exact type on , consisting of natural-number counts with , this definition produces an exact type on whose count at is . These counts sum to . Zero counts and are allowed; if either alphabet is empty, the supplied joint exact type can exist only for .
QAlgorithms.Papers.Independent.Support50.P38.ExactType
For any finite type and natural number , an exact type consists of a function assigning a nonnegative integer count to each letter, together with the requirement . Individual counts may be zero. If , every count is zero; if is empty, an exact type can exist only when .
QAlgorithms.Papers.Independent.Support50.P38.ExactType.right
For finite types , which may be empty, a natural number , and an exact joint type , consisting of counts satisfying , this definition constructs an exact type on with counts
These counts sum to . The definition includes , when all counts are zero; if either alphabet is empty, the existence of forces .
QAlgorithms.Papers.Independent.Support50.P38.FeedbackRates
For finite types , with decidable equality on , an arbitrary function , and real numbers , this is the following property: for every and every , there is a natural-number threshold such that every positive integer at least that threshold admits positive integers , nonnegative seed weights summing to , stochastic encoders on , and stochastic decoders on , such that each decoder is deterministic—there are words with when and otherwise—and
The seed law need not be uniform. No stochasticity assumption on , sign restrictions on the three real parameters, or nonemptiness assumptions on are included; the existential code requirements must still hold when either type is empty.
QAlgorithms.Papers.Independent.Support50.P38.JointTypeWordsCompatible
For finite types with decidable equality, a natural number , an exact joint type with nonnegative integer counts summing to , and words and , this predicate means that
It includes , when both words are empty, all counts are zero, and the predicate holds. Neither alphabet is assumed nonempty.
QAlgorithms.Papers.Independent.Support50.P38.QuestionFour
This proposition says that for every pair of positive natural numbers , every probability distribution on , every stochastic matrix , where , and every real , the sequence converges as to , where and . Being a probability distribution means having nonnegative entries summing to , and stochasticity means this holds for each row of . For each block length , is the natural-number infimum of the sizes of codes having stochastic encoders and stochastic decoders , with induced output , for which . The natural-number infimum has value if its defining set is empty, and the real logarithm convention gives . The sequence uses only positive block lengths ; zero probabilities are allowed.
QAlgorithms.Papers.Independent.Support50.P38.QuestionFourPrime
This proposition says that for every pair of positive natural numbers , probability distribution on , stochastic matrix with , real error , positive real slack , and positive real width , there exists a natural-number threshold such that every with admits a code with positive size , stochastic encoder , stochastic decoder , and output , satisfying and . Here all probability distributions have nonnegative entries summing to , stochasticity requires this row by row, and , with and , using . The same code must additionally satisfy for every word such that, for every , . For letters of probability or , this last condition requires exact equality of the count and ; if no word satisfies all these conditions, the additional universal requirement is vacuous.
QAlgorithms.Papers.Independent.Support50.P38.SharedCode.PassiveFeedback
For any type , finite type with decidable equality, natural number , and shared code with positive seed and message counts , this predicate says that there exists a function assigning a length- output word over to every seed and message , such that when and otherwise, for every . The code’s seed weights form a probability distribution and each encoder row forms a probability distribution on messages; neither is required to be uniform or deterministic. At , the assigned output words are necessarily the unique empty word.
QAlgorithms.Papers.Independent.Support50.P38.SharedCode.Uniform
For any type , finite type , natural number , and shared code , this predicate requires every seed to have probability , where is the code’s seed count. The code also has a positive message count, probability distributions on messages for each seed and input word, and probability distributions on output words for each seed and message; this predicate imposes no further condition on those distributions. Length is allowed.
QAlgorithms.Papers.Independent.Support50.P38.SharedCode
For any type , finite type , and natural number , a shared code consists of positive natural numbers and , seed weights for , encoder weights for every length- word over and , and decoder weights for every length- word over . These satisfy , , and, for every , for all with ; for every , they also satisfy for all with . Neither the seed distribution nor the encoder or decoder is required to be uniform or deterministic. The length is allowed, with one empty word over each alphabet; if is empty and , the decoder normalization makes such a code impossible.
QAlgorithms.Papers.Independent.Support50.P38.SharedCode.output
For any type , finite type , natural number , and shared code with positive message count , positive seed count , seed probabilities , encoder probabilities , and decoder probabilities , its output value on length- words over and over is . Here the seed probabilities are nonnegative and sum to , each encoder row is a probability distribution on messages, and each decoder row is a probability distribution on output words. The formula also includes , when are the unique empty words and the output value is .
QAlgorithms.Papers.Independent.Support50.P38.SourceWord
For any type and natural number , a source word of length is a function , equivalently an ordered sequence of elements of . The case consists of a single empty word, even if is empty; if is empty and , there are no such words.
QAlgorithms.Papers.Independent.Support50.P38.VarianceTypicalWord
For any type with decidable equality, natural number , function , real number , and word , the predicate says that, for every , . There is no assumption that is a probability distribution or that is positive. Real square roots are total and equal on nonpositive arguments, so whenever , the inequality requires . For , the predicate holds for every and ; if is empty, its universal condition is vacuous.
QAlgorithms.Papers.Independent.Support50.P38.VisibleDensityCompressionCode
For an arbitrary type , a finite type with decidable equality, and a natural number , this structure consists of a positive natural number , an encoder assigning to every word a complex matrix that is positive semidefinite and has trace , and a decoder from complex matrices to complex matrices indexed by , together with the requirement that has a finite Kraus representation: there are a natural number and matrices with rows indexed by and columns indexed by such that
The block length may be , in which case and each contain one empty word. Neither nor is assumed nonempty; if is empty and , the decoder completeness condition cannot hold because .
QAlgorithms.Papers.Independent.Support50.P38.diagonalIn
For a finite type with decidable equality, an arbitrary complex matrix indexed by , and an arbitrary function , this defines
where the real numbers are viewed as complex numbers. No unitarity assumption on , nonnegativity or normalization assumption on , or nonemptiness assumption on is imposed; for empty , this is the unique matrix indexed by the empty type.
QAlgorithms.Papers.Independent.Support50.P38.exactEntropy
For finite types , arbitrary real-valued functions and , and a natural number , this definition takes the real infimum of
over all codes with a positive message count , nonnegative encoder rows summing to one, and nonnegative decoder rows summing to one over , subject to
Neither nor is assumed nonnegative or normalized; the logarithm is the total real logarithm, including its values at zero and negative arguments. If the set of candidate values is empty or unbounded below, the total real infimum convention gives zero. The definition includes , when exactness is automatic and the infimum is zero.
QAlgorithms.Papers.Independent.Support50.P38.exactEntropyRate
For finite types , an arbitrary function , and an arbitrary function , this defines
Here is the real infimum of the base-two Shannon entropies of message weights
over all codes with a positive finite message count , stochastic encoder , and stochastic decoder , satisfying
Stochastic means that every entry is nonnegative and every row sums to . No probability-law assumptions on or , and no nonemptiness assumptions on , are imposed. Both infima are taken in the real numbers, whose total infimum operation returns for an empty set or a set unbounded below; in particular, a block length with no exact code contributes .
QAlgorithms.Papers.Independent.Support50.P38.forwardFiber
For finite types with decidable equality, a natural number , an exact joint type with counts summing to , and a word , this definition returns the finite set
This set may be empty. For , it consists of the unique empty word. Neither alphabet is assumed nonempty.
QAlgorithms.Papers.Independent.Support50.P38.generatedPairs
For arbitrary types , natural numbers , arbitrary real-valued functions and indexed by , and a pair of words , this defines
No finiteness, nonnegativity, or normalization assumptions are imposed on the types or functions. When , the sum is empty and real division by zero gives the value . When , each word space consists of its unique empty word.
QAlgorithms.Papers.Independent.Support50.P38.jointWordLaw
For arbitrary types , a natural number , arbitrary functions and , and words , this defines
Neither nonnegativity nor normalization is required of or , and the types need not be finite or nonempty. At , both products are empty products, so the value on the pair of empty words is .
QAlgorithms.Papers.Independent.Support50.P38.letterError
For finite types , with decidable equality on , a natural number , arbitrary functions and , and a distribution compression code , this definition gives the following real number. Such a code has a positive message count , nonnegative encoder weights summing to one over for every , and nonnegative decoder weights summing to one over for every message . Set . The defined value is
No probability-law assumptions are imposed on or . The definition includes , when the position sum is empty and division by zero is defined as zero, so the value is zero.
QAlgorithms.Papers.Independent.Support50.P38.minimumQuantumSize
For finite types , with decidable equality on , arbitrary , arbitrary complex matrices indexed by , a natural number , and a real error bound , this defines the natural-number infimum of all positive encoding dimensions for which there are density matrices on , one for each , and a decoder
with finitely many Kraus matrices mapping to the space indexed by , such that
where . If such dimensions exist, the value is their least member; if none exist, the natural-number infimum is , although every actual code has positive dimension. No nonemptiness assumptions, normalization assumptions on , or sign restriction on are imposed, and is included with empty products equal to .
QAlgorithms.Papers.Independent.Support50.P38.minimumSize
For any finite types , arbitrary functions and , natural number , and real error bound , define the minimum size as the infimum in of all positive message counts for which there exist nonnegative encoder rows summing to and nonnegative decoder rows summing to , satisfying
Words are functions on . No probability assumptions on , or sign restriction on , are imposed. If the admissible set is nonempty, this is its least element; if it is empty, the natural-number infimum is . The case is included: its error is zero for every code, so the minimum is when and otherwise.
QAlgorithms.Papers.Independent.Support50.P38.occurrences
For any type with decidable equality, any natural number , any word , and any , is the number of positions for which . The alphabet need not be finite. If , this number is .
QAlgorithms.Papers.Independent.Support50.P38.positionMarginal
For a finite type with decidable equality, a natural number , an arbitrary real-valued function , a position , and , this definition returns
where is the set of functions from to . No positivity or normalization is required of . The position argument cannot exist when .
QAlgorithms.Papers.Independent.Support50.P38.quantumError
For finite types , with decidable equality on , a natural number , arbitrary , arbitrary complex matrices indexed by , and a visible density compression code , this defines
The code has a positive finite encoding dimension , each is positive semidefinite with trace , and its decoder has the form for a finite family satisfying . The matrix trace norm here is . No probability-law assumption on or density-matrix assumption on is made, so the weights can be negative. The types may be empty and may be ; at , the word weight and the sole entry of are both .
QAlgorithms.Papers.Independent.Support50.P38.quantumSizeRate
For finite types , with decidable equality on , arbitrary , arbitrary complex matrices indexed by , a real error bound , and a natural number , this defines
Here is the least positive integer admitting density matrices on , indexed by , and a decoder with finitely many Kraus matrices and , for which
and . If no such code exists, , and the total real logarithm has , so the defined rate is then . The denominator is always positive, including at . Neither type is assumed nonempty, and no law, density, or error-range assumptions are placed on .
QAlgorithms.Papers.Independent.Support50.P38.quantumWord
For arbitrary types , a natural number , an arbitrary assignment of a complex matrix indexed by to each , and a word , this defines the matrix indexed by whose entries are
No finiteness or nonemptiness assumptions on , and no positivity or trace conditions on , are required. At , the matrix has one entry, equal to the empty product .
QAlgorithms.Papers.Independent.Support50.P38.reverseFiber
For finite types with decidable equality, a natural number , an exact joint type with counts summing to , and a word , this definition returns the finite set
This set may be empty. For , it consists of the unique empty word. Neither alphabet is assumed nonempty.
QAlgorithms.Papers.Independent.Support50.P38.sizeRate
For any finite types , arbitrary functions and , real error bound , and natural number , put . Let be the least positive integer admitting nonnegative encoder rows and decoder rows , each summing to , for which
and set if no such code exists. Define the size rate to be . No probability assumptions on , or sign restriction on , are imposed. The block length is always positive, including when ; if no admissible code exists, the total logarithm convention makes the rate zero.
QAlgorithms.Papers.Independent.Support50.P38.sourceAverageBlockError
For any finite types , natural number , and arbitrary functions , , and , define
Here words are functions on ; none of is required to satisfy probability laws, so the outer weights may be negative. For , the expression is . For , it is zero if either or is empty.
QAlgorithms.Papers.Independent.Support50.P38.sourceBayesReverse
For a finite type , an arbitrary type , arbitrary real-valued functions and , and elements , , define . This definition returns
There are no assumptions that or the rows of are nonnegative or normalized. The fallback applies both when and when .
QAlgorithms.Papers.Independent.Support50.P38.sourceConditionalEntropyBits
For any finite types and arbitrary functions and , define
where uses the total real logarithm, with and for negative . No nonnegativity or normalization assumptions are imposed. If either indexing type is empty, the value is zero.
QAlgorithms.Papers.Independent.Support50.P38.sourceInformationBits
For any finite types and arbitrary functions and , put and define
Here uses the total real logarithm, including and for negative . Neither function is assumed to describe probabilities. If either type is empty, the value is zero.
QAlgorithms.Papers.Independent.Support50.P38.sourceOutputMarginal
For any finite type , any type , and arbitrary functions and , define a function on by
Neither nor is assumed to satisfy probability laws. If is empty, the resulting function is identically zero.
QAlgorithms.Papers.Independent.Support50.P38.tv
For any finite type and arbitrary real-valued functions , define
No probability assumptions are required. If is empty, the value is zero.
QAlgorithms.Papers.Independent.Support50.P38.typeForward
For finite types with decidable equality, a natural number , an exact joint type with counts summing to , and length- words over and over , let
The defined real number is if for every , and is zero otherwise. In the first case , so the denominator is positive; when the fiber is empty, the value is zero for every . For , the value on the unique pair of empty words is one. Neither alphabet is assumed nonempty.
QAlgorithms.Papers.Independent.Support50.P38.typeReverse
For finite types with decidable equality, a natural number , an exact joint type with counts summing to , a length- word over , and a length- word over , let
The defined real number is if for every , and is zero otherwise. In the first case , so the denominator is positive; when the fiber is empty, the value is zero for every . For , the value on the unique pair of empty words is one. Neither alphabet is assumed nonempty.
QAlgorithms.Papers.Independent.Support50.P38.typeUniform
For any finite type with decidable equality, natural number , exact type consisting of natural-number counts with , and length- word over , let be the finite set of words having exactly occurrences of every letter . This definition assigns to if , and otherwise, with the cardinality interpreted as a real number. Division uses the total real convention . At , contains the unique empty word, which receives value .
QAlgorithms.Papers.Independent.Support50.P38.typeWords
For any finite type with decidable equality, natural number , and exact type , meaning natural-number counts satisfying , this definition gives the finite set of all words such that for every . At , this set consists of the unique empty word, including when is empty.
QAlgorithms.Papers.Independent.Support50.P38.wordChannel
For any types , natural number , arbitrary function , and words and , define
The function need not be nonnegative or have rows summing to . For , the value is .
QAlgorithms.Papers.Independent.Support50.P38.wordMass
For any type , natural number , arbitrary real-valued function , and word , define its word mass by
No nonnegativity or normalization assumption is imposed on . For , this empty product equals .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.