Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Classical capacity of a noiseless quantum channel assisted by noisy entanglement

Definition
QAlgorithms_Papers_Independent_Support50_P39

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

prove2quantum

The objects the formalized statements of Classical capacity of a noiseless quantum channel assisted by noisy entanglement (arXiv:quant-ph/0106080) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • noisyResourceCopies: PDF pp.2--4: independent copies, regrouped as A^n:B^n, with all matrix entries, including off-diagonal entries, retained.
  • aliceAction: PDF p.4: Lambda tensor id_B, with Alice the first factor. This is the linear action on every Bob block, rather than an action just on marginals.
  • clippedCoherentInformation: PDF p.2: the paper's coherent information is clipped at zero.
  • quantumMutualInformation: PDF p.8, Eq. (16): quantum mutual information in bits.
  • Preprocessing: PDF pp.2,7: arbitrary positive block length and positive finite output dimension, with an actual CPTP map. Neither integer is bounded in the optimization.
  • processedResource: PDF pp.2,7: the computed preprocessed resource, not a free state parameter.
  • mutualRatios: PDF p.2, Eq. (4), on its actual domain S(A)>0. The missing unassisted baseline is supplied separately in the capacity theorem. For normalized density inputs this set contains 0 (mixed replacement output) and is contained in [0,2]. Invalid inputs are never used in theorems.
  • coherentRatios: PDF p.7, Eq. (15): positive processed-entropy quotients of the clipped coherent information. The set contains 0 and is contained in [0,1] for states.
  • NoisyResourceBlockCode: PDF p.3, Eq. (6): a finite protocol consuming nk copies and sending a register of dimension d^k. Every message has a CPTP encoder. The SINGLE POVM is chosen before the universal message quantifier. Local ancillas and disposal are subsumed by CPTP maps; no side communication or feedback is supplied.
  • FixedRate: PDF p.3, Eq. (6): fixed-(d,n) achievable rate R, already normalized to bits per qubit. d,n are fixed BEFORE error and rate-slack limits. Arbitrary large block encoders are allowed; this is not an independent-letter restriction. Only positive k are tested, and epsilon ranges over (0,1).
  • operationalRates: PDF p.3, Eq. (6): rates obtainable with one chosen d>=2 and n>=1. In finite positive dimensions the set contains [0,1] and is bounded by 2; these guards are included in the full capacity statement.
  • denseCodingCapacity: PDF p.3, Eq. (6): operational capacity, in classical bits per qubit. This definition contains no entropic capacity identity. On nonphysical input the real supremum can have a junk value; all results require a density matrix.
  • ReliableFamily: PDF p.3, Eq. (6): an arbitrary reliable fixed-(d,n) block family. Only the errors must converge; message lengths and rates may oscillate. Encoders and the common decoder are witnessed by NoisyResourceBlockCode at each positive k. This predicate is used only with d>=2 and n>=1.
  • IsEncoding: PDF p.4, Eq. (9): an admissible finite ensemble of encoding channels.
  • encodingHolevo: PDF p.4, Eqs. (8),(9): the Holevo score computed from an encoding ensemble. No clipping occurs in this per-ensemble expression.
  • denseCodingHolevoValue: PDF p.4, RHS of Eq. (9): the finite-ensemble objective H_d, deliberately separate from the operational C_d in Eq. (6). It is nonempty and bounded for d>=1 and normalized input. Attainment is part of the optimization theorem.
  • finiteCoherentOpt: PDF p.4, Eq. (10): the fixed-output-dimensional optimized clipped coherent information. For normalized input and d>=1 this is a nonempty, bounded real supremum, attained by an actual channel.
  • uniformWeight: PDF p.5: probabilities d^(-2) on the d^2 encoding letters, used for d>=1.
  • unitaryEncoders: PDF p.5: unitary encoders Ad(U_i) after a given preprocessing channel.
  • TracelessTwirling: PDF p.5: the source's unnormalized traceless-matrix twirling property.
  • IsDistillable: PDF p.3, citing Ref. 11 (quant-ph/9801069, Eqs. (4)--(10) and the necessary-and-sufficient criterion following Eq. (9)): distillability means some positive finite tensor power has an entangled two-qubit local-filter output. Filters are arbitrary linear maps: they can be rescaled to physical Kraus contractions without changing positivity of the trace or the PPT test. In 2x2, failure of the PPT test is exactly inseparability. Transposing Alice instead of Bob gives the same positivity test by full transposition.
  • IsBoundEntangled: PDF p.3: bound entangled means normalized, entangled AND nondistillable; this is not restricted to PPT states or to no-communication distillation.
  • productFactor: PDF p.6, Bennett's example: tau tensor sigma regrouped as (T,A):B. Alice owns both T and A.
  • discardFirstAlice: PDF p.6: actually discard T, one part of Alice's register.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_BipartiteSeparability
import Definitions.Def_QAlgorithms_Defs_Measurement
import Definitions.Def_QAlgorithms_Defs_Ensemble

/-!
Horodecki--Horodecki--Horodecki--Leung--Terhal, arXiv:quant-ph/0106080v3.
All page references are PDF pages; all entropies and rates are in bits.
The operational capacity below is defined from actual worst-message block codes,
not from an entropy formula or the unregularized Holevo objective.

Source corrections: Eq. (3) needs the unassisted baseline when Eq. (4) is
restricted to its positive-denominator domain; Eq. (5) needs the processed
Alice entropy from Eq. (15), rather than the printed S(rho_A). These corrections
require independent moderation; see the unit's DISCREPANCIES.md.
The fixed-(d,n) operational/single-letter identification in Eqs. (7),(9)
is deferred and is not an assumption of any declaration here.
-/

namespace QAlgorithms.Papers.Independent.Support50.P39

/-! Accepted-library comparison for this repair: the four original short names
matched different frozen concepts, not reusable definitions of these objects.
Dependency50.P45.resourceCopies is a tensor power of a pure vector, whereas
noisyResourceCopies takes an arbitrary mixed density matrix. Information100.P39
coherentInformation is signed Renyi information in nats; Information100.P22
coherentInformation takes a channel and a purified input. Neither is the paper's
clipped bipartite entropy difference in bits. Frontier30.P06.BlockCode describes
feedback executions with average error, whereas NoisyResourceBlockCode uses a
fixed noisy resource, no feedback, and worst-message success. Claimed50.P13
finiteHolevo is an extended nonnegative relative-entropy score of one ensemble,
whereas denseCodingHolevoValue optimizes all finite CPTP encoding ensembles into
a fixed finite output dimension. These complete paper-local bodies are retained
under distinct names; no frozen definition or theorem meaning is changed. -/

noncomputable section

open QAlgorithms
open Filter Topology
open scoped Matrix ComplexConjugate ComplexOrder

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF pp.2--4: independent copies, regrouped as A^n:B^n, with all
matrix entries, including off-diagonal entries, retained. -/
def noisyResourceCopies {A B : Type*} (rho : Matrix (A × B) (A × B) ℂ) (n : ℕ) :
    Matrix ((Fin n → A) × (Fin n → B)) ((Fin n → A) × (Fin n → B)) ℂ :=
  fun i j => ∏ t, rho (i.1 t, i.2 t) (j.1 t, j.2 t)

/-- PDF p.4: Lambda tensor id_B, with Alice the first factor. This is the
linear action on every Bob block, rather than an action just on marginals. -/
def aliceAction {A B C : Type*} (Phi : Superop A C) :
    Superop (A × B) (C × B) :=
  fun X i j => Phi (fun a a2 => X (a,i.2) (a2,j.2)) i.1 j.1

/-- PDF p.2: the paper's coherent information is clipped at zero. -/
def clippedCoherentInformation {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ) : ℝ :=
  max (vnEntropy (traceLeft rho) - vnEntropy rho) 0

/-- PDF p.8, Eq. (16): quantum mutual information in bits. -/
def quantumMutualInformation {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ) : ℝ :=
  vnEntropy (traceRight rho) + vnEntropy (traceLeft rho) - vnEntropy rho

/-- PDF pp.2,7: arbitrary positive block length and positive finite output
dimension, with an actual CPTP map. Neither integer is bounded in the optimization. -/
structure Preprocessing (A : Type*) [Fintype A] [DecidableEq A] where
  copies : ℕ
  copies_pos : 0 < copies
  outputDim : ℕ
  outputDim_pos : 0 < outputDim
  channel : Superop (Fin copies → A) (Fin outputDim)
  valid : IsChannel channel

/-- PDF pp.2,7: the computed preprocessed resource, not a free state parameter. -/
def processedResource {A B : Type*} [Fintype A] [DecidableEq A]
    (rho : Matrix (A × B) (A × B) ℂ) (P : Preprocessing A) :
    Matrix (Fin P.outputDim × (Fin P.copies → B))
      (Fin P.outputDim × (Fin P.copies → B)) ℂ :=
  aliceAction P.channel (noisyResourceCopies rho P.copies)

/-- PDF p.2, Eq. (4), on its actual domain S(A)>0.
The missing unassisted baseline is supplied separately in the capacity theorem.
For normalized density inputs this set contains 0 (mixed replacement output)
and is contained in [0,2]. Invalid inputs are never used in theorems. -/
def mutualRatios {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ) : Set ℝ :=
  {r | ∃ P : Preprocessing A,
    0 < vnEntropy (traceRight (processedResource rho P)) ∧
    r = quantumMutualInformation (processedResource rho P) /
      vnEntropy (traceRight (processedResource rho P))}

/-- PDF p.7, Eq. (15): positive processed-entropy quotients of the clipped
coherent information. The set contains 0 and is contained in [0,1] for states. -/
def coherentRatios {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ) : Set ℝ :=
  {r | ∃ P : Preprocessing A,
    0 < vnEntropy (traceRight (processedResource rho P)) ∧
    r = clippedCoherentInformation (processedResource rho P) /
      vnEntropy (traceRight (processedResource rho P))}

/-- PDF p.3, Eq. (6): a finite protocol consuming nk copies and sending a
register of dimension d^k. Every message has a CPTP encoder. The SINGLE POVM
is chosen before the universal message quantifier. Local ancillas and disposal
are subsumed by CPTP maps; no side communication or feedback is supplied. -/
def NoisyResourceBlockCode {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ)
    (d n k m : ℕ) (epsilon : ℝ) : Prop :=
  ∃ Enc : Qubits m → Superop (Fin (n*k) → A) (Fin (d^k)),
    (∀ x, IsChannel (Enc x)) ∧
    ∃ Dec : Qubits m → Matrix (Fin (d^k) × (Fin (n*k) → B))
      (Fin (d^k) × (Fin (n*k) → B)) ℂ,
      IsPOVM Dec ∧ ∀ x, 1-epsilon ≤
        effectProb (Dec x) (aliceAction (Enc x) (noisyResourceCopies rho (n*k)))

/-- PDF p.3, Eq. (6): fixed-(d,n) achievable rate R, already normalized to
bits per qubit. d,n are fixed BEFORE error and rate-slack limits. Arbitrary
large block encoders are allowed; this is not an independent-letter restriction.
Only positive k are tested, and epsilon ranges over (0,1). -/
def FixedRate {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ)
    (d n : ℕ) (R : ℝ) : Prop :=
  0 ≤ R ∧ ∀ epsilon : ℝ, 0 < epsilon → epsilon < 1 →
    ∀ delta : ℝ, 0 < delta → ∃ K : ℕ, ∀ k : ℕ, K ≤ k → 0 < k →
      ∃ m : ℕ, (R-delta) * (k : ℝ) * Real.logb 2 d ≤ m ∧
        NoisyResourceBlockCode rho d n k m epsilon

/-- PDF p.3, Eq. (6): rates obtainable with one chosen d>=2 and n>=1.
In finite positive dimensions the set contains [0,1] and is bounded by 2;
these guards are included in the full capacity statement. -/
def operationalRates {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ) : Set ℝ :=
  {R | ∃ d n : ℕ, 2 ≤ d ∧ 0 < n ∧ FixedRate rho d n R}

/-- PDF p.3, Eq. (6): operational capacity, in classical bits per qubit.
This definition contains no entropic capacity identity. On nonphysical input
the real supremum can have a junk value; all results require a density matrix. -/
def denseCodingCapacity {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ) : ℝ :=
  sSup (operationalRates rho)

/-- PDF p.3, Eq. (6): an arbitrary reliable fixed-(d,n) block family.
Only the errors must converge; message lengths and rates may oscillate.
Encoders and the common decoder are witnessed by NoisyResourceBlockCode at each positive k.
This predicate is used only with d>=2 and n>=1. -/
def ReliableFamily {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ)
    (d n : ℕ) (m : ℕ → ℕ) (epsilon : ℕ → ℝ) : Prop :=
  (∀ k : ℕ, 0 < k → 0 ≤ epsilon k ∧ epsilon k ≤ 1 ∧
    NoisyResourceBlockCode rho d n k (m k) (epsilon k)) ∧
    Tendsto epsilon atTop (nhds 0)

/-- PDF p.4, Eq. (9): an admissible finite ensemble of encoding channels. -/
def IsEncoding {A C : Type*} [Fintype A] [Fintype C] [DecidableEq A]
    {l : ℕ} (p : Fin l → ℝ) (E : Fin l → Superop A C) : Prop :=
  0 < l ∧ (∀ i, 0 ≤ p i) ∧ (∑ i, p i) = 1 ∧ ∀ i, IsChannel (E i)

/-- PDF p.4, Eqs. (8),(9): the Holevo score computed from an encoding ensemble.
No clipping occurs in this per-ensemble expression. -/
def encodingHolevo {A B C : Type*} [Fintype A] [Fintype B] [Fintype C]
    [DecidableEq A] [DecidableEq B] [DecidableEq C] {l : ℕ}
    (rho : Matrix (A × B) (A × B) ℂ) (n : ℕ)
    (p : Fin l → ℝ) (E : Fin l → Superop (Fin n → A) C) : ℝ :=
  vnEntropy (∑ i, (p i : ℂ) • aliceAction (E i) (noisyResourceCopies rho n)) -
    ∑ i, p i * vnEntropy (aliceAction (E i) (noisyResourceCopies rho n))

/-- PDF p.4, RHS of Eq. (9): the finite-ensemble objective H_d, deliberately
separate from the operational C_d in Eq. (6). It is nonempty and bounded for
d>=1 and normalized input. Attainment is part of the optimization theorem. -/
def denseCodingHolevoValue {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ)
    (n d : ℕ) : ℝ :=
  sSup {r : ℝ | ∃ l : ℕ, ∃ p : Fin l → ℝ,
    ∃ E : Fin l → Superop (Fin n → A) (Fin d),
      IsEncoding p E ∧ r = encodingHolevo rho n p E}

/-- PDF p.4, Eq. (10): the fixed-output-dimensional optimized clipped
coherent information. For normalized input and d>=1 this is a nonempty,
bounded real supremum, attained by an actual channel. -/
def finiteCoherentOpt {A B : Type*} [Fintype A] [Fintype B]
    [DecidableEq A] [DecidableEq B] (rho : Matrix (A × B) (A × B) ℂ)
    (n d : ℕ) : ℝ :=
  sSup {r : ℝ | ∃ Phi : Superop (Fin n → A) (Fin d), IsChannel Phi ∧
    r = clippedCoherentInformation (aliceAction Phi (noisyResourceCopies rho n))}

/-- PDF p.5: probabilities d^(-2) on the d^2 encoding letters, used for d>=1. -/
def uniformWeight (d : ℕ) : Fin (d*d) → ℝ := fun _ => ((d : ℝ)^2)⁻¹

/-- PDF p.5: unitary encoders Ad(U_i) after a given preprocessing channel. -/
def unitaryEncoders {A : Type*} [Fintype A] {d : ℕ}
    (Phi : Superop A (Fin d)) (U : Fin (d*d) → Matrix.unitaryGroup (Fin d) ℂ) :
    Fin (d*d) → Superop A (Fin d) :=
  fun i => conjSuperop (U i : Matrix (Fin d) (Fin d) ℂ) ∘ Phi

/-- PDF p.5: the source's unnormalized traceless-matrix twirling property. -/
def TracelessTwirling {d : ℕ} (U : Fin (d*d) → Matrix.unitaryGroup (Fin d) ℂ) : Prop :=
  ∀ M : Matrix (Fin d) (Fin d) ℂ, M.trace = 0 →
    ∑ i, conjSuperop (U i : Matrix (Fin d) (Fin d) ℂ) M = 0

/-- PDF p.3, citing Ref. 11 (quant-ph/9801069, Eqs. (4)--(10) and the
necessary-and-sufficient criterion following Eq. (9)): distillability means
some positive finite tensor power has an entangled two-qubit local-filter
output. Filters are arbitrary linear maps: they can be rescaled to physical
Kraus contractions without changing positivity of the trace or the PPT test.
In 2x2, failure of the PPT test is exactly inseparability. Transposing Alice
instead of Bob gives the same positivity test by full transposition. -/
def IsDistillable {A B : Type*} [Fintype A] [Fintype B]
    (rho : Matrix (A × B) (A × B) ℂ) : Prop :=
  ∃ n : ℕ, 0 < n ∧
    ∃ F : Matrix (Fin 2) (Fin n → A) ℂ,
    ∃ G : Matrix (Fin 2) (Fin n → B) ℂ,
      let X := Matrix.kronecker F G * noisyResourceCopies rho n * (Matrix.kronecker F G)ᴴ
      0 < X.trace.re ∧ ¬ (QAlgorithms.Entanglement.partialTransposeFirst X).PosSemidef

/-- PDF p.3: bound entangled means normalized, entangled AND nondistillable;
this is not restricted to PPT states or to no-communication distillation. -/
def IsBoundEntangled {A B : Type*} [Fintype A] [Fintype B]
    [Nonempty A] [Nonempty B] (rho : Matrix (A × B) (A × B) ℂ) : Prop :=
  IsDensityMatrix rho ∧ ¬ QAlgorithms.Entanglement.IsSeparableDensity rho ∧
    ¬ IsDistillable rho

/-- PDF p.6, Bennett's example: tau tensor sigma regrouped as (T,A):B.
Alice owns both T and A. -/
def productFactor {T A B : Type*} (tau : Matrix T T ℂ)
    (sigma : Matrix (A × B) (A × B) ℂ) :
    Matrix ((T × A) × B) ((T × A) × B) ℂ :=
  fun i j => tau i.1.1 j.1.1 * sigma (i.1.2,i.2) (j.1.2,j.2)

/-- PDF p.6: actually discard T, one part of Alice's register. -/
def discardFirstAlice {T A B : Type*} [Fintype T]
    (rho : Matrix ((T × A) × B) ((T × A) × B) ℂ) : Matrix (A × B) (A × B) ℂ :=
  fun i j => ∑ t, rho ((t,i.1),i.2) ((t,j.1),j.2)

/-- Sanity: no resource copies is the scalar unit, not a zero state. -/
example {A B : Type*} (rho : Matrix (A × B) (A × B) ℂ)
    (i j : (Fin 0 → A) × (Fin 0 → B)) : noisyResourceCopies rho 0 i j = 1 := by
  simp [noisyResourceCopies]

/-- Sanity: applying the identity to Alice retains every off-diagonal entry. -/
example {A B : Type*} (rho : Matrix (A × B) (A × B) ℂ) :
    aliceAction (fun X : Matrix A A ℂ => X) rho = rho := rfl

/-- Sanity: a one-letter channel ensemble has normalized weights. -/
example {A C : Type*} [Fintype A] [Fintype C] [DecidableEq A]
    (Phi : Superop A C) (hPhi : IsChannel Phi) :
    IsEncoding (fun _ : Fin 1 => (1 : ℝ)) (fun _ => Phi) := by
  simp [IsEncoding, hPhi]

/-- Sanity: the scalar-output unitary ensemble has one letter of weight one. -/
example : uniformWeight 1 0 = 1 := by norm_num [uniformWeight]

/-- Sanity: the clipping convention keeps negative signed coherent information at zero. -/
example {A B : Type*} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
    (rho : Matrix (A × B) (A × B) ℂ)
    (h : vnEntropy (traceLeft rho) ≤ vnEntropy rho) : clippedCoherentInformation rho = 0 := by
  exact max_eq_right (sub_nonpos.mpr h)

/-- Sanity: discarding a scalar Alice factor returns precisely sigma. -/
example {A B : Type*} (sigma : Matrix (A × B) (A × B) ℂ) :
    discardFirstAlice (productFactor (1 : Matrix Unit Unit ℂ) sigma) = sigma := by
  ext i j
  simp [discardFirstAlice, productFactor]

end

end QAlgorithms.Papers.Independent.Support50.P39
Source
Classical capacity of a noiseless quantum channel assisted by noisy entanglement, arXiv:quant-ph/0106080v3, https://arxiv.org/abs/quant-ph/0106080v3
Read-back

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

QAlgorithms.Papers.Independent.Support50.P39.FixedRate

For finite types A,BA,BA,B equipped with decidable equality, possibly empty, any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, natural numbers d,nd,nd,n, and a real number RRR, this predicate requires R≥0R\ge0R≥0 and the following quantified assertion: for every real 0<ϵ<10<\epsilon<10<ϵ<1 and every real δ>0\delta>0δ>0, there exists a natural number KKK such that for every natural number k≥Kk\ge Kk≥K with k>0k>0k>0, there exists a natural number mmm satisfying

(R−δ)klog⁡2d≤m(R-\delta)k\log_2 d\le m(R−δ)klog2​d≤m

and admitting the following encoding and decoding data. For every Boolean string xxx of length mmm, there is a channel Enc⁡x\operatorname{Enc}_xEncx​ from AnkA^{nk}Ank-indexed matrices to matrices indexed by H={0,…,dk−1}H=\{0,\ldots,d^k-1\}H={0,…,dk−1}: each channel has a finite, possibly empty Kraus family Ex,ℓE_{x,\ell}Ex,ℓ​ satisfying ∑ℓEx,ℓ†Ex,ℓ=I\sum_\ell E_{x,\ell}^\dagger E_{x,\ell}=I∑ℓ​Ex,ℓ†​Ex,ℓ​=I and Enc⁡x(X)=∑ℓEx,ℓXEx,ℓ†\operatorname{Enc}_x(X)=\sum_\ell E_{x,\ell}XE_{x,\ell}^\daggerEncx​(X)=∑ℓ​Ex,ℓ​XEx,ℓ†​ for every XXX. There are positive semidefinite matrices DxD_xDx​ indexed by H×BnkH\times B^{nk}H×Bnk, with ∑xDx=I\sum_x D_x=I∑x​Dx​=I, such that, defining

(σx)(u,b),(v,b′)=(Enc⁡x(Yb,b′))u,v,Ya,a′b,b′=∏t=0nk−1ρ(a(t),b(t)),(a′(t),b′(t)),(\sigma_x)_{(u,b),(v,b')}=\bigl(\operatorname{Enc}_x(Y^{b,b'})\bigr)_{u,v}, \qquad Y^{b,b'}_{a,a'}=\prod_{t=0}^{nk-1}\rho_{(a(t),b(t)),(a'(t),b'(t))},(σx​)(u,b),(v,b′)​=(Encx​(Yb,b′))u,v​,Ya,a′b,b′​=t=0∏nk−1​ρ(a(t),b(t)),(a′(t),b′(t))​,

one has 1−ϵ≤Re⁡tr⁡(Dxσx)1-\epsilon\le\operatorname{Re}\operatorname{tr}(D_x\sigma_x)1−ϵ≤Retr(Dx​σx​) for every xxx. The choices K,mK,mK,m and the encoding and decoding data have the dependencies allowed by this quantifier order. No positivity or normalization is assumed for ρ\rhoρ, and neither ddd nor nnn is required to be positive. In particular, n=0n=0n=0 uses empty products, m=0m=0m=0 is permitted, and the total logarithm gives log⁡20=log⁡21=0\log_2 0=\log_2 1=0log2​0=log2​1=0.

QAlgorithms.Papers.Independent.Support50.P39.IsBoundEntangled

For finite, nonempty types A,BA,BA,B and a complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this predicate means that ρ\rhoρ is positive semidefinite with tr⁡(ρ)=1\operatorname{tr}(\rho)=1tr(ρ)=1, that there do not exist a natural number qqq, nonnegative real weights wjw_jwj​ summing to 111, and positive semidefinite matrices Aj,BjA_j,B_jAj​,Bj​ indexed respectively by A,BA,BA,B, each of trace 111, such that ρ=∑j=0q−1wj(Aj⊗Bj)\rho=\sum_{j=0}^{q-1}w_j(A_j\otimes B_j)ρ=∑j=0q−1​wj​(Aj​⊗Bj​), and that the following objects do not exist: a positive integer nnn and matrices F:An→C2F:A^n\to\mathbb C^2F:An→C2, G:Bn→C2G:B^n\to\mathbb C^2G:Bn→C2 such that

X=(F⊗G)Rn(F⊗G)∗,Rn((a,b),(a′,b′))=∏t=0n−1ρ((at,bt),(at′,bt′))X=(F\otimes G)R_n(F\otimes G)^{*}, \qquad R_n\bigl((a,b),(a',b')\bigr) =\prod_{t=0}^{n-1}\rho\bigl((a_t,b_t),(a'_t,b'_t)\bigr)X=(F⊗G)Rn​(F⊗G)∗,Rn​((a,b),(a′,b′))=t=0∏n−1​ρ((at​,bt​),(at′​,bt′​))

has Re⁡tr⁡(X)>0\operatorname{Re}\operatorname{tr}(X)>0Retr(X)>0 while the matrix with entries X((i′,j),(i,j′))X((i',j),(i,j'))X((i′,j),(i,j′)) at row (i,j)(i,j)(i,j), column (i′,j′)(i',j')(i′,j′), is not positive semidefinite. The matrices F,GF,GF,G have no normalization or contraction requirement; the excluded decomposition permits zero weights, although q=0q=0q=0 cannot satisfy its weight-sum condition.

QAlgorithms.Papers.Independent.Support50.P39.IsDistillable

For finite types A,BA,BA,B and an arbitrary complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this predicate means that there exist a positive integer nnn, a complex matrix FFF with rows indexed by {0,1}\{0,1\}{0,1} and columns indexed by AnA^nAn, and a complex matrix GGG with rows indexed by {0,1}\{0,1\}{0,1} and columns indexed by BnB^nBn, such that, on defining

Rn((a,b),(a′,b′))=∏t=0n−1ρ((at,bt),(at′,bt′)),X=(F⊗G)Rn(F⊗G)∗,R_n\bigl((a,b),(a',b')\bigr) =\prod_{t=0}^{n-1}\rho\bigl((a_t,b_t),(a'_t,b'_t)\bigr), \qquad X=(F\otimes G)R_n(F\otimes G)^{*},Rn​((a,b),(a′,b′))=t=0∏n−1​ρ((at​,bt​),(at′​,bt′​)),X=(F⊗G)Rn​(F⊗G)∗,

one has Re⁡tr⁡(X)>0\operatorname{Re}\operatorname{tr}(X)>0Retr(X)>0, and the matrix YYY given by

Y((i,j),(i′,j′))=X((i′,j),(i,j′))Y\bigl((i,j),(i',j')\bigr) =X\bigl((i',j),(i,j')\bigr)Y((i,j),(i′,j′))=X((i′,j),(i,j′))

is not positive semidefinite. No density condition on ρ\rhoρ, normalization or contraction condition on F,GF,GF,G, or nonemptiness assumption on A,BA,BA,B is imposed. If either AAA or BBB is empty, every permitted positive nnn makes X=0X=0X=0, so the strict trace condition cannot hold.

QAlgorithms.Papers.Independent.Support50.P39.IsEncoding

For finite types A,CA,CA,C, with decidable equality on AAA, a natural number lll, real numbers pip_ipi​, and maps EiE_iEi​ from complex matrices indexed by AAA to those indexed by CCC, indexed by 0≤i<l0\le i<l0≤i<l, this predicate means that l>0l>0l>0, every pi≥0p_i\ge0pi​≥0, ∑i=0l−1pi=1\sum_{i=0}^{l-1}p_i=1∑i=0l−1​pi​=1, and each EiE_iEi​ admits a finite Kraus representation: there exist a natural number rir_iri​ and matrices Ki,jK_{i,j}Ki,j​ with rows indexed by CCC and columns indexed by AAA, such that

∑j=0ri−1Ki,j∗Ki,j=IA,Ei(H)=∑j=0ri−1Ki,jHKi,j∗for every complex matrix H.\sum_{j=0}^{r_i-1}K_{i,j}^{*}K_{i,j}=I_A, \qquad E_i(H)=\sum_{j=0}^{r_i-1}K_{i,j}HK_{i,j}^{*} \quad\text{for every complex matrix }H.j=0∑ri​−1​Ki,j∗​Ki,j​=IA​,Ei​(H)=j=0∑ri​−1​Ki,j​HKi,j∗​for every complex matrix H.

Zero weights and empty underlying types are allowed; the Kraus index count may be zero whenever the displayed conditions permit it, but l=0l=0l=0 never satisfies the predicate.

QAlgorithms.Papers.Independent.Support50.P39.NoisyResourceBlockCode

For finite types A,BA,BA,B equipped with decidable equality, possibly empty, any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, natural numbers d,n,k,md,n,k,md,n,k,m, and any real ϵ\epsilonϵ, this predicate asserts the existence of an encoding channel Enc⁡x\operatorname{Enc}_xEncx​ for every Boolean string xxx of length mmm, and a family of decoding matrices DxD_xDx​. Each encoding maps AnkA^{nk}Ank-indexed square matrices to square matrices indexed by H={0,…,dk−1}H=\{0,\ldots,d^k-1\}H={0,…,dk−1}; explicitly, for each xxx there is a finite, possibly empty family Ex,ℓE_{x,\ell}Ex,ℓ​ such that ∑ℓEx,ℓ†Ex,ℓ=I\sum_\ell E_{x,\ell}^\dagger E_{x,\ell}=I∑ℓ​Ex,ℓ†​Ex,ℓ​=I and Enc⁡x(X)=∑ℓEx,ℓXEx,ℓ†\operatorname{Enc}_x(X)=\sum_\ell E_{x,\ell}XE_{x,\ell}^\daggerEncx​(X)=∑ℓ​Ex,ℓ​XEx,ℓ†​ for every XXX. Each DxD_xDx​ is indexed by H×BnkH\times B^{nk}H×Bnk, is positive semidefinite, and the family satisfies ∑xDx=I\sum_x D_x=I∑x​Dx​=I. Define

(σx)(u,b),(v,b′)=(Enc⁡x(Yb,b′))u,v,Ya,a′b,b′=∏t=0nk−1ρ(a(t),b(t)),(a′(t),b′(t)).(\sigma_x)_{(u,b),(v,b')} =\bigl(\operatorname{Enc}_x(Y^{b,b'})\bigr)_{u,v}, \qquad Y^{b,b'}_{a,a'}=\prod_{t=0}^{nk-1}\rho_{(a(t),b(t)),(a'(t),b'(t))}.(σx​)(u,b),(v,b′)​=(Encx​(Yb,b′))u,v​,Ya,a′b,b′​=t=0∏nk−1​ρ(a(t),b(t)),(a′(t),b′(t))​.

The remaining requirement is the separate inequality

1−ϵ≤Re⁡tr⁡(Dxσx)for every Boolean string x of length m.1-\epsilon\le \operatorname{Re}\operatorname{tr}(D_x\sigma_x) \quad\text{for every Boolean string }x\text{ of length }m.1−ϵ≤Retr(Dx​σx​)for every Boolean string x of length m.

There is no assumption that ρ\rhoρ is a density matrix or that ϵ\epsilonϵ lies in any particular interval. All zero values of the natural parameters are included: m=0m=0m=0 gives one message, nk=0nk=0nk=0 gives empty products equal to 111, and k=0k=0k=0 gives dk=1d^k=1dk=1, including when d=0d=0d=0.

QAlgorithms.Papers.Independent.Support50.P39.Preprocessing

For a finite type AAA equipped with decidable equality, possibly empty, a preprocessing object consists of natural numbers c>0c>0c>0 and h>0h>0h>0, together with a function Φ\PhiΦ from complex square matrices indexed by functions {0,…,c−1}→A\{0,\ldots,c-1\}\to A{0,…,c−1}→A to complex square matrices indexed by {0,…,h−1}\{0,\ldots,h-1\}{0,…,h−1}, and a channel certificate for Φ\PhiΦ. Explicitly, this certificate asserts that there exist a natural number qqq and rectangular complex matrices EℓE_\ellEℓ​, for 0≤ℓ<q0\le\ell<q0≤ℓ<q, with rows indexed by {0,…,h−1}\{0,\ldots,h-1\}{0,…,h−1} and columns indexed by those functions into AAA, such that

∑ℓ=0q−1Eℓ†Eℓ=I,Φ(X)=∑ℓ=0q−1EℓXEℓ†for every input matrix X.\sum_{\ell=0}^{q-1}E_\ell^\dagger E_\ell=I, \qquad \Phi(X)=\sum_{\ell=0}^{q-1}E_\ell X E_\ell^\dagger \quad\text{for every input matrix }X.ℓ=0∑q−1​Eℓ†​Eℓ​=I,Φ(X)=ℓ=0∑q−1​Eℓ​XEℓ†​for every input matrix X.

The number qqq may be zero, in which case both sums are empty; the two dimensions c,hc,hc,h must be strictly positive.

QAlgorithms.Papers.Independent.Support50.P39.ReliableFamily

For finite types A,BA,BA,B with decidable equality, an arbitrary complex matrix ρ\rhoρ indexed by A×BA\times BA×B, natural numbers d,nd,nd,n, and functions m:N→Nm:\mathbb N\to\mathbb Nm:N→N and ϵ:N→R\epsilon:\mathbb N\to\mathbb Rϵ:N→R, this predicate means that ϵ(k)→0\epsilon(k)\to0ϵ(k)→0 as k→∞k\to\inftyk→∞, and, for every positive integer kkk, 0≤ϵ(k)≤10\le\epsilon(k)\le10≤ϵ(k)≤1 and the following objects exist. For each bit string x∈{0,1}m(k)x\in\{0,1\}^{m(k)}x∈{0,1}m(k), there is a map Φx\Phi_xΦx​ from complex matrices indexed by AnkA^{nk}Ank to those indexed by {0,…,dk−1}\{0,\ldots,d^k-1\}{0,…,dk−1}, admitting a finite Kraus representation Φx(H)=∑jLx,jHLx,j∗\Phi_x(H)=\sum_j L_{x,j}HL_{x,j}^{*}Φx​(H)=∑j​Lx,j​HLx,j∗​ for every matrix HHH, with ∑jLx,j∗Lx,j=I\sum_jL_{x,j}^{*}L_{x,j}=I∑j​Lx,j∗​Lx,j​=I; there are also positive semidefinite matrices MxM_xMx​, indexed by {0,…,dk−1}×Bnk\{0,\ldots,d^k-1\}\times B^{nk}{0,…,dk−1}×Bnk, such that ∑xMx=I\sum_xM_x=I∑x​Mx​=I and Re⁡tr⁡(Mxσx)≥1−ϵ(k)\operatorname{Re}\operatorname{tr}(M_x\sigma_x)\ge1-\epsilon(k)Retr(Mx​σx​)≥1−ϵ(k) for every xxx. Here AnkA^{nk}Ank and BnkB^{nk}Bnk denote functions on {0,…,nk−1}\{0,\ldots,nk-1\}{0,…,nk−1}, and the output matrix is defined blockwise by

σx((c,b),(c′,b′))=Φx ⁣([∏t=0nk−1ρ((at,bt),(at′,bt′))]a,a′∈Ank)c,c′.\sigma_x\bigl((c,b),(c',b')\bigr) = \Phi_x\!\left( \left[\prod_{t=0}^{nk-1} \rho\bigl((a_t,b_t),(a'_t,b'_t)\bigr)\right]_{a,a'\in A^{nk}} \right)_{c,c'}.σx​((c,b),(c′,b′))=Φx​​[t=0∏nk−1​ρ((at​,bt​),(at′​,bt′​))]a,a′∈Ank​​c,c′​.

There is no condition at k=0k=0k=0 beyond its participation in the sequence whose limit is specified; d=0d=0d=0, n=0n=0n=0, m(k)=0m(k)=0m(k)=0, and empty AAA or BBB are permitted, with empty products equal to 111. No positivity or trace condition on ρ\rhoρ is assumed.

QAlgorithms.Papers.Independent.Support50.P39.TracelessTwirling

For a natural number ddd and a family of unitary complex d×dd\times dd×d matrices UiU_iUi​, indexed by 0≤i<d20\le i<d^20≤i<d2, this predicate means that every complex d×dd\times dd×d matrix MMM with tr⁡(M)=0\operatorname{tr}(M)=0tr(M)=0 satisfies

∑i=0d2−1UiMUi∗=0.\sum_{i=0}^{d^2-1}U_iMU_i^{*}=0.i=0∑d2−1​Ui​MUi∗​=0.

The sum is unnormalized, and MMM is not required to be Hermitian. When d=0d=0d=0, the sum is empty and the equality holds for the unique matrix on the empty index set.

QAlgorithms.Papers.Independent.Support50.P39.aliceAction

For arbitrary types A,B,CA,B,CA,B,C and any function Φ\PhiΦ from complex AAA-indexed square matrices to complex CCC-indexed square matrices, this defines a function from complex matrices indexed by A×BA\times BA×B to complex matrices indexed by C×BC\times BC×B. For every input matrix XXX, its output satisfies

(aliceAction⁡(Φ)(X))(c,b),(c′,b′)=(Φ(Xb,b′))c,c′,Xa,a′b,b′=X(a,b),(a′,b′).\bigl(\operatorname{aliceAction}(\Phi)(X)\bigr)_{(c,b),(c',b')} =\bigl(\Phi(X^{b,b'})\bigr)_{c,c'}, \qquad X^{b,b'}_{a,a'}=X_{(a,b),(a',b')}.(aliceAction(Φ)(X))(c,b),(c′,b′)​=(Φ(Xb,b′))c,c′​,Xa,a′b,b′​=X(a,b),(a′,b′)​.

The types may be empty or infinite, and Φ\PhiΦ is an arbitrary function; linearity and channel properties are not required.

QAlgorithms.Papers.Independent.Support50.P39.clippedCoherentInformation

For any finite types A,BA,BA,B equipped with decidable equality, possibly empty, and any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this defines

max⁡{S(ρB)−S(ρ), 0},(ρB)b,b′=∑a∈Aρ(a,b),(a,b′).\max\{S(\rho_B)-S(\rho),\,0\}, \qquad (\rho_B)_{b,b'}=\sum_{a\in A}\rho_{(a,b),(a,b')}.max{S(ρB​)−S(ρ),0},(ρB​)b,b′​=a∈A∑​ρ(a,b),(a,b′)​.

Here, for a finite square complex matrix XXX, S(X)=−Re⁡tr⁡(f(X))S(X)=-\operatorname{Re}\operatorname{tr}(f(X))S(X)=−Retr(f(X)), where f(t)=tlog⁡2tf(t)=t\log_2 tf(t)=tlog2​t and f(X)f(X)f(X) is formed using the continuous functional calculus appearing in the definition; the real logarithm is total, with log⁡20=0\log_2 0=0log2​0=0. No positivity or trace-one condition is imposed on ρ\rhoρ. The maximum makes the defined value nonnegative.

QAlgorithms.Papers.Independent.Support50.P39.coherentRatios

For finite types A,BA,BA,B equipped with decidable equality, possibly empty, and any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this defines the set of real numbers rrr for which there exist positive natural numbers c,hc,hc,h and a channel Φ\PhiΦ from AcA^cAc-indexed square matrices to hhh-indexed square matrices satisfying the following conditions. The channel requirement means that there is a finite, possibly empty family EℓE_\ellEℓ​ with ∑ℓEℓ†Eℓ=I\sum_\ell E_\ell^\dagger E_\ell=I∑ℓ​Eℓ†​Eℓ​=I and Φ(X)=∑ℓEℓXEℓ†\Phi(X)=\sum_\ell E_\ell X E_\ell^\daggerΦ(X)=∑ℓ​Eℓ​XEℓ†​ for every XXX. Form the matrix σ\sigmaσ indexed by {0,…,h−1}×Bc\{0,\ldots,h-1\}\times B^c{0,…,h−1}×Bc using

σ(u,b),(v,b′)=(Φ(Yb,b′))u,v,Ya,a′b,b′=∏t=0c−1ρ(a(t),b(t)),(a′(t),b′(t)).\sigma_{(u,b),(v,b')}=\bigl(\Phi(Y^{b,b'})\bigr)_{u,v}, \qquad Y^{b,b'}_{a,a'}=\prod_{t=0}^{c-1}\rho_{(a(t),b(t)),(a'(t),b'(t))}.σ(u,b),(v,b′)​=(Φ(Yb,b′))u,v​,Ya,a′b,b′​=t=0∏c−1​ρ(a(t),b(t)),(a′(t),b′(t))​.

Set (σA)u,v=∑b∈Bcσ(u,b),(v,b)(\sigma_A)_{u,v}=\sum_{b\in B^c}\sigma_{(u,b),(v,b)}(σA​)u,v​=∑b∈Bc​σ(u,b),(v,b)​ and (σB)b,b′=∑u=0h−1σ(u,b),(u,b′)(\sigma_B)_{b,b'}=\sum_{u=0}^{h-1}\sigma_{(u,b),(u,b')}(σB​)b,b′​=∑u=0h−1​σ(u,b),(u,b′)​. The required conditions are

S(σA)>0,r=max⁡{S(σB)−S(σ),0}S(σA).S(\sigma_A)>0, \qquad r=\frac{\max\{S(\sigma_B)-S(\sigma),0\}}{S(\sigma_A)}.S(σA​)>0,r=S(σA​)max{S(σB​)−S(σ),0}​.

Here S(X)=−Re⁡tr⁡(f(X))S(X)=-\operatorname{Re}\operatorname{tr}(f(X))S(X)=−Retr(f(X)), where f(t)=tlog⁡2tf(t)=t\log_2 tf(t)=tlog2​t is applied by the continuous functional calculus used in the definition, with log⁡20=0\log_2 0=0log2​0=0. No density-matrix condition is imposed on ρ\rhoρ; the denominator is strictly positive and the resulting ratio is nonnegative.

QAlgorithms.Papers.Independent.Support50.P39.denseCodingCapacity

For finite types A,BA,BA,B equipped with decidable equality, possibly empty, and any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this defines a real number as the real supremum of the following set of rates RRR. A rate belongs to the set exactly when there exist natural numbers d≥2d\ge2d≥2 and n>0n>0n>0 such that R≥0R\ge0R≥0, and for every real 0<ϵ<10<\epsilon<10<ϵ<1 and every real δ>0\delta>0δ>0, there is a natural number KKK such that every natural number k≥Kk\ge Kk≥K with k>0k>0k>0 admits a natural number mmm satisfying

(R−δ)klog⁡2d≤m(R-\delta)k\log_2 d\le m(R−δ)klog2​d≤m

together with an encoding channel Enc⁡x\operatorname{Enc}_xEncx​ for each Boolean string xxx of length mmm and decoding matrices DxD_xDx​. Each encoding maps matrices indexed by AnkA^{nk}Ank to matrices indexed by H={0,…,dk−1}H=\{0,\ldots,d^k-1\}H={0,…,dk−1}, and has a finite, possibly empty family Ex,ℓE_{x,\ell}Ex,ℓ​ satisfying ∑ℓEx,ℓ†Ex,ℓ=I\sum_\ell E_{x,\ell}^\dagger E_{x,\ell}=I∑ℓ​Ex,ℓ†​Ex,ℓ​=I and Enc⁡x(X)=∑ℓEx,ℓXEx,ℓ†\operatorname{Enc}_x(X)=\sum_\ell E_{x,\ell}XE_{x,\ell}^\daggerEncx​(X)=∑ℓ​Ex,ℓ​XEx,ℓ†​ for every input matrix XXX. The matrices DxD_xDx​ are positive semidefinite, indexed by H×BnkH\times B^{nk}H×Bnk, and satisfy ∑xDx=I\sum_x D_x=I∑x​Dx​=I. For every message xxx, they must satisfy

1−ϵ≤Re⁡tr⁡(Dxσx),(σx)(u,b),(v,b′)=(Enc⁡x ⁣[∏t=0nk−1ρ(a(t),b(t)),(a′(t),b′(t))]a,a′)u,v.1-\epsilon\le\operatorname{Re}\operatorname{tr}(D_x\sigma_x), \qquad (\sigma_x)_{(u,b),(v,b')}= \left(\operatorname{Enc}_x\!\left[ \prod_{t=0}^{nk-1}\rho_{(a(t),b(t)),(a'(t),b'(t))} \right]_{a,a'}\right)_{u,v}.1−ϵ≤Retr(Dx​σx​),(σx​)(u,b),(v,b′)​=​Encx​[t=0∏nk−1​ρ(a(t),b(t)),(a′(t),b′(t))​]a,a′​​u,v​.

Here AnkA^{nk}Ank and BnkB^{nk}Bnk are spaces of functions on {0,…,nk−1}\{0,\ldots,nk-1\}{0,…,nk−1}, and m=0m=0m=0 is allowed. No positivity or trace-one hypothesis is imposed on ρ\rhoρ. The supremum is taken in the real numbers using the total supremum operation, which returns 000 for an empty set or a set unbounded above; in particular, if either AAA or BBB is empty, the rate set is empty and the defined value is 000.

QAlgorithms.Papers.Independent.Support50.P39.denseCodingHolevoValue

For finite types A,BA,BA,B with decidable equality, an arbitrary complex matrix ρ\rhoρ indexed by A×BA\times BA×B, and natural numbers n,dn,dn,d, this is the real supremum of all values

S ⁣(∑i=0l−1piσi)−∑i=0l−1piS(σi)S\!\left(\sum_{i=0}^{l-1}p_i\sigma_i\right) - \sum_{i=0}^{l-1}p_iS(\sigma_i)S(i=0∑l−1​pi​σi​)−i=0∑l−1​pi​S(σi​)

obtained by choosing a positive integer lll, weights pi≥0p_i\ge0pi​≥0 with ∑ipi=1\sum_i p_i=1∑i​pi​=1, and maps EiE_iEi​ from matrices indexed by AnA^nAn to matrices indexed by {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, each having a finite representation Ei(H)=∑jKi,jHKi,j∗E_i(H)=\sum_jK_{i,j}HK_{i,j}^{*}Ei​(H)=∑j​Ki,j​HKi,j∗​ for all HHH, with ∑jKi,j∗Ki,j=I\sum_jK_{i,j}^{*}K_{i,j}=I∑j​Ki,j∗​Ki,j​=I. Here

σi((c,b),(c′,b′))=Ei ⁣([∏t=0n−1ρ((at,bt),(at′,bt′))]a,a′∈An)c,c′,S(H)=−Re⁡tr⁡(cfc⁡[u↦ulog⁡2u](H)).\sigma_i\bigl((c,b),(c',b')\bigr) = E_i\!\left( \left[\prod_{t=0}^{n-1} \rho\bigl((a_t,b_t),(a'_t,b'_t)\bigr)\right]_{a,a'\in A^n} \right)_{c,c'}, \qquad S(H)=-\operatorname{Re}\operatorname{tr} \left(\operatorname{cfc}[u\mapsto u\log_2u](H)\right).σi​((c,b),(c′,b′))=Ei​​[t=0∏n−1​ρ((at​,bt​),(at′​,bt′​))]a,a′∈An​​c,c′​,S(H)=−Retr(cfc[u↦ulog2​u](H)).

The real logarithm and functional calculus are used as total operations. No density condition on ρ\rhoρ is imposed; n=0n=0n=0, d=0d=0d=0, and empty underlying types are included, with empty products equal to 111. The supremum uses the total real supremum operation, whose value is 000 for an empty or unbounded-above defining set.

QAlgorithms.Papers.Independent.Support50.P39.discardFirstAlice

For arbitrary types T,A,BT,A,BT,A,B, with TTT finite, and an arbitrary complex matrix ρ\rhoρ indexed by (T×A)×B(T\times A)\times B(T×A)×B, this defines a complex matrix indexed by A×BA\times BA×B with entries

D((a,b),(a′,b′))=∑t∈Tρ(((t,a),b),((t,a′),b′))D\bigl((a,b),(a',b')\bigr) =\sum_{t\in T}\rho\bigl(((t,a),b),((t,a'),b')\bigr)D((a,b),(a′,b′))=t∈T∑​ρ(((t,a),b),((t,a′),b′))

for all a,a′∈Aa,a'\in Aa,a′∈A and b,b′∈Bb,b'\in Bb,b′∈B. No positivity or trace condition on ρ\rhoρ, or finiteness condition on A,BA,BA,B, is assumed. If TTT is empty, the result is the zero matrix.

QAlgorithms.Papers.Independent.Support50.P39.encodingHolevo

For finite types A,B,CA,B,CA,B,C with decidable equality, an arbitrary complex matrix ρ\rhoρ indexed by A×BA\times BA×B, natural numbers n,ln,ln,l, arbitrary real weights pip_ipi​, and arbitrary maps EiE_iEi​ from complex matrices indexed by AnA^nAn to those indexed by CCC, for 0≤i<l0\le i<l0≤i<l, define matrices σi\sigma_iσi​ indexed by C×BnC\times B^nC×Bn by

σi((c,b),(c′,b′))=Ei ⁣([∏t=0n−1ρ((at,bt),(at′,bt′))]a,a′∈An)c,c′.\sigma_i\bigl((c,b),(c',b')\bigr) = E_i\!\left( \left[\prod_{t=0}^{n-1} \rho\bigl((a_t,b_t),(a'_t,b'_t)\bigr)\right]_{a,a'\in A^n} \right)_{c,c'}.σi​((c,b),(c′,b′))=Ei​​[t=0∏n−1​ρ((at​,bt​),(at′​,bt′​))]a,a′∈An​​c,c′​.

The declared real number is

S ⁣(∑i=0l−1piσi)−∑i=0l−1piS(σi),S(H)=−Re⁡tr⁡ ⁣(cfc⁡[u↦ulog⁡2u](H)),S\!\left(\sum_{i=0}^{l-1}p_i\sigma_i\right) - \sum_{i=0}^{l-1}p_iS(\sigma_i), \qquad S(H)=-\operatorname{Re}\operatorname{tr}\!\left( \operatorname{cfc}[u\mapsto u\log_2u](H)\right),S(i=0∑l−1​pi​σi​)−i=0∑l−1​pi​S(σi​),S(H)=−Retr(cfc[u↦ulog2​u](H)),

where cfc⁡\operatorname{cfc}cfc is the continuous functional calculus and the real logarithm is interpreted as its total real-valued operation. No distribution condition on ppp, channel condition on EiE_iEi​, or density-matrix condition on ρ\rhoρ is required. The formula includes n=0n=0n=0, when the product is empty and equals 111, and l=0l=0l=0, when its value is S(0)=0S(0)=0S(0)=0; the underlying finite types may also be empty.

QAlgorithms.Papers.Independent.Support50.P39.finiteCoherentOpt

For finite types A,BA,BA,B with decidable equality, an arbitrary complex matrix ρ\rhoρ indexed by A×BA\times BA×B, and natural numbers n,dn,dn,d, this is the real supremum, over all maps Φ\PhiΦ from matrices indexed by AnA^nAn to matrices indexed by {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1} that admit a finite Kraus representation Φ(H)=∑jKjHKj∗\Phi(H)=\sum_jK_jHK_j^{*}Φ(H)=∑j​Kj​HKj∗​ for every HHH, with ∑jKj∗Kj=I\sum_jK_j^{*}K_j=I∑j​Kj∗​Kj​=I, of

max⁡{S(σB)−S(σ), 0}.\max\{S(\sigma_B)-S(\sigma),\,0\}.max{S(σB​)−S(σ),0}.

Here

σ((c,b),(c′,b′))=Φ ⁣([∏t=0n−1ρ((at,bt),(at′,bt′))]a,a′∈An)c,c′,(σB)b,b′=∑c=0d−1σ((c,b),(c,b′)),\sigma\bigl((c,b),(c',b')\bigr) = \Phi\!\left( \left[\prod_{t=0}^{n-1} \rho\bigl((a_t,b_t),(a'_t,b'_t)\bigr)\right]_{a,a'\in A^n} \right)_{c,c'}, \quad (\sigma_B)_{b,b'}=\sum_{c=0}^{d-1}\sigma\bigl((c,b),(c,b')\bigr),σ((c,b),(c′,b′))=Φ​[t=0∏n−1​ρ((at​,bt​),(at′​,bt′​))]a,a′∈An​​c,c′​,(σB​)b,b′​=c=0∑d−1​σ((c,b),(c,b′)),

and S(H)=−Re⁡tr⁡(cfc⁡[u↦ulog⁡2u](H))S(H)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[u\mapsto u\log_2u](H))S(H)=−Retr(cfc[u↦ulog2​u](H)), using the total real logarithm and functional calculus. There is no density condition on ρ\rhoρ. Zero values of n,dn,dn,d and empty underlying types are allowed, with empty products equal to 111; the total real supremum is 000 if its defining set is empty or unbounded above.

QAlgorithms.Papers.Independent.Support50.P39.mutualRatios

For finite types A,BA,BA,B equipped with decidable equality, possibly empty, and any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this defines the set of real numbers rrr for which there exist positive natural numbers c,hc,hc,h and a channel Φ\PhiΦ from AcA^cAc-indexed square matrices to hhh-indexed square matrices with the following properties. Being a channel means that some finite, possibly empty family EℓE_\ellEℓ​ satisfies ∑ℓEℓ†Eℓ=I\sum_\ell E_\ell^\dagger E_\ell=I∑ℓ​Eℓ†​Eℓ​=I and Φ(X)=∑ℓEℓXEℓ†\Phi(X)=\sum_\ell E_\ell X E_\ell^\daggerΦ(X)=∑ℓ​Eℓ​XEℓ†​ for every XXX. Define a matrix σ\sigmaσ indexed by {0,…,h−1}×Bc\{0,\ldots,h-1\}\times B^c{0,…,h−1}×Bc by

σ(u,b),(v,b′)=(Φ(Yb,b′))u,v,Ya,a′b,b′=∏t=0c−1ρ(a(t),b(t)),(a′(t),b′(t)).\sigma_{(u,b),(v,b')}=\bigl(\Phi(Y^{b,b'})\bigr)_{u,v}, \qquad Y^{b,b'}_{a,a'}=\prod_{t=0}^{c-1}\rho_{(a(t),b(t)),(a'(t),b'(t))}.σ(u,b),(v,b′)​=(Φ(Yb,b′))u,v​,Ya,a′b,b′​=t=0∏c−1​ρ(a(t),b(t)),(a′(t),b′(t))​.

Writing (σA)u,v=∑b∈Bcσ(u,b),(v,b)(\sigma_A)_{u,v}=\sum_{b\in B^c}\sigma_{(u,b),(v,b)}(σA​)u,v​=∑b∈Bc​σ(u,b),(v,b)​ and (σB)b,b′=∑u=0h−1σ(u,b),(u,b′)(\sigma_B)_{b,b'}=\sum_{u=0}^{h-1}\sigma_{(u,b),(u,b')}(σB​)b,b′​=∑u=0h−1​σ(u,b),(u,b′)​, the required conditions are

S(σA)>0,r=S(σA)+S(σB)−S(σ)S(σA).S(\sigma_A)>0, \qquad r=\frac{S(\sigma_A)+S(\sigma_B)-S(\sigma)}{S(\sigma_A)}.S(σA​)>0,r=S(σA​)S(σA​)+S(σB​)−S(σ)​.

Here S(X)=−Re⁡tr⁡(f(X))S(X)=-\operatorname{Re}\operatorname{tr}(f(X))S(X)=−Retr(f(X)), where f(t)=tlog⁡2tf(t)=t\log_2 tf(t)=tlog2​t is applied through the continuous functional calculus used in the definition, with the total convention log⁡20=0\log_2 0=0log2​0=0. Thus the denominator is required to be strictly positive; no density-matrix condition is imposed on ρ\rhoρ.

QAlgorithms.Papers.Independent.Support50.P39.noisyResourceCopies

For arbitrary types A,BA,BA,B, any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, and any natural number nnn, this defines a complex matrix indexed by pairs of functions (a,b)(a,b)(a,b), where a:{0,…,n−1}→Aa:\{0,\ldots,n-1\}\to Aa:{0,…,n−1}→A and b:{0,…,n−1}→Bb:\{0,\ldots,n-1\}\to Bb:{0,…,n−1}→B, by

(noisyResourceCopies⁡(ρ,n))(a,b),(a′,b′)=∏t=0n−1ρ(a(t),b(t)),(a′(t),b′(t)).\bigl(\operatorname{noisyResourceCopies}(\rho,n)\bigr)_{(a,b),(a',b')} =\prod_{t=0}^{n-1}\rho_{(a(t),b(t)),(a'(t),b'(t))}.(noisyResourceCopies(ρ,n))(a,b),(a′,b′)​=t=0∏n−1​ρ(a(t),b(t)),(a′(t),b′(t))​.

There are no finiteness, positivity, or normalization assumptions on A,B,ρA,B,\rhoA,B,ρ. The case n=0n=0n=0 is included: both function spaces are singletons, and the resulting one-by-one matrix has entry 111, the empty product.

QAlgorithms.Papers.Independent.Support50.P39.operationalRates

For finite types A,BA,BA,B equipped with decidable equality, possibly empty, and any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this defines the set of real numbers RRR for which there exist natural numbers d≥2d\ge2d≥2 and n>0n>0n>0 such that R≥0R\ge0R≥0 and the following holds: for every real 0<ϵ<10<\epsilon<10<ϵ<1 and every real δ>0\delta>0δ>0, there exists a natural number KKK such that every natural number k≥Kk\ge Kk≥K with k>0k>0k>0 admits a natural number mmm with

(R−δ)klog⁡2d≤m(R-\delta)k\log_2 d\le m(R−δ)klog2​d≤m

and encoding and decoding data as follows. For each Boolean string xxx of length mmm, an encoding channel Enc⁡x\operatorname{Enc}_xEncx​ maps matrices indexed by AnkA^{nk}Ank to matrices indexed by H={0,…,dk−1}H=\{0,\ldots,d^k-1\}H={0,…,dk−1}; it has some finite Kraus family Ex,ℓE_{x,\ell}Ex,ℓ​, possibly empty, with ∑ℓEx,ℓ†Ex,ℓ=I\sum_\ell E_{x,\ell}^\dagger E_{x,\ell}=I∑ℓ​Ex,ℓ†​Ex,ℓ​=I and Enc⁡x(X)=∑ℓEx,ℓXEx,ℓ†\operatorname{Enc}_x(X)=\sum_\ell E_{x,\ell}XE_{x,\ell}^\daggerEncx​(X)=∑ℓ​Ex,ℓ​XEx,ℓ†​ for every XXX. There are positive semidefinite matrices DxD_xDx​ indexed by H×BnkH\times B^{nk}H×Bnk, summing to the identity, such that

1−ϵ≤Re⁡tr⁡(Dxσx)for every x,(σx)(u,b),(v,b′)=(Enc⁡x ⁣[∏t=0nk−1ρ(a(t),b(t)),(a′(t),b′(t))]a,a′)u,v.1-\epsilon\le\operatorname{Re}\operatorname{tr}(D_x\sigma_x) \quad\text{for every }x, \qquad (\sigma_x)_{(u,b),(v,b')}= \left(\operatorname{Enc}_x\!\left[ \prod_{t=0}^{nk-1}\rho_{(a(t),b(t)),(a'(t),b'(t))} \right]_{a,a'}\right)_{u,v}.1−ϵ≤Retr(Dx​σx​)for every x,(σx​)(u,b),(v,b′)​=​Encx​[t=0∏nk−1​ρ(a(t),b(t)),(a′(t),b′(t))​]a,a′​​u,v​.

The dimensions d,nd,nd,n are fixed before ϵ,δ,k\epsilon,\delta,kϵ,δ,k are chosen, and m=0m=0m=0 is allowed. No density-matrix condition is imposed on ρ\rhoρ. If either AAA or BBB is empty, the positive copy count nknknk makes every displayed success value zero, so the set is empty.

QAlgorithms.Papers.Independent.Support50.P39.processedResource

For a finite type AAA equipped with decidable equality, an arbitrary type BBB, any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, and a preprocessing object PPP, this defines a matrix σ\sigmaσ indexed by {0,…,h−1}×Bc\{0,\ldots,h-1\}\times B^c{0,…,h−1}×Bc, where c=P.copies>0c=P.\mathrm{copies}>0c=P.copies>0, h=P.outputDim>0h=P.\mathrm{outputDim}>0h=P.outputDim>0, and BcB^cBc denotes functions {0,…,c−1}→B\{0,\ldots,c-1\}\to B{0,…,c−1}→B. The object supplies a channel Φ=P.channel\Phi=P.\mathrm{channel}Φ=P.channel: there is a finite, possibly empty family of matrices EℓE_\ellEℓ​ satisfying ∑ℓEℓ†Eℓ=I\sum_\ell E_\ell^\dagger E_\ell=I∑ℓ​Eℓ†​Eℓ​=I and Φ(X)=∑ℓEℓXEℓ†\Phi(X)=\sum_\ell E_\ell X E_\ell^\daggerΦ(X)=∑ℓ​Eℓ​XEℓ†​ for every AcA^cAc-indexed input matrix XXX. The defined matrix has entries

σ(u,b),(v,b′)=(Φ(Yb,b′))u,v,Ya,a′b,b′=∏t=0c−1ρ(a(t),b(t)),(a′(t),b′(t)).\sigma_{(u,b),(v,b')} =\bigl(\Phi(Y^{b,b'})\bigr)_{u,v}, \qquad Y^{b,b'}_{a,a'} =\prod_{t=0}^{c-1}\rho_{(a(t),b(t)),(a'(t),b'(t))}.σ(u,b),(v,b′)​=(Φ(Yb,b′))u,v​,Ya,a′b,b′​=t=0∏c−1​ρ(a(t),b(t)),(a′(t),b′(t))​.

Neither ρ\rhoρ nor BBB has an additional positivity, normalization, or finiteness requirement.

QAlgorithms.Papers.Independent.Support50.P39.productFactor

For arbitrary types T,A,BT,A,BT,A,B, a complex matrix τ\tauτ indexed by TTT, and a complex matrix σ\sigmaσ indexed by A×BA\times BA×B, this defines a complex matrix indexed by (T×A)×B(T\times A)\times B(T×A)×B through

P(((t,a),b),((t′,a′),b′))=τt,t′ σ((a,b),(a′,b′))P\bigl(((t,a),b),((t',a'),b')\bigr) =\tau_{t,t'}\,\sigma\bigl((a,b),(a',b')\bigr)P(((t,a),b),((t′,a′),b′))=τt,t′​σ((a,b),(a′,b′))

for every t,t′∈Tt,t'\in Tt,t′∈T, a,a′∈Aa,a'\in Aa,a′∈A, and b,b′∈Bb,b'\in Bb,b′∈B. No finiteness, nonemptiness, positivity, or trace assumptions are imposed; empty types simply leave no corresponding entries.

QAlgorithms.Papers.Independent.Support50.P39.quantumMutualInformation

For any finite types A,BA,BA,B equipped with decidable equality, possibly empty, and any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this defines

S(ρA)+S(ρB)−S(ρ),(ρA)a,a′=∑b∈Bρ(a,b),(a′,b),(ρB)b,b′=∑a∈Aρ(a,b),(a,b′).S(\rho_A)+S(\rho_B)-S(\rho), \qquad (\rho_A)_{a,a'}=\sum_{b\in B}\rho_{(a,b),(a',b)}, \qquad (\rho_B)_{b,b'}=\sum_{a\in A}\rho_{(a,b),(a,b')}.S(ρA​)+S(ρB​)−S(ρ),(ρA​)a,a′​=b∈B∑​ρ(a,b),(a′,b)​,(ρB​)b,b′​=a∈A∑​ρ(a,b),(a,b′)​.

Here S(X)=−Re⁡tr⁡(f(X))S(X)=-\operatorname{Re}\operatorname{tr}(f(X))S(X)=−Retr(f(X)), with f(t)=tlog⁡2tf(t)=t\log_2 tf(t)=tlog2​t applied by the continuous functional calculus used in the definition, and with the total real logarithm satisfying log⁡20=0\log_2 0=0log2​0=0. No positivity, normalization, or nonnegativity condition is imposed on this expression or on ρ\rhoρ.

QAlgorithms.Papers.Independent.Support50.P39.uniformWeight

For every natural number ddd, this defines the real-valued function on {0,…,d2−1}\{0,\ldots,d^2-1\}{0,…,d2−1} that takes the constant value (d2)−1(d^2)^{-1}(d2)−1. When d=0d=0d=0, its domain is empty; the total real inverse used in the formula assigns 0−1=00^{-1}=00−1=0.

QAlgorithms.Papers.Independent.Support50.P39.unitaryEncoders

For a finite type AAA, a natural number ddd, an arbitrary map Φ\PhiΦ from complex matrices indexed by AAA to complex d×dd\times dd×d matrices, and a family of unitary d×dd\times dd×d matrices UiU_iUi​ indexed by 0≤i<d20\le i<d^20≤i<d2, this defines a family of maps by

Ei(H)=Ui Φ(H) Ui∗for every complex matrix H indexed by A.E_i(H)=U_i\,\Phi(H)\,U_i^{*} \quad\text{for every complex matrix }H\text{ indexed by }A.Ei​(H)=Ui​Φ(H)Ui∗​for every complex matrix H indexed by A.

No channel or linearity condition on Φ\PhiΦ is assumed. The type AAA may be empty, and d=0d=0d=0 gives an empty family.

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).

  • Endorsed by Gohan · Oct 30, 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