Definitions for Classical codes for quantum broadcast channels
DefinitionQAlgorithms_Papers_Independent_Support50_P26The 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 kbounds alphabet size,noneleaves 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.
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
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 , with decidable equality on the output types, a broadcast channel whose matrices are positive semidefinite with trace , and a real pair , this property means and the following: for every and every , there exists a positive natural number such that, for every natural number , there is a code with positive message counts , encoded words , and positive semidefinite decoding families , each summing to its respective identity, satisfying
where . The threshold may depend on both tolerances, and the code may depend on 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 , a broadcast channel consists of witnesses that all three types are nonempty and a family of complex matrices indexed by , such that every is positive semidefinite and has trace . No additional map or channel condition is part of this structure.
QAlgorithms.Papers.Independent.Support50.P26.ConditionalSpectralTypical
For index types , a natural number , an arbitrary function , a real number , and words , , this declaration defines the conjunction
where . No positivity or normalization assumptions on the rows of , and no nonnegativity assumption on , are supplied separately. Symbols absent from impose no frequency condition, so their zero block sizes do not enter a required division. At , both conditions hold vacuously for every and ; at positive , a negative makes the property impossible.
QAlgorithms.Papers.Independent.Support50.P26.CqBroadcastCode
For an arbitrary type , finite types with decidable equality, and a natural number , a code consists of positive natural numbers , an encoding function assigning a word to every and , and families of complex matrices on the -word space and on the -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 , that be finite or nonempty, or that the encoding function be injective.
QAlgorithms.Papers.Independent.Support50.P26.FiniteSpectralResolution
For a finite type equipped with decidable equality and an arbitrary complex matrix indexed by , this structure consists of a function , proofs that for every and , a unitary matrix on , and proofs of the entrywise identities
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 is empty, no such structure exists because the normalization would require .
QAlgorithms.Papers.Independent.Support50.P26.MartonData
For finite types and an arbitrary type , this structure consists of a probability law on , including the requirements for every pair and , together with an arbitrary function . There are no independence, injectivity, or surjectivity requirements on these data. Although empty or are permitted as type parameters, no such structure exists when either is empty, since its probability masses must sum to .
QAlgorithms.Papers.Independent.Support50.P26.MartonRegion
For finite index types , with decidable equality where required, let specify nonempty input and output types and a positive semidefinite, trace-one matrix on for each . Let specify a probability mass function , with , and a function . Write , , and form the block diagonal matrices
For a bipartite matrix , put , where , , and is defined by continuous functional calculus. Put , , , and . The declaration defines the set of precisely those real pairs satisfying
Zero probabilities are allowed.
QAlgorithms.Papers.Independent.Support50.P26.StrongTypical
For an index type , a natural number , an arbitrary function , a real tolerance , and a word , this declaration defines the property
No assumption that is a probability distribution, or that is nonnegative, is part of the definition. At 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 is impossible, and every symbol appearing in the word must have strictly positive -value.
QAlgorithms.Papers.Independent.Support50.P26.SuccessiveRegion
For finite types with decidable equality, a broadcast channel with nonempty input and output types and positive semidefinite, trace-one matrices , and a probability law on , let , , , , and ; 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 satisfying
The weights are nonnegative and sum to , , and , where is applied by continuous functional calculus. Zero weights and equality in every displayed bound are allowed; under the totalized real logarithm.
QAlgorithms.Papers.Independent.Support50.P26.SuperRegion
For finite types with decidable equality, a broadcast channel with nonempty input and output types and positive semidefinite, trace-one matrices , and a probability law on , let , , , , and ; 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 satisfying
The weights are nonnegative and sum to , , and , where is applied by continuous functional calculus. Zero weights and equality in every displayed bound are allowed; under the totalized real logarithm.
QAlgorithms.Papers.Independent.Support50.P26.auxiliaryMI
For finite types , an arbitrary type , and data consisting of a probability law with total mass and a function , this definition gives
Zero probabilities are allowed and contribute zero. The value uses only the law in ; its encoding function does not enter the expression.
QAlgorithms.Papers.Independent.Support50.P26.auxiliaryRateSystem
For arbitrary real numbers and an arbitrary real pair , this declaration defines the conjunction
There are no separate sign assumptions on any of these real numbers.
QAlgorithms.Papers.Independent.Support50.P26.averageJointError
For finite nonempty types , with decidable equality on the output types, a broadcast channel , a natural number , and a code with positive message counts , encoded words , and positive semidefinite decoding families , each summing to the identity, the average joint error is the real number
where . Each is positive semidefinite with trace . The definition includes , with empty products equal to ; the denominator is nonzero because both message counts are positive.
QAlgorithms.Papers.Independent.Support50.P26.averageState1
For finite index types , with decidable equality where required, let specify nonempty input and output types and a positive semidefinite, trace-one matrix on for each input . Let specify a probability mass function , with , and a function . This declaration defines the matrix
on , where . Terms with zero probability contribute zero; the definition contains no conditional normalization or division.
QAlgorithms.Papers.Independent.Support50.P26.averagedProjector
Let be a finite type with decidable equality, let be a complex matrix on , and let supply nonnegative real numbers summing to and a unitary matrix satisfying . For every natural number and real number , this declaration defines the matrix on
The same supplied unitary basis is used at every position. The definition allows every real ; when , no word meets the conditions. At , no word is accepted because acceptance explicitly requires , so the result is the zero matrix on the singleton empty-word space. Supplying is impossible when is empty.
QAlgorithms.Papers.Independent.Support50.P26.broadcastWordOutput
For finite types , a broadcast channel assigning a positive semidefinite, trace-one matrix on to each , any natural number , and a word , the definition gives the complex matrix indexed by pairs of words in and , with entries
The case is included: the indexing type then has one element and the empty product gives its sole entry the value .
QAlgorithms.Papers.Independent.Support50.P26.conditionalState1
For finite index types , with decidable equality where required, let specify nonempty input and output types and density matrices on , and let specify a probability mass function on and a function . For each , put . The declaration defines a matrix on by
where is the input selected by classical choice from the supplied nonemptiness of , and . Since is nonnegative, the second branch occurs precisely when ; it uses this chosen input rather than dividing the zero-mass sum by zero.
QAlgorithms.Papers.Independent.Support50.P26.conditionalTypicalProjector
Let be finite types, with decidable equality as required, and let assign a positive semidefinite, trace-one matrix on to each , with nonempty. Let consist of a probability mass function on and a map . Write , where . For each , put and let when ; otherwise let , using the input chosen from the nonemptiness of . Suppose supplies numbers summing to one and a unitary matrix on satisfying . For every natural number , word , and real , the declaration defines the matrix on by
where the conditions are for every , and, for every whose position set is nonempty and every ,
There is no restriction on ; symbols absent from impose no frequency conditions. For , 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 be a broadcast channel on finite nonempty types , assigning each a positive semidefinite trace-one matrix on . Let be finite auxiliary types, with decidable equality for the block labels, and let consist of a nonnegative probability law summing to and an arbitrary encoding function . This definition gives the matrix on whose entries are
The weights may vanish, and the encoding need not be injective.
QAlgorithms.Papers.Independent.Support50.P26.martonU1B1
Let assign each input in a finite nonempty type a positive semidefinite trace-one matrix on finite nonempty output types . Let finite auxiliary types carry a law with , and let be arbitrary, as supplied by ; assume the decidable equalities needed for the block construction. The defined matrix on is
Thus the blocks use the unnormalized weighted sums of the first-output partial traces; no division by the marginal probability of occurs.
QAlgorithms.Papers.Independent.Support50.P26.martonU2B2
Let assign each input in a finite nonempty type a positive semidefinite trace-one matrix on finite nonempty output types . Let finite auxiliary types carry a law with , and let be arbitrary, as supplied by ; assume the decidable equalities needed for the block construction. The defined matrix on is
Thus the blocks use the unnormalized weighted sums of the second-output partial traces; no division by the marginal probability of occurs.
QAlgorithms.Papers.Independent.Support50.P26.martonUnion
For finite input and output types , with decidable equality where required, let give nonempty such types and density matrices on , and let be either absent or a natural number. This declaration defines a set of real pairs : membership means that there exist natural numbers , a probability mass function on , and a function from this product to , such that the following inequalities hold. Define
, and , where and uses continuous functional calculus with . The required rate inequalities are
If the cap is , the additional requirements are and ; an absent cap imposes no such restriction. Both auxiliary alphabets are always nonempty, including when or . A cap of zero therefore gives the empty set.
QAlgorithms.Papers.Independent.Support50.P26.receiver1Word
Let be finite types, with decidable equality as required. Let have nonempty input and output types and assign a positive semidefinite, trace-one matrix on to each input . Let consist of a nonnegative probability mass function on , summing to one, and an encoding map . For every natural number and words , , the declaration defines a matrix on by
Thus its entries are products of entries of the first-output marginal matrices; the probability mass function carried by does not occur in this formula. The definition includes , when the empty product is and the matrix has a single entry equal to .
QAlgorithms.Papers.Independent.Support50.P26.separatingChannel
This defines a broadcast channel whose input is a pair of Booleans and whose two output types are each Boolean. Its output is the matrix
Thus its output is the rank-one computational-basis projector at . The structure includes nonemptiness of all three types and the facts that every output is positive semidefinite and has trace .
QAlgorithms.Papers.Independent.Support50.P26.separatingLaw
This defines a probability law on triples of Booleans by
All four triples satisfying receive mass , including both possible values of ; the structure includes nonnegativity of every mass and total mass .
QAlgorithms.Papers.Independent.Support50.P26.spectralWordProjector
For a finite index type , any natural number , any family of complex matrices on indexed by , and any predicate on words , this declaration defines the matrix on whose entries are
No unitarity, orthogonality, or normalization assumption on the supplied matrices is imposed. For , there is exactly one empty word and the empty product is , so the resulting one-dimensional matrix is if the predicate accepts that word and otherwise.
QAlgorithms.Papers.Independent.Support50.P26.successiveCorner
Let be finite types with the decidable equalities needed below. A broadcast channel includes their nonemptiness and assigns each a positive semidefinite matrix on with trace . Let be a finite auxiliary type and a probability law on , meaning and . Put , , , and define block matrices by . Write , , where is applied through continuous functional calculus, and . The defined ordered pair is
Zero probabilities are permitted, with ; no nonnegativity condition is imposed separately on the resulting coordinates.
QAlgorithms.Papers.Independent.Support50.P26.superCap
For any finite types , the defined natural number is
where subtraction is natural-number subtraction, truncated at zero. No nonemptiness assumptions are required: in particular, the value is zero if 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 , with decidable equality on and , a broadcast channel with nonempty input and output types and positive semidefinite, trace-one matrices , and a probability law on , define , , and . The definition gives the real number
where , with applied by continuous functional calculus, and . The law requires nonnegative weights summing to , but allows zero weights; the real logarithm is totalized, with .
QAlgorithms.Papers.Independent.Support50.P26.superState
For finite types , with decidable equality on and , a broadcast channel with nonempty input and output types and positive semidefinite, trace-one matrices , and a probability law on , meaning and , this definition gives the complex matrix indexed by whose entries are
Zero probabilities are allowed; the existence of the probability law excludes an empty .
QAlgorithms.Papers.Independent.Support50.P26.superTotal
For finite types , with decidable equality on , a broadcast channel with nonempty input and output types and positive semidefinite, trace-one matrices , and a probability law on , meaning nonnegative weights summing to , put . The definition gives
where , with applied by continuous functional calculus. Zero probabilities are allowed, and the real logarithm is totalized with .
QAlgorithms.Papers.Independent.Support50.P26.superUnion
For a broadcast channel on finite nonempty types , with decidable equality where needed, write its trace-one positive semidefinite output at as , and its two partial traces as . Given either no cap or a natural-number cap , this definition gives the set of real pairs for which there exist and nonnegative numbers , indexed by and , summing to . When the cap is , they must satisfy ; without a cap there is no such bound. Set , , and . With , for the continuous-functional-calculus function , and , the required inequalities are
Here , hence a one-element auxiliary alphabet, is allowed; cap gives the empty set, and zero-probability auxiliary values are allowed.
QAlgorithms.Papers.Independent.Support50.P26.superWB1
For finite types , with decidable equality on , a broadcast channel with nonempty input and output types and positive semidefinite, trace-one matrices , and a probability law on , meaning and , this definition gives the complex matrix on with entries
The block corresponding to a label is not divided by its probability, so labels of probability zero have zero blocks.
QAlgorithms.Papers.Independent.Support50.P26.superWB2
For finite types , with decidable equality on , a broadcast channel with nonempty input and output types and positive semidefinite, trace-one matrices , and a probability law on , meaning and , this definition gives the complex matrix on with entries
The block corresponding to a label is not divided by its probability, so labels of probability zero have zero blocks.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.