Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Distributed Compression and Multiparty Squashed Entanglement

Definition
QAlgorithms_Papers_Independent_Support50_P09

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

prove2quantum

The objects the formalized statements of Distributed Compression and Multiparty Squashed Entanglement (arXiv:0707.2792) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • SenderBlock: PDF pp.2–3: sender blocks, with arbitrary finite local dimensions.
  • blockInput: PDF p.3, (1): n independent copies, ordered as reference then sender blocks.
  • independentEncoders: PDF pp.2–3: tensor product of independent local encoders, on matrix units. Each encoder acts on its sender's entire n-copy block; no shared ancilla is supplied.
  • MultipartyCompressionCode: Definition II.1, PDF p.3: one compression code, with the reference untouched. log2(c_i) <= n Q_i expresses an available dimension budget; smaller outputs can be padded. Integer dimensions avoid the printed idealization 2^(n Q_i).
  • multipartyAchievable: Definition II.1, PDF p.3: all sufficiently large positive blocklengths, with no rate slack inside this set; success is squared pure-state fidelity.
  • multipartyCompressionRegion: Definition II.1, PDF p.3: the closed operational rate region.
  • entropyThreshold: PDF p.7, (7): C_K, with the factor 1/2 on the entire entropy expression.
  • SelectedDims: PDF pp.6,15: local dimensions of the actual selected marginal, in increasing order.
  • selectedState: PDF p.6, (6): trace out the reference and all senders outside K, then reindex. No independently chosen extension or entropy property is assumed.
  • subsetSquashed: PDF p.6, (6), and Definition V.1, pp.15–16: the half-infimum over ALL finite extension dimensions of the actual A_K marginal. The empty-party measure is zero; nonempty one-party inputs use the entropy definition itself.
  • entropyPolyhedron: PDF p.9, (15): the entropy halfspace polyhedron P_H.
  • outerPolyhedron: PDF p.6, (6): the outer family; E_sq is outside the factor 1/2.
  • senderSuffix: PDF pp.7–9: last l senders of one fixed permutation, including l=0.
  • compressionCorner: Definition III.1, PDF p.7: the rate at pi(j) is half its mutual information with R and the STRICTLY LATER senders.
  • compressionCorners: Definition III.1, PDF p.7: set of corner rates; coincidences are allowed.
  • positiveCone: PDF p.9, (13): the resource-wasting cone.
  • vertexPolyhedron: PDF p.9, (14): convex combinations of corners plus arbitrary resource wasting.
  • rateRecession: PDF p.13, Step 3: recession directions, at every feasible point and all t>=0.
  • IsMaximalChain: PDF p.12, (28): m strict inclusions from empty to the full sender set.
  • chainEquations: PDF p.12, (27): the m NONEMPTY chain equations.
  • localMarginal: PDF pp.13–14: single-party partial trace in the original local basis.
  • productOfMarginals: PDF p.14: product of rho's OWN marginals, not a freely chosen product state.
  • stateMixture: PDF p.17, (53): the specified convex mixture.
  • continuityModulus: PDF p.19, (67): the printed modulus, using FULL trace norm (p.2,(66)). The theorem restricts 2 sqrt(eps)<=1; no extension dimension appears.
Definition code
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P33

/-! Avis, Hayden and Savov, arXiv:0707.2792v2.
All systems are finite and nonzero, and entropies are in bits.
The imported halfExtensionSquashed .total is exactly Definition V.1.
Compilation is pending the separately scheduled mechanical compilation stage. -/

noncomputable section

namespace QAlgorithms.Papers.Independent.Support50.P09

open QAlgorithms.Papers.Independent.Claimed50.P33
open scoped Matrix ComplexConjugate ComplexOrder

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF pp.2–3: sender blocks, with arbitrary finite local dimensions. -/
abbrev SenderBlock {m : ℕ} (D : Fin m → Type) (n : ℕ) :=
  (i : Fin m) → Fin n → D i

/-- PDF p.3, (1): n independent copies, ordered as reference then sender blocks. -/
def blockInput {m : ℕ} {D : Fin m → Type} {R : Type}
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ) (n : ℕ) :
    Matrix ((Fin n → R) × SenderBlock D n) ((Fin n → R) × SenderBlock D n) ℂ :=
  fun a b => ∏ t, rho ((fun i => a.2 i t),a.1 t) ((fun i => b.2 i t),b.1 t)

/-- PDF pp.2–3: tensor product of independent local encoders, on matrix units.
Each encoder acts on its sender's entire n-copy block; no shared ancilla is supplied. -/
def independentEncoders {m n : ℕ} {D C : Fin m → Type} [∀ i, Fintype (D i)]
    (enc : (i : Fin m) → Superop (Fin n → D i) (C i)) :
    Superop (SenderBlock D n) (RegisterBasis C) :=
  fun M a b => ∑ x : SenderBlock D n, ∑ y : SenderBlock D n,
    M x y * ∏ i, enc i (Matrix.single (x i) (y i) 1) (a i) (b i)

/-- Definition II.1, PDF p.3: one compression code, with the reference untouched.
log2(c_i) <= n Q_i expresses an available dimension budget; smaller outputs can
be padded. Integer dimensions avoid the printed idealization 2^(n Q_i). -/
def MultipartyCompressionCode {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ)
    (n : ℕ) (Q : Fin m → ℝ) (eps : ℝ) : Prop :=
  ∃ c : Fin m → ℕ, (∀ i, 0 < c i) ∧
    (∀ i, Real.logb 2 (c i) ≤ (n : ℝ) * Q i) ∧
    ∃ enc : (i : Fin m) → Superop (Fin n → D i) (Fin (c i)),
      (∀ i, IsChannel (enc i)) ∧
    ∃ dec : Superop (RegisterBasis (fun i => Fin (c i))) (SenderBlock D n),
      IsChannel dec ∧
      1 - eps ≤ ((blockInput rho n) *
        idTensorSuperop (dec ∘ independentEncoders enc) (blockInput rho n)).trace.re

/-- Definition II.1, PDF p.3: all sufficiently large positive blocklengths,
with no rate slack inside this set; success is squared pure-state fidelity. -/
def multipartyAchievable {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ) : Set (Fin m → ℝ) :=
  {Q | (∀ i, 0 ≤ Q i) ∧ ∀ eps : ℝ, 0 < eps → ∃ N : ℕ,
    ∀ n : ℕ, N ≤ n → 0 < n → MultipartyCompressionCode rho n Q eps}

/-- Definition II.1, PDF p.3: the closed operational rate region. -/
def multipartyCompressionRegion {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ) : Set (Fin m → ℝ) :=
  closure (multipartyAchievable rho)

/-- PDF p.7, (7): C_K, with the factor 1/2 on the entire entropy expression. -/
def entropyThreshold {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ)
    (K : Finset (Fin m)) : ℝ :=
  ((∑ i ∈ K, entropyAt (trivialExtension (forgetEnvironment rho)) {i}) +
    vnEntropy (traceLeft rho) - entropyAt rho K) / 2

/-- PDF pp.6,15: local dimensions of the actual selected marginal, in increasing order. -/
abbrev SelectedDims {m : ℕ} (D : Fin m → Type) (K : Finset (Fin m)) :=
  fun j : Fin K.card => D ((K.orderIsoOfFin rfl) j).val

/-- PDF p.6, (6): trace out the reference and all senders outside K, then reindex.
No independently chosen extension or entropy property is assumed. -/
def selectedState {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ)
    (K : Finset (Fin m)) :
    Matrix (RegisterBasis (SelectedDims D K)) (RegisterBasis (SelectedDims D K)) ℂ :=
  fun a b => forgetEnvironment (registerMarginal rho K)
    (fun i => cast (congrArg (fun j : {j : Fin m // j ∈ K} => D j.val)
      ((K.orderIsoOfFin rfl).apply_symm_apply i)) (a ((K.orderIsoOfFin rfl).symm i)))
    (fun i => cast (congrArg (fun j : {j : Fin m // j ∈ K} => D j.val)
      ((K.orderIsoOfFin rfl).apply_symm_apply i)) (b ((K.orderIsoOfFin rfl).symm i)))

/-- PDF p.6, (6), and Definition V.1, pp.15–16: the half-infimum over ALL
finite extension dimensions of the actual A_K marginal. The empty-party
measure is zero; nonempty one-party inputs use the entropy definition itself. -/
def subsetSquashed {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ)
    (K : Finset (Fin m)) : ℝ :=
  if K = ∅ then 0 else halfExtensionSquashed .total (selectedState rho K)

/-- PDF p.9, (15): the entropy halfspace polyhedron P_H. -/
def entropyPolyhedron {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ) : Set (Fin m → ℝ) :=
  {Q | ∀ K : Finset (Fin m), entropyThreshold rho K ≤ ∑ i ∈ K, Q i}

/-- PDF p.6, (6): the outer family; E_sq is outside the factor 1/2. -/
def outerPolyhedron {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ) : Set (Fin m → ℝ) :=
  {Q | ∀ K : Finset (Fin m),
    entropyThreshold rho K - subsetSquashed rho K ≤ ∑ i ∈ K, Q i}

/-- PDF pp.7–9: last l senders of one fixed permutation, including l=0. -/
def senderSuffix {m : ℕ} (pi : Equiv.Perm (Fin m)) (l : ℕ) : Finset (Fin m) :=
  (Finset.univ.filter fun j : Fin m => m ≤ j.val + l).image pi

/-- Definition III.1, PDF p.7: the rate at pi(j) is half its mutual information
with R and the STRICTLY LATER senders. -/
def compressionCorner {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ)
    (pi : Equiv.Perm (Fin m)) : Fin m → ℝ :=
  fun i =>
    let later := (Finset.univ.filter fun j : Fin m => (pi.symm i).val < j.val).image pi
    (entropyAt (trivialExtension (forgetEnvironment rho)) {i} +
      entropyAt rho later - entropyAt rho (insert i later)) / 2

/-- Definition III.1, PDF p.7: set of corner rates; coincidences are allowed. -/
def compressionCorners {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ) : Set (Fin m → ℝ) :=
  Set.range (compressionCorner rho)

/-- PDF p.9, (13): the resource-wasting cone. -/
def positiveCone (m : ℕ) : Set (Fin m → ℝ) := {v | ∀ i, 0 ≤ v i}

/-- PDF p.9, (14): convex combinations of corners plus arbitrary resource wasting. -/
def vertexPolyhedron {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ) : Set (Fin m → ℝ) :=
  {Q | ∃ x ∈ convexHull ℝ (compressionCorners rho), ∃ v ∈ positiveCone m, Q = x + v}

/-- PDF p.13, Step 3: recession directions, at every feasible point and all t>=0. -/
def rateRecession {m : ℕ} (P : Set (Fin m → ℝ)) : Set (Fin m → ℝ) :=
  {v | ∀ x ∈ P, ∀ t : ℝ, 0 ≤ t → x + t • v ∈ P}

/-- PDF p.12, (28): m strict inclusions from empty to the full sender set. -/
def IsMaximalChain {m : ℕ} (K : Fin (m+1) → Finset (Fin m)) : Prop :=
  K 0 = ∅ ∧ K ⟨m,Nat.lt_succ_self m⟩ = Finset.univ ∧
    ∀ j : Fin m, K j.castSucc ⊂ K j.succ

/-- PDF p.12, (27): the m NONEMPTY chain equations. -/
def chainEquations {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ)
    (K : Fin (m+1) → Finset (Fin m)) (Q : Fin m → ℝ) : Prop :=
  ∀ j : Fin m, (∑ i ∈ K j.succ, Q i) = entropyThreshold rho (K j.succ)

/-- PDF pp.13–14: single-party partial trace in the original local basis. -/
def localMarginal {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    (rho : Matrix (RegisterBasis D) (RegisterBasis D) ℂ) (i : Fin m) :
    Matrix (D i) (D i) ℂ :=
  fun a b => ∑ x : RegisterBasis D, ∑ y : RegisterBasis D,
    if x i = a ∧ y i = b ∧ (∀ j, j ≠ i → x j = y j) then rho x y else 0

/-- PDF p.14: product of rho's OWN marginals, not a freely chosen product state. -/
def productOfMarginals {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    (rho : Matrix (RegisterBasis D) (RegisterBasis D) ℂ) :
    Matrix (RegisterBasis D) (RegisterBasis D) ℂ :=
  fun a b => ∏ i, localMarginal rho i (a i) (b i)

/-- PDF p.17, (53): the specified convex mixture. -/
def stateMixture {I : Type} (lambda : ℝ) (rho sigma : Matrix I I ℂ) : Matrix I I ℂ :=
  (lambda : ℂ) • rho + ((1-lambda : ℝ) : ℂ) • sigma

/-- PDF p.19, (67): the printed modulus, using FULL trace norm (p.2,(66)).
The theorem restricts 2 sqrt(eps)<=1; no extension dimension appears. -/
def continuityModulus {m : ℕ} (D : Fin m → Type) [∀ i, Fintype (D i)] (eps : ℝ) : ℝ :=
  16 * Real.sqrt eps * Real.logb 2 (∏ i, (Fintype.card (D i) : ℝ)) +
    ((m : ℝ)+1) * 2 * binEntropy2 (2 * Real.sqrt eps)

/-! Small sanity examples for the new constructions; no target theorem is proved. -/

example {m : ℕ} {D : Fin m → Type} {R : Type}
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ)
    (a b : (Fin 0 → R) × SenderBlock D 0) : blockInput rho 0 a b = 1 := by
  simp [blockInput]

example {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)] {R : Type} [Fintype R]
    (rho : Matrix (RegisterBasis D × R) (RegisterBasis D × R) ℂ) :
    subsetSquashed rho ∅ = 0 := by simp [subsetSquashed]

example {m : ℕ} (pi : Equiv.Perm (Fin m)) : senderSuffix pi 0 = ∅ := by
  apply Finset.eq_empty_iff_forall_notMem.mpr
  intro i hi
  obtain ⟨j,hj,_⟩ := Finset.mem_image.mp hi
  have h := (Finset.mem_filter.mp hj).2
  exact (Nat.not_le.mpr j.isLt) (by simpa using h)

example {I : Type} (rho sigma : Matrix I I ℂ) : stateMixture 0 rho sigma = sigma := by
  simp [stateMixture]

example {m : ℕ} {Q : Fin m → ℝ} : Q ∈ positiveCone m ↔ ∀ i, 0 ≤ Q i := Iff.rfl

example {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)]
    (rho : Matrix (RegisterBasis D) (RegisterBasis D) ℂ) (a b : RegisterBasis D) :
    productOfMarginals rho a b = ∏ i, localMarginal rho i (a i) (b i) := rfl

section Compression

variable {m : ℕ} {D : Fin m → Type} [∀ i, Fintype (D i)] [hD : ∀ i, Nonempty (D i)]
variable {R : Type} [Fintype R] [hR : Nonempty R]
variable (phi : EuclideanSpace ℂ (RegisterBasis D × R)) (hphi : ‖phi‖ = 1)

include hphi hD hR

end Compression

end QAlgorithms.Papers.Independent.Support50.P09
Source
Distributed Compression and Multiparty Squashed Entanglement, arXiv:0707.2792v2, https://arxiv.org/abs/0707.2792v2
Read-back

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

QAlgorithms.Papers.Independent.Support50.P09.IsMaximalChain

For every natural number mmm and sequence (K0,…,Km)(K_0,\ldots,K_m)(K0​,…,Km​) of subsets of {0,…,m−1}\{0,\ldots,m-1\}{0,…,m−1}, this predicate means

K0=∅,Km={0,…,m−1},Kj⊊Kj+1(0≤j<m).K_0=\varnothing,\qquad K_m=\{0,\ldots,m-1\},\qquad K_j\subsetneq K_{j+1}\quad(0\le j<m).K0​=∅,Km​={0,…,m−1},Kj​⊊Kj+1​(0≤j<m).

Each inclusion is strict. When m=0m=0m=0, there are no inclusion conditions, and the predicate requires the sole set K0K_0K0​ to be empty.

QAlgorithms.Papers.Independent.Support50.P09.MultipartyCompressionCode

For any natural number mmm, finite types DiD_iDi​ indexed by i<mi<mi<m, finite type RRR, arbitrary complex matrix ρ\rhoρ indexed by (∏i<mDi)×R(\prod_{i<m}D_i)\times R(∏i<m​Di​)×R, natural number nnn, real vector Q=(Qi)i<mQ=(Q_i)_{i<m}Q=(Qi​)i<m​, and real number ε\varepsilonε, this predicate asserts that there are positive integers cic_ici​ satisfying log⁡2ci≤nQi\log_2 c_i\le nQ_ilog2​ci​≤nQi​, channels Ei:Din→{0,…,ci−1}\mathcal E_i:D_i^n\to\{0,\ldots,c_i-1\}Ei​:Din​→{0,…,ci​−1}, and a channel D:∏i<m{0,…,ci−1}→∏i<mDin\mathcal D:\prod_{i<m}\{0,\ldots,c_i-1\}\to\prod_{i<m}D_i^nD:∏i<m​{0,…,ci​−1}→∏i<m​Din​, such that

1−ε≤Re⁡tr⁡[Bρ,n (id⁡Rn⊗(D∘E))(Bρ,n)].1-\varepsilon\le \operatorname{Re}\operatorname{tr} \left[B_{\rho,n}\, (\operatorname{id}_{R^n}\otimes(\mathcal D\circ\mathcal E))(B_{\rho,n})\right].1−ε≤Retr[Bρ,n​(idRn​⊗(D∘E))(Bρ,n​)].

Here a channel from a finite basis III to a finite basis JJJ means a matrix function of the form X↦∑ℓ<sKℓXKℓ†X\mapsto\sum_{\ell<s}K_\ell X K_\ell^\daggerX↦∑ℓ<s​Kℓ​XKℓ†​ for some natural number sss, with ∑ℓ<sKℓ†Kℓ=I\sum_{\ell<s}K_\ell^\dagger K_\ell=I∑ℓ<s​Kℓ†​Kℓ​=I; E(M)a,b=∑x,yMx,y∏i<m[Ei(Exi,yi)]ai,bi\mathcal E(M)_{a,b}=\sum_{x,y}M_{x,y}\prod_{i<m}[\mathcal E_i(E_{x_i,y_i})]_{a_i,b_i}E(M)a,b​=∑x,y​Mx,y​∏i<m​[Ei​(Exi​,yi​​)]ai​,bi​​, where x,y∈∏iDinx,y\in\prod_iD_i^nx,y∈∏i​Din​ and Eu,vE_{u,v}Eu,v​ is the matrix unit; and

(Bρ,n)(r,x),(s,y)=∏t<nρ((xi,t)i,rt),((yi,t)i,st).(B_{\rho,n})_{(r,x),(s,y)} =\prod_{t<n}\rho_{((x_{i,t})_i,r_t),((y_{i,t})_i,s_t)}.(Bρ,n​)(r,x),(s,y)​=t<n∏​ρ((xi,t​)i​,rt​),((yi,t​)i​,st​)​.

For any matrix function Λ\LambdaΛ, the displayed extension acts by [(id⁡Rn⊗Λ)(Y)](r,u),(s,v)=[Λ((Y(r,x),(s,y))x,y)]u,v[(\operatorname{id}_{R^n}\otimes\Lambda)(Y)]_{(r,u),(s,v)}=[\Lambda((Y_{(r,x),(s,y)})_{x,y})]_{u,v}[(idRn​⊗Λ)(Y)](r,u),(s,v)​=[Λ((Y(r,x),(s,y)​)x,y​)]u,v​. No density-matrix assumption on ρ\rhoρ, restriction on ε\varepsilonε, or positivity assumption on nnn is included. The finite bases may be empty, and m=0m=0m=0 and n=0n=0n=0 are included; for n=0n=0n=0, Bρ,0B_{\rho,0}Bρ,0​ is the one-entry matrix [1][1][1].

QAlgorithms.Papers.Independent.Support50.P09.SelectedDims

For any natural number mmm, family of types DiD_iDi​ indexed by i<mi<mi<m, and subset K⊆{0,…,m−1}K\subseteq\{0,\ldots,m-1\}K⊆{0,…,m−1}, let i0<i1<⋯<ir−1i_0<i_1<\cdots<i_{r-1}i0​<i1​<⋯<ir−1​ be the increasing enumeration of KKK, where r=∣K∣r=|K|r=∣K∣. The selected family is the family of types indexed by j<rj<rj<r whose jjj-th type is DijD_{i_j}Dij​​. No finiteness or nonemptiness assumptions are imposed on the types DiD_iDi​. If K=∅K=\varnothingK=∅, this is a family with no indices.

QAlgorithms.Papers.Independent.Support50.P09.SenderBlock

For any natural numbers m,nm,nm,n and any family of types DiD_iDi​, indexed by i∈{0,…,m−1}i\in\{0,\ldots,m-1\}i∈{0,…,m−1}, the sender block is the type

∏i=0m−1Di{0,…,n−1}.\prod_{i=0}^{m-1} D_i^{\{0,\ldots,n-1\}}.i=0∏m−1​Di{0,…,n−1}​.

Thus an element assigns a value in DiD_iDi​ to every sender iii and every position t<nt<nt<n. The types DiD_iDi​ need not be finite or nonempty. If m=0m=0m=0 or n=0n=0n=0, this type has exactly one element.

QAlgorithms.Papers.Independent.Support50.P09.blockInput

For any natural number mmm, family of types DiD_iDi​ indexed by i<mi<mi<m, type RRR, complex matrix ρ\rhoρ indexed by (∏i<mDi)×R(\prod_{i<m}D_i)\times R(∏i<m​Di​)×R, and natural number nnn, define a complex matrix Bρ,nB_{\rho,n}Bρ,n​ indexed by R{0,…,n−1}×∏i<mDi{0,…,n−1}R^{\{0,\ldots,n-1\}}\times\prod_{i<m}D_i^{\{0,\ldots,n-1\}}R{0,…,n−1}×∏i<m​Di{0,…,n−1}​ as follows: writing its row and column indices as (r,x)(r,x)(r,x) and (s,y)(s,y)(s,y), respectively,

(Bρ,n)(r,x),(s,y)=∏t=0n−1ρ((xi,t)i<m,rt), ((yi,t)i<m,st).(B_{\rho,n})_{(r,x),(s,y)} = \prod_{t=0}^{n-1} \rho_{\bigl((x_{i,t})_{i<m},r_t\bigr),\, \bigl((y_{i,t})_{i<m},s_t\bigr)}.(Bρ,n​)(r,x),(s,y)​=t=0∏n−1​ρ((xi,t​)i<m​,rt​),((yi,t​)i<m​,st​)​.

No finiteness, nonemptiness, positivity, or normalization assumptions are imposed on these types or on ρ\rhoρ. When n=0n=0n=0, the indexing type is a singleton and the sole matrix entry is the empty product 111.

QAlgorithms.Papers.Independent.Support50.P09.chainEquations

For every natural number mmm, family of finite types (Di)i=0m−1(D_i)_{i=0}^{m-1}(Di​)i=0m−1​, finite type RRR, arbitrary complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, sequence (K0,…,Km)(K_0,\ldots,K_m)(K0​,…,Km​) of subsets of the mmm indices, and real vector Q∈RmQ\in\mathbb R^mQ∈Rm, this predicate requires, for every 0≤j<m0\le j<m0≤j<m,

∑i∈Kj+1Qi=∑i∈Kj+1H(τ{i})+H(ρR)−H(ρKj+1R)2.\sum_{i\in K_{j+1}}Q_i = \frac{\displaystyle\sum_{i\in K_{j+1}}H(\tau_{\{i\}}) +H(\rho_R)-H(\rho_{K_{j+1}R})}{2}.i∈Kj+1​∑​Qi​=2i∈Kj+1​∑​H(τ{i}​)+H(ρR​)−H(ρKj+1​R​)​.

Here ρSR((u,r),(v,s))=∑zρ((u⊔z,r),(v⊔z,s))\rho_{SR}((u,r),(v,s))=\sum_z\rho((u\sqcup z,r),(v\sqcup z,s))ρSR​((u,r),(v,s))=∑z​ρ((u⊔z,r),(v⊔z,s)), with zzz ranging over assignments to coordinates outside SSS; τS(u,v)=∑r∈RρSR((u,r),(v,r))\tau_S(u,v)=\sum_{r\in R}\rho_{SR}((u,r),(v,r))τS​(u,v)=∑r∈R​ρSR​((u,r),(v,r)); and ρR(r,s)=∑x∈∏iDiρ((x,r),(x,s))\rho_R(r,s)=\sum_{x\in\prod_iD_i}\rho((x,r),(x,s))ρR​(r,s)=∑x∈∏i​Di​​ρ((x,r),(x,s)). The functional H(X)H(X)H(X) is −Re⁡tr⁡(f(X))-\operatorname{Re}\operatorname{tr}(f(X))−Retr(f(X)), where f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t is applied through real continuous functional calculus. There is no requirement that ρ\rhoρ be a density matrix, that the finite types be nonempty, that QQQ be nonnegative, or that KKK be a maximal chain. The value K0K_0K0​ is unused, and when m=0m=0m=0 the predicate is vacuously true.

QAlgorithms.Papers.Independent.Support50.P09.compressionCorner

For every natural number mmm, family of finite types (Di)i=0m−1(D_i)_{i=0}^{m-1}(Di​)i=0m−1​, finite type RRR, arbitrary complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, and permutation π\piπ of {0,…,m−1}\{0,\ldots,m-1\}{0,…,m−1}, this defines a real vector with coordinate

Cπ(i)=H(τ{i})+H(ρLiR)−H(ρ(Li∪{i})R)2,Li={π(j):π−1(i)<j<m}.C_\pi(i)=\frac{H(\tau_{\{i\}})+H(\rho_{L_iR})-H(\rho_{(L_i\cup\{i\})R})}{2}, \qquad L_i=\{\pi(j):\pi^{-1}(i)<j<m\}.Cπ​(i)=2H(τ{i}​)+H(ρLi​R​)−H(ρ(Li​∪{i})R​)​,Li​={π(j):π−1(i)<j<m}.

Here ρSR\rho_{SR}ρSR​ retains the coordinates in SSS and the register RRR: its entry at (u,r),(v,s)(u,r),(v,s)(u,r),(v,s) is

ρSR((u,r),(v,s))=∑z∈∏j∉SDjρ((u⊔z,r),(v⊔z,s)),\rho_{SR}((u,r),(v,s)) =\sum_{z\in\prod_{j\notin S}D_j}\rho((u\sqcup z,r),(v\sqcup z,s)),ρSR​((u,r),(v,s))=z∈∏j∈/S​Dj​∑​ρ((u⊔z,r),(v⊔z,s)),

where u⊔zu\sqcup zu⊔z combines the assignments on SSS and its complement; τS(u,v)=∑r∈RρSR((u,r),(v,r))\tau_S(u,v)=\sum_{r\in R}\rho_{SR}((u,r),(v,r))τS​(u,v)=∑r∈R​ρSR​((u,r),(v,r)). The functional H(X)H(X)H(X) means −Re⁡tr⁡(f(X))-\operatorname{Re}\operatorname{tr}(f(X))−Retr(f(X)), with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied through the real continuous functional calculus; adjoining a one-element register to τS\tau_SτS​ leaves the displayed indexing interpretation unchanged. No positivity, Hermiticity, or trace-one assumption on ρ\rhoρ, and no nonemptiness assumption on the finite types, is imposed. Empty sums are zero; for m=0m=0m=0, the result is the unique vector with no coordinates.

QAlgorithms.Papers.Independent.Support50.P09.compressionCorners

For every natural number mmm, family of finite types (Di)i=0m−1(D_i)_{i=0}^{m-1}(Di​)i=0m−1​, finite type RRR, and arbitrary complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, this defines the set of real vectors

{Cπ:π is a permutation of {0,…,m−1}},Cπ(i)=H(τ{i})+H(ρLiR)−H(ρ(Li∪{i})R)2,Li={π(j):π−1(i)<j<m}.\left\{C_\pi:\pi\text{ is a permutation of }\{0,\ldots,m-1\}\right\}, \qquad C_\pi(i)=\frac{H(\tau_{\{i\}})+H(\rho_{L_iR})-H(\rho_{(L_i\cup\{i\})R})}{2}, \quad L_i=\{\pi(j):\pi^{-1}(i)<j<m\}.{Cπ​:π is a permutation of {0,…,m−1}},Cπ​(i)=2H(τ{i}​)+H(ρLi​R​)−H(ρ(Li​∪{i})R​)​,Li​={π(j):π−1(i)<j<m}.

For a subset SSS, the matrix ρSR\rho_{SR}ρSR​ has entries ∑zρ((u⊔z,r),(v⊔z,s))\sum_z\rho((u\sqcup z,r),(v\sqcup z,s))∑z​ρ((u⊔z,r),(v⊔z,s)), where u,v∈∏i∈SDiu,v\in\prod_{i\in S}D_iu,v∈∏i∈S​Di​, r,s∈Rr,s\in Rr,s∈R, and zzz ranges over assignments to the complementary coordinates; τS(u,v)=∑r∈RρSR((u,r),(v,r))\tau_S(u,v)=\sum_{r\in R}\rho_{SR}((u,r),(v,r))τS​(u,v)=∑r∈R​ρSR​((u,r),(v,r)). Here H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), using real continuous functional calculus with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t. The set contains the vectors obtained from all permutations, without requiring distinct permutations to give distinct vectors. The matrix need not be a density matrix, and the finite types may be empty. When m=0m=0m=0, this is the singleton containing the unique vector with no coordinates.

QAlgorithms.Papers.Independent.Support50.P09.continuityModulus

For every natural number mmm, family of finite types (Di)i=0m−1(D_i)_{i=0}^{m-1}(Di​)i=0m−1​, and arbitrary real number ε\varepsilonε, this defines

16ε log⁡2 ⁣(∏i=0m−1∣Di∣)+2(m+1) binEntropy⁡(2ε)ln⁡2.16\sqrt{\varepsilon}\, \log_2\!\left(\prod_{i=0}^{m-1}|D_i|\right) +2(m+1)\, \frac{\operatorname{binEntropy}(2\sqrt{\varepsilon})}{\ln2}.16ε​log2​(i=0∏m−1​∣Di​∣)+2(m+1)ln2binEntropy(2ε​)​.

Here binEntropy⁡(p)=−pln⁡p−(1−p)ln⁡(1−p)\operatorname{binEntropy}(p)=-p\ln p-(1-p)\ln(1-p)binEntropy(p)=−plnp−(1−p)ln(1−p), using the total real logarithm, with ln⁡0=0\ln0=0ln0=0 and ln⁡x=ln⁡∣x∣\ln x=\ln|x|lnx=ln∣x∣ for negative xxx. No positivity of ε\varepsilonε or nonemptiness of the finite types is assumed, and 2ε2\sqrt{\varepsilon}2ε​ need not lie in [0,1][0,1][0,1]. The real square root is zero for ε≤0\varepsilon\le0ε≤0, giving value zero in that case. An empty factor type makes the product zero and hence the logarithmic term zero; when m=0m=0m=0, the empty product is 111 and the value is 2binEntropy⁡(2ε)/ln⁡22\operatorname{binEntropy}(2\sqrt{\varepsilon})/\ln22binEntropy(2ε​)/ln2.

QAlgorithms.Papers.Independent.Support50.P09.entropyPolyhedron

For any natural number mmm, finite types DiD_iDi​ indexed by i<mi<mi<m, finite type RRR, and arbitrary complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, this is the set of real vectors Q=(Qi)i<mQ=(Q_i)_{i<m}Q=(Qi​)i<m​ satisfying, for every subset K⊆{0,…,m−1}K\subseteq\{0,\ldots,m-1\}K⊆{0,…,m−1},

∑i∈KS(ρi)+S(ρR)−S(ρKR)2≤∑i∈KQi.\frac{\displaystyle\sum_{i\in K}S(\rho_i)+S(\rho_R)-S(\rho_{KR})}{2} \le \sum_{i\in K}Q_i.2i∈K∑​S(ρi​)+S(ρR​)−S(ρKR​)​≤i∈K∑​Qi​.

Here ρi\rho_iρi​ is obtained by summing over equal reference indices and equal indices of all sender factors except iii; ρR\rho_RρR​ sums over equal indices of all sender factors; and ρKR\rho_{KR}ρKR​ sums over equal indices of sender factors outside KKK, retaining the reference. Explicitly, its entry at (u,r),(v,s)(u,r),(v,s)(u,r),(v,s) sums ρ(x,r),(y,s)\rho_{(x,r),(y,s)}ρ(x,r),(y,s)​ over x∣K=ux|_K=ux∣K​=u, y∣K=vy|_K=vy∣K​=v, and x∣Kc=y∣Kcx|_{K^c}=y|_{K^c}x∣Kc​=y∣Kc​. The entropy is S(X)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](X))S(X)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](X))S(X)=−Retr(cfc[x↦xlog2​x](X)). No density-matrix, nonemptiness, or separate coordinatewise nonnegativity assumptions are imposed. The empty-subset inequality is 0≤00\le00≤0, and m=0m=0m=0 is allowed.

QAlgorithms.Papers.Independent.Support50.P09.entropyThreshold

For any natural number mmm, finite types DiD_iDi​ indexed by i<mi<mi<m, finite type RRR, complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, and subset K⊆{0,…,m−1}K\subseteq\{0,\ldots,m-1\}K⊆{0,…,m−1}, define

Tρ(K)=∑i∈KS(ρi)+S(ρR)−S(ρKR)2.T_\rho(K)= \frac{\displaystyle\sum_{i\in K}S(\rho_i)+S(\rho_R)-S(\rho_{KR})}{2}.Tρ​(K)=2i∈K∑​S(ρi​)+S(ρR​)−S(ρKR​)​.

Here (ρR)r,s=∑xρ(x,r),(x,s)(\rho_R)_{r,s}=\sum_x\rho_{(x,r),(x,s)}(ρR​)r,s​=∑x​ρ(x,r),(x,s)​; (ρi)a,b(\rho_i)_{a,b}(ρi​)a,b​ is the sum of ρ(x,r),(y,r)\rho_{(x,r),(y,r)}ρ(x,r),(y,r)​ over all r,x,yr,x,yr,x,y with xi=ax_i=axi​=a, yi=by_i=byi​=b, and xj=yjx_j=y_jxj​=yj​ for every j≠ij\ne ij=i; and (ρKR)(u,r),(v,s)(\rho_{KR})_{(u,r),(v,s)}(ρKR​)(u,r),(v,s)​ is the sum of ρ(x,r),(y,s)\rho_{(x,r),(y,s)}ρ(x,r),(y,s)​ over x,yx,yx,y restricting to u,vu,vu,v on KKK and agreeing outside KKK. The entropy used here is the total matrix expression S(X)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](X))S(X)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](X))S(X)=−Retr(cfc[x↦xlog2​x](X)), with cfc⁡\operatorname{cfc}cfc denoting the continuous functional calculus. No positivity, normalization, or nonemptiness assumptions are imposed. The empty subset is included and gives Tρ(∅)=0T_\rho(\varnothing)=0Tρ​(∅)=0.

QAlgorithms.Papers.Independent.Support50.P09.independentEncoders

For any natural numbers m,nm,nm,n, finite types DiD_iDi​ and arbitrary types CiC_iCi​ indexed by i<mi<mi<m, and functions Ei\mathcal E_iEi​ from complex matrices indexed by Di{0,…,n−1}D_i^{\{0,\ldots,n-1\}}Di{0,…,n−1}​ to complex matrices indexed by CiC_iCi​, define a function E\mathcal EE from complex matrices indexed by ∏i<mDi{0,…,n−1}\prod_{i<m}D_i^{\{0,\ldots,n-1\}}∏i<m​Di{0,…,n−1}​ to complex matrices indexed by ∏i<mCi\prod_{i<m}C_i∏i<m​Ci​ by

E(M)a,b=∑x,y∈∏i<mDi{0,…,n−1}Mx,y∏i<m[Ei(Exi,yi)]ai,bi,\mathcal E(M)_{a,b} = \sum_{x,y\in\prod_{i<m}D_i^{\{0,\ldots,n-1\}}} M_{x,y}\prod_{i<m} \bigl[\mathcal E_i(E_{x_i,y_i})\bigr]_{a_i,b_i},E(M)a,b​=x,y∈∏i<m​Di{0,…,n−1}​∑​Mx,y​i<m∏​[Ei​(Exi​,yi​​)]ai​,bi​​,

where Eu,vE_{u,v}Eu,v​ is the matrix with entry 111 at (u,v)(u,v)(u,v) and 000 elsewhere. The supplied functions Ei\mathcal E_iEi​ are not assumed to be linear or channels. The finite types DiD_iDi​ may be empty, and m,nm,nm,n may be zero; all sums and products use their usual empty-index conventions.

QAlgorithms.Papers.Independent.Support50.P09.localMarginal

For every natural number mmm, family of finite types (Dj)j=0m−1(D_j)_{j=0}^{m-1}(Dj​)j=0m−1​, arbitrary complex matrix ρ\rhoρ indexed by ∏jDj\prod_jD_j∏j​Dj​, and index i∈{0,…,m−1}i\in\{0,\ldots,m-1\}i∈{0,…,m−1}, this defines the complex matrix on DiD_iDi​ whose entry at a,b∈Dia,b\in D_ia,b∈Di​ is

∑x,y∈∏jDjxi=a, yi=bxj=yj for every j≠iρ(x,y).\sum_{\substack{x,y\in\prod_jD_j\\ x_i=a,\ y_i=b\\ x_j=y_j\ \text{for every }j\ne i}}\rho(x,y).x,y∈∏j​Dj​xi​=a, yi​=bxj​=yj​ for every j=i​∑​ρ(x,y).

No density-matrix assumption is imposed, and the finite types may be empty; empty sums contribute zero. An index iii cannot be supplied when m=0m=0m=0.

QAlgorithms.Papers.Independent.Support50.P09.multipartyAchievable

For any natural number mmm, finite types DiD_iDi​ indexed by i<mi<mi<m, finite type RRR, and arbitrary complex matrix ρ\rhoρ indexed by (∏i<mDi)×R(\prod_{i<m}D_i)\times R(∏i<m​Di​)×R, this is the set of real vectors QQQ with Qi≥0Q_i\ge0Qi​≥0 for every i<mi<mi<m such that, for every real ε>0\varepsilon>0ε>0, there is a natural number NNN for which every natural number n≥Nn\ge Nn≥N with n>0n>0n>0 admits positive integers cic_ici​, channels Ei:Din→{0,…,ci−1}\mathcal E_i:D_i^n\to\{0,\ldots,c_i-1\}Ei​:Din​→{0,…,ci​−1}, and a channel D:∏i{0,…,ci−1}→∏iDin\mathcal D:\prod_i\{0,\ldots,c_i-1\}\to\prod_iD_i^nD:∏i​{0,…,ci​−1}→∏i​Din​, satisfying

log⁡2ci≤nQi(i<m),1−ε≤Re⁡tr⁡[Bρ,n(id⁡Rn⊗(D∘E))(Bρ,n)].\log_2c_i\le nQ_i\quad(i<m),\qquad 1-\varepsilon\le \operatorname{Re}\operatorname{tr} \left[B_{\rho,n}(\operatorname{id}_{R^n}\otimes(\mathcal D\circ\mathcal E))(B_{\rho,n})\right].log2​ci​≤nQi​(i<m),1−ε≤Retr[Bρ,n​(idRn​⊗(D∘E))(Bρ,n​)].

Here Bρ,n((r,x),(s,y))=∏t<nρ(((xi,t)i,rt),((yi,t)i,st))B_{\rho,n}((r,x),(s,y))=\prod_{t<n}\rho(((x_{i,t})_i,r_t),((y_{i,t})_i,s_t))Bρ,n​((r,x),(s,y))=∏t<n​ρ(((xi,t​)i​,rt​),((yi,t​)i​,st​)), and E(M)a,b=∑x,yMx,y∏i[Ei(Exi,yi)]ai,bi\mathcal E(M)_{a,b}=\sum_{x,y}M_{x,y}\prod_i[\mathcal E_i(E_{x_i,y_i})]_{a_i,b_i}E(M)a,b​=∑x,y​Mx,y​∏i​[Ei​(Exi​,yi​​)]ai​,bi​​, with Eu,vE_{u,v}Eu,v​ the matrix unit. The extension id⁡⊗Λ\operatorname{id}\otimes\Lambdaid⊗Λ applies Λ\LambdaΛ separately to each matrix block with fixed reference row and column. Each channel is required to have a finite Kraus representation X↦∑ℓKℓXKℓ†X\mapsto\sum_\ell K_\ell X K_\ell^\daggerX↦∑ℓ​Kℓ​XKℓ†​ with ∑ℓKℓ†Kℓ=I\sum_\ell K_\ell^\dagger K_\ell=I∑ℓ​Kℓ†​Kℓ​=I. The choices may depend on ε\varepsilonε and nnn; no density-matrix or nonemptiness assumptions are imposed on ρ\rhoρ or its bases, m=0m=0m=0 is allowed, and block length n=0n=0n=0 is excluded from the eventual requirement.

QAlgorithms.Papers.Independent.Support50.P09.multipartyCompressionRegion

For any natural number mmm, finite types DiD_iDi​ indexed by i<mi<mi<m, finite type RRR, and arbitrary complex matrix ρ\rhoρ indexed by (∏i<mDi)×R(\prod_{i<m}D_i)\times R(∏i<m​Di​)×R, this region is the closure in Rm\mathbb R^mRm of the following set A\mathcal AA: a vector QQQ lies in A\mathcal AA exactly when every Qi≥0Q_i\ge0Qi​≥0 and, for every ε>0\varepsilon>0ε>0, all sufficiently large positive integers nnn admit positive integers cic_ici​, channels Ei:Din→{0,…,ci−1}\mathcal E_i:D_i^n\to\{0,\ldots,c_i-1\}Ei​:Din​→{0,…,ci​−1}, and a channel D:∏i{0,…,ci−1}→∏iDin\mathcal D:\prod_i\{0,\ldots,c_i-1\}\to\prod_iD_i^nD:∏i​{0,…,ci​−1}→∏i​Din​, for which

log⁡2ci≤nQi,1−ε≤Re⁡tr⁡[Bρ,n(id⁡Rn⊗(D∘E))(Bρ,n)].\log_2c_i\le nQ_i,\qquad 1-\varepsilon\le \operatorname{Re}\operatorname{tr} \left[B_{\rho,n}(\operatorname{id}_{R^n}\otimes(\mathcal D\circ\mathcal E))(B_{\rho,n})\right].log2​ci​≤nQi​,1−ε≤Retr[Bρ,n​(idRn​⊗(D∘E))(Bρ,n​)].

The matrix Bρ,nB_{\rho,n}Bρ,n​ has entries ∏t<nρ(((xi,t)i,rt),((yi,t)i,st))\prod_{t<n}\rho(((x_{i,t})_i,r_t),((y_{i,t})_i,s_t))∏t<n​ρ(((xi,t​)i​,rt​),((yi,t​)i​,st​)), and E(M)a,b=∑x,yMx,y∏i[Ei(Exi,yi)]ai,bi\mathcal E(M)_{a,b}=\sum_{x,y}M_{x,y}\prod_i[\mathcal E_i(E_{x_i,y_i})]_{a_i,b_i}E(M)a,b​=∑x,y​Mx,y​∏i​[Ei​(Exi​,yi​​)]ai​,bi​​, where Eu,vE_{u,v}Eu,v​ is the matrix unit. The reference extension applies the indicated matrix function to each block with fixed reference indices. A channel is a function X↦∑ℓKℓXKℓ†X\mapsto\sum_\ell K_\ell X K_\ell^\daggerX↦∑ℓ​Kℓ​XKℓ†​ with finitely many Kraus matrices and ∑ℓKℓ†Kℓ=I\sum_\ell K_\ell^\dagger K_\ell=I∑ℓ​Kℓ†​Kℓ​=I. Equivalently, every neighborhood of a vector in this region meets A\mathcal AA. No density-matrix or nonemptiness assumptions are imposed, and m=0m=0m=0 is included.

QAlgorithms.Papers.Independent.Support50.P09.outerPolyhedron

For any natural number mmm, finite types DiD_iDi​ indexed by i<mi<mi<m, finite type RRR, and arbitrary complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, this is the set of real vectors QQQ satisfying, for every subset K⊆{0,…,m−1}K\subseteq\{0,\ldots,m-1\}K⊆{0,…,m−1},

∑i∈KS(ρi)+S(ρR)−S(ρKR)2−qρ(K)≤∑i∈KQi.\frac{\displaystyle\sum_{i\in K}S(\rho_i)+S(\rho_R)-S(\rho_{KR})}{2} -q_\rho(K)\le\sum_{i\in K}Q_i.2i∈K∑​S(ρi​)+S(ρR​)−S(ρKR​)​−qρ​(K)≤i∈K∑​Qi​.

The matrices ρi,ρR,ρKR\rho_i,\rho_R,\rho_{KR}ρi​,ρR​,ρKR​ are obtained by summing over equal row and column indices of the discarded factors, retaining respectively sender iii, the reference RRR, and the senders in KKK together with RRR. Set qρ(∅)=0q_\rho(\varnothing)=0qρ​(∅)=0; for nonempty K={i0<⋯<ir−1}K=\{i_0<\cdots<i_{r-1}\}K={i0​<⋯<ir−1​}, set

qρ(K)=12inf⁡e>0, e∈Nσ≥0, tr⁡σ=1Tr⁡Eσ=τK[∑j<rS(σjE)−S(σ)−(r−1)S(σE)],q_\rho(K)=\frac12 \inf_{\substack{e>0,\ e\in\mathbb N\\ \sigma\ge0,\ \operatorname{tr}\sigma=1\\ \operatorname{Tr}_{E}\sigma=\tau_K}} \left[\sum_{j<r}S(\sigma_{jE})-S(\sigma)-(r-1)S(\sigma_E)\right],qρ​(K)=21​e>0, e∈Nσ≥0, trσ=1TrE​σ=τK​​inf​[j<r∑​S(σjE​)−S(σ)−(r−1)S(σE​)],

where E={0,…,e−1}E=\{0,\ldots,e-1\}E={0,…,e−1}, τK=Tr⁡RρKR\tau_K=\operatorname{Tr}_R\rho_{KR}τK​=TrR​ρKR​ with its sender factors ordered increasingly, and σ\sigmaσ is indexed by (∏j<rDij)×E(\prod_{j<r}D_{i_j})\times E(∏j<r​Dij​​)×E. Its marginals retain the indicated factors, and its extensions need not be classical. Throughout, S(X)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](X))S(X)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](X))S(X)=−Retr(cfc[x↦xlog2​x](X)); an infimum over no admissible extensions is 000. No density-matrix or nonemptiness assumptions on the original input, or separate coordinatewise nonnegativity condition on QQQ, are imposed. The empty-subset inequality is 0≤00\le00≤0, and m=0m=0m=0 is included.

QAlgorithms.Papers.Independent.Support50.P09.positiveCone

For every natural number mmm, this defines the set

{v∈R{0,…,m−1}:∀i, vi≥0}.\{v\in\mathbb R^{\{0,\ldots,m-1\}}:\forall i,\ v_i\ge0\}.{v∈R{0,…,m−1}:∀i, vi​≥0}.

Zero coordinates are permitted. When m=0m=0m=0, the condition is vacuous, so the set contains the unique vector with no coordinates.

QAlgorithms.Papers.Independent.Support50.P09.productOfMarginals

For every natural number mmm, family of finite types (Di)i=0m−1(D_i)_{i=0}^{m-1}(Di​)i=0m−1​, and arbitrary complex matrix ρ\rhoρ indexed by ∏iDi\prod_iD_i∏i​Di​, this defines the matrix whose entry at assignments a,b∈∏iDia,b\in\prod_iD_ia,b∈∏i​Di​ is

∏i=0m−1(∑x,y∈∏jDjxi=ai, yi=bixj=yj for every j≠iρ(x,y)).\prod_{i=0}^{m-1} \left( \sum_{\substack{x,y\in\prod_jD_j\\ x_i=a_i,\ y_i=b_i\\ x_j=y_j\ \text{for every }j\ne i}} \rho(x,y) \right).i=0∏m−1​​x,y∈∏j​Dj​xi​=ai​, yi​=bi​xj​=yj​ for every j=i​∑​ρ(x,y)​.

Thus each factor is obtained by summing entries with all coordinates other than iii equal. No positivity or trace normalization is assumed, and the finite types need not be nonempty. When m=0m=0m=0, the assignment type has one element and the empty product is 111, so the resulting one-by-one matrix has entry 111, independently of ρ\rhoρ.

QAlgorithms.Papers.Independent.Support50.P09.rateRecession

For every natural number mmm and arbitrary set P⊆RmP\subseteq\mathbb R^mP⊆Rm, this defines

{v∈Rm:∀x∈P, ∀t∈R, t≥0⟹x+tv∈P}.\{v\in\mathbb R^m:\forall x\in P,\ \forall t\in\mathbb R,\ t\ge0\Longrightarrow x+tv\in P\}.{v∈Rm:∀x∈P, ∀t∈R, t≥0⟹x+tv∈P}.

No convexity, closedness, or nonemptiness of PPP is required. In particular, if P=∅P=\varnothingP=∅, every vector satisfies the condition vacuously. When m=0m=0m=0, the resulting set contains the unique vector with no coordinates, regardless of PPP.

QAlgorithms.Papers.Independent.Support50.P09.selectedState

For any natural number mmm, finite types DiD_iDi​ indexed by i<mi<mi<m, finite type RRR, arbitrary complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, and subset K⊆{0,…,m−1}K\subseteq\{0,\ldots,m-1\}K⊆{0,…,m−1}, enumerate KKK increasingly as i0,…,ir−1i_0,\ldots,i_{r-1}i0​,…,ir−1​. The selected matrix τK\tau_KτK​, indexed by ∏j<rDij\prod_{j<r}D_{i_j}∏j<r​Dij​​, is defined by

(τK)a,b=∑z∈R ∑x,y∈∏i<mDixij=aj, yij=bj (j<r)xi=yi (i∉K)ρ(x,z),(y,z).(\tau_K)_{a,b} = \sum_{z\in R} \ \sum_{\substack{x,y\in\prod_{i<m}D_i\\ x_{i_j}=a_j,\ y_{i_j}=b_j\ (j<r)\\ x_i=y_i\ (i\notin K)}} \rho_{(x,z),(y,z)}.(τK​)a,b​=z∈R∑​ x,y∈∏i<m​Di​xij​​=aj​, yij​​=bj​ (j<r)xi​=yi​ (i∈/K)​∑​ρ(x,z),(y,z)​.

Thus it sums over the reference index and matching indices outside KKK, and orders the retained indices increasingly. No positivity or normalization of ρ\rhoρ, or nonemptiness of the finite types, is assumed. For K=∅K=\varnothingK=∅, the resulting matrix has a singleton indexing type and its sole entry is tr⁡ρ\operatorname{tr}\rhotrρ.

QAlgorithms.Papers.Independent.Support50.P09.senderSuffix

For every natural number mmm, permutation π\piπ of {0,…,m−1}\{0,\ldots,m-1\}{0,…,m−1}, and natural number lll, this defines the finite set

{π(j):0≤j<m, m≤j+l}.\{\pi(j):0\le j<m,\ m\le j+l\}.{π(j):0≤j<m, m≤j+l}.

Thus l=0l=0l=0 gives the empty set, 0≤l≤m0\le l\le m0≤l≤m selects the images of the last lll indices, and l≥ml\ge ml≥m gives all mmm indices. When m=0m=0m=0, the set is empty for every lll.

QAlgorithms.Papers.Independent.Support50.P09.stateMixture

For every type III, real number λ\lambdaλ, and pair of complex matrices ρ,σ\rho,\sigmaρ,σ indexed by III, this defines the matrix

λρ+(1−λ)σ,\lambda\rho+(1-\lambda)\sigma,λρ+(1−λ)σ,

with the real coefficients regarded as complex scalars; its (a,b)(a,b)(a,b) entry is λρ(a,b)+(1−λ)σ(a,b)\lambda\rho(a,b)+(1-\lambda)\sigma(a,b)λρ(a,b)+(1−λ)σ(a,b). The type III need not be finite or nonempty, the matrices need not be density matrices, and λ\lambdaλ is not required to lie in [0,1][0,1][0,1].

QAlgorithms.Papers.Independent.Support50.P09.subsetSquashed

For any natural number mmm, finite types DiD_iDi​ indexed by i<mi<mi<m, finite type RRR, arbitrary complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, and subset K⊆{0,…,m−1}K\subseteq\{0,\ldots,m-1\}K⊆{0,…,m−1}, this quantity is 000 if K=∅K=\varnothingK=∅; otherwise, writing K={i0<⋯<ir−1}K=\{i_0<\cdots<i_{r-1}\}K={i0​<⋯<ir−1​}, it is

12inf⁡e∈N, e>0σ≥0, tr⁡σ=1Tr⁡Eσ=τK[∑j<rS(σjE)−S(σ)−(r−1)S(σE)],\frac12\inf_{\substack{e\in\mathbb N,\ e>0\\ \sigma\ge0,\ \operatorname{tr}\sigma=1\\ \operatorname{Tr}_{E}\sigma=\tau_K}} \left[\sum_{j<r}S(\sigma_{jE})-S(\sigma)-(r-1)S(\sigma_E)\right],21​e∈N, e>0σ≥0, trσ=1TrE​σ=τK​​inf​[j<r∑​S(σjE​)−S(σ)−(r−1)S(σE​)],

where E={0,…,e−1}E=\{0,\ldots,e-1\}E={0,…,e−1}, σ\sigmaσ is indexed by (∏j<rDij)×E(\prod_{j<r}D_{i_j})\times E(∏j<r​Dij​​)×E, and (τK)a,b(\tau_K)_{a,b}(τK​)a,b​ is the sum of ρ(x,z),(y,z)\rho_{(x,z),(y,z)}ρ(x,z),(y,z)​ over z∈Rz\in Rz∈R and x,yx,yx,y with xij=ajx_{i_j}=a_jxij​​=aj​, yij=bjy_{i_j}=b_jyij​​=bj​, and xi=yix_i=y_ixi​=yi​ outside KKK. Each marginal in the infimum sums over equal row and column indices of the discarded factors, retaining EEE. The entropy is S(X)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](X))S(X)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](X))S(X)=−Retr(cfc[x↦xlog2​x](X)). The extensions are not required to be classical. No density-matrix or nonemptiness assumptions are imposed on the original input; if there are no admissible extensions, the real infimum used by the definition is 000.

QAlgorithms.Papers.Independent.Support50.P09.vertexPolyhedron

For every natural number mmm, family of finite types (Di)i=0m−1(D_i)_{i=0}^{m-1}(Di​)i=0m−1​, finite type RRR, and arbitrary complex matrix ρ\rhoρ indexed by (∏iDi)×R(\prod_iD_i)\times R(∏i​Di​)×R, this defines the set of vectors Q∈RmQ\in\mathbb R^mQ∈Rm admitting a representation

Q=∑a=1rλaCπa+v,r≥1,λa≥0,∑a=1rλa=1,vi≥0,Q=\sum_{a=1}^{r}\lambda_aC_{\pi_a}+v, \qquad r\ge1,\quad \lambda_a\ge0,\quad \sum_{a=1}^{r}\lambda_a=1,\quad v_i\ge0,Q=a=1∑r​λa​Cπa​​+v,r≥1,λa​≥0,a=1∑r​λa​=1,vi​≥0,

where each πa\pi_aπa​ is a permutation of the mmm indices and

Cπ(i)=H(τ{i})+H(ρLiR)−H(ρ(Li∪{i})R)2,Li={π(j):π−1(i)<j<m}.C_\pi(i)=\frac{H(\tau_{\{i\}})+H(\rho_{L_iR})-H(\rho_{(L_i\cup\{i\})R})}{2}, \qquad L_i=\{\pi(j):\pi^{-1}(i)<j<m\}.Cπ​(i)=2H(τ{i}​)+H(ρLi​R​)−H(ρ(Li​∪{i})R​)​,Li​={π(j):π−1(i)<j<m}.

For every subset SSS, ρSR((u,r),(v,s))=∑zρ((u⊔z,r),(v⊔z,s))\rho_{SR}((u,r),(v,s))=\sum_z\rho((u\sqcup z,r),(v\sqcup z,s))ρSR​((u,r),(v,s))=∑z​ρ((u⊔z,r),(v⊔z,s)), summing over assignments zzz to coordinates outside SSS, and τS(u,v)=∑r∈RρSR((u,r),(v,r))\tau_S(u,v)=\sum_{r\in R}\rho_{SR}((u,r),(v,r))τS​(u,v)=∑r∈R​ρSR​((u,r),(v,r)). The notation H(X)H(X)H(X) denotes −Re⁡tr⁡(f(X))-\operatorname{Re}\operatorname{tr}(f(X))−Retr(f(X)) for f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t, evaluated by real continuous functional calculus. Thus the definition uses finite convex combinations of the permutation-indexed vectors and adds an arbitrary coordinatewise nonnegative vector; it does not take an additional closure. No density-matrix or nonemptiness assumptions are imposed. For m=0m=0m=0, the set contains the unique vector with no coordinates.

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