Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for On the quantum, classical and total amount of correlations in a quantum state

Definition
QAlgorithms_Papers_Independent_Intakenext100_P47

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of On the quantum, classical and total amount of correlations in a quantum state (arXiv:quant-ph/0410091) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • sourcePower: PDF p.2: rho tensor n in party order A^n:B^n.
  • LocalNoise: PDF p.2: a finite probability ensemble; zero-weight entries are permitted.
  • COLUR: PDF p.2, (2): one shared random index, with actual product unitaries.
  • COLUR.operation: PDF p.2, (2): the channel implemented by the chosen ensemble.
  • NoiseClass: PDF p.2: the four noise restrictions distinguished by the source.
  • COLUR.allowed: PDF p.2: LUR independence is imposed on the implementing ensemble, not just its channel.
  • NoiseCost: PDF pp.2--3, (4): the three ensemble noise costs.
  • COLUR.cost: PDF pp.2--3: size and Shannon cost belong to an ensemble; exchange belongs to its channel.
  • Decorrelates: PDF p.2, (3): approximation by a normalized product, full trace norm.
  • Disentangles: PDF p.6, (14): closeness to an actual normalized separable state.
  • erasureEta: PDF p.3, (5): the capped entropy correction, including the continuous value at zero.
  • logDimension: PDF pp.3,6: fixed one-copy dimension d=d_A*d_B, independent of blocklength.
  • totalCosts: PDF p.4: feasible noise costs at a finite block.
  • totalBlockRate: PDF p.4: optimal finite noise per copy; n=k+1 excludes division by zero.
  • rateLimit: PDF pp.4,7: choose liminf (optimistic) or limsup (pessimistic), before vanishing error.
  • totalErasure: PDF p.4, Theorem II.3: operational erasure rate, independently computed from ensembles.
  • disentanglingSizes: PDF p.7: admissible finite ensemble sizes for entanglement erasure.
  • minimumDisentanglingSize: PDF p.7: N(n,eps), the smallest size, defined by the actual feasible channels.
  • entanglementBlockRate: PDF p.7: normalized finite-block cost; only positive lengths enter the limit.
  • entanglementErasure: PDF pp.7--8: optimistic/pessimistic erasure, without assuming the conjectured entropy formula.
  • separableEntropyCosts: PDF p.6, Proposition III.1: all COLUR maps and nearby separable targets are optimized.
  • withAncilla: PDF p.5: combine rho and an arbitrary ancillary bipartite state in party order.
  • discountedCosts: PDF p.5: finite ancillary dimensions are varied explicitly, with their cost discounted.
  • blockIndex: PDF pp.6--7: concatenate n successive k-copy blocks, retaining the party order.
  • regroupedChannelPower: PDF p.7: transport the accepted tensor-power channel from copy order (AB)^n into party order A^n:B^n, on every matrix coefficient including reference blocks.
  • schmidtKet: PDF p.8: normalized Schmidt ket in arbitrary orthonormal local frames.
  • schmidtDiagonal: PDF p.8: the dephased Schmidt state; the output is constructed, not assumed.
  • schmidtPhase: PDF p.8: positive phase exp(2piikj/D), identity on the unused orthogonal complement.
  • PublicProtocol: PDF pp.5--6, Remark II.6: a finite adaptive public-instrument tree. Every outcome is public; subsequent local instruments may depend on the full transcript. All finite local dimensions, outcomes, Kraus counts, and finite numbers of rounds occur.
  • PublicProtocol.average: PDF pp.5--6, (12)--(13): actual expected final mutual information conditional on all public messages. Zero-probability branches contribute zero, without normalization.
  • MultiCopies: PDF p.10: party i's n-copy register.
  • multiSourcePower: PDF p.10: independent copies of the multipartite source, regrouped by party.
  • MultiNoise: PDF p.10: multipartite COLUR, with actual product unitaries and one shared index.
  • MultiNoise.productUnitary: PDF p.10: the tensor-product unitary for one ensemble member.
  • MultiNoise.operation: PDF p.10: the actual randomizing operation on every joint operator.
  • MultiNoise.independent: PDF p.10: independent LUR choices imposed on the ensemble itself.
  • MultiNoise.cost: PDF p.10: the same three costs, counted on a multipartite ensemble.
  • MultiDecorrelates: PDF p.10: a fully product target, normalized at every party.
  • reducedOn: PDF p.10: an actual partial trace onto a specified set of parties.
  • multiInformation: PDF p.10, (16): the entropy expression, distinct from the operational erasure rate.
  • tailInformation: PDF p.10: I(A_j : A_{j+1}...A_p), on the original tail marginal.
  • multiCosts: PDF p.10: finite-block multipartite feasible costs.
  • multiBlockRate: PDF p.10: normalized finite cost, with strictly positive copy count.
  • multiErasure: PDF p.10: operational multipartite total erasure, without an entropy definition.
  • successiveBlockOutput: PDF p.10: the same execution at arbitrary positive blocklength.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Ensemble
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Defs_BipartiteSeparability
import Definitions.Def_QAlgorithms_Defs_Measurement
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P20
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P19
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P45
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P27
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P71
import Definitions.Def_QAlgorithms_Papers_Independent_Advance50_P05

/-!
Groisman--Popescu--Winter, arXiv:quant-ph/0410091v2.
All entropies are in bits; traceNorm is the full Schatten 1-norm.
Accepted frozen interfaces are imported; new operational definitions are confined to
this paper. The operational costs below contain no mutual-information formula. Finite nonzero local spaces may have unequal dimensions.
The source's conjectures, erroneous formulas, and cited background are inventoried
in HARD.md. Compilation is pending the separate mechanical handoff.
-/

noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P47

open QAlgorithms Filter
open QAlgorithms.Papers.Independent.Gap48.P20 (Copies localProduct)
open QAlgorithms.Papers.Independent.Dependency50.P19 (mutualInformation first)
open QAlgorithms.Papers.Independent.Dependency50.P45 (entropyExchange)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon Config)
open QAlgorithms.Papers.Independent.Information100.P71 (channelPower)
open QAlgorithms.Papers.Independent.Advance50.P05 (RectangularInstrument)
open scoped Matrix ComplexConjugate

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF p.2: rho tensor n in party order A^n:B^n. -/
def sourcePower {A B : Type} (rho : Matrix (A × B) (A × B) ℂ) (n : ℕ) :
    Matrix (Copies A n × Copies B n) (Copies A n × Copies B n) ℂ :=
  fun x y => ∏ t, rho (x.1 t, x.2 t) (y.1 t, y.2 t)

/-- PDF p.2: a finite probability ensemble; zero-weight entries are permitted. -/
structure LocalNoise (A : Type) [Fintype A] where
  count : ℕ
  count_pos : 0 < count
  weight : Fin count → ℝ
  weight_nonneg : ∀ i, 0 ≤ weight i
  weight_sum : ∑ i, weight i = 1
  unitary : Fin count → Matrix.unitaryGroup A ℂ

/-- PDF p.2, (2): one shared random index, with actual product unitaries. -/
structure COLUR (A B : Type) [Fintype A] [Fintype B] where
  count : ℕ
  count_pos : 0 < count
  weight : Fin count → ℝ
  weight_nonneg : ∀ i, 0 ≤ weight i
  weight_sum : ∑ i, weight i = 1
  alice : Fin count → Matrix.unitaryGroup A ℂ
  bob : Fin count → Matrix.unitaryGroup B ℂ

/-- PDF p.2, (2): the channel implemented by the chosen ensemble. -/
def COLUR.operation {A B : Type} [Fintype A] [Fintype B] (R : COLUR A B) :
    Superop (A × B) (A × B) :=
  fun rho => ∑ i, (R.weight i : ℂ) •
    (Matrix.kronecker (R.alice i : Matrix A A ℂ) (R.bob i : Matrix B B ℂ) * rho *
      (Matrix.kronecker (R.alice i : Matrix A A ℂ) (R.bob i : Matrix B B ℂ))ᴴ)

/-- PDF p.2: the four noise restrictions distinguished by the source. -/
inductive NoiseClass where
  | coordinated | alice | bob | independent
  deriving DecidableEq

/-- PDF p.2: LUR independence is imposed on the implementing ensemble, not just its channel. -/
def COLUR.allowed {A B : Type} [Fintype A] [Fintype B]
    (R : COLUR A B) : NoiseClass → Prop
  | .coordinated => True
  | .alice => ∀ i, R.bob i = 1
  | .bob => ∀ i, R.alice i = 1
  | .independent => ∃ L : LocalNoise A, ∃ M : LocalNoise B,
      ∃ e : Fin R.count ≃ (Fin L.count × Fin M.count),
        (∀ i, R.weight i = L.weight (e i).1 * M.weight (e i).2) ∧
        (∀ i, R.alice i = L.unitary (e i).1) ∧
        (∀ i, R.bob i = M.unitary (e i).2)

/-- PDF pp.2--3, (4): the three ensemble noise costs. -/
inductive NoiseCost where
  | size | entropy | exchange
  deriving DecidableEq

/-- PDF pp.2--3: size and Shannon cost belong to an ensemble; exchange belongs to its channel. -/
def COLUR.cost {A B : Type} [Fintype A] [Fintype B] (R : COLUR A B)
    (rho : Matrix (A × B) (A × B) ℂ) : NoiseCost → ℝ
  | .size => Real.logb 2 R.count
  | .entropy => shannon R.weight
  | .exchange => entropyExchange R.operation rho

/-- PDF p.2, (3): approximation by a normalized product, full trace norm. -/
def Decorrelates {A B : Type} [Fintype A] [Fintype B]
    (out : Matrix (A × B) (A × B) ℂ) (eps : ℝ) : Prop :=
  ∃ a : Matrix A A ℂ, ∃ b : Matrix B B ℂ,
    IsDensityMatrix a ∧ IsDensityMatrix b ∧ traceNorm (out - Matrix.kronecker a b) ≤ eps

/-- PDF p.6, (14): closeness to an actual normalized separable state. -/
def Disentangles {A B : Type} [Fintype A] [Fintype B] [Nonempty A] [Nonempty B]
    (out : Matrix (A × B) (A × B) ℂ) (eps : ℝ) : Prop :=
  ∃ sigma : Matrix (A × B) (A × B) ℂ,
    Entanglement.IsSeparableDensity sigma ∧ traceNorm (out - sigma) ≤ eps

/-- PDF p.3, (5): the capped entropy correction, including the continuous value at zero. -/
def erasureEta (x : ℝ) : ℝ :=
  if x ≤ (Real.exp 1)⁻¹ then -x * Real.logb 2 x
  else (Real.exp 1)⁻¹ * Real.logb 2 (Real.exp 1)

/-- PDF pp.3,6: fixed one-copy dimension d=d_A*d_B, independent of blocklength. -/
def logDimension (A B : Type) [Fintype A] [Fintype B] : ℝ :=
  Real.logb 2 (Fintype.card A * Fintype.card B : ℕ)

/-- PDF p.4: feasible noise costs at a finite block. -/
def totalCosts {A B : Type} [Fintype A] [Fintype B]
    (rho : Matrix (A × B) (A × B) ℂ) (n : ℕ) (eps : ℝ)
    (mode : NoiseClass) (cost : NoiseCost) : Set ℝ :=
  {v | ∃ R : COLUR (Copies A n) (Copies B n), R.allowed mode ∧
    Decorrelates (R.operation (sourcePower rho n)) eps ∧
    v = R.cost (sourcePower rho n) cost}

/-- PDF p.4: optimal finite noise per copy; n=k+1 excludes division by zero. -/
def totalBlockRate {A B : Type} [Fintype A] [Fintype B]
    (rho : Matrix (A × B) (A × B) ℂ) (eps : ℝ) (mode : NoiseClass)
    (cost : NoiseCost) (k : ℕ) : ℝ :=
  sInf (totalCosts rho (k+1) eps mode cost) / (k+1 : ℕ)

/-- PDF pp.4,7: choose liminf (optimistic) or limsup (pessimistic), before vanishing error. -/
def rateLimit (pessimistic : Bool) (f : ℕ → ℝ) : ℝ :=
  if pessimistic then limsup f atTop else liminf f atTop

/-- PDF p.4, Theorem II.3: operational erasure rate, independently computed from ensembles. -/
def totalErasure {A B : Type} [Fintype A] [Fintype B]
    (rho : Matrix (A × B) (A × B) ℂ) (mode : NoiseClass)
    (cost : NoiseCost) (pessimistic : Bool) : ℝ :=
  sSup {v | ∃ eps > (0 : ℝ), v = rateLimit pessimistic (totalBlockRate rho eps mode cost)}

/-- PDF p.7: admissible finite ensemble sizes for entanglement erasure. -/
def disentanglingSizes {A B : Type} [Fintype A] [Fintype B] [Nonempty A] [Nonempty B]
    (rho : Matrix (A × B) (A × B) ℂ) (n : ℕ) (eps : ℝ) : Set ℕ :=
  {N | ∃ R : COLUR (Copies A n) (Copies B n), R.count = N ∧
    Disentangles (R.operation (sourcePower rho n)) eps}

/-- PDF p.7: N(n,eps), the smallest size, defined by the actual feasible channels. -/
def minimumDisentanglingSize {A B : Type} [Fintype A] [Fintype B]
    [Nonempty A] [Nonempty B] (rho : Matrix (A × B) (A × B) ℂ) (n : ℕ) (eps : ℝ) : ℕ :=
  sInf (disentanglingSizes rho n eps)

/-- PDF p.7: normalized finite-block cost; only positive lengths enter the limit. -/
def entanglementBlockRate {A B : Type} [Fintype A] [Fintype B]
    [Nonempty A] [Nonempty B] (rho : Matrix (A × B) (A × B) ℂ) (eps : ℝ) (k : ℕ) : ℝ :=
  Real.logb 2 (minimumDisentanglingSize rho (k+1) eps) / (k+1 : ℕ)

/-- PDF pp.7--8: optimistic/pessimistic erasure, without assuming the conjectured entropy formula. -/
def entanglementErasure {A B : Type} [Fintype A] [Fintype B]
    [Nonempty A] [Nonempty B] (rho : Matrix (A × B) (A × B) ℂ)
    (pessimistic : Bool) : ℝ :=
  sSup {v | ∃ eps > (0 : ℝ), v = rateLimit pessimistic (entanglementBlockRate rho eps)}

/-- PDF p.6, Proposition III.1: all COLUR maps and nearby separable targets are optimized. -/
def separableEntropyCosts {A B : Type} [Fintype A] [Fintype B]
    [Nonempty A] [Nonempty B] (rho : Matrix (A × B) (A × B) ℂ)
    (n : ℕ) (eps : ℝ) : Set ℝ :=
  {v | ∃ R : COLUR (Copies A n) (Copies B n),
    ∃ sigma : Matrix (Copies A n × Copies B n) (Copies A n × Copies B n) ℂ,
      Entanglement.IsSeparableDensity sigma ∧
      traceNorm (sigma - R.operation (sourcePower rho n)) ≤ eps ∧
      v = vnEntropy sigma - n * vnEntropy rho - n * eps * logDimension A B - erasureEta eps}

/-- Sanity: no-copy tensors are the scalar unit, not the zero state. -/
example {A B : Type} (rho : Matrix (A × B) (A × B) ℂ)
    (x y : Copies A 0 × Copies B 0) : sourcePower rho 0 x y = 1 := by
  simp [sourcePower]

/-- Sanity: the one-copy matrix preserves every entry and its party order. -/
example {A B : Type} (rho : Matrix (A × B) (A × B) ℂ)
    (x y : Copies A 1 × Copies B 1) :
    sourcePower rho 1 x y = rho (x.1 0, x.2 0) (y.1 0, y.2 0) := by
  simp [sourcePower]

/-- Sanity: the zero probability and erasureEta boundary are continuous entropy contributions. -/
example : shannon (fun _ : Fin 1 => (1 : ℝ)) = 0 ∧ erasureEta 0 = 0 := by
  simp [shannon, erasureEta, le_of_lt (inv_pos.mpr (Real.exp_pos 1))]

/-- Sanity: every chosen randomizing ensemble sends the zero operator to zero. -/
example {A B : Type} [Fintype A] [Fintype B] (R : COLUR A B) :
    R.operation 0 = 0 := by
  simp [COLUR.operation]

/-- Sanity: the one-copy zero source retains zero. -/
example {A B : Type}
    (x y : Copies A 1 × Copies B 1) :
    sourcePower (0 : Matrix (A × B) (A × B) ℂ) 1 x y = 0 := by
  simp [sourcePower]

/-- PDF p.5: combine rho and an arbitrary ancillary bipartite state in party order. -/
def withAncilla {A B C D : Type} (rho : Matrix (A × B) (A × B) ℂ)
    (gamma : Matrix (C × D) (C × D) ℂ) :
    Matrix ((A × C) × (B × D)) ((A × C) × (B × D)) ℂ :=
  fun x y => rho (x.1.1,x.2.1) (y.1.1,y.2.1) * gamma (x.1.2,x.2.2) (y.1.2,y.2.2)

/-- PDF p.5: finite ancillary dimensions are varied explicitly, with their cost discounted. -/
def discountedCosts {A B : Type} [Fintype A] [Fintype B]
    (rho : Matrix (A × B) (A × B) ℂ) : Set ℝ :=
  {v | ∃ c d : ℕ, ∃ hc : 0 < c, ∃ hd : 0 < d,
    ∃ gamma : Matrix (Fin c × Fin d) (Fin c × Fin d) ℂ, IsDensityMatrix gamma ∧
      v = totalErasure (withAncilla rho gamma) .coordinated .size true -
        totalErasure gamma .coordinated .size true}

/-- PDF pp.6--7: concatenate n successive k-copy blocks, retaining the party order. -/
def blockIndex {k n : ℕ} (t : Fin n) (s : Fin k) : Fin (k*n) :=
  Fin.cast (Nat.mul_comm n k) (finProdFinEquiv (t,s))

/-- PDF p.7: transport the accepted tensor-power channel from copy order (AB)^n
into party order A^n:B^n, on every matrix coefficient including reference blocks. -/
def regroupedChannelPower {A B : Type} [Fintype A] [Fintype B]
    (T : Superop (A × B) (A × B)) (n : ℕ) :
    Superop (Copies A n × Copies B n) (Copies A n × Copies B n) :=
  fun rho x y => channelPower T n
    (fun u v => rho ((fun t => (u t).1), (fun t => (u t).2))
      ((fun t => (v t).1), (fun t => (v t).2)))
    (fun t => (x.1 t, x.2 t)) (fun t => (y.1 t, y.2 t))

/-- PDF p.8: normalized Schmidt ket in arbitrary orthonormal local frames. -/
def schmidtKet {A B : Type} {D : ℕ} (f : Fin D → ℝ)
    (a : Matrix A (Fin D) ℂ) (b : Matrix B (Fin D) ℂ) : EuclideanSpace ℂ (A × B) :=
  WithLp.toLp 2 fun x => ∑ j, (Real.sqrt (f j) : ℂ) * a x.1 j * b x.2 j

/-- PDF p.8: the dephased Schmidt state; the output is constructed, not assumed. -/
def schmidtDiagonal {A B : Type} {D : ℕ} (f : Fin D → ℝ)
    (a : Matrix A (Fin D) ℂ) (b : Matrix B (Fin D) ℂ) : Matrix (A × B) (A × B) ℂ :=
  fun x y => ∑ j, (f j : ℂ) * a x.1 j * b x.2 j * conj (a y.1 j * b y.2 j)

/-- PDF p.8: positive phase exp(2*pi*i*k*j/D), identity on the unused orthogonal complement. -/
def schmidtPhase {A : Type} [Fintype A] {D : ℕ}
    (a : Matrix A (Fin D) ℂ) (k : Fin D) : Matrix A A ℂ :=
  (1 : Matrix A A ℂ) + (Matrix.of fun (x y : A) => ∑ j,
    (Complex.exp (2 * Real.pi * Complex.I *
      (k.val : ℂ) * (j.val : ℂ) / (D : ℂ)) - 1) * a x j * conj (a y j))

/-- PDF pp.5--6, Remark II.6: a finite adaptive public-instrument tree.
Every outcome is public; subsequent local instruments may depend on the full transcript.
All finite local dimensions, outcomes, Kraus counts, and finite numbers of rounds occur. -/
inductive PublicProtocol : ℕ → ℕ → Type
  | stop {a b : ℕ} : PublicProtocol a b
  | alice {a b c : ℕ} (hc : 0 < c) (outcomeCount : ℕ)
      (I : RectangularInstrument (Fin a) (Fin c) (Fin (outcomeCount+1)))
      (next : Fin (outcomeCount+1) → PublicProtocol c b) : PublicProtocol a b
  | bob {a b d : ℕ} (hd : 0 < d) (outcomeCount : ℕ)
      (I : RectangularInstrument (Fin b) (Fin d) (Fin (outcomeCount+1)))
      (next : Fin (outcomeCount+1) → PublicProtocol a d) : PublicProtocol a b

/-- PDF pp.5--6, (12)--(13): actual expected final mutual information conditional on
all public messages. Zero-probability branches contribute zero, without normalization. -/
def PublicProtocol.average : {a b : ℕ} → PublicProtocol a b →
    Matrix (Fin a × Fin b) (Fin a × Fin b) ℂ → ℝ
  | _, _, .stop, rho => mutualInformation rho
  | _, _, .alice _ _ I next, rho => ∑ x,
      let omega := first (I.branch x) rho
      let p := omega.trace.re
      if 0 < p then p * (next x).average ((p : ℂ)⁻¹ • omega) else 0
  | _, _, .bob _ _ I next, rho => ∑ x,
      let omega := idTensorSuperop (I.branch x) rho
      let p := omega.trace.re
      if 0 < p then p * (next x).average ((p : ℂ)⁻¹ • omega) else 0

/-- Sanity: no instrument leaves the original total correlation. -/
example {a b : ℕ} (rho : Matrix (Fin a × Fin b) (Fin a × Fin b) ℂ) :
    PublicProtocol.average .stop rho = mutualInformation rho := rfl

/-- PDF p.10: party i's n-copy register. -/
abbrev MultiCopies {p : ℕ} (d : Fin p → ℕ) (n : ℕ) (i : Fin p) := Copies (Fin (d i)) n

/-- PDF p.10: independent copies of the multipartite source, regrouped by party. -/
def multiSourcePower {p : ℕ} {d : Fin p → ℕ}
    (rho : Matrix (Config d) (Config d) ℂ) (n : ℕ) :
    Matrix ((i : Fin p) → MultiCopies d n i) ((i : Fin p) → MultiCopies d n i) ℂ :=
  fun x y => ∏ t, rho (fun i => x i t) (fun i => y i t)

/-- PDF p.10: multipartite COLUR, with actual product unitaries and one shared index. -/
structure MultiNoise {p : ℕ} (D : Fin p → Type) [∀ i, Fintype (D i)] where
  count : ℕ
  count_pos : 0 < count
  weight : Fin count → ℝ
  weight_nonneg : ∀ j, 0 ≤ weight j
  weight_sum : ∑ j, weight j = 1
  unitary : Fin count → (i : Fin p) → Matrix.unitaryGroup (D i) ℂ

/-- PDF p.10: the tensor-product unitary for one ensemble member. -/
def MultiNoise.productUnitary {p : ℕ} {D : Fin p → Type} [∀ i, Fintype (D i)]
    (R : MultiNoise D) (j : Fin R.count) : Matrix ((i : Fin p) → D i) ((i : Fin p) → D i) ℂ :=
  fun x y => ∏ i, (R.unitary j i : Matrix (D i) (D i) ℂ) (x i) (y i)

/-- PDF p.10: the actual randomizing operation on every joint operator. -/
def MultiNoise.operation {p : ℕ} {D : Fin p → Type} [∀ i, Fintype (D i)]
    (R : MultiNoise D) : Superop ((i : Fin p) → D i) ((i : Fin p) → D i) :=
  fun rho => ∑ j, (R.weight j : ℂ) •
    (R.productUnitary j * rho * (R.productUnitary j)ᴴ)

/-- PDF p.10: independent LUR choices imposed on the ensemble itself. -/
def MultiNoise.independent {p : ℕ} {D : Fin p → Type} [∀ i, Fintype (D i)]
    (R : MultiNoise D) : Prop :=
  ∃ L : (i : Fin p) → LocalNoise (D i),
    ∃ e : Fin R.count ≃ ((i : Fin p) → Fin (L i).count),
      (∀ j, R.weight j = ∏ i, (L i).weight (e j i)) ∧
      (∀ j i, R.unitary j i = (L i).unitary (e j i))

/-- PDF p.10: the same three costs, counted on a multipartite ensemble. -/
def MultiNoise.cost {p : ℕ} {D : Fin p → Type} [∀ i, Fintype (D i)]
    (R : MultiNoise D) (rho : Matrix ((i : Fin p) → D i) ((i : Fin p) → D i) ℂ) : NoiseCost → ℝ
  | .size => Real.logb 2 R.count
  | .entropy => shannon R.weight
  | .exchange => entropyExchange R.operation rho

/-- PDF p.10: a fully product target, normalized at every party. -/
def MultiDecorrelates {p : ℕ} {D : Fin p → Type} [∀ i, Fintype (D i)]
    (out : Matrix ((i : Fin p) → D i) ((i : Fin p) → D i) ℂ) (eps : ℝ) : Prop :=
  ∃ sigma : (i : Fin p) → Matrix (D i) (D i) ℂ,
    (∀ i, IsDensityMatrix (sigma i)) ∧
    traceNorm (out - (Matrix.of fun (x y : (i : Fin p) → D i) =>
      ∏ i, sigma i (x i) (y i))) ≤ eps

/-- PDF p.10: an actual partial trace onto a specified set of parties. -/
def reducedOn {p : ℕ} {d : Fin p → ℕ}
    (rho : Matrix (Config d) (Config d) ℂ)
    (S : Finset (Fin p)) :
    Matrix ((i : {i // i ∈ S}) → Fin (d i.val))
      ((i : {i // i ∈ S}) → Fin (d i.val)) ℂ :=
  fun u v => ∑ x, ∑ y,
    if (∀ i : {i // i ∈ S}, x i.val = u i) ∧
       (∀ i : {i // i ∈ S}, y i.val = v i) ∧
       (∀ i, i ∉ S → x i = y i) then rho x y else 0

/-- PDF p.10, (16): the entropy expression, distinct from the operational erasure rate. -/
def multiInformation {p : ℕ} {d : Fin p → ℕ}
    (rho : Matrix (Config d) (Config d) ℂ) : ℝ :=
  (∑ i, vnEntropy (reducedOn rho {i})) - vnEntropy rho

/-- PDF p.10: I(A_j : A_{j+1}...A_p), on the original tail marginal. -/
def tailInformation {p : ℕ} {d : Fin p → ℕ}
    (rho : Matrix (Config d) (Config d) ℂ)
    (j : Fin (p-1)) : ℝ :=
  vnEntropy (reducedOn rho (Finset.univ.filter fun i => i.val = j.val)) +
    vnEntropy (reducedOn rho (Finset.univ.filter fun i => j.val < i.val)) -
    vnEntropy (reducedOn rho (Finset.univ.filter fun i => j.val ≤ i.val))

/-- PDF p.10: finite-block multipartite feasible costs. -/
def multiCosts {p : ℕ} {d : Fin p → ℕ}
    (rho : Matrix (Config d) (Config d) ℂ)
    (n : ℕ) (eps : ℝ) (independent : Bool) (cost : NoiseCost) : Set ℝ :=
  {v | ∃ R : MultiNoise (MultiCopies d n),
    (independent = true → R.independent) ∧
    MultiDecorrelates (R.operation (multiSourcePower rho n)) eps ∧
    v = R.cost (multiSourcePower rho n) cost}

/-- PDF p.10: normalized finite cost, with strictly positive copy count. -/
def multiBlockRate {p : ℕ} {d : Fin p → ℕ}
    (rho : Matrix (Config d) (Config d) ℂ)
    (eps : ℝ) (independent : Bool) (cost : NoiseCost) (k : ℕ) : ℝ :=
  sInf (multiCosts rho (k+1) eps independent cost) / (k+1 : ℕ)

/-- PDF p.10: operational multipartite total erasure, without an entropy definition. -/
def multiErasure {p : ℕ} {d : Fin p → ℕ}
    (rho : Matrix (Config d) (Config d) ℂ)
    (independent : Bool) (cost : NoiseCost) (pessimistic : Bool) : ℝ :=
  sSup {v | ∃ eps > (0 : ℝ), v = rateLimit pessimistic (multiBlockRate rho eps independent cost)}

/-- PDF p.10: the same execution at arbitrary positive blocklength. -/
def successiveBlockOutput {p : ℕ} {d : Fin p → ℕ} {n : ℕ}
    (R : Fin (p-1) → MultiNoise (MultiCopies d n))
    (rho : Matrix ((i : Fin p) → MultiCopies d n i) ((i : Fin p) → MultiCopies d n i) ℂ) :=
  (List.finRange (p-1)).foldl (fun state j => (R j).operation state) rho

/-- Sanity: a single party requires no successive stage. -/
example {d : Fin 1 → ℕ} {n : ℕ}
    (R : Fin (1-1) → MultiNoise (MultiCopies d n))
    (rho : Matrix ((i : Fin 1) → MultiCopies d n i) ((i : Fin 1) → MultiCopies d n i) ℂ) :
    successiveBlockOutput R rho = rho := by
  simp [successiveBlockOutput]

end QAlgorithms.Papers.Independent.Intakenext100.P47
Source
On the quantum, classical and total amount of correlations in a quantum state, arXiv:quant-ph/0410091v2, https://arxiv.org/abs/quant-ph/0410091v2
Read-back

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

QAlgorithms.Papers.Independent.Intakenext100.P47.COLUR.allowed

For finite enumerated types A,BA,BA,B, let RRR consist of N>0N>0N>0, nonnegative weights wiw_iwi​ summing to 111, and unitary matrices UiU_iUi​ on AAA and ViV_iVi​ on BBB. This defines a predicate depending on one of four class labels: coordinated\mathrm{coordinated}coordinated is always allowed; alice\mathrm{alice}alice is allowed exactly when every ViV_iVi​ is the identity; bob\mathrm{bob}bob is allowed exactly when every UiU_iUi​ is the identity; and independent\mathrm{independent}independent is allowed exactly when there exist positive natural numbers L,ML,ML,M, nonnegative normalized weight families (pj)j<L(p_j)_{j<L}(pj​)j<L​, (qk)k<M(q_k)_{k<M}(qk​)k<M​, unitary families (Sj)j<L(S_j)_{j<L}(Sj​)j<L​ on AAA, (Tk)k<M(T_k)_{k<M}(Tk​)k<M​ on BBB, and a bijection e:{0,…,N−1}→{0,…,L−1}×{0,…,M−1}e:\{0,\ldots,N-1\}\to\{0,\ldots,L-1\}\times\{0,\ldots,M-1\}e:{0,…,N−1}→{0,…,L−1}×{0,…,M−1} such that, whenever e(i)=(j,k)e(i)=(j,k)e(i)=(j,k),

wi=pjqk,Ui=Sj,Vi=Tk.w_i=p_jq_k,\qquad U_i=S_j,\qquad V_i=T_k.wi​=pj​qk​,Ui​=Sj​,Vi​=Tk​.

These conditions apply to every index, including indices of zero weight; A,BA,BA,B may be empty.

QAlgorithms.Papers.Independent.Intakenext100.P47.COLUR.cost

For finite enumerated types A,BA,BA,B, let RRR have N>0N>0N>0, nonnegative normalized weights wiw_iwi​, and unitary families Ui,ViU_i,V_iUi​,Vi​, and let ρ\rhoρ be any complex matrix on A×BA\times BA×B. Set ΦR(X)=∑iwi(Ui⊗Vi)X(Ui⊗Vi)†\Phi_R(X)=\sum_iw_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerΦR​(X)=∑i​wi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†. This defines three real costs: the size\mathrm{size}size cost is log⁡2N\log_2Nlog2​N; the entropy\mathrm{entropy}entropy cost is −∑iwilog⁡2wi-\sum_iw_i\log_2w_i−∑i​wi​log2​wi​; and the exchange\mathrm{exchange}exchange cost is S(χ)S(\chi)S(χ), constructed as follows. Write H=A×BH=A\times BH=A×B, choose the finite-enumeration bijection e:H→{0,…,∣H∣−1}e:H\to\{0,\ldots,|H|-1\}e:H→{0,…,∣H∣−1}, and put ρfin(i,j)=ρ(e−1i,e−1j)\rho_{\mathrm{fin}}(i,j)=\rho(e^{-1}i,e^{-1}j)ρfin​(i,j)=ρ(e−1i,e−1j). Define

ψ(a,b)=[cfc⁡(⋅,ρfin)]e(b),e(a),χ(a,u),(b,v)=[ΦR ⁣((ψ(a,c)ψ(b,d)‾)c,d∈H)]u,v,\psi(a,b)=\bigl[\operatorname{cfc}(\sqrt{\cdot},\rho_{\mathrm{fin}})\bigr]_{e(b),e(a)},\qquad \chi_{(a,u),(b,v)} =\left[\Phi_R\!\left((\psi(a,c)\overline{\psi(b,d)})_{c,d\in H}\right)\right]_{u,v},ψ(a,b)=[cfc(⋅​,ρfin​)]e(b),e(a)​,χ(a,u),(b,v)​=[ΦR​((ψ(a,c)ψ(b,d)​)c,d∈H​)]u,v​,

where 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)=−Retrcfc(x↦xlog2​x,X) and cfc⁡\operatorname{cfc}cfc is continuous functional calculus. Zero weights contribute zero under the total logarithm convention. No density-matrix assumption is made on ρ\rhoρ, and A,BA,BA,B may be empty.

QAlgorithms.Papers.Independent.Intakenext100.P47.COLUR

For types A,BA,BA,B, each equipped with a finite enumeration, a value of this structure consists of a natural number N>0N>0N>0, real weights wi≥0w_i\ge0wi​≥0 for 0≤i<N0\le i<N0≤i<N with ∑iwi=1\sum_iw_i=1∑i​wi​=1, and two families of complex unitary matrices: UiU_iUi​ indexed by AAA, and ViV_iVi​ indexed by BBB. Both families use the same index and weights. Zero weights and repeated matrices are permitted, and neither AAA nor BBB is required to be nonempty.

QAlgorithms.Papers.Independent.Intakenext100.P47.COLUR.operation

For finite enumerated types A,BA,BA,B and a structure RRR consisting of N>0N>0N>0, weights wi≥0w_i\ge0wi​≥0 summing to 111, and unitary matrices UiU_iUi​ on AAA and ViV_iVi​ on BBB, this defines the function on all complex matrices indexed by A×BA\times BA×B given by

ΦR(ρ)=∑i=0N−1wi(Ui⊗Vi)ρ(Ui⊗Vi)†,(Ui⊗Vi)(a,b),(a′,b′)=(Ui)a,a′(Vi)b,b′.\Phi_R(\rho)=\sum_{i=0}^{N-1}w_i(U_i\otimes V_i)\rho(U_i\otimes V_i)^\dagger, \qquad (U_i\otimes V_i)_{(a,b),(a',b')}=(U_i)_{a,a'}(V_i)_{b,b'}.ΦR​(ρ)=i=0∑N−1​wi​(Ui​⊗Vi​)ρ(Ui​⊗Vi​)†,(Ui​⊗Vi​)(a,b),(a′,b′)​=(Ui​)a,a′​(Vi​)b,b′​.

Here †\dagger† denotes conjugate transpose. No positivity or normalization condition is imposed on the argument ρ\rhoρ, and the finite types may be empty.

QAlgorithms.Papers.Independent.Intakenext100.P47.Decorrelates

For finite enumerated types A,BA,BA,B, any complex matrix XXX indexed by A×BA\times BA×B, and any real ε\varepsilonε, this predicate means that there exist matrices aaa on AAA and bbb on BBB, both positive semidefinite with trace exactly 111, such that

∥X−a⊗b∥1≤ε,∥M∥1=Re⁡tr⁡cfc⁡(⋅,M†M).\|X-a\otimes b\|_1\le\varepsilon, \qquad \|M\|_1=\operatorname{Re}\operatorname{tr}\operatorname{cfc}(\sqrt{\cdot},M^\dagger M).∥X−a⊗b∥1​≤ε,∥M∥1​=Retrcfc(⋅​,M†M).

No density-matrix condition is imposed on XXX, and the product factors need not equal its marginals. Negative ε\varepsilonε cannot satisfy the predicate; if either finite type is empty, the required trace-one factor does not exist.

QAlgorithms.Papers.Independent.Intakenext100.P47.Disentangles

For nonempty finite enumerated types A,BA,BA,B, any complex matrix XXX indexed by A×BA\times BA×B, and any real ε\varepsilonε, this predicate means that there exist a natural number qqq, real weights wj≥0w_j\ge0wj​≥0 summing to 111, and positive semidefinite trace-one matrices aja_jaj​ on AAA and bjb_jbj​ on BBB, such that

∥X−∑j=0q−1wj(aj⊗bj)∥1≤ε,∥M∥1=Re⁡tr⁡cfc⁡(⋅,M†M).\left\|X-\sum_{j=0}^{q-1}w_j(a_j\otimes b_j)\right\|_1\le\varepsilon, \qquad \|M\|_1=\operatorname{Re}\operatorname{tr}\operatorname{cfc}(\sqrt{\cdot},M^\dagger M).​X−j=0∑q−1​wj​(aj​⊗bj​)​1​≤ε,∥M∥1​=Retrcfc(⋅​,M†M).

The weight normalization excludes q=0q=0q=0, but individual weights may be zero. No density-matrix condition is imposed on XXX, and negative ε\varepsilonε cannot satisfy the predicate.

QAlgorithms.Papers.Independent.Intakenext100.P47.LocalNoise

For any type AAA equipped with a finite enumeration, a value of this structure consists of a natural number N>0N>0N>0, real weights wi≥0w_i\ge0wi​≥0 for 0≤i<N0\le i<N0≤i<N satisfying ∑iwi=1\sum_i w_i=1∑i​wi​=1, and an AAA-indexed complex unitary matrix UiU_iUi​ for each iii. Zero weights and repeated unitary matrices are permitted. The type AAA is not required to be nonempty.

QAlgorithms.Papers.Independent.Intakenext100.P47.MultiCopies

For any natural number ppp, dimension function d:{0,…,p−1}→Nd:\{0,\ldots,p-1\}\to\mathbb Nd:{0,…,p−1}→N, natural number nnn, and party index i<pi<pi<p, this is an abbreviation for the type of functions

{0,…,n−1}⟶{0,…,di−1},\{0,\ldots,n-1\}\longrightarrow\{0,\ldots,d_i-1\},{0,…,n−1}⟶{0,…,di​−1},

that is, length-nnn strings of basis labels for party iii. No positivity assumption is imposed on did_idi​ or nnn. For n=0n=0n=0 this type has exactly one element, even if di=0d_i=0di​=0; if n>0n>0n>0 and di=0d_i=0di​=0, it is empty. When p=0p=0p=0, there is no party index iii.

QAlgorithms.Papers.Independent.Intakenext100.P47.MultiDecorrelates

For any natural number ppp, finite types DiD_iDi​ for i=0,…,p−1i=0,\ldots,p-1i=0,…,p−1, arbitrary complex matrix XXX on H=∏iDi\mathcal H=\prod_iD_iH=∏i​Di​, and real number ε\varepsilonε, this predicate means that there exist matrices σi\sigma_iσi​ on the respective DiD_iDi​, each positive semidefinite with complex trace exactly 111, such that

∥X−Σ∥1≤ε,Σxy=∏i=0p−1(σi)xiyi,∥M∥1=Re⁡tr⁡ ⁣(cfc⁡[⋅](M†M)).\left\|X-\Sigma\right\|_1\le\varepsilon, \qquad \Sigma_{xy}=\prod_{i=0}^{p-1}(\sigma_i)_{x_i y_i}, \qquad \|M\|_1=\operatorname{Re}\operatorname{tr}\!\left(\operatorname{cfc}[\sqrt{\cdot}](M^\dagger M)\right).∥X−Σ∥1​≤ε,Σxy​=i=0∏p−1​(σi​)xi​yi​​,∥M∥1​=Retr(cfc[⋅​](M†M)).

No density-matrix assumption is imposed on XXX. A negative ε\varepsilonε cannot satisfy this inequality. If any DiD_iDi​ is empty, its required trace-one matrix cannot exist. When p=0p=0p=0, there are no local matrices to choose, the configuration space is a singleton, and Σ\SigmaΣ is its 1×11\times11×1 identity matrix.

QAlgorithms.Papers.Independent.Intakenext100.P47.MultiNoise.cost

For any natural number ppp, finite types DiD_iDi​ indexed by i=0,…,p−1i=0,\ldots,p-1i=0,…,p−1, and matrix ρ\rhoρ on the configuration space H=∏iDi\mathcal H=\prod_i D_iH=∏i​Di​, let RRR consist of a positive integer NNN, nonnegative real weights wtw_twt​ summing to 111, and a unitary matrix Ut,iU_{t,i}Ut,i​ on each DiD_iDi​, for t=0,…,N−1t=0,\ldots,N-1t=0,…,N−1. Set Vt(x,y)=∏iUt,i(xi,yi)V_t(x,y)=\prod_i U_{t,i}(x_i,y_i)Vt​(x,y)=∏i​Ut,i​(xi​,yi​) and ΦR(X)=∑twtVtXVt†\Phi_R(X)=\sum_t w_tV_tXV_t^\daggerΦR​(X)=∑t​wt​Vt​XVt†​. The cost is the following function of the selected cost kind:

cost⁡R(ρ)={log⁡2N,size,−∑twtlog⁡2wt,entropy,S ⁣((id⁡H⊗ΦR)(∣ψρ⟩⟨ψρ∣)),exchange.\operatorname{cost}_R(\rho)= \begin{cases} \log_2N,&\text{size},\\ -\sum_t w_t\log_2w_t,&\text{entropy},\\ S\!\left((\operatorname{id}_{\mathcal H}\otimes\Phi_R)(|\psi_\rho\rangle\langle\psi_\rho|)\right),&\text{exchange}. \end{cases}costR​(ρ)=⎩⎨⎧​log2​N,−∑t​wt​log2​wt​,S((idH​⊗ΦR​)(∣ψρ​⟩⟨ψρ​∣)),​size,entropy,exchange.​

Here 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)), using the formal functional calculus. To define ψρ\psi_\rhoψρ​ literally, take the finite enumeration e:H≅{0,…,∣H∣−1}e:\mathcal H\cong\{0,\ldots,|\mathcal H|-1\}e:H≅{0,…,∣H∣−1}, put ρ~ab=ρe−1(a),e−1(b)\widetilde\rho_{ab}=\rho_{e^{-1}(a),e^{-1}(b)}ρ​ab​=ρe−1(a),e−1(b)​, and set ψρ(x,y)=cfc⁡[⋅](ρ~)e(y),e(x)\psi_\rho(x,y)=\operatorname{cfc}[\sqrt{\cdot}](\widetilde\rho)_{e(y),e(x)}ψρ​(x,y)=cfc[⋅​](ρ​)e(y),e(x)​. No positivity or normalization of ρ\rhoρ is required. Empty DiD_iDi​ and p=0p=0p=0 are allowed; when p=0p=0p=0, the configuration space has one element and each product defining VtV_tVt​ is 111.

QAlgorithms.Papers.Independent.Intakenext100.P47.MultiNoise.independent

For any natural number ppp, family of finite types DiD_iDi​, and noise data RRR with positive count NNN, nonnegative weights wjw_jwj​ summing to one, and local unitaries Uj,iU_{j,i}Uj,i​, this property means that there exist, for every party i<pi<pi<p, local noise data with a positive natural count NiN_iNi​, nonnegative real weights vi,rv_{i,r}vi,r​ summing to one, and unitaries Vi,rV_{i,r}Vi,r​ on DiD_iDi​, together with a bijection

e:{0,…,N−1}⟶∏i=0p−1{0,…,Ni−1},e:\{0,\ldots,N-1\}\longrightarrow \prod_{i=0}^{p-1}\{0,\ldots,N_i-1\},e:{0,…,N−1}⟶i=0∏p−1​{0,…,Ni​−1},

such that, for every j<Nj<Nj<N and every i<pi<pi<p,

wj=∏i′=0p−1vi′, e(j)i′,Uj,i=Vi, e(j)i.w_j=\prod_{i'=0}^{p-1}v_{i',\,e(j)_{i'}}, \qquad U_{j,i}=V_{i,\,e(j)_i}.wj​=i′=0∏p−1​vi′,e(j)i′​​,Uj,i​=Vi,e(j)i​​.

These are equalities of the listed weights and unitary matrices under the bijection, including entries of weight zero; distinct indices need not specify distinct unitaries. The local types may be empty. When p=0p=0p=0, the product index set is a singleton, so the property requires N=1N=1N=1 and its sole weight to equal 111.

QAlgorithms.Papers.Independent.Intakenext100.P47.MultiNoise

For any natural number ppp and family of finite types DiD_iDi​, i<pi<pi<p, this structure consists of a natural count N>0N>0N>0, real weights wj≥0w_j\ge0wj​≥0 for j<Nj<Nj<N satisfying ∑j<Nwj=1\sum_{j<N}w_j=1∑j<N​wj​=1, and, for every j<Nj<Nj<N and i<pi<pi<p, a unitary complex matrix Uj,iU_{j,i}Uj,i​ indexed by DiD_iDi​. The finite local types need not be nonempty. Zero weights and repeated choices of unitaries are allowed. The case p=0p=0p=0 is included: it retains the positive count and probability weights, while requiring no local-unitary data.

QAlgorithms.Papers.Independent.Intakenext100.P47.MultiNoise.operation

For any natural number ppp, family of finite types DiD_iDi​, and noise data RRR with positive count NNN, weights wj≥0w_j\ge0wj​≥0 summing to one, and local unitaries Uj,iU_{j,i}Uj,i​ on DiD_iDi​, this defines a map from complex matrices on ∏i<pDi\prod_{i<p}D_i∏i<p​Di​ to matrices on the same type by

R(ρ)=∑j=0N−1wj UjρUj†,(Uj)xy=∏i=0p−1(Uj,i)xiyi.\mathcal R(\rho)=\sum_{j=0}^{N-1}w_j\,U_j\rho U_j^\dagger, \qquad (U_j)_{xy}=\prod_{i=0}^{p-1}(U_{j,i})_{x_i y_i}.R(ρ)=j=0∑N−1​wj​Uj​ρUj†​,(Uj​)xy​=i=0∏p−1​(Uj,i​)xi​yi​​.

The input ρ\rhoρ is arbitrary; no density-matrix hypothesis is imposed. Zero weights, repeated unitary choices, and empty local types are allowed. When p=0p=0p=0, the configuration space is a singleton, every UjU_jUj​ has sole entry 111, and this operation is the identity on its scalar matrices.

QAlgorithms.Papers.Independent.Intakenext100.P47.MultiNoise.productUnitary

For any natural number ppp, family of finite types DiD_iDi​, and noise data RRR consisting of a positive count NNN, nonnegative weights summing to one, and local unitaries Uj,iU_{j,i}Uj,i​ on DiD_iDi​, this defines, for every j<Nj<Nj<N, a matrix on configurations x∈∏i<pDix\in\prod_{i<p}D_ix∈∏i<p​Di​ by

(Uj)xy=∏i=0p−1(Uj,i)xiyi.(U_j)_{xy}=\prod_{i=0}^{p-1}(U_{j,i})_{x_i y_i}.(Uj​)xy​=i=0∏p−1​(Uj,i​)xi​yi​​.

The weights are part of the supplied data but do not enter this definition. Local types may be empty. For p=0p=0p=0, the configuration type is a singleton and the matrix’s sole entry is the empty product 111.

QAlgorithms.Papers.Independent.Intakenext100.P47.NoiseClass

This defines a type with exactly four distinct values, named coordinated\mathrm{coordinated}coordinated, alice\mathrm{alice}alice, bob\mathrm{bob}bob, and independent\mathrm{independent}independent, together with decidable equality. The declaration itself imposes no mathematical conditions associated with these names.

QAlgorithms.Papers.Independent.Intakenext100.P47.NoiseCost

This defines a type with exactly three distinct values, named size\mathrm{size}size, entropy\mathrm{entropy}entropy, and exchange\mathrm{exchange}exchange, together with decidable equality. No numerical cost is assigned by this declaration itself.

QAlgorithms.Papers.Independent.Intakenext100.P47.PublicProtocol.average

For all natural dimensions a,ba,ba,b, every protocol tree PPP of dimensions a,ba,ba,b, and every complex matrix ρ\rhoρ on {0,…,a−1}×{0,…,b−1}\{0,\ldots,a-1\}\times\{0,\ldots,b-1\}{0,…,a−1}×{0,…,b−1}, this defines a real number recursively. At a stop node its value is

I(ρ)=S(Tr⁡Bρ)+S(Tr⁡Aρ)−S(ρ),\mathcal I(\rho)=S(\operatorname{Tr}_B\rho)+S(\operatorname{Tr}_A\rho)-S(\rho),I(ρ)=S(TrB​ρ)+S(TrA​ρ)−S(ρ),

where S(X)=−Re⁡tr⁡[(x↦xlog⁡2x)(X)]S(X)=-\operatorname{Re}\operatorname{tr}[(x\mapsto x\log_2x)(X)]S(X)=−Retr[(x↦xlog2​x)(X)] uses continuous functional calculus. At an Alice instrument node, whose finite rectangular Kraus matrices KxjK_{xj}Kxj​ satisfy ∑x,jKxj†Kxj=Ia\sum_{x,j}K_{xj}^\dagger K_{xj}=I_a∑x,j​Kxj†​Kxj​=Ia​, form

ωx=∑j(Kxj⊗Ib)ρ(Kxj⊗Ib)†,px=Re⁡tr⁡ωx.\omega_x=\sum_j(K_{xj}\otimes I_b)\rho(K_{xj}\otimes I_b)^\dagger, \qquad p_x=\operatorname{Re}\operatorname{tr}\omega_x.ωx​=j∑​(Kxj​⊗Ib​)ρ(Kxj​⊗Ib​)†,px​=Retrωx​.

Its value is ∑xpx Px.average(ωx/px)\sum_x p_x\,P_x.\mathrm{average}(\omega_x/p_x)∑x​px​Px​.average(ωx​/px​), with each summand defined instead to be zero whenever px≤0p_x\le0px​≤0. At a Bob node the same rule uses ωx=∑j(Ia⊗Kxj)ρ(Ia⊗Kxj)†\omega_x=\sum_j(I_a\otimes K_{xj})\rho(I_a\otimes K_{xj})^\daggerωx​=∑j​(Ia​⊗Kxj​)ρ(Ia​⊗Kxj​)†. Each node has a positive output dimension and one continuation PxP_xPx​ per outcome. No positivity, Hermiticity, or trace normalization is required of the input matrix, and zero initial dimensions are included; in particular, branches of zero or negative real trace contribute zero without evaluating a normalized continuation.

QAlgorithms.Papers.Independent.Intakenext100.P47.PublicProtocol

This defines a family of inductively generated protocol trees indexed by natural numbers a,ba,ba,b, representing local matrix dimensions. A protocol of dimensions a,ba,ba,b is either a stop node, an Alice node, or a Bob node. An Alice node specifies a positive output dimension ccc, a natural number rrr, an instrument with outcomes x∈{0,…,r}x\in\{0,\ldots,r\}x∈{0,…,r}, and a continuation of dimensions c,bc,bc,b for every outcome. The instrument specifies a natural Kraus count hhh and matrices Kxj∈Cc×aK_{xj}\in\mathbb C^{c\times a}Kxj​∈Cc×a, j<hj<hj<h, satisfying ∑x∑j<hKxj†Kxj=Ia\sum_x\sum_{j<h}K_{xj}^\dagger K_{xj}=I_a∑x​∑j<h​Kxj†​Kxj​=Ia​. A Bob node analogously specifies a positive output dimension ddd, a natural number rrr, matrices Kxj∈Cd×bK_{xj}\in\mathbb C^{d\times b}Kxj​∈Cd×b satisfying the same completeness equation with IbI_bIb​, and a continuation of dimensions a,da,da,d for each outcome. The trees are finite, with no prescribed common depth bound. Every instrument node has at least one outcome, although its Kraus count may be zero if the completeness equation permits it. Initial dimensions aaa or bbb may be zero; a stop node is available for every pair of dimensions.

QAlgorithms.Papers.Independent.Intakenext100.P47.blockIndex

For natural numbers k,nk,nk,n, an index t∈{0,…,n−1}t\in\{0,\ldots,n-1\}t∈{0,…,n−1}, and an index s∈{0,…,k−1}s\in\{0,\ldots,k-1\}s∈{0,…,k−1}, this defines the index in {0,…,kn−1}\{0,\ldots,kn-1\}{0,…,kn−1} with numerical value

blockIndex⁡(t,s)=kt+s.\operatorname{blockIndex}(t,s)=kt+s.blockIndex(t,s)=kt+s.

If k=0k=0k=0 or n=0n=0n=0, there is no pair of input indices.

QAlgorithms.Papers.Independent.Intakenext100.P47.discountedCosts

For any finite types A,BA,BA,B, possibly empty, and any complex matrix ρ\rhoρ on A×BA\times BA×B, this defines the set of real numbers

{E(ρ⊗γ)−E(γ):c,d∈N, c>0, d>0, γ is positive semidefinite on {0,…,c−1}×{0,…,d−1}, Tr⁡γ=1},\left\{\mathcal E(\rho\otimes\gamma)-\mathcal E(\gamma): c,d\in\mathbb N,\ c>0,\ d>0,\ \gamma\text{ is positive semidefinite on }\{0,\ldots,c-1\}\times\{0,\ldots,d-1\}, \ \operatorname{Tr}\gamma=1\right\},{E(ρ⊗γ)−E(γ):c,d∈N, c>0, d>0, γ is positive semidefinite on {0,…,c−1}×{0,…,d−1}, Trγ=1},

where ρ⊗γ\rho\otimes\gammaρ⊗γ is regrouped across the two parties, with entry ρ(a,b),(a′,b′)γ(u,v),(u′,v′)\rho_{(a,b),(a',b')}\gamma_{(u,v),(u',v')}ρ(a,b),(a′,b′)​γ(u,v),(u′,v′)​. For a bipartite matrix XXX, the real-valued expression E(X)\mathcal E(X)E(X) means

E(X)=sup⁡ε>0lim sup⁡k→∞inf⁡Ck+1,ε(X)k+1.\mathcal E(X)= \sup_{\varepsilon>0}\limsup_{k\to\infty} \frac{\inf C_{k+1,\varepsilon}(X)}{k+1}.E(X)=ε>0sup​k→∞limsup​k+1infCk+1,ε​(X)​.

Here XnX_nXn​ has entries (Xn)(a,b),(a′,b′)=∏t=0n−1X(at,bt),(at′,bt′)(X_n)_{(a,b),(a',b')}=\prod_{t=0}^{n-1}X_{(a_t,b_t),(a'_t,b'_t)}(Xn​)(a,b),(a′,b′)​=∏t=0n−1​X(at​,bt​),(at′​,bt′​)​, and Cn,ε(X)C_{n,\varepsilon}(X)Cn,ε​(X) consists of log⁡2r\log_2 rlog2​r for positive finite integers rrr and operations R(Y)=∑i=0r−1wi(Ui⊗Vi)Y(Ui⊗Vi)†\mathcal R(Y)=\sum_{i=0}^{r-1}w_i(U_i\otimes V_i)Y(U_i\otimes V_i)^\daggerR(Y)=∑i=0r−1​wi​(Ui​⊗Vi​)Y(Ui​⊗Vi​)†, with nonnegative weights summing to 111 and local unitaries Ui,ViU_i,V_iUi​,Vi​, whose output on XnX_nXn​ is within trace norm ε\varepsilonε of some product of density matrices. No independence restriction is placed on the paired local choices. The trace norm is ∥M∥1=Re⁡Tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{Tr}\sqrt{M^\dagger M}∥M∥1​=ReTrM†M​. These are the total real infimum and supremum operations, which return 000 for empty sets or, respectively, sets unbounded below or above; this definition assumes no density-matrix condition on ρ\rhoρ and asserts no attainment.

QAlgorithms.Papers.Independent.Intakenext100.P47.disentanglingSizes

For any finite nonempty types A,BA,BA,B, any complex matrix ρ\rhoρ on A×BA\times BA×B, any natural number nnn, and any real ε\varepsilonε, this defines the set of natural numbers NNN for which there exist N>0N>0N>0 pairs of local unitaries UiU_iUi​ on AnA^nAn and ViV_iVi​ on BnB^nBn, with nonnegative weights pip_ipi​ summing to 111, such that ∥T(Xn)−σ∥1≤ε\|T(X_n)-\sigma\|_1\le\varepsilon∥T(Xn​)−σ∥1​≤ε, where T(X)=∑i<Npi(Ui⊗Vi)X(Ui⊗Vi)†T(X)=\sum_{i<N}p_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerT(X)=∑i<N​pi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†, (Xn)(a,b),(a′,b′)=∏t<nρ(at,bt),(at′,bt′)(X_n)_{(a,b),(a',b')}=\prod_{t<n}\rho_{(a_t,b_t),(a'_t,b'_t)}(Xn​)(a,b),(a′,b′)​=∏t<n​ρ(at​,bt​),(at′​,bt′​)​, and ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​. The matrix σ\sigmaσ must have a finite representation σ=∑j<qwjaj⊗bj\sigma=\sum_{j<q}w_j a_j\otimes b_jσ=∑j<q​wj​aj​⊗bj​, with wj≥0w_j\ge0wj​≥0, ∑jwj=1\sum_jw_j=1∑j​wj​=1, and every aj,bja_j,b_jaj​,bj​ positive semidefinite with trace 111. There is no restriction on the noise list beyond those stated, no assumption that ρ\rhoρ is a density matrix, and zero weights are allowed. The set never contains 000, is empty for ε<0\varepsilon<0ε<0, and includes the case n=0n=0n=0, when XnX_nXn​ is the scalar matrix 111.

QAlgorithms.Papers.Independent.Intakenext100.P47.entanglementBlockRate

For any finite nonempty types A,BA,BA,B, any complex matrix ρ\rhoρ on A×BA\times BA×B, any real ε\varepsilonε, and any natural number kkk, put n=k+1n=k+1n=k+1. This defines log⁡2Nmin⁡/n\log_2N_{\min}/nlog2​Nmin​/n, where Nmin⁡N_{\min}Nmin​ is the least positive integer NNN for which there are local unitaries Ui,ViU_i,V_iUi​,Vi​ and nonnegative weights pip_ipi​ summing to 111 such that ∥T(Xn)−σ∥1≤ε\|T(X_n)-\sigma\|_1\le\varepsilon∥T(Xn​)−σ∥1​≤ε, with T(X)=∑i<Npi(Ui⊗Vi)X(Ui⊗Vi)†T(X)=\sum_{i<N}p_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerT(X)=∑i<N​pi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†, (Xn)(a,b),(a′,b′)=∏t<nρ(at,bt),(at′,bt′)(X_n)_{(a,b),(a',b')}=\prod_{t<n}\rho_{(a_t,b_t),(a'_t,b'_t)}(Xn​)(a,b),(a′,b′)​=∏t<n​ρ(at​,bt​),(at′​,bt′​)​, and σ\sigmaσ a finite convex combination of products of positive semidefinite, trace-one matrices on AnA^nAn and BnB^nBn. The trace norm is ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​, and zero noise weights are allowed. If no such list exists, the natural-number infimum defining Nmin⁡N_{\min}Nmin​ is 000, and the real logarithm convention log⁡20=0\log_2 0=0log2​0=0 makes the defined rate 000; this includes negative ε\varepsilonε. No density assumption on ρ\rhoρ is imposed, and the block length is always positive, including at k=0k=0k=0.

QAlgorithms.Papers.Independent.Intakenext100.P47.entanglementErasure

For any finite nonempty types A,BA,BA,B, any complex matrix ρ\rhoρ on A×BA\times BA×B, and any Boolean ppp, this defines

sup⁡ε>0{lim sup⁡k→∞log⁡2Nmin⁡(k+1,ε)k+1,p=true,lim inf⁡k→∞log⁡2Nmin⁡(k+1,ε)k+1,p=false.\sup_{\varepsilon>0} \begin{cases} \displaystyle\limsup_{k\to\infty}\frac{\log_2N_{\min}(k+1,\varepsilon)}{k+1},&p=\mathrm{true},\\[4pt] \displaystyle\liminf_{k\to\infty}\frac{\log_2N_{\min}(k+1,\varepsilon)}{k+1},&p=\mathrm{false}. \end{cases}ε>0sup​⎩⎨⎧​k→∞limsup​k+1log2​Nmin​(k+1,ε)​,k→∞liminf​k+1log2​Nmin​(k+1,ε)​,​p=true,p=false.​

Here Nmin⁡(n,ε)N_{\min}(n,\varepsilon)Nmin​(n,ε) is the least positive length NNN of a probability-weighted list of pairs of local unitaries producing T(X)=∑i<Npi(Ui⊗Vi)X(Ui⊗Vi)†T(X)=\sum_{i<N}p_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerT(X)=∑i<N​pi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†, with pi≥0p_i\ge0pi​≥0 and ∑ipi=1\sum_ip_i=1∑i​pi​=1, for which T(Xn)T(X_n)T(Xn​) is within trace norm ε\varepsilonε of a finite convex combination of products of positive semidefinite, trace-one matrices on AnA^nAn and BnB^nBn. The entries of XnX_nXn​ are ∏t<nρ(at,bt),(at′,bt′)\prod_{t<n}\rho_{(a_t,b_t),(a'_t,b'_t)}∏t<n​ρ(at​,bt​),(at′​,bt′​)​, and ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​. If no admissible list exists, Nmin⁡N_{\min}Nmin​ is defined to be 000, and log⁡20=0\log_2 0=0log2​0=0. Zero weights are permitted, and ρ\rhoρ is not required to be positive or normalized. The supremum and sequence limits are totalized real-valued operations, with no boundedness or convergence hypotheses, and the supremum ranges over every positive tolerance.

QAlgorithms.Papers.Independent.Intakenext100.P47.erasureEta

For every real number xxx, this defines

η(x)={−xlog⁡2x,x≤e−1,e−1log⁡2e,x>e−1.\eta(x)= \begin{cases} -x\log_2x,&x\le e^{-1},\\ e^{-1}\log_2e,&x>e^{-1}. \end{cases}η(x)={−xlog2​x,e−1log2​e,​x≤e−1,x>e−1.​

The boundary x=e−1x=e^{-1}x=e−1 uses the first branch. There is no nonnegativity assumption on xxx: the real logarithm is total, with log⁡20=0\log_2 0=0log2​0=0 and log⁡2x=log⁡2∣x∣\log_2x=\log_2|x|log2​x=log2​∣x∣ for negative xxx, so in particular η(0)=0\eta(0)=0η(0)=0.

QAlgorithms.Papers.Independent.Intakenext100.P47.logDimension

For any types A,BA,BA,B, each equipped with a finite enumeration, this defines the real number

log⁡2(∣A∣ ∣B∣).\log_2\bigl(|A|\,|B|\bigr).log2​(∣A∣∣B∣).

Neither type is required to be nonempty. If either is empty, the product of cardinalities is zero and the total real logarithm convention makes the value 000.

QAlgorithms.Papers.Independent.Intakenext100.P47.minimumDisentanglingSize

For any finite nonempty types A,BA,BA,B, any complex matrix ρ\rhoρ on A×BA\times BA×B, any natural number nnn, and any real ε\varepsilonε, this defines the infimum in N\mathbb NN of all positive list lengths NNN for which a map T(X)=∑i<Npi(Ui⊗Vi)X(Ui⊗Vi)†T(X)=\sum_{i<N}p_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerT(X)=∑i<N​pi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†, with local unitaries Ui,ViU_i,V_iUi​,Vi​ and nonnegative weights summing to 111, sends the matrix XnX_nXn​, whose entries are ∏t<nρ(at,bt),(at′,bt′)\prod_{t<n}\rho_{(a_t,b_t),(a'_t,b'_t)}∏t<n​ρ(at​,bt​),(at′​,bt′​)​, within trace norm ε\varepsilonε of some finite convex combination σ=∑jwjaj⊗bj\sigma=\sum_jw_j a_j\otimes b_jσ=∑j​wj​aj​⊗bj​ of products of positive semidefinite, trace-one matrices. Here the trace norm is ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​. Thus it is the least admissible positive list length when such a length exists, and is 000 when no such length exists, including whenever ε<0\varepsilon<0ε<0. No normalization or positivity of ρ\rhoρ is assumed, zero weights in the noise list are permitted, and n=0n=0n=0 uses the empty-product matrix X0=1X_0=1X0​=1.

QAlgorithms.Papers.Independent.Intakenext100.P47.multiBlockRate

For any natural number ppp, natural dimensions did_idi​, arbitrary complex matrix ρ\rhoρ on X=∏i{0,…,di−1}\mathcal X=\prod_i\{0,\ldots,d_i-1\}X=∏i​{0,…,di​−1}, real ε\varepsilonε, Boolean independence flag bbb, cost kind ccc, and natural number kkk, this definition gives

inf⁡Ck+1(ρ,ε,b,c)k+1.\frac{\inf\mathcal C_{k+1}(\rho,\varepsilon,b,c)}{k+1}.k+1infCk+1​(ρ,ε,b,c)​.

To define Cn\mathcal C_nCn​, put Hi={0,…,di−1}{0,…,n−1}\mathcal H_i=\{0,\ldots,d_i-1\}^{\{0,\ldots,n-1\}}Hi​={0,…,di​−1}{0,…,n−1} and (ρ[n])xy=∏t<nρ(xi(t))i,(yi(t))i(\rho^{[n]})_{xy}=\prod_{t<n}\rho_{(x_i(t))_i,(y_i(t))_i}(ρ[n])xy​=∏t<n​ρ(xi​(t))i​,(yi​(t))i​​. Its elements are costs of maps Φ(X)=∑a<NwaVaXVa†\Phi(X)=\sum_{a<N}w_aV_aXV_a^\daggerΦ(X)=∑a<N​wa​Va​XVa†​, where N>0N>0N>0, wa≥0w_a\ge0wa​≥0, ∑awa=1\sum_aw_a=1∑a​wa​=1, and Va=⨂iUa,iV_a=\bigotimes_iU_{a,i}Va​=⨂i​Ua,i​ with local unitaries Ua,iU_{a,i}Ua,i​ on Hi\mathcal H_iHi​, such that ∥Φ(ρ[n])−⨂iσi∥1≤ε\|\Phi(\rho^{[n]})-\bigotimes_i\sigma_i\|_1\le\varepsilon∥Φ(ρ[n])−⨂i​σi​∥1​≤ε for some positive semidefinite trace-one σi\sigma_iσi​. If b=trueb=\mathrm{true}b=true, the choices must be indexed, through a bijection, by a product of positive-sized local choice sets, with weights equal to products of local probability weights and each Ua,iU_{a,i}Ua,i​ depending only on the corresponding local choice; if b=falseb=\mathrm{false}b=false, no such restriction applies. The cost is respectively log⁡2N\log_2Nlog2​N, −∑awalog⁡2wa-\sum_aw_a\log_2w_a−∑a​wa​log2​wa​, or S((id⁡⊗Φ)(∣ψρ[n]⟩⟨ψρ[n]∣))S((\operatorname{id}\otimes\Phi)(|\psi_{\rho^{[n]}}\rangle\langle\psi_{\rho^{[n]}}|))S((id⊗Φ)(∣ψρ[n]​⟩⟨ψρ[n]​∣)) for size, entropy, or exchange, where S(M)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](M))S(M)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](M))S(M)=−Retr(cfc[x↦xlog2​x](M)), ψX\psi_XψX​ uses the transposed entries of cfc⁡[⋅](X)\operatorname{cfc}[\sqrt{\cdot}](X)cfc[⋅​](X) in the finite enumeration used by the definition, and ∥M∥1=Re⁡tr⁡(cfc⁡[⋅](M†M))\|M\|_1=\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[\sqrt{\cdot}](M^\dagger M))∥M∥1​=Retr(cfc[⋅​](M†M)). The infimum is taken in the real numbers with the total formal convention, so an empty or unbounded-below cost set has infimum 000; attainment is not required here. The divisor is always positive, including k=0k=0k=0. No density assumption on ρ\rhoρ, positivity of the did_idi​, or positivity of ppp is imposed.

QAlgorithms.Papers.Independent.Intakenext100.P47.multiCosts

For any natural number ppp, natural dimensions did_idi​, arbitrary complex matrix ρ\rhoρ on X=∏i{0,…,di−1}\mathcal X=\prod_i\{0,\ldots,d_i-1\}X=∏i​{0,…,di​−1}, natural block length nnn, real tolerance ε\varepsilonε, Boolean flag bbb, and cost kind c∈{size,entropy,exchange}c\in\{\text{size},\text{entropy},\text{exchange}\}c∈{size,entropy,exchange}, this definition is the set of real costs obtainable as follows. Give party iii the block configuration space Hi={0,…,di−1}{0,…,n−1}\mathcal H_i=\{0,\ldots,d_i-1\}^{\{0,\ldots,n-1\}}Hi​={0,…,di​−1}{0,…,n−1}, and define the block input by (ρ[n])xy=∏t=0n−1ρ(xi(t))i,(yi(t))i(\rho^{[n]})_{xy}=\prod_{t=0}^{n-1}\rho_{(x_i(t))_i,(y_i(t))_i}(ρ[n])xy​=∏t=0n−1​ρ(xi​(t))i​,(yi​(t))i​​. Choose a positive integer NNN, nonnegative weights waw_awa​ summing to 111, and local unitaries Ua,iU_{a,i}Ua,i​ on Hi\mathcal H_iHi​; these determine Va=⨂iUa,iV_a=\bigotimes_iU_{a,i}Va​=⨂i​Ua,i​ and Φ(X)=∑awaVaXVa†\Phi(X)=\sum_aw_aV_aXV_a^\daggerΦ(X)=∑a​wa​Va​XVa†​. If b=trueb=\mathrm{true}b=true, additionally require local choices with positive counts NiN_iNi​, probability weights w(i)w^{(i)}w(i), and unitaries U(i)U^{(i)}U(i), together with a bijection e:{0,…,N−1}≅∏i{0,…,Ni−1}e:\{0,\ldots,N-1\}\cong\prod_i\{0,\ldots,N_i-1\}e:{0,…,N−1}≅∏i​{0,…,Ni​−1}, such that wa=∏iwe(a)i(i)w_a=\prod_iw^{(i)}_{e(a)_i}wa​=∏i​we(a)i​(i)​ and Ua,i=Ue(a)i(i)U_{a,i}=U^{(i)}_{e(a)_i}Ua,i​=Ue(a)i​(i)​; when b=falseb=\mathrm{false}b=false, this requirement imposes no condition. Require positive semidefinite trace-one matrices σi\sigma_iσi​ on Hi\mathcal H_iHi​ satisfying

∥Φ(ρ[n])−⨂iσi∥1≤ε.\left\|\Phi(\rho^{[n]})-\bigotimes_i\sigma_i\right\|_1\le\varepsilon.​Φ(ρ[n])−i⨂​σi​​1​≤ε.

The included value is log⁡2N\log_2Nlog2​N for size, −∑awalog⁡2wa-\sum_aw_a\log_2w_a−∑a​wa​log2​wa​ for entropy, or S((id⁡⊗Φ)(∣ψρ[n]⟩⟨ψρ[n]∣))S((\operatorname{id}\otimes\Phi)(|\psi_{\rho^{[n]}}\rangle\langle\psi_{\rho^{[n]}}|))S((id⊗Φ)(∣ψρ[n]​⟩⟨ψρ[n]​∣)) for exchange. Here ∥M∥1=Re⁡tr⁡(cfc⁡[⋅](M†M))\|M\|_1=\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[\sqrt{\cdot}](M^\dagger M))∥M∥1​=Retr(cfc[⋅​](M†M)), S(M)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](M))S(M)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](M))S(M)=−Retr(cfc[x↦xlog2​x](M)), and ψX\psi_XψX​ is formed from the transposed entries of cfc⁡[⋅](X)\operatorname{cfc}[\sqrt{\cdot}](X)cfc[⋅​](X) after the finite enumeration used in the definition. No density assumption on ρ\rhoρ is required. The definition permits p=0p=0p=0, zero dimensions, and n=0n=0n=0; at n=0n=0n=0, every local block space is a singleton and every product defining the block input is 111. For ε<0\varepsilon<0ε<0, the cost set is empty.

QAlgorithms.Papers.Independent.Intakenext100.P47.multiErasure

For any natural number ppp, natural dimensions did_idi​, arbitrary complex matrix ρ\rhoρ on X=∏i{0,…,di−1}\mathcal X=\prod_i\{0,\ldots,d_i-1\}X=∏i​{0,…,di​−1}, Boolean independence flag bbb, cost kind ccc, and Boolean flag hhh, this definition is

sup⁡ε>0{lim sup⁡k→∞inf⁡Ck+1(ρ,ε,b,c)k+1,h=true,lim inf⁡k→∞inf⁡Ck+1(ρ,ε,b,c)k+1,h=false.\sup_{\varepsilon>0} \begin{cases} \displaystyle\limsup_{k\to\infty}\frac{\inf\mathcal C_{k+1}(\rho,\varepsilon,b,c)}{k+1}, &h=\mathrm{true},\\[6pt] \displaystyle\liminf_{k\to\infty}\frac{\inf\mathcal C_{k+1}(\rho,\varepsilon,b,c)}{k+1}, &h=\mathrm{false}. \end{cases}ε>0sup​⎩⎨⎧​k→∞limsup​k+1infCk+1​(ρ,ε,b,c)​,k→∞liminf​k+1infCk+1​(ρ,ε,b,c)​,​h=true,h=false.​

Here Cn\mathcal C_nCn​ contains the selected costs of finite random products of local unitaries on the spaces Hi={0,…,di−1}{0,…,n−1}\mathcal H_i=\{0,\ldots,d_i-1\}^{\{0,\ldots,n-1\}}Hi​={0,…,di​−1}{0,…,n−1}: a choice has N>0N>0N>0, weights wa≥0w_a\ge0wa​≥0 summing to 111, local unitaries Ua,iU_{a,i}Ua,i​, and map Φ(X)=∑a<Nwa(⨂iUa,i)X(⨂iUa,i)†\Phi(X)=\sum_{a<N}w_a(\bigotimes_iU_{a,i})X(\bigotimes_iU_{a,i})^\daggerΦ(X)=∑a<N​wa​(⨂i​Ua,i​)X(⨂i​Ua,i​)†. Its block input has entries (ρ[n])xy=∏t<nρ(xi(t))i,(yi(t))i(\rho^{[n]})_{xy}=\prod_{t<n}\rho_{(x_i(t))_i,(y_i(t))_i}(ρ[n])xy​=∏t<n​ρ(xi​(t))i​,(yi​(t))i​​, and its output must lie within trace norm ε\varepsilonε of ⨂iσi\bigotimes_i\sigma_i⨂i​σi​ for some positive semidefinite trace-one matrices σi\sigma_iσi​. When b=trueb=\mathrm{true}b=true, the choice set must be bijective to a product of positive-sized local choice sets, with product probability weights and each party’s unitary determined by its own choice; b=falseb=\mathrm{false}b=false adds no restriction. Size cost is log⁡2N\log_2Nlog2​N, entropy cost is −∑awalog⁡2wa-\sum_aw_a\log_2w_a−∑a​wa​log2​wa​, and exchange cost is S((id⁡⊗Φ)(∣ψρ[n]⟩⟨ψρ[n]∣))S((\operatorname{id}\otimes\Phi)(|\psi_{\rho^{[n]}}\rangle\langle\psi_{\rho^{[n]}}|))S((id⊗Φ)(∣ψρ[n]​⟩⟨ψρ[n]​∣)), where S(M)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](M))S(M)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](M))S(M)=−Retr(cfc[x↦xlog2​x](M)) and ψX\psi_XψX​ uses the transposed entries of cfc⁡[⋅](X)\operatorname{cfc}[\sqrt{\cdot}](X)cfc[⋅​](X) in the finite enumeration used by the definition. The trace norm is ∥M∥1=Re⁡tr⁡(cfc⁡[⋅](M†M))\|M\|_1=\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[\sqrt{\cdot}](M^\dagger M))∥M∥1​=Retr(cfc[⋅​](M†M)). All infima, suprema, and order limits here are real-valued formal operations; no boundedness or existence of limits is assumed, and an empty or unbounded-below cost set has infimum 000. The outer operation ranges over every positive tolerance, rather than asserting a limit as the tolerance decreases to zero. Zero dimensions and p=0p=0p=0 are permitted, and ρ\rhoρ need not be a density matrix.

QAlgorithms.Papers.Independent.Intakenext100.P47.multiInformation

For any natural number ppp, natural dimensions did_idi​, and arbitrary complex matrix ρ\rhoρ on X=∏i=0p−1{0,…,di−1}\mathcal X=\prod_{i=0}^{p-1}\{0,\ldots,d_i-1\}X=∏i=0p−1​{0,…,di​−1}, this definition assigns the real number

∑i=0p−1S(ρ{i})−S(ρ),S(M)=−Re⁡tr⁡ ⁣(cfc⁡[x↦xlog⁡2x](M)).\sum_{i=0}^{p-1}S(\rho_{\{i\}})-S(\rho), \qquad S(M)=-\operatorname{Re}\operatorname{tr}\!\left(\operatorname{cfc}[x\mapsto x\log_2x](M)\right).i=0∑p−1​S(ρ{i}​)−S(ρ),S(M)=−Retr(cfc[x↦xlog2​x](M)).

For any subset SSS, the matrix ρS\rho_SρS​ has entries (ρS)uv=∑ρxy(\rho_S)_{uv}=\sum\rho_{xy}(ρS​)uv​=∑ρxy​, where the sum runs over full configurations x,yx,yx,y restricting to u,vu,vu,v on SSS and agreeing at every coordinate outside SSS. The functional calculus in SSS is the total formal operation used in the definition; no density-matrix assumption is made on ρ\rhoρ. Dimensions may be zero, and p=0p=0p=0 is included: then the sum over parties is empty and the value is −S(ρ)-S(\rho)−S(ρ) for a matrix on a singleton configuration space.

QAlgorithms.Papers.Independent.Intakenext100.P47.multiSourcePower

For any natural number ppp, dimension function d:{0,…,p−1}→Nd:\{0,\ldots,p-1\}\to\mathbb Nd:{0,…,p−1}→N, complex matrix ρ\rhoρ indexed by configurations uuu with ui<diu_i<d_iui​<di​, and natural number nnn, this defines a matrix whose basis labels xxx assign a length-nnn string xix_ixi​ of labels below did_idi​ to every party. Its entries are

(ρ[n])xy=∏t=0n−1ρ(xi(t))i<p, (yi(t))i<p.\bigl(\rho^{[n]}\bigr)_{xy} =\prod_{t=0}^{n-1}\rho_{(x_i(t))_{i<p},\,(y_i(t))_{i<p}}.(ρ[n])xy​=t=0∏n−1​ρ(xi​(t))i<p​,(yi​(t))i<p​​.

No density-matrix or positivity hypothesis is required, and the local dimensions may be zero. When n=0n=0n=0, the matrix has a single basis label and its sole entry is the empty product 111. When p=0p=0p=0, the configuration type is a singleton, and the displayed entry is the nnn-th power of the sole entry of ρ\rhoρ.

QAlgorithms.Papers.Independent.Intakenext100.P47.rateLimit

For any Boolean choice ppp and any sequence f:N→Rf:\mathbb N\to\mathbb Rf:N→R, this defines lim sup⁡k→∞f(k)\limsup_{k\to\infty}f(k)limsupk→∞​f(k) when ppp is true, and lim inf⁡k→∞f(k)\liminf_{k\to\infty}f(k)liminfk→∞​f(k) when ppp is false, using the order-theoretic limits along the filter of sufficiently large natural numbers. No convergence or boundedness assumption is imposed; these are totalized real-valued operations, rather than operations taking values in the extended real numbers.

QAlgorithms.Papers.Independent.Intakenext100.P47.reducedOn

For any natural number ppp, natural dimensions did_idi​ indexed by i=0,…,p−1i=0,\ldots,p-1i=0,…,p−1, arbitrary complex matrix ρ\rhoρ on X=∏i{0,…,di−1}\mathcal X=\prod_i\{0,\ldots,d_i-1\}X=∏i​{0,…,di​−1}, and subset SSS of the party indices, this definition gives a matrix on XS=∏i∈S{0,…,di−1}\mathcal X_S=\prod_{i\in S}\{0,\ldots,d_i-1\}XS​=∏i∈S​{0,…,di​−1} whose entries are

(ρS)uv=∑x,y∈Xx∣S=u, y∣S=vxi=yi for every i∉Sρxy.(\rho_S)_{uv} = \sum_{\substack{x,y\in\mathcal X\\ x|_S=u,\ y|_S=v\\ x_i=y_i\ \text{for every }i\notin S}} \rho_{xy}.(ρS​)uv​=x,y∈Xx∣S​=u, y∣S​=vxi​=yi​ for every i∈/S​∑​ρxy​.

Thus coordinates outside SSS are summed over with equal row and column values, while coordinates in SSS are fixed by uuu and vvv. No positivity or trace condition is assumed. Zero dimensions are permitted and can make the configuration space empty, in which case the sums are zero. For S=∅S=\varnothingS=∅, the output is the scalar matrix with entry ∑xρxx\sum_x\rho_{xx}∑x​ρxx​; for p=0p=0p=0, the full configuration space itself is a singleton.

QAlgorithms.Papers.Independent.Intakenext100.P47.regroupedChannelPower

For finite types A,BA,BA,B, possibly empty, an arbitrary map TTT from complex matrices on A×BA\times BA×B to complex matrices on A×BA\times BA×B, and any natural number nnn, this defines a map Tn\mathcal T_nTn​ on matrices indexed by An×BnA^n\times B^nAn×Bn. For tuples x=(xA,xB)x=(x^A,x^B)x=(xA,xB), y=(yA,yB)y=(y^A,y^B)y=(yA,yB), its entries are

Tn(X)x,y=∑u,v:{0,…,n−1}→A×BX((utA)t,(utB)t), ((vtA)t,(vtB)t)∏t=0n−1T(Eut,vt)(xtA,xtB),(ytA,ytB),\mathcal T_n(X)_{x,y} =\sum_{u,v:\{0,\ldots,n-1\}\to A\times B} X_{((u_t^A)_t,(u_t^B)_t),\,((v_t^A)_t,(v_t^B)_t)} \prod_{t=0}^{n-1} T(E_{u_t,v_t})_{(x_t^A,x_t^B),(y_t^A,y_t^B)},Tn​(X)x,y​=u,v:{0,…,n−1}→A×B∑​X((utA​)t​,(utB​)t​),((vtA​)t​,(vtB​)t​)​t=0∏n−1​T(Eut​,vt​​)(xtA​,xtB​),(ytA​,ytB​)​,

where Ea,bE_{a,b}Ea,b​ is the matrix with its sole nonzero entry 111 in row aaa, column bbb. No linearity, positivity, or channel assumption is imposed on TTT. When n=0n=0n=0, the tuple spaces are singletons and the empty product is 111, so this map is the identity on the resulting one-dimensional matrix space.

QAlgorithms.Papers.Independent.Intakenext100.P47.schmidtDiagonal

For arbitrary types A,BA,BA,B, a natural number DDD, any function f:{0,…,D−1}→Rf:\{0,\ldots,D-1\}\to\mathbb Rf:{0,…,D−1}→R, and complex matrices a,ba,ba,b with respective row sets A,BA,BA,B and DDD columns, this defines a complex matrix on A×BA\times BA×B by

X(x,y),(x′,y′)=∑j=0D−1fj axjbyj ax′jby′j‾.X_{(x,y),(x',y')} =\sum_{j=0}^{D-1} f_j\,a_{xj}b_{yj}\, \overline{a_{x'j}b_{y'j}}.X(x,y),(x′,y′)​=j=0∑D−1​fj​axj​byj​ax′j​by′j​​.

No finiteness or nonemptiness assumptions are imposed on A,BA,BA,B, and neither normalization nor orthogonality is assumed for the columns. The coefficients fjf_jfj​ may be negative, and no positivity or trace-one condition is required of the resulting matrix; when D=0D=0D=0, it is the zero matrix.

QAlgorithms.Papers.Independent.Intakenext100.P47.schmidtKet

For arbitrary types A,BA,BA,B, a natural number DDD, any real-valued function fff on {0,…,D−1}\{0,\ldots,D-1\}{0,…,D−1}, and complex matrices aaa with rows indexed by AAA and bbb with rows indexed by BBB, both having DDD columns, this defines the vector with coefficients

ψ(x,y)=∑j=0D−1fj axjbyj.\psi_{(x,y)}=\sum_{j=0}^{D-1}\sqrt{f_j}\,a_{xj}b_{yj}.ψ(x,y)​=j=0∑D−1​fj​​axj​byj​.

There are no nonnegativity or normalization assumptions on fff, no orthogonality assumptions on the columns, and no finiteness assumptions on A,BA,BA,B. The real square root is 000 on negative inputs, so nonpositive fjf_jfj​ contribute 000; when D=0D=0D=0, the vector is 000.

QAlgorithms.Papers.Independent.Intakenext100.P47.schmidtPhase

For any finite type AAA, natural number DDD, complex matrix aaa with rows indexed by AAA and columns indexed by {0,…,D−1}\{0,\ldots,D-1\}{0,…,D−1}, and index k<Dk<Dk<D, this defines the matrix SkS_kSk​ on AAA by

(Sk)xy=δxy+∑j=0D−1(e2πikj/D−1)axjayj‾.(S_k)_{xy} =\delta_{xy}+\sum_{j=0}^{D-1} \left(e^{2\pi i kj/D}-1\right)a_{xj}\overline{a_{yj}}.(Sk​)xy​=δxy​+j=0∑D−1​(e2πikj/D−1)axj​ayj​​.

There is no assumption that the columns of aaa are orthonormal, or that this matrix is unitary. The type AAA may be empty. When D=0D=0D=0, there is no admissible index kkk, so the definition has no instance with such a kkk.

QAlgorithms.Papers.Independent.Intakenext100.P47.separableEntropyCosts

For any finite nonempty types A,BA,BA,B, any complex matrix ρ\rhoρ on A×BA\times BA×B, any natural number nnn, and any real ε\varepsilonε, this defines the set of real numbers

H(σ)−nH(ρ)−nεlog⁡2(∣A∣∣B∣)−η(ε)H(\sigma)-nH(\rho)-n\varepsilon\log_2(|A||B|)-\eta(\varepsilon)H(σ)−nH(ρ)−nεlog2​(∣A∣∣B∣)−η(ε)

obtained by choosing a positive-length list of pairs of local unitaries on An,BnA^n,B^nAn,Bn, with nonnegative weights pip_ipi​ summing to 111, setting T(X)=∑ipi(Ui⊗Vi)X(Ui⊗Vi)†T(X)=\sum_ip_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerT(X)=∑i​pi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†, and choosing σ=∑j<qwjaj⊗bj\sigma=\sum_{j<q}w_j a_j\otimes b_jσ=∑j<q​wj​aj​⊗bj​, where wj≥0w_j\ge0wj​≥0, ∑jwj=1\sum_jw_j=1∑j​wj​=1, and every aj,bja_j,b_jaj​,bj​ is positive semidefinite with trace 111, such that ∥σ−T(Xn)∥1≤ε\|\sigma-T(X_n)\|_1\le\varepsilon∥σ−T(Xn​)∥1​≤ε. Here (Xn)(a,b),(a′,b′)=∏t<nρ(at,bt),(at′,bt′)(X_n)_{(a,b),(a',b')}=\prod_{t<n}\rho_{(a_t,b_t),(a'_t,b'_t)}(Xn​)(a,b),(a′,b′)​=∏t<n​ρ(at​,bt​),(at′​,bt′​)​, ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​, H(Y)=−Re⁡tr⁡[ x↦xlog⁡2x ](Y)H(Y)=-\operatorname{Re}\operatorname{tr}[\,x\mapsto x\log_2x\,](Y)H(Y)=−Retr[x↦xlog2​x](Y), and matrix functions use continuous functional calculus. The correction is η(x)=−xlog⁡2x\eta(x)=-x\log_2xη(x)=−xlog2​x if x≤e−1x\le e^{-1}x≤e−1, and η(x)=e−1log⁡2e\eta(x)=e^{-1}\log_2eη(x)=e−1log2​e otherwise. There is no noise-class restriction and no density assumption on ρ\rhoρ; zero noise weights are permitted. Negative ε\varepsilonε makes the set empty, while n=0n=0n=0 uses X0=1X_0=1X0​=1.

QAlgorithms.Papers.Independent.Intakenext100.P47.sourcePower

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 matrix indexed by An×BnA^n\times B^nAn×Bn, where AnA^nAn means the functions {0,…,n−1}→A\{0,\ldots,n-1\}\to A{0,…,n−1}→A. Its entries are

(ρ[n])(a,b),(a′,b′)=∏t=0n−1ρ(at,bt),(at′,bt′).(\rho^{[n]})_{(a,b),(a',b')}=\prod_{t=0}^{n-1}\rho_{(a_t,b_t),(a'_t,b'_t)}.(ρ[n])(a,b),(a′,b′)​=t=0∏n−1​ρ(at​,bt​),(at′​,bt′​)​.

There are no finiteness, positivity, or normalization assumptions on A,B,ρA,B,\rhoA,B,ρ. When n=0n=0n=0, each function space has one element and the empty product is 111, so the resulting matrix is the 1×11\times11×1 matrix with entry 111.

QAlgorithms.Papers.Independent.Intakenext100.P47.successiveBlockOutput

For any natural numbers p,np,np,n, natural dimensions did_idi​, and arbitrary complex matrix ρ\rhoρ on H=∏i=0p−1{0,…,di−1}{0,…,n−1}\mathcal H=\prod_{i=0}^{p-1}\{0,\ldots,d_i-1\}^{\{0,\ldots,n-1\}}H=∏i=0p−1​{0,…,di​−1}{0,…,n−1}, suppose that for every j∈{0,…,p−2}j\in\{0,\ldots,p-2\}j∈{0,…,p−2} a noise choice RjR_jRj​ is given. Each RjR_jRj​ consists of a positive count NjN_jNj​, nonnegative weights wj,tw_{j,t}wj,t​ summing to 111, and local unitaries Uj,t,iU_{j,t,i}Uj,t,i​ on the party block spaces, determining

Φj(X)=∑t=0Nj−1wj,tVj,tXVj,t†,Vj,t(x,y)=∏i=0p−1Uj,t,i(xi,yi).\Phi_j(X)=\sum_{t=0}^{N_j-1}w_{j,t}V_{j,t}XV_{j,t}^\dagger, \qquad V_{j,t}(x,y)=\prod_{i=0}^{p-1}U_{j,t,i}(x_i,y_i).Φj​(X)=t=0∑Nj​−1​wj,t​Vj,t​XVj,t†​,Vj,t​(x,y)=i=0∏p−1​Uj,t,i​(xi​,yi​).

The output is obtained by starting with ρ0=ρ\rho_0=\rhoρ0​=ρ, setting ρj+1=Φj(ρj)\rho_{j+1}=\Phi_j(\rho_j)ρj+1​=Φj​(ρj​) in increasing order j=0,…,p−2j=0,\ldots,p-2j=0,…,p−2, and returning ρp−1\rho_{p-1}ρp−1​. No restriction requires RjR_jRj​ to act only on party jjj, have independent local choices, or have uniform weights. No density assumption on ρ\rhoρ is imposed, and n=0n=0n=0 and zero dimensions are allowed. When p=0p=0p=0 or p=1p=1p=1, natural subtraction makes the list of steps empty and the output is exactly ρ\rhoρ.

QAlgorithms.Papers.Independent.Intakenext100.P47.tailInformation

For any natural number ppp, natural dimensions did_idi​, arbitrary complex matrix ρ\rhoρ on X=∏i=0p−1{0,…,di−1}\mathcal X=\prod_{i=0}^{p-1}\{0,\ldots,d_i-1\}X=∏i=0p−1​{0,…,di​−1}, and index j∈{0,…,p−2}j\in\{0,\ldots,p-2\}j∈{0,…,p−2}, this definition gives

S(ρ{j})+S(ρ{i:j<i<p})−S(ρ{i:j≤i<p}).S(\rho_{\{j\}}) + S(\rho_{\{i:j<i<p\}}) - S(\rho_{\{i:j\le i<p\}}).S(ρ{j}​)+S(ρ{i:j<i<p}​)−S(ρ{i:j≤i<p}​).

Here S(M)=−Re⁡tr⁡(cfc⁡[x↦xlog⁡2x](M))S(M)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[x\mapsto x\log_2x](M))S(M)=−Retr(cfc[x↦xlog2​x](M)), and (ρS)uv(\rho_S)_{uv}(ρS​)uv​ is the sum of ρxy\rho_{xy}ρxy​ over full configurations with x∣S=ux|_S=ux∣S​=u, y∣S=vy|_S=vy∣S​=v, and xi=yix_i=y_ixi​=yi​ for every i∉Si\notin Si∈/S. No positivity or normalization is assumed, and zero dimensions are allowed. The index type has p−1p-1p−1 elements with natural-number subtraction truncated at zero, so there is no possible argument jjj when p=0p=0p=0 or p=1p=1p=1.

QAlgorithms.Papers.Independent.Intakenext100.P47.totalBlockRate

For any finite types A,BA,BA,B, any complex matrix ρ\rhoρ on A×BA\times BA×B, any real ε\varepsilonε, any noise class and cost, and any natural number kkk, put n=k+1n=k+1n=k+1. This defines n−1inf⁡Cnn^{-1}\inf\mathcal C_nn−1infCn​, where Cn\mathcal C_nCn​ consists of the following real costs. Form XnX_nXn​ with entries (Xn)(a,b),(a′,b′)=∏t<nρ(at,bt),(at′,bt′)(X_n)_{(a,b),(a',b')}=\prod_{t<n}\rho_{(a_t,b_t),(a'_t,b'_t)}(Xn​)(a,b),(a′,b′)​=∏t<n​ρ(at​,bt​),(at′​,bt′​)​, and choose a positive-length list of pairs of local unitaries Ui,ViU_i,V_iUi​,Vi​, with nonnegative weights pip_ipi​ summing to 111, giving T(X)=∑ipi(Ui⊗Vi)X(Ui⊗Vi)†T(X)=\sum_i p_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerT(X)=∑i​pi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†. The output must satisfy ∥T(Xn)−a⊗b∥1≤ε\|T(X_n)-a\otimes b\|_1\le\varepsilon∥T(Xn​)−a⊗b∥1​≤ε for some positive semidefinite, trace-one matrices a,ba,ba,b, where ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​. Coordinated noise imposes no further restriction; Alice noise requires Vi=1V_i=1Vi​=1; Bob noise requires Ui=1U_i=1Ui​=1; independent noise requires the list and weights to be, up to a bijection, a Cartesian product of two local probability-weighted unitary lists. For a list of length ccc, its cost is respectively log⁡2c\log_2clog2​c, −∑ipilog⁡2pi-\sum_i p_i\log_2p_i−∑i​pi​log2​pi​, or H((id⊗T)(∣ξXn⟩⟨ξXn∣))H((\mathrm{id}\otimes T)(|\xi_{X_n}\rangle\langle\xi_{X_n}|))H((id⊗T)(∣ξXn​​⟩⟨ξXn​​∣)), according to the cost choice, where ξX(u,v)=(X)v,u\xi_X(u,v)=(\sqrt X)_{v,u}ξX​(u,v)=(X​)v,u​, H(Y)=−Re⁡tr⁡[ x↦xlog⁡2x ](Y)H(Y)=-\operatorname{Re}\operatorname{tr}[\,x\mapsto x\log_2x\,](Y)H(Y)=−Retr[x↦xlog2​x](Y), and matrix functions use continuous functional calculus. The infimum is taken in R\mathbb RR, whose totalized infimum is 000 for an empty set or a set unbounded below. The denominator is always positive, including at k=0k=0k=0. Neither normalization of ρ\rhoρ nor nonemptiness of A,BA,BA,B is assumed; in particular, a negative ε\varepsilonε makes Cn\mathcal C_nCn​ empty and the defined rate 000.

QAlgorithms.Papers.Independent.Intakenext100.P47.totalCosts

For any finite types A,BA,BA,B, any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, any natural number nnn, any real ε\varepsilonε, and choices of noise class and cost, this defines the set of real numbers obtainable as follows. Write An={0,…,n−1}→AA^n=\{0,\ldots,n-1\}\to AAn={0,…,n−1}→A, similarly for BnB^nBn, and define XnX_nXn​ by (Xn)(a,b),(a′,b′)=∏t=0n−1ρ(at,bt),(at′,bt′)(X_n)_{(a,b),(a',b')}=\prod_{t=0}^{n-1}\rho_{(a_t,b_t),(a'_t,b'_t)}(Xn​)(a,b),(a′,b′)​=∏t=0n−1​ρ(at​,bt​),(at′​,bt′​)​. Choose a positive integer ccc, nonnegative weights pip_ipi​ summing to 111, and unitary matrices UiU_iUi​ on AnA^nAn and ViV_iVi​ on BnB^nBn, and put T(X)=∑i=0c−1pi(Ui⊗Vi)X(Ui⊗Vi)†T(X)=\sum_{i=0}^{c-1}p_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerT(X)=∑i=0c−1​pi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†. For coordinated noise there is no additional restriction; for Alice noise every ViV_iVi​ is the identity; for Bob noise every UiU_iUi​ is the identity; for independent noise the indexed list must, up to a bijection, be the Cartesian product of two positive-length lists of local unitaries with probability weights, with pip_ipi​ equal to the product of the corresponding local weights. Require density matrices aaa on AnA^nAn and bbb on BnB^nBn such that ∥T(Xn)−a⊗b∥1≤ε\|T(X_n)-a\otimes b\|_1\le\varepsilon∥T(Xn​)−a⊗b∥1​≤ε, where a density matrix is positive semidefinite with trace 111, and ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​, with the square root given by continuous functional calculus. The resulting number is log⁡2c\log_2clog2​c for size cost, −∑ipilog⁡2pi-\sum_i p_i\log_2p_i−∑i​pi​log2​pi​ for entropy cost, or H((id⊗T)(∣ξXn⟩⟨ξXn∣))H((\mathrm{id}\otimes T)(|\xi_{X_n}\rangle\langle\xi_{X_n}|))H((id⊗T)(∣ξXn​​⟩⟨ξXn​​∣)) for exchange cost, where ξX(u,v)=(X)v,u\xi_X(u,v)=(\sqrt X)_{v,u}ξX​(u,v)=(X​)v,u​ and H(Y)=−Re⁡tr⁡[ x↦xlog⁡2x ](Y)H(Y)=-\operatorname{Re}\operatorname{tr}[\,x\mapsto x\log_2x\,](Y)H(Y)=−Retr[x↦xlog2​x](Y). There is no density assumption on ρ\rhoρ, no nonemptiness assumption on A,BA,BA,B, and zero weights are permitted. When n=0n=0n=0, the product defining XnX_nXn​ is 111; when ε<0\varepsilon<0ε<0, the defined set is empty.

QAlgorithms.Papers.Independent.Intakenext100.P47.totalErasure

For any finite types A,BA,BA,B, any complex matrix ρ\rhoρ on A×BA\times BA×B, any noise class and cost, and any Boolean ppp, this defines

sup⁡ε>0{lim sup⁡k→∞inf⁡Ck+1(ε)k+1,p=true,lim inf⁡k→∞inf⁡Ck+1(ε)k+1,p=false.\sup_{\varepsilon>0} \begin{cases} \displaystyle\limsup_{k\to\infty}\frac{\inf\mathcal C_{k+1}(\varepsilon)}{k+1},&p=\mathrm{true},\\[4pt] \displaystyle\liminf_{k\to\infty}\frac{\inf\mathcal C_{k+1}(\varepsilon)}{k+1},&p=\mathrm{false}. \end{cases}ε>0sup​⎩⎨⎧​k→∞limsup​k+1infCk+1​(ε)​,k→∞liminf​k+1infCk+1​(ε)​,​p=true,p=false.​

Here XnX_nXn​ is the matrix on An×BnA^n\times B^nAn×Bn with entries ∏t<nρ(at,bt),(at′,bt′)\prod_{t<n}\rho_{(a_t,b_t),(a'_t,b'_t)}∏t<n​ρ(at​,bt​),(at′​,bt′​)​, and Cn(ε)\mathcal C_n(\varepsilon)Cn​(ε) consists of costs of maps T(X)=∑i<cpi(Ui⊗Vi)X(Ui⊗Vi)†T(X)=\sum_{i<c}p_i(U_i\otimes V_i)X(U_i\otimes V_i)^\daggerT(X)=∑i<c​pi​(Ui​⊗Vi​)X(Ui​⊗Vi​)†, where c>0c>0c>0, the pip_ipi​ are nonnegative and sum to 111, and Ui,ViU_i,V_iUi​,Vi​ are local unitaries, such that ∥T(Xn)−a⊗b∥1≤ε\|T(X_n)-a\otimes b\|_1\le\varepsilon∥T(Xn​)−a⊗b∥1​≤ε for some positive semidefinite, trace-one matrices a,ba,ba,b. The trace norm is ∥M∥1=Re⁡tr⁡M†M\|M\|_1=\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}∥M∥1​=RetrM†M​. Coordinated noise adds no restriction; Alice noise requires every Vi=1V_i=1Vi​=1; Bob noise requires every Ui=1U_i=1Ui​=1; independent noise requires a bijective identification with a Cartesian product of two local probability-weighted unitary lists, including factorization of the weights. The selected cost is log⁡2c\log_2clog2​c, −∑ipilog⁡2pi-\sum_i p_i\log_2p_i−∑i​pi​log2​pi​, or H((id⊗T)(∣ξXn⟩⟨ξXn∣))H((\mathrm{id}\otimes T)(|\xi_{X_n}\rangle\langle\xi_{X_n}|))H((id⊗T)(∣ξXn​​⟩⟨ξXn​​∣)), where ξX(u,v)=(X)v,u\xi_X(u,v)=(\sqrt X)_{v,u}ξX​(u,v)=(X​)v,u​ and H(Y)=−Re⁡tr⁡[ x↦xlog⁡2x ](Y)H(Y)=-\operatorname{Re}\operatorname{tr}[\,x\mapsto x\log_2x\,](Y)H(Y)=−Retr[x↦xlog2​x](Y); matrix functions use continuous functional calculus. All infima, suprema and sequence limits here are real-valued and totalized; in particular, an empty inner cost set has infimum 000. The definition assumes neither that ρ\rhoρ is a density matrix nor that A,BA,BA,B are nonempty, and it takes a supremum over all positive tolerances.

QAlgorithms.Papers.Independent.Intakenext100.P47.withAncilla

For arbitrary types A,B,C,DA,B,C,DA,B,C,D, any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, and any complex matrix γ\gammaγ indexed by C×DC\times DC×D, this defines a complex matrix on (A×C)×(B×D)(A\times C)\times(B\times D)(A×C)×(B×D) by

(ρwithAncillaγ)((a,c),(b,d)), ((a′,c′),(b′,d′))=ρ(a,b),(a′,b′) γ(c,d),(c′,d′).(\rho\mathbin{\mathrm{withAncilla}}\gamma)_{((a,c),(b,d)),\,((a',c'),(b',d'))} =\rho_{(a,b),(a',b')}\,\gamma_{(c,d),(c',d')}.(ρwithAncillaγ)((a,c),(b,d)),((a′,c′),(b′,d′))​=ρ(a,b),(a′,b′)​γ(c,d),(c′,d′)​.

There are no finiteness, nonemptiness, positivity, trace, or normalization assumptions on these types or matrices.

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

    Confirmed by the moderator at approval.

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