Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Classical codes for quantum broadcast channels

Definition
QAlgorithms_Papers_Independent_Support50_P26

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of Classical codes for quantum broadcast channels (arXiv:1111.3645) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • BroadcastChannel: The fixed cq broadcast channel (1), PDF p.2. Nonempty finite alphabets and nonzero finite output dimensions are explicit; dimension one is allowed.
  • broadcastWordOutput: Actual memoryless output (5), PDF pp.2–3, regrouped by receiver.
  • CqBroadcastCode: Definition 1, PDF p.3: deterministic encoder and separate collective block POVMs. The two positive message sizes permit singleton messages at zero rate.
  • averageJointError: Equations (6)–(7), PDF p.3: joint error averaged over independent uniform messages. Both POVMs are fixed before the unknown message pair.
  • AverageJointAchievable: Definition 1, PDF p.3, including boundary rates via arbitrary positive backoff. The threshold precedes every sufficiently large block length.
  • superState: State (12), PDF p.3. A joint law is exactly p_W p_(X|W), including null rows.
  • superWB1: The actual WB1 marginal of (12), PDF pp.3–4.
  • superWB2: The actual WB2 marginal of (12), PDF p.4.
  • superPrivate: I(X;B1|W) of (12), PDF p.3: H(WB1)-H(W)-sum p(w,x)H(rho_x^B1). This form avoids conditional division at null W.
  • superTotal: I(X;B1) of (12), PDF p.3, as entropy of the actual average minus average entropy.
  • SuperRegion: All three inequalities (9)–(11), PDF p.3, at a fixed auxiliary law.
  • SuccessiveRegion: Equations (61)–(63), Remark 2, PDF pp.7–8, for the same fixed law.
  • successiveCorner: The shared successive-decoding corner, Remark 2, PDF p.7.
  • superUnion: Full auxiliary union; some k bounds alphabet size, none leaves it unrestricted. Positive finite alphabets are represented up to relabeling by Fin(w+1).
  • superCap: Auxiliary cardinality bound in Theorem 1, PDF p.3; positive dimensions prevent truncation.
  • separatingChannel: A finite classical-output witness for Remark 2: input (w,v) gives |v,w><v,w|. The construction only instantiates the source's existential noncoincidence assertion.
  • separatingLaw: W,V independent fair bits, X=(W,V), so the joint (W,X) weight is 1/4 on consistency.
  • MartonData: Marton auxiliary data, (67), PDF p.8: arbitrary correlated law and deterministic map. The existence of a law enforces nonemptiness of both auxiliary alphabets.
  • martonState: Actual state (67), PDF p.8, computed from the law, map, and fixed channel.
  • martonU1B1: Actual U1B1 marginal of (67), PDF p.8.
  • martonU2B2: Actual U2B2 marginal of (67), PDF p.8.
  • auxiliaryMI: I(U1;U2) of the actual joint law, (66)–(67), PDF p.8.
  • MartonRegion: All Marton inequalities (64)–(66), PDF p.8, including the correlation penalty.
  • martonUnion: Union over all finite correlated auxiliaries and deterministic maps; both sizes are capped when cap is specified, Theorem 3, PDF p.8.
  • auxiliaryRateSystem: The seven constraints (124)–(128) plus R_i <= tilde R_i, PDF pp.13–14. The two eliminated rates are real, not integer message counts.
  • StrongTypical: Strongly typical supported input words, Appendix B, PDF p.17. Printed support omission is corrected explicitly; n=0 is excluded.
  • conditionalState1: Receiver-1 conditional state (69), PDF p.8. At a null U1 use an arbitrary normalized channel output; supported input words never contain that U1.
  • averageState1: Actual receiver-1 averaged state (70), PDF p.8; null conditional choices have no weight.
  • FiniteSpectralResolution: A fixed orthonormal eigenbasis of the actual state, (141), (155), PDF pp.17–18. This record supplies eigenvalues and a unitary change of basis, never acceptance bounds.
  • spectralWordProjector: Sum of product eigenvector rank-one projectors over the specified eigen-index words. It acts on the receiver's actual coordinate space, with no untracked permutation.
  • averagedProjector: Strong averaged spectral projector, (145), PDF p.17, for the given actual eigenbasis.
  • ConditionalSpectralTypical: Blockwise conditional spectral typicality, (164)–(170), PDF p.19. Each nonempty U1 block has its own empirical frequencies; absent blocks impose no condition.
  • conditionalTypicalProjector: Strong conditional projector, PDF p.9 after (75) and p.19 (170). At each position the eigenbasis belongs to the corresponding conditional state.
  • receiver1Word: Actual receiver-1 product state (68), (73)–(74), PDF pp.8–9.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Ensemble
import Definitions.Def_QAlgorithms_Defs_Measurement
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P22
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P27
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P08
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P47

/-!
Classical codes for quantum broadcast channels, arXiv:1111.3645v4.
PDF page numbers throughout. All entropies and rates are in bits.
The operational average-joint-error region is independent of the information regions.
Appendix B uses supported strong typicality and compatible tolerances; see the
printed/changed/why audit in MODERATION_NOTES.md. Compilation is pending batch handoff.
-/

noncomputable section

open scoped BigOperators Matrix ComplexConjugate ComplexOrder

namespace QAlgorithms.Papers.Independent.Support50.P26

attribute [local instance] Classical.propDecidable Classical.decEq

-- Exact primitives from pinned accepted modules, under the independent-paper override.
-- No coding theorem or other paper's channel model is reused.
open QAlgorithms.Papers.Independent.Information100.P22 (Op quantumMI)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon)
open QAlgorithms.Papers.Independent.Claimed50.P08 (cqBlocks)
open QAlgorithms.Papers.Independent.Dependency50.P47 (Law)

variable {X B1 B2 W U V A B : Type}
variable [Fintype X] [Fintype B1] [Fintype B2] [Fintype W] [Fintype U] [Fintype V]
variable [Fintype A] [Fintype B]
variable [DecidableEq X] [DecidableEq B1] [DecidableEq B2] [DecidableEq W]
variable [DecidableEq U] [DecidableEq V] [DecidableEq A] [DecidableEq B]

/-- The fixed cq broadcast channel (1), PDF p.2. Nonempty finite alphabets and
nonzero finite output dimensions are explicit; dimension one is allowed. -/
structure BroadcastChannel (X B1 B2 : Type) [Fintype X] [Fintype B1] [Fintype B2] where
  input_nonempty : Nonempty X
  output1_nonempty : Nonempty B1
  output2_nonempty : Nonempty B2
  rho : X → Op (B1 × B2)
  density : ∀ x, IsDensityMatrix (rho x)

/-- Actual memoryless output (5), PDF pp.2–3, regrouped by receiver. -/
def broadcastWordOutput (C : BroadcastChannel X B1 B2) {n : ℕ} (x : Fin n → X) :
    Op ((Fin n → B1) × (Fin n → B2)) :=
  fun a b => ∏ i, C.rho (x i) (a.1 i, a.2 i) (b.1 i, b.2 i)

/-- Definition 1, PDF p.3: deterministic encoder and separate collective block POVMs.
The two positive message sizes permit singleton messages at zero rate. -/
structure CqBroadcastCode (X B1 B2 : Type) [Fintype B1] [Fintype B2]
    [DecidableEq B1] [DecidableEq B2] (n : ℕ) where
  messages1 : ℕ
  messages2 : ℕ
  messages1_positive : 0 < messages1
  messages2_positive : 0 < messages2
  encode : Fin messages1 → Fin messages2 → Fin n → X
  decode1 : Fin messages1 → Op (Fin n → B1)
  decode2 : Fin messages2 → Op (Fin n → B2)
  decode1_povm : IsPOVM decode1
  decode2_povm : IsPOVM decode2

/-- Equations (6)–(7), PDF p.3: joint error averaged over independent uniform messages.
Both POVMs are fixed before the unknown message pair. -/
def averageJointError (C : BroadcastChannel X B1 B2) {n : ℕ}
    (D : CqBroadcastCode X B1 B2 n) : ℝ :=
  ((D.messages1 : ℝ) * D.messages2)⁻¹ *
    ∑ m1, ∑ m2, (1 - effectProb
      (Matrix.kronecker (D.decode1 m1) (D.decode2 m2))
      (broadcastWordOutput C (D.encode m1 m2)))

/-- Definition 1, PDF p.3, including boundary rates via arbitrary positive backoff.
The threshold precedes every sufficiently large block length. -/
def AverageJointAchievable (C : BroadcastChannel X B1 B2) (r : ℝ × ℝ) : Prop :=
  0 ≤ r.1 ∧ 0 ≤ r.2 ∧
    ∀ epsilon > (0 : ℝ), ∀ delta > (0 : ℝ), ∃ N : ℕ, 0 < N ∧
      ∀ n ≥ N, ∃ D : CqBroadcastCode X B1 B2 n,
        r.1 - delta ≤ Real.logb 2 D.messages1 / n ∧
        r.2 - delta ≤ Real.logb 2 D.messages2 / n ∧
        averageJointError C D ≤ epsilon

/-- State (12), PDF p.3. A joint law is exactly p_W p_(X|W), including null rows. -/
def superState (C : BroadcastChannel X B1 B2) (p : Law (W × X)) :
    Op ((W × X) × (B1 × B2)) :=
  cqBlocks fun wx => (p.prob wx : ℂ) • C.rho wx.2

/-- The actual WB1 marginal of (12), PDF pp.3–4. -/
def superWB1 (C : BroadcastChannel X B1 B2) (p : Law (W × X)) : Op (W × B1) :=
  cqBlocks fun w => ∑ x, (p.prob (w, x) : ℂ) • traceRight (C.rho x)

/-- The actual WB2 marginal of (12), PDF p.4. -/
def superWB2 (C : BroadcastChannel X B1 B2) (p : Law (W × X)) : Op (W × B2) :=
  cqBlocks fun w => ∑ x, (p.prob (w, x) : ℂ) • traceLeft (C.rho x)

/-- I(X;B1|W) of (12), PDF p.3: H(WB1)-H(W)-sum p(w,x)H(rho_x^B1).
This form avoids conditional division at null W. -/
def superPrivate (C : BroadcastChannel X B1 B2) (p : Law (W × X)) : ℝ :=
  vnEntropy (superWB1 C p) - shannon (fun w => ∑ x, p.prob (w, x)) -
    ∑ w, ∑ x, p.prob (w, x) * vnEntropy (traceRight (C.rho x))

/-- I(X;B1) of (12), PDF p.3, as entropy of the actual average minus average entropy. -/
def superTotal (C : BroadcastChannel X B1 B2) (p : Law (W × X)) : ℝ :=
  vnEntropy (∑ w, ∑ x, (p.prob (w, x) : ℂ) • traceRight (C.rho x)) -
    ∑ w, ∑ x, p.prob (w, x) * vnEntropy (traceRight (C.rho x))

/-- All three inequalities (9)–(11), PDF p.3, at a fixed auxiliary law. -/
def SuperRegion (C : BroadcastChannel X B1 B2) (p : Law (W × X)) : Set (ℝ × ℝ) :=
  {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧ r.1 ≤ superPrivate C p ∧
    r.2 ≤ quantumMI (superWB2 C p) ∧ r.1 + r.2 ≤ superTotal C p}

/-- Equations (61)–(63), Remark 2, PDF pp.7–8, for the same fixed law. -/
def SuccessiveRegion (C : BroadcastChannel X B1 B2) (p : Law (W × X)) : Set (ℝ × ℝ) :=
  {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧ r.1 ≤ superPrivate C p ∧
    r.2 ≤ quantumMI (superWB2 C p) ∧ r.2 ≤ quantumMI (superWB1 C p)}

/-- The shared successive-decoding corner, Remark 2, PDF p.7. -/
def successiveCorner (C : BroadcastChannel X B1 B2) (p : Law (W × X)) : ℝ × ℝ :=
  (superPrivate C p, min (quantumMI (superWB1 C p)) (quantumMI (superWB2 C p)))

/-- Full auxiliary union; `some k` bounds alphabet size, `none` leaves it unrestricted.
Positive finite alphabets are represented up to relabeling by Fin(w+1). -/
def superUnion (C : BroadcastChannel X B1 B2) (cap : Option ℕ) : Set (ℝ × ℝ) :=
  {r | ∃ w : ℕ, (∀ k ∈ cap, w + 1 ≤ k) ∧
    ∃ p : Law (Fin (w + 1) × X), r ∈ SuperRegion C p}

/-- Auxiliary cardinality bound in Theorem 1, PDF p.3; positive dimensions prevent truncation. -/
def superCap (X B1 B2 : Type) [Fintype X] [Fintype B1] [Fintype B2] : ℕ :=
  min (Fintype.card X) (Fintype.card B1 ^ 2 + Fintype.card B2 ^ 2 - 1)

/-- A finite classical-output witness for Remark 2: input (w,v) gives |v,w><v,w|.
The construction only instantiates the source's existential noncoincidence assertion. -/
def separatingChannel : BroadcastChannel (Bool × Bool) Bool Bool where
  input_nonempty := inferInstance
  output1_nonempty := inferInstance
  output2_nonempty := inferInstance
  rho x := Matrix.diagonal fun z => if z = (x.2, x.1) then 1 else 0
  density x := by
    constructor
    · apply Matrix.PosSemidef.diagonal
      intro z
      change (0 : ℂ) ≤ (if z = (x.2, x.1) then 1 else 0)
      split_ifs <;> norm_num
    · simp [Matrix.trace]

/-- W,V independent fair bits, X=(W,V), so the joint (W,X) weight is 1/4 on consistency. -/
def separatingLaw : Law (Bool × (Bool × Bool)) where
  prob wx := if wx.1 = wx.2.1 then 1 / 4 else 0
  nonneg wx := by split_ifs <;> norm_num
  total := by norm_num [Fintype.sum_prod_type, Fintype.sum_bool]

/-- Marton auxiliary data, (67), PDF p.8: arbitrary correlated law and deterministic map.
The existence of a law enforces nonemptiness of both auxiliary alphabets. -/
structure MartonData (U V X : Type) [Fintype U] [Fintype V] where
  law : Law (U × V)
  encode : U → V → X

/-- Actual state (67), PDF p.8, computed from the law, map, and fixed channel. -/
def martonState (C : BroadcastChannel X B1 B2) (D : MartonData U V X) :
    Op ((U × V) × (B1 × B2)) :=
  cqBlocks fun uv => (D.law.prob uv : ℂ) • C.rho (D.encode uv.1 uv.2)

/-- Actual U1B1 marginal of (67), PDF p.8. -/
def martonU1B1 (C : BroadcastChannel X B1 B2) (D : MartonData U V X) : Op (U × B1) :=
  cqBlocks fun u => ∑ v, (D.law.prob (u, v) : ℂ) • traceRight (C.rho (D.encode u v))

/-- Actual U2B2 marginal of (67), PDF p.8. -/
def martonU2B2 (C : BroadcastChannel X B1 B2) (D : MartonData U V X) : Op (V × B2) :=
  cqBlocks fun v => ∑ u, (D.law.prob (u, v) : ℂ) • traceLeft (C.rho (D.encode u v))

/-- I(U1;U2) of the actual joint law, (66)–(67), PDF p.8. -/
def auxiliaryMI (D : MartonData U V X) : ℝ :=
  shannon (fun u => ∑ v, D.law.prob (u, v)) +
    shannon (fun v => ∑ u, D.law.prob (u, v)) - shannon D.law.prob

/-- All Marton inequalities (64)–(66), PDF p.8, including the correlation penalty. -/
def MartonRegion (C : BroadcastChannel X B1 B2) (D : MartonData U V X) : Set (ℝ × ℝ) :=
  {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧ r.1 ≤ quantumMI (martonU1B1 C D) ∧
    r.2 ≤ quantumMI (martonU2B2 C D) ∧
    r.1 + r.2 ≤ quantumMI (martonU1B1 C D) + quantumMI (martonU2B2 C D) - auxiliaryMI D}

/-- Union over all finite correlated auxiliaries and deterministic maps; both sizes are capped
when cap is specified, Theorem 3, PDF p.8. -/
def martonUnion (C : BroadcastChannel X B1 B2) (cap : Option ℕ) : Set (ℝ × ℝ) :=
  {r | ∃ u v : ℕ, (∀ k ∈ cap, u + 1 ≤ k ∧ v + 1 ≤ k) ∧
    ∃ D : MartonData (Fin (u + 1)) (Fin (v + 1)) X, r ∈ MartonRegion C D}

/-- The seven constraints (124)–(128) plus R_i <= tilde R_i, PDF pp.13–14.
The two eliminated rates are real, not integer message counts. -/
def auxiliaryRateSystem (a b c : ℝ) (r : ℝ × ℝ) (t1 t2 : ℝ) : Prop :=
  r.1 + r.2 + c ≤ t1 + t2 ∧
  2 * t1 + t2 ≤ a + 2 * r.1 + r.2 + c ∧ t1 ≤ a ∧
  2 * t2 + t1 ≤ b + 2 * r.2 + r.1 + c ∧ t2 ≤ b ∧
  r.1 ≤ t1 ∧ r.2 ≤ t2

/-- Strongly typical supported input words, Appendix B, PDF p.17.
Printed support omission is corrected explicitly; n=0 is excluded. -/
def StrongTypical {n : ℕ} (p : A → ℝ) (eta : ℝ) (x : Fin n → A) : Prop :=
  0 < n ∧ (∀ a, |((Finset.univ.filter fun i => x i = a).card : ℝ) / n - p a| ≤ eta) ∧
    ∀ i, 0 < p (x i)

/-- Receiver-1 conditional state (69), PDF p.8. At a null U1 use an arbitrary normalized
channel output; supported input words never contain that U1. -/
def conditionalState1 (C : BroadcastChannel X B1 B2) (D : MartonData U V X) (u : U) : Op B1 :=
  let mass := ∑ v, D.law.prob (u, v)
  if 0 < mass then (mass⁻¹ : ℂ) •
    ∑ v, (D.law.prob (u, v) : ℂ) • traceRight (C.rho (D.encode u v))
  else traceRight (C.rho (Classical.choice C.input_nonempty))

/-- Actual receiver-1 averaged state (70), PDF p.8; null conditional choices have no weight. -/
def averageState1 (C : BroadcastChannel X B1 B2) (D : MartonData U V X) : Op B1 :=
  ∑ u, ∑ v, (D.law.prob (u, v) : ℂ) • traceRight (C.rho (D.encode u v))

/-- A fixed orthonormal eigenbasis of the actual state, (141), (155), PDF pp.17–18.
This record supplies eigenvalues and a unitary change of basis, never acceptance bounds. -/
structure FiniteSpectralResolution (B : Type) [Fintype B] [DecidableEq B] (rho : Op B) where
  eigenvalue : B → ℝ
  nonnegative : ∀ z, 0 ≤ eigenvalue z
  normalized : ∑ z, eigenvalue z = 1
  basis : Matrix.unitaryGroup B ℂ
  reconstruct : ∀ a b, rho a b = ∑ z,
    (eigenvalue z : ℂ) * (basis : Op B) a z * conj ((basis : Op B) b z)

/-- Sum of product eigenvector rank-one projectors over the specified eigen-index words.
It acts on the receiver's actual coordinate space, with no untracked permutation. -/
def spectralWordProjector {n : ℕ} (basis : Fin n → Op B) (accept : (Fin n → B) → Prop) :
    Op (Fin n → B) :=
  fun a b => ∑ z : Fin n → B, if accept z then
    ∏ i, basis i (a i) (z i) * conj (basis i (b i) (z i)) else 0

/-- Strong averaged spectral projector, (145), PDF p.17, for the given actual eigenbasis. -/
def averagedProjector {rho : Op B} (S : FiniteSpectralResolution B rho) (n : ℕ) (delta : ℝ) :
    Op (Fin n → B) :=
  spectralWordProjector (fun _ => (S.basis : Op B)) (StrongTypical S.eigenvalue delta)

/-- Blockwise conditional spectral typicality, (164)–(170), PDF p.19.
Each nonempty U1 block has its own empirical frequencies; absent blocks impose no condition. -/
def ConditionalSpectralTypical {n : ℕ} (q : U → B → ℝ) (delta : ℝ)
    (u : Fin n → U) (z : Fin n → B) : Prop :=
  (∀ i, 0 < q (u i) (z i)) ∧
    ∀ a, let block := Finset.univ.filter fun i => u i = a
      0 < block.card → ∀ b,
        |((block.filter fun i => z i = b).card : ℝ) / block.card - q a b| ≤ delta

/-- Strong conditional projector, PDF p.9 after (75) and p.19 (170).
At each position the eigenbasis belongs to the corresponding conditional state. -/
def conditionalTypicalProjector (C : BroadcastChannel X B1 B2) (D : MartonData U V X)
    (S : ∀ u, FiniteSpectralResolution B1 (conditionalState1 C D u))
    {n : ℕ} (u : Fin n → U) (delta : ℝ) : Op (Fin n → B1) :=
  spectralWordProjector (fun i => ((S (u i)).basis : Op B1))
    (ConditionalSpectralTypical (fun a => (S a).eigenvalue) delta u)

/-- Actual receiver-1 product state (68), (73)–(74), PDF pp.8–9. -/
def receiver1Word (C : BroadcastChannel X B1 B2) (D : MartonData U V X)
    {n : ℕ} (u : Fin n → U) (v : Fin n → V) : Op (Fin n → B1) :=
  fun a b => ∏ i, traceRight (C.rho (D.encode (u i) (v i))) (a i) (b i)

/-- Empty tensor products are scalar identity; operational statements require positive n. -/
example (C : BroadcastChannel X B1 B2) (x : Fin 0 → X)
    (a b : (Fin 0 → B1) × (Fin 0 → B2)) : broadcastWordOutput C x a b = 1 := by
  simp [broadcastWordOutput]

/-- Classical labels give the actual diagonal block. -/
example (blocks : A → Op B) (a : A) (b c : B) :
    cqBlocks blocks (a, b) (a, c) = blocks a b c := by
  simp [cqBlocks]

/-- Both lower bounds on auxiliary rates are part of the projection system. -/
example (a b c : ℝ) (r : ℝ × ℝ) (t1 t2 : ℝ)
    (h : auxiliaryRateSystem a b c r t1 t2) : r.1 ≤ t1 ∧ r.2 ≤ t2 :=
  ⟨h.2.2.2.2.2.1, h.2.2.2.2.2.2⟩

/-- An absent conditional block contributes no constraint, including the empty tensor word. -/
example (q : U → B → ℝ) (delta : ℝ) (u : Fin 0 → U) (z : Fin 0 → B) :
    ConditionalSpectralTypical q delta u z := by
  simp [ConditionalSpectralTypical]

/-- A one-symbol probability distribution has zero Shannon entropy. -/
example : shannon (fun _ : Unit => (1 : ℝ)) = 0 := by
  simp [shannon]

/-- An off-diagonal classical-label block vanishes. -/
example (blocks : A → Op B) (a a2 : A) (h : a ≠ a2) (b c : B) :
    cqBlocks blocks (a, b) (a2, c) = 0 := by
  simp [cqBlocks, h]

/-- The concrete witness uses the consistency law, including its zero-probability pairs. -/
example : separatingLaw.prob (false, (false, true)) = 1 / 4 ∧
    separatingLaw.prob (false, (true, true)) = 0 := by
  constructor <;> rfl

/-- With one channel use, the receiver-1 product is exactly its channel marginal. -/
example (C : BroadcastChannel X B1 B2) (D : MartonData U V X)
    (u : Fin 1 → U) (v : Fin 1 → V) (a b : Fin 1 → B1) :
    receiver1Word C D u v a b =
      traceRight (C.rho (D.encode (u 0) (v 0))) (a 0) (b 0) := by
  simp [receiver1Word]

/-- A zero-weight conditioning symbol takes the stated normalized fallback. -/
example (C : BroadcastChannel X B1 B2) (D : MartonData U V X) (u : U)
    (h : (∑ v, D.law.prob (u, v)) = 0) :
    conditionalState1 C D u = traceRight (C.rho (Classical.choice C.input_nonempty)) := by
  simp [conditionalState1, h]

end QAlgorithms.Papers.Independent.Support50.P26
Source
Classical codes for quantum broadcast channels, arXiv:1111.3645v4, https://arxiv.org/abs/1111.3645v4
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

QAlgorithms.Papers.Independent.Support50.P26.AverageJointAchievable

For finite nonempty types X,B1,B2X,B_1,B_2X,B1​,B2​, with decidable equality on the output types, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​ whose matrices are positive semidefinite with trace 111, and a real pair r=(r1,r2)r=(r_1,r_2)r=(r1​,r2​), this property means r1,r2≥0r_1,r_2\ge0r1​,r2​≥0 and the following: for every ϵ>0\epsilon>0ϵ>0 and every δ>0\delta>0δ>0, there exists a positive natural number NNN such that, for every natural number n≥Nn\ge Nn≥N, there is a code with positive message counts M1,M2M_1,M_2M1​,M2​, encoded words xm1,m2∈Xnx_{m_1,m_2}\in X^nxm1​,m2​​∈Xn, and positive semidefinite decoding families (Dm1(1))(D^{(1)}_{m_1})(Dm1​(1)​), (Dm2(2))(D^{(2)}_{m_2})(Dm2​(2)​) each summing to its respective identity, satisfying

r1−δ≤log⁡2M1n,r2−δ≤log⁡2M2n,1M1M2∑m1,m2[1−Re⁡tr⁡((Dm1(1)⊗Dm2(2))Ωm1,m2)]≤ϵ,r_1-\delta\le\frac{\log_2 M_1}{n},\qquad r_2-\delta\le\frac{\log_2 M_2}{n},\qquad \frac{1}{M_1M_2}\sum_{m_1,m_2} \left[1-\operatorname{Re}\operatorname{tr} \left((D^{(1)}_{m_1}\otimes D^{(2)}_{m_2})\Omega_{m_1,m_2}\right)\right]\le\epsilon,r1​−δ≤nlog2​M1​​,r2​−δ≤nlog2​M2​​,M1​M2​1​m1​,m2​∑​[1−Retr((Dm1​(1)​⊗Dm2​(2)​)Ωm1​,m2​​)]≤ϵ,

where Ωm1,m2((a1,a2),(b1,b2))=∏i<nρxm1,m2(i)((a1(i),a2(i)),(b1(i),b2(i)))\Omega_{m_1,m_2}((a_1,a_2),(b_1,b_2))=\prod_{i<n}\rho_{x_{m_1,m_2}(i)}((a_1(i),a_2(i)),(b_1(i),b_2(i)))Ωm1​,m2​​((a1​,a2​),(b1​,b2​))=∏i<n​ρxm1​,m2​​(i)​((a1​(i),a2​(i)),(b1​(i),b2​(i))). The threshold may depend on both tolerances, and the code may depend on nnn and those tolerances; zero rates are allowed, and only positive block lengths occur in the required codes.

QAlgorithms.Papers.Independent.Support50.P26.BroadcastChannel

For finite types X,B1,B2X,B_1,B_2X,B1​,B2​, a broadcast channel consists of witnesses that all three types are nonempty and a family (ρx)x∈X(\rho_x)_{x\in X}(ρx​)x∈X​ of complex matrices indexed by B1×B2B_1\times B_2B1​×B2​, such that every ρx\rho_xρx​ is positive semidefinite and has trace 111. No additional map or channel condition is part of this structure.

QAlgorithms.Papers.Independent.Support50.P26.ConditionalSpectralTypical

For index types U,BU,BU,B, a natural number nnn, an arbitrary function q:U×B→Rq:U\times B\to\mathbb Rq:U×B→R, a real number δ\deltaδ, and words u∈Unu\in U^nu∈Un, z∈Bnz\in B^nz∈Bn, this declaration defines the conjunction

∀i<n,q(ui,zi)>0,∀a∈U with Na>0, ∀b∈B,∣∣{i<n:ui=a, zi=b}∣Na−q(a,b)∣≤δ,\forall i<n,\quad q(u_i,z_i)>0, \qquad \forall a\in U\text{ with }N_a>0,\ \forall b\in B,\quad \left|\frac{|\{i<n:u_i=a,\ z_i=b\}|}{N_a}-q(a,b)\right|\le\delta,∀i<n,q(ui​,zi​)>0,∀a∈U with Na​>0, ∀b∈B,​Na​∣{i<n:ui​=a, zi​=b}∣​−q(a,b)​≤δ,

where Na=∣{i<n:ui=a}∣N_a=|\{i<n:u_i=a\}|Na​=∣{i<n:ui​=a}∣. No positivity or normalization assumptions on the rows of qqq, and no nonnegativity assumption on δ\deltaδ, are supplied separately. Symbols aaa absent from uuu impose no frequency condition, so their zero block sizes do not enter a required division. At n=0n=0n=0, both conditions hold vacuously for every qqq and δ\deltaδ; at positive nnn, a negative δ\deltaδ makes the property impossible.

QAlgorithms.Papers.Independent.Support50.P26.CqBroadcastCode

For an arbitrary type XXX, finite types B1,B2B_1,B_2B1​,B2​ with decidable equality, and a natural number nnn, a code consists of positive natural numbers M1,M2M_1,M_2M1​,M2​, an encoding function assigning a word xm1,m2:{0,…,n−1}→Xx_{m_1,m_2}:\{0,\ldots,n-1\}\to Xxm1​,m2​​:{0,…,n−1}→X to every m1<M1m_1<M_1m1​<M1​ and m2<M2m_2<M_2m2​<M2​, and families of complex matrices Dm1(1)D^{(1)}_{m_1}Dm1​(1)​ on the B1B_1B1​-word space and Dm2(2)D^{(2)}_{m_2}Dm2​(2)​ on the B2B_2B2​-word space. Each matrix in either family must be positive semidefinite, and each family must sum to the identity on its respective word space. There is no requirement that n>0n>0n>0, that XXX be finite or nonempty, or that the encoding function be injective.

QAlgorithms.Papers.Independent.Support50.P26.FiniteSpectralResolution

For a finite type BBB equipped with decidable equality and an arbitrary complex matrix ρ\rhoρ indexed by B×BB\times BB×B, this structure consists of a function λ:B→R\lambda:B\to\mathbb Rλ:B→R, proofs that λz≥0\lambda_z\ge0λz​≥0 for every zzz and ∑zλz=1\sum_z\lambda_z=1∑z​λz​=1, a unitary matrix UUU on BBB, and proofs of the entrywise identities

ρab=∑z∈Bλz Uaz Ubz‾(a,b∈B).\rho_{ab}=\sum_{z\in B}\lambda_z\,U_{az}\,\overline{U_{bz}} \qquad(a,b\in B).ρab​=z∈B∑​λz​Uaz​Ubz​​(a,b∈B).

Thus the data include both the normalized nonnegative coefficients and the unitary basis reconstructing the given matrix. Repeated and zero coefficients are allowed, and no ordering of them is required. If BBB is empty, no such structure exists because the normalization would require 0=10=10=1.

QAlgorithms.Papers.Independent.Support50.P26.MartonData

For finite types U,VU,VU,V and an arbitrary type XXX, this structure consists of a probability law ppp on U×VU\times VU×V, including the requirements p(u,v)≥0p(u,v)\ge0p(u,v)≥0 for every pair and ∑u,vp(u,v)=1\sum_{u,v}p(u,v)=1∑u,v​p(u,v)=1, together with an arbitrary function e:U×V→Xe:U\times V\to Xe:U×V→X. There are no independence, injectivity, or surjectivity requirements on these data. Although empty UUU or VVV are permitted as type parameters, no such structure exists when either is empty, since its probability masses must sum to 111.

QAlgorithms.Papers.Independent.Support50.P26.MartonRegion

For finite index types X,B1,B2,U,VX,B_1,B_2,U,VX,B1​,B2​,U,V, with decidable equality where required, let CCC specify nonempty input and output types and a positive semidefinite, trace-one matrix ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​ for each x∈Xx\in Xx∈X. Let DDD specify a probability mass function p(u,v)≥0p(u,v)\ge0p(u,v)≥0, with ∑u,vp(u,v)=1\sum_{u,v}p(u,v)=1∑u,v​p(u,v)=1, and a function f:U×V→Xf:U\times V\to Xf:U×V→X. Write ρx(1)=Tr⁡B2ρx\rho_x^{(1)}=\operatorname{Tr}_{B_2}\rho_xρx(1)​=TrB2​​ρx​, ρx(2)=Tr⁡B1ρx\rho_x^{(2)}=\operatorname{Tr}_{B_1}\rho_xρx(2)​=TrB1​​ρx​, and form the block diagonal matrices

J1=⨁u∈U∑v∈Vp(u,v)ρf(u,v)(1),J2=⨁v∈V∑u∈Up(u,v)ρf(u,v)(2).J_1=\bigoplus_{u\in U}\sum_{v\in V}p(u,v)\rho_{f(u,v)}^{(1)}, \qquad J_2=\bigoplus_{v\in V}\sum_{u\in U}p(u,v)\rho_{f(u,v)}^{(2)}.J1​=u∈U⨁​v∈V∑​p(u,v)ρf(u,v)(1)​,J2​=v∈V⨁​u∈U∑​p(u,v)ρf(u,v)(2)​.

For a bipartite matrix JJJ, put I(J)=S(Tr⁡2J)+S(Tr⁡1J)−S(J)\mathcal I(J)=S(\operatorname{Tr}_2J)+S(\operatorname{Tr}_1J)-S(J)I(J)=S(Tr2​J)+S(Tr1​J)−S(J), where S(A)=−Re⁡Tr⁡(h(A))S(A)=-\operatorname{Re}\operatorname{Tr}(h(A))S(A)=−ReTr(h(A)), h(t)=tlog⁡2th(t)=t\log_2th(t)=tlog2​t, and h(A)h(A)h(A) is defined by continuous functional calculus. Put H(q)=−∑zq(z)log⁡2q(z)H(q)=-\sum_zq(z)\log_2q(z)H(q)=−∑z​q(z)log2​q(z), pU(u)=∑vp(u,v)p_U(u)=\sum_vp(u,v)pU​(u)=∑v​p(u,v), pV(v)=∑up(u,v)p_V(v)=\sum_up(u,v)pV​(v)=∑u​p(u,v), and Ip=H(pU)+H(pV)−H(p)I_p=H(p_U)+H(p_V)-H(p)Ip​=H(pU​)+H(pV​)−H(p). The declaration defines the set of precisely those real pairs (r1,r2)(r_1,r_2)(r1​,r2​) satisfying

r1≥0,r2≥0,r1≤I(J1),r2≤I(J2),r1+r2≤I(J1)+I(J2)−Ip.r_1\ge0,\qquad r_2\ge0,\qquad r_1\le\mathcal I(J_1),\qquad r_2\le\mathcal I(J_2),\qquad r_1+r_2\le\mathcal I(J_1)+\mathcal I(J_2)-I_p.r1​≥0,r2​≥0,r1​≤I(J1​),r2​≤I(J2​),r1​+r2​≤I(J1​)+I(J2​)−Ip​.

Zero probabilities are allowed.

QAlgorithms.Papers.Independent.Support50.P26.StrongTypical

For an index type AAA, a natural number nnn, an arbitrary function p:A→Rp:A\to\mathbb Rp:A→R, a real tolerance η\etaη, and a word x:{0,…,n−1}→Ax:\{0,\ldots,n-1\}\to Ax:{0,…,n−1}→A, this declaration defines the property

n>0,∀a∈A,∣∣{i<n:xi=a}∣n−p(a)∣≤η,∀i<n,p(xi)>0.n>0,\qquad \forall a\in A,\quad \left|\frac{|\{i<n:x_i=a\}|}{n}-p(a)\right|\le\eta,\qquad \forall i<n,\quad p(x_i)>0.n>0,∀a∈A,​n∣{i<n:xi​=a}∣​−p(a)​≤η,∀i<n,p(xi​)>0.

No assumption that ppp is a probability distribution, or that η\etaη is nonnegative, is part of the definition. At n=0n=0n=0 the property is false because of its first conjunct, even though real division by zero is defined to be zero. For a word satisfying the property, negative η\etaη is impossible, and every symbol appearing in the word must have strictly positive ppp-value.

QAlgorithms.Papers.Independent.Support50.P26.SuccessiveRegion

For finite types W,X,B1,B2W,X,B_1,B_2W,X,B1​,B2​ with decidable equality, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​ with nonempty input and output types and positive semidefinite, trace-one matrices ρx\rho_xρx​, and a probability law ppp on W×XW\times XW×X, let σ1,x=Tr⁡B2ρx\sigma_{1,x}=\operatorname{Tr}_{B_2}\rho_xσ1,x​=TrB2​​ρx​, σ2,x=Tr⁡B1ρx\sigma_{2,x}=\operatorname{Tr}_{B_1}\rho_xσ2,x​=TrB1​​ρx​, pW(w)=∑xp(w,x)p_W(w)=\sum_xp(w,x)pW​(w)=∑x​p(w,x), σˉj=∑w,xp(w,x)σj,x\bar\sigma_j=\sum_{w,x}p(w,x)\sigma_{j,x}σˉj​=∑w,x​p(w,x)σj,x​, and τj=⨁w∈W∑xp(w,x)σj,x\tau_j=\bigoplus_{w\in W}\sum_xp(w,x)\sigma_{j,x}τj​=⨁w∈W​∑x​p(w,x)σj,x​; here partial trace means summing matrix entries over equal row and column indices of the discarded factor. This definition is the set of real pairs (r1,r2)(r_1,r_2)(r1​,r2​) satisfying

r1≥0,r2≥0,r1≤S(τ1)−H(pW)−∑w,xp(w,x)S(σ1,x),r2≤H(pW)+S(σˉ2)−S(τ2),r2≤H(pW)+S(σˉ1)−S(τ1).r_1\ge0,\quad r_2\ge0,\quad r_1\le S(\tau_1)-H(p_W)-\sum_{w,x}p(w,x)S(\sigma_{1,x}),\quad r_2\le H(p_W)+S(\bar\sigma_2)-S(\tau_2),\quad r_2\le H(p_W)+S(\bar\sigma_1)-S(\tau_1).r1​≥0,r2​≥0,r1​≤S(τ1​)−H(pW​)−w,x∑​p(w,x)S(σ1,x​),r2​≤H(pW​)+S(σˉ2​)−S(τ2​),r2​≤H(pW​)+S(σˉ1​)−S(τ1​).

The weights p(w,x)p(w,x)p(w,x) are nonnegative and sum to 111, H(q)=−∑wq(w)log⁡2q(w)H(q)=-\sum_wq(w)\log_2q(w)H(q)=−∑w​q(w)log2​q(w), and S(A)=−Re⁡tr⁡(f(A))S(A)=-\operatorname{Re}\operatorname{tr}(f(A))S(A)=−Retr(f(A)), where f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t is applied by continuous functional calculus. Zero weights and equality in every displayed bound are allowed; log⁡20=0\log_2 0=0log2​0=0 under the totalized real logarithm.

QAlgorithms.Papers.Independent.Support50.P26.SuperRegion

For finite types W,X,B1,B2W,X,B_1,B_2W,X,B1​,B2​ with decidable equality, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​ with nonempty input and output types and positive semidefinite, trace-one matrices ρx\rho_xρx​, and a probability law ppp on W×XW\times XW×X, let σ1,x=Tr⁡B2ρx\sigma_{1,x}=\operatorname{Tr}_{B_2}\rho_xσ1,x​=TrB2​​ρx​, σ2,x=Tr⁡B1ρx\sigma_{2,x}=\operatorname{Tr}_{B_1}\rho_xσ2,x​=TrB1​​ρx​, pW(w)=∑xp(w,x)p_W(w)=\sum_xp(w,x)pW​(w)=∑x​p(w,x), σˉj=∑w,xp(w,x)σj,x\bar\sigma_j=\sum_{w,x}p(w,x)\sigma_{j,x}σˉj​=∑w,x​p(w,x)σj,x​, and τj=⨁w∈W∑xp(w,x)σj,x\tau_j=\bigoplus_{w\in W}\sum_xp(w,x)\sigma_{j,x}τj​=⨁w∈W​∑x​p(w,x)σj,x​; here partial trace means summing matrix entries over equal row and column indices of the discarded factor. This definition is the set of real pairs (r1,r2)(r_1,r_2)(r1​,r2​) satisfying

r1≥0,r2≥0,r1≤S(τ1)−H(pW)−∑w,xp(w,x)S(σ1,x),r2≤H(pW)+S(σˉ2)−S(τ2),r1+r2≤S(σˉ1)−∑w,xp(w,x)S(σ1,x).r_1\ge0,\quad r_2\ge0,\quad r_1\le S(\tau_1)-H(p_W)-\sum_{w,x}p(w,x)S(\sigma_{1,x}),\quad r_2\le H(p_W)+S(\bar\sigma_2)-S(\tau_2),\quad r_1+r_2\le S(\bar\sigma_1)-\sum_{w,x}p(w,x)S(\sigma_{1,x}).r1​≥0,r2​≥0,r1​≤S(τ1​)−H(pW​)−w,x∑​p(w,x)S(σ1,x​),r2​≤H(pW​)+S(σˉ2​)−S(τ2​),r1​+r2​≤S(σˉ1​)−w,x∑​p(w,x)S(σ1,x​).

The weights p(w,x)p(w,x)p(w,x) are nonnegative and sum to 111, H(q)=−∑wq(w)log⁡2q(w)H(q)=-\sum_wq(w)\log_2q(w)H(q)=−∑w​q(w)log2​q(w), and S(A)=−Re⁡tr⁡(f(A))S(A)=-\operatorname{Re}\operatorname{tr}(f(A))S(A)=−Retr(f(A)), where f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t is applied by continuous functional calculus. Zero weights and equality in every displayed bound are allowed; log⁡20=0\log_2 0=0log2​0=0 under the totalized real logarithm.

QAlgorithms.Papers.Independent.Support50.P26.auxiliaryMI

For finite types U,VU,VU,V, an arbitrary type XXX, and data DDD consisting of a probability law p(u,v)≥0p(u,v)\ge0p(u,v)≥0 with total mass 111 and a function e:U×V→Xe:U\times V\to Xe:U×V→X, this definition gives

−∑upU(u)log⁡2pU(u)−∑vpV(v)log⁡2pV(v)+∑u,vp(u,v)log⁡2p(u,v),pU(u)=∑vp(u,v),pV(v)=∑up(u,v).-\sum_u p_U(u)\log_2p_U(u) -\sum_v p_V(v)\log_2p_V(v) +\sum_{u,v}p(u,v)\log_2p(u,v), \qquad p_U(u)=\sum_vp(u,v),\quad p_V(v)=\sum_up(u,v).−u∑​pU​(u)log2​pU​(u)−v∑​pV​(v)log2​pV​(v)+u,v∑​p(u,v)log2​p(u,v),pU​(u)=v∑​p(u,v),pV​(v)=u∑​p(u,v).

Zero probabilities are allowed and contribute zero. The value uses only the law in DDD; its encoding function does not enter the expression.

QAlgorithms.Papers.Independent.Support50.P26.auxiliaryRateSystem

For arbitrary real numbers a,b,c,t1,t2a,b,c,t_1,t_2a,b,c,t1​,t2​ and an arbitrary real pair r=(r1,r2)r=(r_1,r_2)r=(r1​,r2​), this declaration defines the conjunction

r1+r2+c≤t1+t2,2t1+t2≤a+2r1+r2+c,t1≤a,2t2+t1≤b+2r2+r1+c,t2≤b,r1≤t1,r2≤t2.\begin{aligned} r_1+r_2+c&\le t_1+t_2,\\ 2t_1+t_2&\le a+2r_1+r_2+c,& t_1&\le a,\\ 2t_2+t_1&\le b+2r_2+r_1+c,& t_2&\le b,\\ r_1&\le t_1,& r_2&\le t_2. \end{aligned}r1​+r2​+c2t1​+t2​2t2​+t1​r1​​≤t1​+t2​,≤a+2r1​+r2​+c,≤b+2r2​+r1​+c,≤t1​,​t1​t2​r2​​≤a,≤b,≤t2​.​

There are no separate sign assumptions on any of these real numbers.

QAlgorithms.Papers.Independent.Support50.P26.averageJointError

For finite nonempty types X,B1,B2X,B_1,B_2X,B1​,B2​, with decidable equality on the output types, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​, a natural number nnn, and a code DDD with positive message counts M1,M2M_1,M_2M1​,M2​, encoded words xm1,m2x_{m_1,m_2}xm1​,m2​​, and positive semidefinite decoding families (Dm1(1))(D^{(1)}_{m_1})(Dm1​(1)​), (Dm2(2))(D^{(2)}_{m_2})(Dm2​(2)​) each summing to the identity, the average joint error is the real number

1M1M2∑m1=0M1−1∑m2=0M2−1[1−Re⁡tr⁡((Dm1(1)⊗Dm2(2))Ωm1,m2)],\frac{1}{M_1M_2}\sum_{m_1=0}^{M_1-1}\sum_{m_2=0}^{M_2-1} \left[1-\operatorname{Re}\operatorname{tr} \left((D^{(1)}_{m_1}\otimes D^{(2)}_{m_2})\Omega_{m_1,m_2}\right)\right],M1​M2​1​m1​=0∑M1​−1​m2​=0∑M2​−1​[1−Retr((Dm1​(1)​⊗Dm2​(2)​)Ωm1​,m2​​)],

where Ωm1,m2((a1,a2),(b1,b2))=∏i<nρxm1,m2(i)((a1(i),a2(i)),(b1(i),b2(i)))\Omega_{m_1,m_2}((a_1,a_2),(b_1,b_2))=\prod_{i<n}\rho_{x_{m_1,m_2}(i)}((a_1(i),a_2(i)),(b_1(i),b_2(i)))Ωm1​,m2​​((a1​,a2​),(b1​,b2​))=∏i<n​ρxm1​,m2​​(i)​((a1​(i),a2​(i)),(b1​(i),b2​(i))). Each ρx\rho_xρx​ is positive semidefinite with trace 111. The definition includes n=0n=0n=0, with empty products equal to 111; the denominator is nonzero because both message counts are positive.

QAlgorithms.Papers.Independent.Support50.P26.averageState1

For finite index types X,B1,B2,U,VX,B_1,B_2,U,VX,B1​,B2​,U,V, with decidable equality where required, let CCC specify nonempty input and output types and a positive semidefinite, trace-one matrix ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​ for each input xxx. Let DDD specify a probability mass function p(u,v)≥0p(u,v)\ge0p(u,v)≥0, with ∑u,vp(u,v)=1\sum_{u,v}p(u,v)=1∑u,v​p(u,v)=1, and a function f:U×V→Xf:U\times V\to Xf:U×V→X. This declaration defines the matrix

ρ‾1=∑u∈U∑v∈Vp(u,v)Tr⁡B2ρf(u,v)\overline{\rho}_1=\sum_{u\in U}\sum_{v\in V}p(u,v)\operatorname{Tr}_{B_2}\rho_{f(u,v)}ρ​1​=u∈U∑​v∈V∑​p(u,v)TrB2​​ρf(u,v)​

on B1B_1B1​, where (Tr⁡B2ρ)ab=∑z∈B2ρ(a,z),(b,z)(\operatorname{Tr}_{B_2}\rho)_{ab}=\sum_{z\in B_2}\rho_{(a,z),(b,z)}(TrB2​​ρ)ab​=∑z∈B2​​ρ(a,z),(b,z)​. Terms with zero probability contribute zero; the definition contains no conditional normalization or division.

QAlgorithms.Papers.Independent.Support50.P26.averagedProjector

Let BBB be a finite type with decidable equality, let ρ\rhoρ be a complex matrix on BBB, and let SSS supply nonnegative real numbers λz\lambda_zλz​ summing to 111 and a unitary matrix UUU satisfying ρab=∑zλzUazUbz‾\rho_{ab}=\sum_z\lambda_zU_{az}\overline{U_{bz}}ρab​=∑z​λz​Uaz​Ubz​​. For every natural number nnn and real number δ\deltaδ, this declaration defines the matrix on BnB^nBn

Pab=∑z∈Bn: n>0∀c∈B, ∣∣{i<n:zi=c}∣/n−λc∣≤δ∀i<n, λzi>0∏i=0n−1UaiziUbizi‾.P_{ab}= \sum_{\substack{z\in B^n:\ n>0\\ \forall c\in B,\ \left||\{i<n:z_i=c\}|/n-\lambda_c\right|\le\delta\\ \forall i<n,\ \lambda_{z_i}>0}} \prod_{i=0}^{n-1}U_{a_i z_i}\overline{U_{b_i z_i}}.Pab​=z∈Bn: n>0∀c∈B, ∣∣{i<n:zi​=c}∣/n−λc​∣≤δ∀i<n, λzi​​>0​∑​i=0∏n−1​Uai​zi​​Ubi​zi​​​.

The same supplied unitary basis is used at every position. The definition allows every real δ\deltaδ; when δ<0\delta<0δ<0, no word meets the conditions. At n=0n=0n=0, no word is accepted because acceptance explicitly requires n>0n>0n>0, so the result is the zero matrix on the singleton empty-word space. Supplying SSS is impossible when BBB is empty.

QAlgorithms.Papers.Independent.Support50.P26.broadcastWordOutput

For finite types X,B1,B2X,B_1,B_2X,B1​,B2​, a broadcast channel CCC assigning a positive semidefinite, trace-one matrix ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​ to each x∈Xx\in Xx∈X, any natural number nnn, and a word x:{0,…,n−1}→Xx:\{0,\ldots,n-1\}\to Xx:{0,…,n−1}→X, the definition gives the complex matrix Ωx\Omega_xΩx​ indexed by pairs of words in B1B_1B1​ and B2B_2B2​, with entries

Ωx((a1,a2),(b1,b2))=∏i=0n−1ρx(i)((a1(i),a2(i)),(b1(i),b2(i))).\Omega_x\bigl((a_1,a_2),(b_1,b_2)\bigr) =\prod_{i=0}^{n-1}\rho_{x(i)}\bigl((a_1(i),a_2(i)),(b_1(i),b_2(i))\bigr).Ωx​((a1​,a2​),(b1​,b2​))=i=0∏n−1​ρx(i)​((a1​(i),a2​(i)),(b1​(i),b2​(i))).

The case n=0n=0n=0 is included: the indexing type then has one element and the empty product gives its sole entry the value 111.

QAlgorithms.Papers.Independent.Support50.P26.conditionalState1

For finite index types X,B1,B2,U,VX,B_1,B_2,U,VX,B1​,B2​,U,V, with decidable equality where required, let CCC specify nonempty input and output types and density matrices ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​, and let DDD specify a probability mass function ppp on U×VU\times VU×V and a function f:U×V→Xf:U\times V\to Xf:U×V→X. For each u∈Uu\in Uu∈U, put mu=∑vp(u,v)m_u=\sum_vp(u,v)mu​=∑v​p(u,v). The declaration defines a matrix on B1B_1B1​ by

σu={mu−1∑vp(u,v)Tr⁡B2ρf(u,v),mu>0,Tr⁡B2ρx0,mu≤0,\sigma_u= \begin{cases} m_u^{-1}\displaystyle\sum_vp(u,v)\operatorname{Tr}_{B_2}\rho_{f(u,v)},&m_u>0,\\[2mm] \operatorname{Tr}_{B_2}\rho_{x_0},&m_u\le0, \end{cases}σu​=⎩⎨⎧​mu−1​v∑​p(u,v)TrB2​​ρf(u,v)​,TrB2​​ρx0​​,​mu​>0,mu​≤0,​

where x0x_0x0​ is the input selected by classical choice from the supplied nonemptiness of XXX, and (Tr⁡B2ρ)ab=∑z∈B2ρ(a,z),(b,z)(\operatorname{Tr}_{B_2}\rho)_{ab}=\sum_{z\in B_2}\rho_{(a,z),(b,z)}(TrB2​​ρ)ab​=∑z∈B2​​ρ(a,z),(b,z)​. Since ppp is nonnegative, the second branch occurs precisely when mu=0m_u=0mu​=0; it uses this chosen input rather than dividing the zero-mass sum by zero.

QAlgorithms.Papers.Independent.Support50.P26.conditionalTypicalProjector

Let X,B1,B2,U,VX,B_1,B_2,U,VX,B1​,B2​,U,V be finite types, with decidable equality as required, and let CCC assign a positive semidefinite, trace-one matrix ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​ to each x∈Xx\in Xx∈X, with X,B1,B2X,B_1,B_2X,B1​,B2​ nonempty. Let DDD consist of a probability mass function ppp on U×VU\times VU×V and a map e:U×V→Xe:U\times V\to Xe:U×V→X. Write ρab(1)=Tr⁡B2ρe(a,b)\rho_{ab}^{(1)}=\operatorname{Tr}_{B_2}\rho_{e(a,b)}ρab(1)​=TrB2​​ρe(a,b)​, where (Tr⁡B2M)s,t=∑hM(s,h),(t,h)(\operatorname{Tr}_{B_2}M)_{s,t}=\sum_h M_{(s,h),(t,h)}(TrB2​​M)s,t​=∑h​M(s,h),(t,h)​. For each a∈Ua\in Ua∈U, put pU(a)=∑bp(a,b)p_U(a)=\sum_b p(a,b)pU​(a)=∑b​p(a,b) and let σa=pU(a)−1∑bp(a,b)ρab(1)\sigma_a=p_U(a)^{-1}\sum_b p(a,b)\rho_{ab}^{(1)}σa​=pU​(a)−1∑b​p(a,b)ρab(1)​ when pU(a)>0p_U(a)>0pU​(a)>0; otherwise let σa=Tr⁡B2ρx∗\sigma_a=\operatorname{Tr}_{B_2}\rho_{x_*}σa​=TrB2​​ρx∗​​, using the input x∗x_*x∗​ chosen from the nonemptiness of XXX. Suppose SaS_aSa​ supplies numbers λa(z)≥0\lambda_a(z)\ge0λa​(z)≥0 summing to one and a unitary matrix WaW_aWa​ on B1B_1B1​ satisfying (σa)s,t=∑zλa(z)(Wa)s,z(Wa)t,z‾(\sigma_a)_{s,t}=\sum_z\lambda_a(z)(W_a)_{s,z}\overline{(W_a)_{t,z}}(σa​)s,t​=∑z​λa​(z)(Wa​)s,z​(Wa​)t,z​​. For every natural number nnn, word u:{0,…,n−1}→Uu:\{0,\ldots,n-1\}\to Uu:{0,…,n−1}→U, and real δ\deltaδ, the declaration defines the matrix PPP on B1nB_1^nB1n​ by

Ps,t=∑z∈B1nz satisfies the conditions below∏i=0n−1(Wui)si,zi(Wui)ti,zi‾,P_{s,t}=\sum_{\substack{z\in B_1^n\\ z\text{ satisfies the conditions below}}} \prod_{i=0}^{n-1}(W_{u_i})_{s_i,z_i}\overline{(W_{u_i})_{t_i,z_i}},Ps,t​=z∈B1n​z satisfies the conditions below​∑​i=0∏n−1​(Wui​​)si​,zi​​(Wui​​)ti​,zi​​​,

where the conditions are λui(zi)>0\lambda_{u_i}(z_i)>0λui​​(zi​)>0 for every iii, and, for every a∈Ua\in Ua∈U whose position set Ia={i:ui=a}I_a=\{i:u_i=a\}Ia​={i:ui​=a} is nonempty and every b∈B1b\in B_1b∈B1​,

∣∣{i∈Ia:zi=b}∣∣Ia∣−λa(b)∣≤δ.\left|\frac{|\{i\in I_a:z_i=b\}|}{|I_a|}-\lambda_a(b)\right|\le\delta.​∣Ia​∣∣{i∈Ia​:zi​=b}∣​−λa​(b)​≤δ.

There is no restriction on δ\deltaδ; symbols absent from uuu impose no frequency conditions. For n=0n=0n=0, all acceptance conditions are vacuous and this is the identity on the one-dimensional space indexed by the empty word.

QAlgorithms.Papers.Independent.Support50.P26.martonState

Let CCC be a broadcast channel on finite nonempty types X,B1,B2X,B_1,B_2X,B1​,B2​, assigning each xxx a positive semidefinite trace-one matrix ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​. Let U,VU,VU,V be finite auxiliary types, with decidable equality for the block labels, and let DDD consist of a nonnegative probability law p(u,v)p(u,v)p(u,v) summing to 111 and an arbitrary encoding function e:U×V→Xe:U\times V\to Xe:U×V→X. This definition gives the matrix on (U×V)×(B1×B2)(U\times V)\times(B_1\times B_2)(U×V)×(B1​×B2​) whose entries are

Ω(((u,v),b),((u′,v′),b′))={p(u,v)ρe(u,v)(b,b′),(u,v)=(u′,v′),0,otherwise.\Omega(((u,v),b),((u',v'),b'))= \begin{cases} p(u,v)\rho_{e(u,v)}(b,b'),&(u,v)=(u',v'),\\ 0,&\text{otherwise}. \end{cases}Ω(((u,v),b),((u′,v′),b′))={p(u,v)ρe(u,v)​(b,b′),0,​(u,v)=(u′,v′),otherwise.​

The weights may vanish, and the encoding need not be injective.

QAlgorithms.Papers.Independent.Support50.P26.martonU1B1

Let CCC assign each input xxx in a finite nonempty type XXX a positive semidefinite trace-one matrix ρx\rho_xρx​ on finite nonempty output types B1×B2B_1\times B_2B1​×B2​. Let finite auxiliary types U,VU,VU,V carry a law p(u,v)≥0p(u,v)\ge0p(u,v)≥0 with ∑u,vp(u,v)=1\sum_{u,v}p(u,v)=1∑u,v​p(u,v)=1, and let e:U×V→Xe:U\times V\to Xe:U×V→X be arbitrary, as supplied by DDD; assume the decidable equalities needed for the block construction. The defined matrix on U×B1U\times B_1U×B1​ is

Ω1((u,b),(u′,b′))={∑v∈Vp(u,v)∑c∈B2ρe(u,v)((b,c),(b′,c)),u=u′,0,u≠u′.\Omega_1((u,b),(u',b'))= \begin{cases} \displaystyle\sum_{v\in V}p(u,v)\sum_{c\in B_2} \rho_{e(u,v)}((b,c),(b',c)),&u=u',\\ 0,&u\ne u'. \end{cases}Ω1​((u,b),(u′,b′))=⎩⎨⎧​v∈V∑​p(u,v)c∈B2​∑​ρe(u,v)​((b,c),(b′,c)),0,​u=u′,u=u′.​

Thus the blocks use the unnormalized weighted sums of the first-output partial traces; no division by the marginal probability of uuu occurs.

QAlgorithms.Papers.Independent.Support50.P26.martonU2B2

Let CCC assign each input xxx in a finite nonempty type XXX a positive semidefinite trace-one matrix ρx\rho_xρx​ on finite nonempty output types B1×B2B_1\times B_2B1​×B2​. Let finite auxiliary types U,VU,VU,V carry a law p(u,v)≥0p(u,v)\ge0p(u,v)≥0 with ∑u,vp(u,v)=1\sum_{u,v}p(u,v)=1∑u,v​p(u,v)=1, and let e:U×V→Xe:U\times V\to Xe:U×V→X be arbitrary, as supplied by DDD; assume the decidable equalities needed for the block construction. The defined matrix on V×B2V\times B_2V×B2​ is

Ω2((v,c),(v′,c′))={∑u∈Up(u,v)∑b∈B1ρe(u,v)((b,c),(b,c′)),v=v′,0,v≠v′.\Omega_2((v,c),(v',c'))= \begin{cases} \displaystyle\sum_{u\in U}p(u,v)\sum_{b\in B_1} \rho_{e(u,v)}((b,c),(b,c')),&v=v',\\ 0,&v\ne v'. \end{cases}Ω2​((v,c),(v′,c′))=⎩⎨⎧​u∈U∑​p(u,v)b∈B1​∑​ρe(u,v)​((b,c),(b,c′)),0,​v=v′,v=v′.​

Thus the blocks use the unnormalized weighted sums of the second-output partial traces; no division by the marginal probability of vvv occurs.

QAlgorithms.Papers.Independent.Support50.P26.martonUnion

For finite input and output types X,B1,B2X,B_1,B_2X,B1​,B2​, with decidable equality where required, let CCC give nonempty such types and density matrices ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​, and let cap\mathrm{cap}cap be either absent or a natural number. This declaration defines a set of real pairs r=(r1,r2)r=(r_1,r_2)r=(r1​,r2​): membership means that there exist natural numbers u,vu,vu,v, a probability mass function ppp on {0,…,u}×{0,…,v}\{0,\ldots,u\}\times\{0,\ldots,v\}{0,…,u}×{0,…,v}, and a function fff from this product to XXX, such that the following inequalities hold. Define

J1=⨁a∑bp(a,b)Tr⁡B2ρf(a,b),J2=⨁b∑ap(a,b)Tr⁡B1ρf(a,b),J_1=\bigoplus_a\sum_bp(a,b)\operatorname{Tr}_{B_2}\rho_{f(a,b)}, \qquad J_2=\bigoplus_b\sum_ap(a,b)\operatorname{Tr}_{B_1}\rho_{f(a,b)},J1​=a⨁​b∑​p(a,b)TrB2​​ρf(a,b)​,J2​=b⨁​a∑​p(a,b)TrB1​​ρf(a,b)​,

I(J)=S(Tr⁡2J)+S(Tr⁡1J)−S(J)\mathcal I(J)=S(\operatorname{Tr}_2J)+S(\operatorname{Tr}_1J)-S(J)I(J)=S(Tr2​J)+S(Tr1​J)−S(J), and Ip=H(pU)+H(pV)−H(p)I_p=H(p_U)+H(p_V)-H(p)Ip​=H(pU​)+H(pV​)−H(p), where H(q)=−∑zq(z)log⁡2q(z)H(q)=-\sum_zq(z)\log_2q(z)H(q)=−∑z​q(z)log2​q(z) and S(A)=−Re⁡Tr⁡(h(A))S(A)=-\operatorname{Re}\operatorname{Tr}(h(A))S(A)=−ReTr(h(A)) uses continuous functional calculus with h(t)=tlog⁡2th(t)=t\log_2th(t)=tlog2​t. The required rate inequalities are

r1,r2≥0,r1≤I(J1),r2≤I(J2),r1+r2≤I(J1)+I(J2)−Ip.r_1,r_2\ge0,\qquad r_1\le\mathcal I(J_1),\qquad r_2\le\mathcal I(J_2),\qquad r_1+r_2\le\mathcal I(J_1)+\mathcal I(J_2)-I_p.r1​,r2​≥0,r1​≤I(J1​),r2​≤I(J2​),r1​+r2​≤I(J1​)+I(J2​)−Ip​.

If the cap is KKK, the additional requirements are u+1≤Ku+1\le Ku+1≤K and v+1≤Kv+1\le Kv+1≤K; an absent cap imposes no such restriction. Both auxiliary alphabets are always nonempty, including when u=0u=0u=0 or v=0v=0v=0. A cap of zero therefore gives the empty set.

QAlgorithms.Papers.Independent.Support50.P26.receiver1Word

Let X,B1,B2,U,VX,B_1,B_2,U,VX,B1​,B2​,U,V be finite types, with decidable equality as required. Let CCC have nonempty input and output types X,B1,B2X,B_1,B_2X,B1​,B2​ and assign a positive semidefinite, trace-one matrix ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​ to each input xxx. Let DDD consist of a nonnegative probability mass function ppp on U×VU\times VU×V, summing to one, and an encoding map e:U×V→Xe:U\times V\to Xe:U×V→X. For every natural number nnn and words u∈Unu\in U^nu∈Un, v∈Vnv\in V^nv∈Vn, the declaration defines a matrix Ru,vR_{u,v}Ru,v​ on B1nB_1^nB1n​ by

(Ru,v)s,t=∏i=0n−1(∑h∈B2(ρe(ui,vi))(si,h),(ti,h)).(R_{u,v})_{s,t} =\prod_{i=0}^{n-1}\left(\sum_{h\in B_2} (\rho_{e(u_i,v_i)})_{(s_i,h),(t_i,h)}\right).(Ru,v​)s,t​=i=0∏n−1​(h∈B2​∑​(ρe(ui​,vi​)​)(si​,h),(ti​,h)​).

Thus its entries are products of entries of the first-output marginal matrices; the probability mass function carried by DDD does not occur in this formula. The definition includes n=0n=0n=0, when the empty product is 111 and the matrix has a single entry equal to 111.

QAlgorithms.Papers.Independent.Support50.P26.separatingChannel

This defines a broadcast channel whose input is a pair of Booleans x=(x1,x2)x=(x_1,x_2)x=(x1​,x2​) and whose two output types are each Boolean. Its output is the matrix

ρx(z,z′)={1,z=z′=(x2,x1),0,otherwise,z,z′∈{false,true}2.\rho_x(z,z')= \begin{cases} 1,&z=z'=(x_2,x_1),\\ 0,&\text{otherwise}, \end{cases} \qquad z,z'\in\{\mathrm{false},\mathrm{true}\}^2.ρx​(z,z′)={1,0,​z=z′=(x2​,x1​),otherwise,​z,z′∈{false,true}2.

Thus its output is the rank-one computational-basis projector at (x2,x1)(x_2,x_1)(x2​,x1​). The structure includes nonemptiness of all three types and the facts that every output is positive semidefinite and has trace 111.

QAlgorithms.Papers.Independent.Support50.P26.separatingLaw

This defines a probability law on triples (w,(x1,x2))(w,(x_1,x_2))(w,(x1​,x2​)) of Booleans by

p(w,(x1,x2))={14,w=x1,0,w≠x1.p(w,(x_1,x_2))= \begin{cases} \frac14,&w=x_1,\\ 0,&w\ne x_1. \end{cases}p(w,(x1​,x2​))={41​,0,​w=x1​,w=x1​.​

All four triples satisfying w=x1w=x_1w=x1​ receive mass 1/41/41/4, including both possible values of x2x_2x2​; the structure includes nonnegativity of every mass and total mass 111.

QAlgorithms.Papers.Independent.Support50.P26.spectralWordProjector

For a finite index type BBB, any natural number nnn, any family of complex matrices MiM_iMi​ on BBB indexed by 0≤i<n0\le i<n0≤i<n, and any predicate AAA on words z∈Bnz\in B^nz∈Bn, this declaration defines the matrix on BnB^nBn whose entries are

Pab=∑z∈Bn{∏i=0n−1(Mi)aizi (Mi)bizi‾,A(z),0,¬A(z).P_{ab}=\sum_{z\in B^n} \begin{cases} \displaystyle\prod_{i=0}^{n-1}(M_i)_{a_i z_i}\, \overline{(M_i)_{b_i z_i}},&A(z),\\ 0,&\neg A(z). \end{cases}Pab​=z∈Bn∑​⎩⎨⎧​i=0∏n−1​(Mi​)ai​zi​​(Mi​)bi​zi​​​,0,​A(z),¬A(z).​

No unitarity, orthogonality, or normalization assumption on the supplied matrices is imposed. For n=0n=0n=0, there is exactly one empty word and the empty product is 111, so the resulting one-dimensional matrix is 111 if the predicate accepts that word and 000 otherwise.

QAlgorithms.Papers.Independent.Support50.P26.successiveCorner

Let X,B1,B2X,B_1,B_2X,B1​,B2​ be finite types with the decidable equalities needed below. A broadcast channel CCC includes their nonemptiness and assigns each x∈Xx\in Xx∈X a positive semidefinite matrix ρx\rho_xρx​ on B1×B2B_1\times B_2B1​×B2​ with trace 111. Let WWW be a finite auxiliary type and ppp a probability law on W×XW\times XW×X, meaning p(w,x)≥0p(w,x)\ge0p(w,x)≥0 and ∑w,xp(w,x)=1\sum_{w,x}p(w,x)=1∑w,x​p(w,x)=1. Put ρx(1)=Tr⁡B2ρx\rho_x^{(1)}=\operatorname{Tr}_{B_2}\rho_xρx(1)​=TrB2​​ρx​, ρx(2)=Tr⁡B1ρx\rho_x^{(2)}=\operatorname{Tr}_{B_1}\rho_xρx(2)​=TrB1​​ρx​, pW(w)=∑xp(w,x)p_W(w)=\sum_xp(w,x)pW​(w)=∑x​p(w,x), and define block matrices σj\sigma_jσj​ by σj((w,b),(w′,b′))=1w=w′∑xp(w,x)ρx(j)(b,b′)\sigma_j((w,b),(w',b'))=\mathbf1_{w=w'}\sum_xp(w,x)\rho_x^{(j)}(b,b')σj​((w,b),(w′,b′))=1w=w′​∑x​p(w,x)ρx(j)​(b,b′). Write H(q)=−∑iq(i)log⁡2q(i)H(q)=-\sum_iq(i)\log_2q(i)H(q)=−∑i​q(i)log2​q(i), S(A)=−Re⁡tr⁡[f(A)]S(A)=-\operatorname{Re}\operatorname{tr}[f(A)]S(A)=−Retr[f(A)], where f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t is applied through continuous functional calculus, and I(A)=S(Tr⁡2A)+S(Tr⁡1A)−S(A)I(A)=S(\operatorname{Tr}_2A)+S(\operatorname{Tr}_1A)-S(A)I(A)=S(Tr2​A)+S(Tr1​A)−S(A). The defined ordered pair is

(S(σ1)−H(pW)−∑w,xp(w,x)S(ρx(1)), min⁡{I(σ1),I(σ2)}).\left( S(\sigma_1)-H(p_W)-\sum_{w,x}p(w,x)S(\rho_x^{(1)}), \ \min\{I(\sigma_1),I(\sigma_2)\} \right).(S(σ1​)−H(pW​)−w,x∑​p(w,x)S(ρx(1)​), min{I(σ1​),I(σ2​)}).

Zero probabilities are permitted, with 0log⁡20=00\log_2 0=00log2​0=0; no nonnegativity condition is imposed separately on the resulting coordinates.

QAlgorithms.Papers.Independent.Support50.P26.superCap

For any finite types X,B1,B2X,B_1,B_2X,B1​,B2​, the defined natural number is

min⁡{∣X∣, ∣B1∣2+∣B2∣2−1},\min\bigl\{|X|,\ |B_1|^2+|B_2|^2-1\bigr\},min{∣X∣, ∣B1​∣2+∣B2​∣2−1},

where subtraction is natural-number subtraction, truncated at zero. No nonemptiness assumptions are required: in particular, the value is zero if XXX is empty, and the second argument of the minimum is zero if both output types are empty.

QAlgorithms.Papers.Independent.Support50.P26.superPrivate

For finite types W,X,B1,B2W,X,B_1,B_2W,X,B1​,B2​, with decidable equality on WWW and B1B_1B1​, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​ with nonempty input and output types and positive semidefinite, trace-one matrices ρx\rho_xρx​, and a probability law ppp on W×XW\times XW×X, define σx(b,b′)=∑c∈B2ρx((b,c),(b′,c))\sigma_x(b,b')=\sum_{c\in B_2}\rho_x((b,c),(b',c))σx​(b,b′)=∑c∈B2​​ρx​((b,c),(b′,c)), pW(w)=∑xp(w,x)p_W(w)=\sum_xp(w,x)pW​(w)=∑x​p(w,x), and τ1((w,b),(w′,b′))=1w=w′∑xp(w,x)σx(b,b′)\tau_1((w,b),(w',b'))=\mathbf1_{w=w'}\sum_xp(w,x)\sigma_x(b,b')τ1​((w,b),(w′,b′))=1w=w′​∑x​p(w,x)σx​(b,b′). The definition gives the real number

S(τ1)−H(pW)−∑w,xp(w,x)S(σx),S(\tau_1)-H(p_W)-\sum_{w,x}p(w,x)S(\sigma_x),S(τ1​)−H(pW​)−w,x∑​p(w,x)S(σx​),

where S(A)=−Re⁡tr⁡(f(A))S(A)=-\operatorname{Re}\operatorname{tr}(f(A))S(A)=−Retr(f(A)), with f(t)=tlog⁡2tf(t)=t\log_2 tf(t)=tlog2​t applied by continuous functional calculus, and H(q)=−∑wq(w)log⁡2q(w)H(q)=-\sum_wq(w)\log_2q(w)H(q)=−∑w​q(w)log2​q(w). The law requires nonnegative weights summing to 111, but allows zero weights; the real logarithm is totalized, with log⁡20=0\log_2 0=0log2​0=0.

QAlgorithms.Papers.Independent.Support50.P26.superState

For finite types W,X,B1,B2W,X,B_1,B_2W,X,B1​,B2​, with decidable equality on WWW and XXX, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​ with nonempty input and output types and positive semidefinite, trace-one matrices ρx\rho_xρx​, and a probability law ppp on W×XW\times XW×X, meaning p(w,x)≥0p(w,x)\ge0p(w,x)≥0 and ∑w,xp(w,x)=1\sum_{w,x}p(w,x)=1∑w,x​p(w,x)=1, this definition gives the complex matrix Θ\ThetaΘ indexed by (W×X)×(B1×B2)(W\times X)\times(B_1\times B_2)(W×X)×(B1​×B2​) whose entries are

Θ(((w,x),u),((w′,x′),v))={p(w,x)ρx(u,v),(w,x)=(w′,x′),0,otherwise.\Theta\bigl(((w,x),u),((w',x'),v)\bigr) =\begin{cases} p(w,x)\rho_x(u,v),&(w,x)=(w',x'),\\ 0,&\text{otherwise}. \end{cases}Θ(((w,x),u),((w′,x′),v))={p(w,x)ρx​(u,v),0,​(w,x)=(w′,x′),otherwise.​

Zero probabilities are allowed; the existence of the probability law excludes an empty WWW.

QAlgorithms.Papers.Independent.Support50.P26.superTotal

For finite types W,X,B1,B2W,X,B_1,B_2W,X,B1​,B2​, with decidable equality on B1B_1B1​, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​ with nonempty input and output types and positive semidefinite, trace-one matrices ρx\rho_xρx​, and a probability law ppp on W×XW\times XW×X, meaning nonnegative weights summing to 111, put σx(b,b′)=∑c∈B2ρx((b,c),(b′,c))\sigma_x(b,b')=\sum_{c\in B_2}\rho_x((b,c),(b',c))σx​(b,b′)=∑c∈B2​​ρx​((b,c),(b′,c)). The definition gives

S(∑w,xp(w,x)σx)−∑w,xp(w,x)S(σx),S\left(\sum_{w,x}p(w,x)\sigma_x\right) -\sum_{w,x}p(w,x)S(\sigma_x),S(w,x∑​p(w,x)σx​)−w,x∑​p(w,x)S(σx​),

where S(A)=−Re⁡tr⁡(f(A))S(A)=-\operatorname{Re}\operatorname{tr}(f(A))S(A)=−Retr(f(A)), with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied by continuous functional calculus. Zero probabilities are allowed, and the real logarithm is totalized with log⁡20=0\log_2 0=0log2​0=0.

QAlgorithms.Papers.Independent.Support50.P26.superUnion

For a broadcast channel CCC on finite nonempty types X,B1,B2X,B_1,B_2X,B1​,B2​, with decidable equality where needed, write its trace-one positive semidefinite output at xxx as ρx\rho_xρx​, and its two partial traces as ρx(1),ρx(2)\rho_x^{(1)},\rho_x^{(2)}ρx(1)​,ρx(2)​. Given either no cap or a natural-number cap KKK, this definition gives the set of real pairs (r1,r2)(r_1,r_2)(r1​,r2​) for which there exist w∈Nw\in\mathbb Nw∈N and nonnegative numbers p(a,x)p(a,x)p(a,x), indexed by a∈{0,…,w}a\in\{0,\ldots,w\}a∈{0,…,w} and x∈Xx\in Xx∈X, summing to 111. When the cap is KKK, they must satisfy w+1≤Kw+1\le Kw+1≤K; without a cap there is no such bound. Set pA(a)=∑xp(a,x)p_A(a)=\sum_xp(a,x)pA​(a)=∑x​p(a,x), ρˉ1=∑a,xp(a,x)ρx(1)\bar\rho_1=\sum_{a,x}p(a,x)\rho_x^{(1)}ρˉ​1​=∑a,x​p(a,x)ρx(1)​, and σj((a,b),(a′,b′))=1a=a′∑xp(a,x)ρx(j)(b,b′)\sigma_j((a,b),(a',b'))=\mathbf1_{a=a'}\sum_xp(a,x)\rho_x^{(j)}(b,b')σj​((a,b),(a′,b′))=1a=a′​∑x​p(a,x)ρx(j)​(b,b′). With H(q)=−∑iq(i)log⁡2q(i)H(q)=-\sum_iq(i)\log_2q(i)H(q)=−∑i​q(i)log2​q(i), S(M)=−Re⁡tr⁡[f(M)]S(M)=-\operatorname{Re}\operatorname{tr}[f(M)]S(M)=−Retr[f(M)] for the continuous-functional-calculus function f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t, and I(M)=S(Tr⁡2M)+S(Tr⁡1M)−S(M)I(M)=S(\operatorname{Tr}_2M)+S(\operatorname{Tr}_1M)-S(M)I(M)=S(Tr2​M)+S(Tr1​M)−S(M), the required inequalities are

r1,r2≥0,r1≤S(σ1)−H(pA)−∑a,xp(a,x)S(ρx(1)),r2≤I(σ2),r1+r2≤S(ρˉ1)−∑a,xp(a,x)S(ρx(1)).r_1,r_2\ge0,\qquad r_1\le S(\sigma_1)-H(p_A)-\sum_{a,x}p(a,x)S(\rho_x^{(1)}),\qquad r_2\le I(\sigma_2),\qquad r_1+r_2\le S(\bar\rho_1)-\sum_{a,x}p(a,x)S(\rho_x^{(1)}).r1​,r2​≥0,r1​≤S(σ1​)−H(pA​)−a,x∑​p(a,x)S(ρx(1)​),r2​≤I(σ2​),r1​+r2​≤S(ρˉ​1​)−a,x∑​p(a,x)S(ρx(1)​).

Here w=0w=0w=0, hence a one-element auxiliary alphabet, is allowed; cap 000 gives the empty set, and zero-probability auxiliary values are allowed.

QAlgorithms.Papers.Independent.Support50.P26.superWB1

For finite types W,X,B1,B2W,X,B_1,B_2W,X,B1​,B2​, with decidable equality on WWW, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​ with nonempty input and output types and positive semidefinite, trace-one matrices ρx\rho_xρx​, and a probability law ppp on W×XW\times XW×X, meaning p(w,x)≥0p(w,x)\ge0p(w,x)≥0 and ∑w,xp(w,x)=1\sum_{w,x}p(w,x)=1∑w,x​p(w,x)=1, this definition gives the complex matrix τ1\tau_1τ1​ on W×B1W\times B_1W×B1​ with entries

τ1((w,b),(w′,b′))={∑x∈Xp(w,x)∑c∈B2ρx((b,c),(b′,c)),w=w′,0,w≠w′.\tau_1((w,b),(w',b')) =\begin{cases} \displaystyle\sum_{x\in X}p(w,x)\sum_{c\in B_2}\rho_x((b,c),(b',c)),&w=w',\\ 0,&w\ne w'. \end{cases}τ1​((w,b),(w′,b′))=⎩⎨⎧​x∈X∑​p(w,x)c∈B2​∑​ρx​((b,c),(b′,c)),0,​w=w′,w=w′.​

The block corresponding to a label www is not divided by its probability, so labels of probability zero have zero blocks.

QAlgorithms.Papers.Independent.Support50.P26.superWB2

For finite types W,X,B1,B2W,X,B_1,B_2W,X,B1​,B2​, with decidable equality on WWW, a broadcast channel C=(ρx)x∈XC=(\rho_x)_{x\in X}C=(ρx​)x∈X​ with nonempty input and output types and positive semidefinite, trace-one matrices ρx\rho_xρx​, and a probability law ppp on W×XW\times XW×X, meaning p(w,x)≥0p(w,x)\ge0p(w,x)≥0 and ∑w,xp(w,x)=1\sum_{w,x}p(w,x)=1∑w,x​p(w,x)=1, this definition gives the complex matrix τ2\tau_2τ2​ on W×B2W\times B_2W×B2​ with entries

τ2((w,c),(w′,c′))={∑x∈Xp(w,x)∑b∈B1ρx((b,c),(b,c′)),w=w′,0,w≠w′.\tau_2((w,c),(w',c')) =\begin{cases} \displaystyle\sum_{x\in X}p(w,x)\sum_{b\in B_1}\rho_x((b,c),(b,c')),&w=w',\\ 0,&w\ne w'. \end{cases}τ2​((w,c),(w′,c′))=⎩⎨⎧​x∈X∑​p(w,x)b∈B1​∑​ρx​((b,c),(b,c′)),0,​w=w′,w=w′.​

The block corresponding to a label www is not divided by its probability, so labels of probability zero have zero blocks.

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me