Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Trade-off capacities of the quantum Hadamard channels

Definition
QAlgorithms_Papers_Independent_Gap20_P04

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

prove2quantum

The objects the formalized statements of Trade-off capacities of the quantum Hadamard channels (arXiv:1001.1732) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • product: PDF pp.10,19: distinct channels; receiver and environment factors are regrouped.
  • PurifiedInputFamily: PDF p.7, (15): arbitrary finite alphabet and reference; validity is separate.
  • PurifiedInputFamily.Valid: PDF pp.3,7: normalized distribution; every conditional vector has norm one.
  • PurifiedInputFamily.input: PDF p.7: input marginal of the conditional PURE reference-input state.
  • PurifiedInputFamily.average: PDF pp.3--4: average input.
  • inputEntropy: PDF p.4: H(A|X)=H(A'|X), by purity of each input.
  • ensembleReceiverEntropy: PDF p.4: H(B).
  • conditionalReceiverEntropy: PDF p.4: H(B|X).
  • conditionalEnvironmentEntropy: PDF p.4: H(E|X), using the same isometry.
  • ensembleCoherentBits: PDF pp.4,9: q=I(A>B X), using conditional ABE purity.
  • jointInfo: PDF pp.4,8: j=I(AX;B), using conditional ABE purity.
  • cqScore: PDF p.9, (21): CQ support objective.
  • ceScore: PDF p.11, (23): CE support objective, with MINUS consumption.
  • purifiedValues: PDF p.7, (15): physical ensembles only.
  • PureInputs: PDF pp.10,20: pure channel-input ensembles in the Holevo maximum.
  • holevoValues: PDF pp.10,20: one-use Holevo values, not regularized classical capacity.
  • RepeatedMax: Positive-block homogeneity with attainment.
  • oneCQ: PDF p.7: literal one-use CQ union, with ONE ensemble.
  • oneCE: PDF p.8: CE rectangle union, E>=0 denotes consumption and may be wasted.
  • oneCQE: PDF p.8, (17)--(19): all THREE inequalities use ONE ensemble.
  • capacityCQ: PDF p.7, (14): closure OUTSIDE the positive-block union.
  • capacityCE: PDF p.8, (16): unrestricted block-input CE region.
  • capacityCQE: PDF p.8: regularized positive-consumption CQE region.
  • CQSupport: PDF pp.9--11: full supporting CQ face, retaining optimizer ties.
  • CEUpper: PDF pp.11,19: upper C at the given consumption budget, allowing flat portions.
  • cqHull: PDF p.21: nonnegative resource-monotone CQ hull, with convex combinations and limits.
  • ceHull: PDF pp.8,21: CE hull permits lowering C and increasing consumption E.
  • binaryEnsemble: PDF pp.13,22: actual purifications with the specified swapped diagonal marginals.
  • binaryCQ: PDF pp.12--13: CQ coordinates of the purified binary ensemble.
  • binaryCE: PDF pp.15,23: CE coordinates of the same purified ensemble.
  • gdDilation: PDF p.5, (10): generalized-dephasing parent isometry when each v_i is unit.
  • measureBasis: PDF p.5: basis measurement, storing its classical outcome diagonally.
  • basisStatePreparation: PDF p.5: basisStatePreparation the conditional environment state.
  • degradingKraus: PDF p.5: rank-one degrading Kraus |xi_b><b|.
  • hadamardCoefficient: PDF p.5, (9): explicit coefficient fixes the conjugations.
  • DephasedReplacement: PDF pp.21,23: same probabilities, dephased INPUT marginals, NEW purifications.
  • dephasingCQ: PDF p.12, Theorem 4: CQ generating family.
  • dephasingCE: PDF p.12, Theorem 4: CE generating family.
  • cloneDelta: PDF pp.6,12: normalization, in real arithmetic.
  • cloneLambda: PDF p.12: lambda_i for i=0,...,N; subtraction is in reals.
  • cloneEta: PDF p.12: eta_i for i=0,...,N-1; subtraction is in reals.
  • entropyVector: PDF p.12: finite Shannon entropy, bits; 0 log 0=0.
  • cloningCQ: PDF p.12, Theorem 5: cloning CQ coordinates.
  • cloningCE: PDF p.12, Theorem 5: cloning CE coordinates.
  • CESupport: PDF pp.11,21: CE supporting face, distinct from choosing one optimizer.
  • selectedCQHull: PDF p.21: CQ hull from one selection per support face and the resource endpoints. Endpoints are represented by their full axis intervals; resource monotonicity is explicit.
  • selectedCEHull: PDF p.21: CE selection hull, including the zero-consumption endpoint and limits.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Ensemble
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_BipartiteSeparability
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P24
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P67
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P32
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P44
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P24

/-!
Bradler--Hayden--Touchette--Wilde, arXiv:1001.1732v2, statement draft.
Entropies are bits; E>=0 is consumption. Capacity sets are the source's
regularized entropy-region definitions (14)--(19), whose operational meaning
is recalled in Section III. No signed-rate region or Unruh cutoff is substituted.
-/

noncomputable section

namespace QAlgorithms.Papers.Independent.Gap20.P04

open QAlgorithms
open QAlgorithms.Papers.Independent.Claimed50.P24
  (Dilation PhysicalDilation ChannelEB Hadamard EqualMax AdditiveMax
   dephasingDilation dephasingGamma cloningDilation)
open QAlgorithms.Papers.Independent.Information100.P67
  (receiverChannel complementaryChannel dilationPower)
open QAlgorithms.Papers.Independent.Information100.P32 (diagonal)
open QAlgorithms.Papers.Independent.Dependency50.P24 (ensembleHolevoBits)
open QAlgorithms.Papers.Independent.Gap48.P44 (cqTimeSharing ceTimeSharing)
open scoped BigOperators Matrix ComplexConjugate

attribute [local instance] Classical.propDecidable Classical.decEq

/-!
Repair provenance: frozen Stinespring primitives, Hadamard/EB predicates,
attained-maximum relations, explicit qubit dilations, diagonal map and endpoint
time sharing are imported from the pinned accepted library. No signed-rate
capacity theorem is imported or asserted equivalent to the consumption theorem.

The remaining distinctly named interfaces have different domains from their
frozen namesakes: PurifiedInputFamily stores arbitrary finite reference-input
unit vectors with validity separate, whereas Information100.P58.InputEnsemble
stores mixed erasure-block inputs. ensembleReceiverEntropy is finite base-two
matrix entropy, not Information100.P49.outputEntropy's Gaussian scalar formula;
conditionalReceiverEntropy accepts those purified inputs rather than a
multi-sender product law. The Holevo coordinate reuses Dependency50.P24.ensembleHolevoBits
on the probabilities and conditional receiver densities. ensembleCoherentBits is
a real entropy coordinate, unlike the frozen Hamiltonian commutator coherent.
purifiedValues ranges over this raw family's Valid members, not P24's mixed
two-label ensembles. basisStatePreparation is the linear basis-controlled
preparation map, not Frontier30.P06.FeedbackExecution.prepare's next-input encoding.
-/

variable {I B E J D F : Type}
variable [Fintype I] [Fintype B] [Fintype E]
variable [Fintype J] [Fintype D] [Fintype F]
variable [DecidableEq I] [DecidableEq B] [DecidableEq E]
variable [DecidableEq J] [DecidableEq D] [DecidableEq F]
variable [Nonempty I] [Nonempty B] [Nonempty E]
variable [Nonempty J] [Nonempty D] [Nonempty F]

/-- PDF pp.10,19: distinct channels; receiver and environment factors are regrouped. -/
def product (U : Dilation I B E) (V : Dilation J D F) :
    Dilation (I × J) (B × D) (E × F) :=
  fun be i => U (be.1.1,be.2.1) i.1 * V (be.1.2,be.2.2) i.2

/-- PDF p.7, (15): arbitrary finite alphabet and reference; validity is separate. -/
structure PurifiedInputFamily (I : Type) where
  labels : ℕ
  reference : ℕ
  prob : Fin labels → ℝ
  psi : Fin labels → EuclideanSpace ℂ (Fin reference × I)

/-- PDF pp.3,7: normalized distribution; every conditional vector has norm one. -/
def PurifiedInputFamily.Valid (e : PurifiedInputFamily I) : Prop :=
  0 < e.labels ∧ 0 < e.reference ∧ (∀ x, 0 ≤ e.prob x) ∧
    (∑ x, e.prob x) = 1 ∧ ∀ x, ‖e.psi x‖ = 1

/-- PDF p.7: input marginal of the conditional PURE reference-input state. -/
def PurifiedInputFamily.input (e : PurifiedInputFamily I) (x : Fin e.labels) : Matrix I I ℂ :=
  traceLeft (pureDensity (e.psi x))

/-- PDF pp.3--4: average input. -/
def PurifiedInputFamily.average (e : PurifiedInputFamily I) : Matrix I I ℂ :=
  ∑ x, (e.prob x : ℂ) • e.input x

/-- PDF p.4: H(A|X)=H(A'|X), by purity of each input. -/
def inputEntropy (e : PurifiedInputFamily I) : ℝ :=
  ∑ x, e.prob x * vnEntropy (e.input x)

/-- PDF p.4: H(B). -/
def ensembleReceiverEntropy (U : Dilation I B E) (e : PurifiedInputFamily I) : ℝ :=
  vnEntropy (receiverChannel U e.average)

/-- PDF p.4: H(B|X). -/
def conditionalReceiverEntropy (U : Dilation I B E) (e : PurifiedInputFamily I) : ℝ :=
  ∑ x, e.prob x * vnEntropy (receiverChannel U (e.input x))

/-- PDF p.4: H(E|X), using the same isometry. -/
def conditionalEnvironmentEntropy (U : Dilation I B E) (e : PurifiedInputFamily I) : ℝ :=
  ∑ x, e.prob x * vnEntropy (complementaryChannel U (e.input x))

/-- PDF pp.4,9: q=I(A>B X), using conditional ABE purity. -/
def ensembleCoherentBits (U : Dilation I B E) (e : PurifiedInputFamily I) : ℝ :=
  conditionalReceiverEntropy U e - conditionalEnvironmentEntropy U e

/-- PDF pp.4,8: j=I(AX;B), using conditional ABE purity. -/
def jointInfo (U : Dilation I B E) (e : PurifiedInputFamily I) : ℝ :=
  inputEntropy e + ensembleReceiverEntropy U e - conditionalEnvironmentEntropy U e

/-- PDF p.9, (21): CQ support objective. -/
def cqScore (U : Dilation I B E) (lam : ℝ) (e : PurifiedInputFamily I) : ℝ :=
  ensembleHolevoBits e.prob (fun x => receiverChannel U (e.input x)) + lam * ensembleCoherentBits U e

/-- PDF p.11, (23): CE support objective, with MINUS consumption. -/
def ceScore (U : Dilation I B E) (lam : ℝ) (e : PurifiedInputFamily I) : ℝ :=
  jointInfo U e - lam * inputEntropy e

/-- PDF p.7, (15): physical ensembles only. -/
def purifiedValues (f : PurifiedInputFamily I → ℝ) : Set ℝ :=
  {v | ∃ e, e.Valid ∧ v = f e}

/-- PDF pp.10,20: pure channel-input ensembles in the Holevo maximum. -/
def PureInputs (e : PurifiedInputFamily I) : Prop :=
  ∀ x, ∃ v : EuclideanSpace ℂ I, ‖v‖ = 1 ∧ e.input x = pureDensity v

/-- PDF pp.10,20: one-use Holevo values, not regularized classical capacity. -/
def holevoValues (U : Dilation I B E) : Set ℝ :=
  {v | ∃ e, e.Valid ∧ PureInputs e ∧ v = ensembleHolevoBits e.prob (fun x => receiverChannel U (e.input x))}

/-- Positive-block homogeneity with attainment. -/
def RepeatedMax (n : ℕ) (S T : Set ℝ) : Prop :=
  ∃ v, IsGreatest S v ∧ IsGreatest T ((n : ℝ)*v)

/-- PDF p.7: literal one-use CQ union, with ONE ensemble. -/
def oneCQ (U : Dilation I B E) : Set (ℝ × ℝ) :=
  {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧ ∃ e, e.Valid ∧ r.1 ≤ ensembleHolevoBits e.prob (fun x => receiverChannel U (e.input x)) ∧ r.2 ≤ ensembleCoherentBits U e}

/-- PDF p.8: CE rectangle union, E>=0 denotes consumption and may be wasted. -/
def oneCE (U : Dilation I B E) : Set (ℝ × ℝ) :=
  {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧ ∃ e, e.Valid ∧ r.1 ≤ jointInfo U e ∧ inputEntropy e ≤ r.2}

/-- PDF p.8, (17)--(19): all THREE inequalities use ONE ensemble. -/
def oneCQE (U : Dilation I B E) : Set (Fin 3 → ℝ) :=
  {r | (∀ i, 0 ≤ r i) ∧ ∃ e, e.Valid ∧
    r 0 + 2*r 1 ≤ jointInfo U e ∧ r 1 ≤ ensembleCoherentBits U e + r 2 ∧
      r 0 + r 1 ≤ ensembleHolevoBits e.prob (fun x => receiverChannel U (e.input x)) + ensembleCoherentBits U e + r 2}

/-- PDF p.7, (14): closure OUTSIDE the positive-block union. -/
def capacityCQ (U : Dilation I B E) : Set (ℝ × ℝ) :=
  closure {r | ∃ n : ℕ, 0 < n ∧ (n : ℝ) • r ∈ oneCQ (dilationPower U n)}

/-- PDF p.8, (16): unrestricted block-input CE region. -/
def capacityCE (U : Dilation I B E) : Set (ℝ × ℝ) :=
  closure {r | ∃ n : ℕ, 0 < n ∧ (n : ℝ) • r ∈ oneCE (dilationPower U n)}

/-- PDF p.8: regularized positive-consumption CQE region. -/
def capacityCQE (U : Dilation I B E) : Set (Fin 3 → ℝ) :=
  closure {r | ∃ n : ℕ, 0 < n ∧ (n : ℝ) • r ∈ oneCQE (dilationPower U n)}

/-- PDF pp.9--11: full supporting CQ face, retaining optimizer ties. -/
def CQSupport (S : Set (ℝ × ℝ)) (lam : ℝ) (r : ℝ × ℝ) : Prop :=
  r ∈ S ∧ ∀ s ∈ S, s.1 + lam*s.2 ≤ r.1 + lam*r.2

/-- PDF pp.11,19: upper C at the given consumption budget, allowing flat portions. -/
def CEUpper (S : Set (ℝ × ℝ)) (r : ℝ × ℝ) : Prop :=
  r ∈ S ∧ ∀ s ∈ S, s.2 ≤ r.2 → s.1 ≤ r.1

/-- PDF p.21: nonnegative resource-monotone CQ hull, with convex combinations and limits. -/
def cqHull (f : ℝ → ℝ × ℝ) : Set (ℝ × ℝ) :=
  closure (convexHull ℝ {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧
    ∃ mu ∈ Set.Icc (0 : ℝ) (1/2), r.1 ≤ (f mu).1 ∧ r.2 ≤ (f mu).2})

/-- PDF pp.8,21: CE hull permits lowering C and increasing consumption E. -/
def ceHull (f : ℝ → ℝ × ℝ) : Set (ℝ × ℝ) :=
  closure (convexHull ℝ {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧
    ∃ mu ∈ Set.Icc (0 : ℝ) (1/2), r.1 ≤ (f mu).1 ∧ (f mu).2 ≤ r.2})

/-- PDF pp.13,22: actual purifications with the specified swapped diagonal marginals. -/
def binaryEnsemble (mu : ℝ) : PurifiedInputFamily (Fin 2) where
  labels := 2
  reference := 2
  prob := fun _ => 1/2
  psi := fun x => WithLp.toLp 2 fun ai =>
    if ai.1 = ai.2 then
      if ai.2 = x then (Real.sqrt mu : ℂ) else (Real.sqrt (1-mu) : ℂ)
    else 0

/-- PDF pp.12--13: CQ coordinates of the purified binary ensemble. -/
def binaryCQ (U : Dilation (Fin 2) B E) (mu : ℝ) : ℝ × ℝ :=
  (ensembleHolevoBits (binaryEnsemble mu).prob
    (fun x => receiverChannel U ((binaryEnsemble mu).input x)), ensembleCoherentBits U (binaryEnsemble mu))

/-- PDF pp.15,23: CE coordinates of the same purified ensemble. -/
def binaryCE (U : Dilation (Fin 2) B E) (mu : ℝ) : ℝ × ℝ :=
  (jointInfo U (binaryEnsemble mu), inputEntropy (binaryEnsemble mu))

/-- PDF p.5, (10): generalized-dephasing parent isometry when each v_i is unit. -/
def gdDilation (v : I → EuclideanSpace ℂ E) : Dilation I I E :=
  fun be i => if be.1 = i then v i be.2 else 0

/-- PDF p.5: basis measurement, storing its classical outcome diagonally. -/
def measureBasis : Superop B B := diagonal

/-- PDF p.5: basisStatePreparation the conditional environment state. -/
def basisStatePreparation (v : B → EuclideanSpace ℂ E) : Superop B E :=
  fun rho => ∑ b, rho b b • pureDensity (v b)

/-- PDF p.5: rank-one degrading Kraus |xi_b><b|. -/
def degradingKraus (v : B → EuclideanSpace ℂ E) (b : B) : Matrix E B ℂ :=
  fun e c => if c = b then v b e else 0

/-- PDF p.5, (9): explicit coefficient fixes the conjugations. -/
def hadamardCoefficient (zeta : B → EuclideanSpace ℂ I)
    (xi : B → EuclideanSpace ℂ E) (rho : Matrix I I ℂ) : Matrix B B ℂ :=
  fun b c => (∑ i, ∑ j, conj (zeta b i) * rho i j * zeta c j) *
    (∑ e, conj (xi c e) * xi b e)

/-- PDF pp.21,23: same probabilities, dephased INPUT marginals, NEW purifications. -/
def DephasedReplacement (e t : PurifiedInputFamily I) : Prop :=
  ∃ f : Fin e.labels ≃ Fin t.labels, ∀ x,
    t.prob (f x) = e.prob x ∧ t.input (f x) = diagonal (e.input x)

/-- PDF p.12, Theorem 4: CQ generating family. -/
def dephasingCQ (p mu : ℝ) : ℝ × ℝ :=
  (1-binEntropy2 mu, binEntropy2 mu-binEntropy2 (dephasingGamma mu p))

/-- PDF p.12, Theorem 4: CE generating family. -/
def dephasingCE (p mu : ℝ) : ℝ × ℝ :=
  (1+binEntropy2 mu-binEntropy2 (dephasingGamma mu p), binEntropy2 mu)

/-- PDF pp.6,12: normalization, in real arithmetic. -/
def cloneDelta (N : ℕ) : ℝ := (N : ℝ)*((N : ℝ)+1)/2

/-- PDF p.12: lambda_i for i=0,...,N; subtraction is in reals. -/
def cloneLambda (N : ℕ) (mu : ℝ) (i : Fin (N+1)) : ℝ :=
  ((N : ℝ)-2*(i.val : ℝ))*mu+(i.val : ℝ)

/-- PDF p.12: eta_i for i=0,...,N-1; subtraction is in reals. -/
def cloneEta (N : ℕ) (mu : ℝ) (i : Fin N) : ℝ :=
  ((N : ℝ)-1-2*(i.val : ℝ))*mu+(i.val : ℝ)+1

/-- PDF p.12: finite Shannon entropy, bits; 0 log 0=0. -/
def entropyVector {K : Type} [Fintype K] (p : K → ℝ) : ℝ :=
  -∑ i, p i * Real.logb 2 (p i)

/-- PDF p.12, Theorem 5: cloning CQ coordinates. -/
def cloningCQ (N : ℕ) (mu : ℝ) : ℝ × ℝ :=
  let hb := entropyVector (fun i => cloneLambda N mu i / cloneDelta N)
  let he := entropyVector (fun i => cloneEta N mu i / cloneDelta N)
  (Real.logb 2 ((N : ℝ)+1)-hb, hb-he)

/-- PDF p.12, Theorem 5: cloning CE coordinates. -/
def cloningCE (N : ℕ) (mu : ℝ) : ℝ × ℝ :=
  (Real.logb 2 ((N : ℝ)+1)+binEntropy2 mu-
    entropyVector (fun i => cloneEta N mu i / cloneDelta N), binEntropy2 mu)

/-- PDF pp.11,21: CE supporting face, distinct from choosing one optimizer. -/
def CESupport (S : Set (ℝ × ℝ)) (lam : ℝ) (r : ℝ × ℝ) : Prop :=
  r ∈ S ∧ ∀ s ∈ S, s.1-lam*s.2 ≤ r.1-lam*r.2

/-- PDF p.21: CQ hull from one selection per support face and the resource endpoints.
Endpoints are represented by their full axis intervals; resource monotonicity is explicit. -/
def selectedCQHull (S : Set (ℝ × ℝ)) (f : ℝ → ℝ × ℝ) : Set (ℝ × ℝ) :=
  closure (convexHull ℝ {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧ ∃ s : ℝ × ℝ,
    ((∃ lam : ℝ, 1 ≤ lam ∧ s = f lam) ∨ (s ∈ S ∧ (s.1 = 0 ∨ s.2 = 0))) ∧
    r.1 ≤ s.1 ∧ r.2 ≤ s.2})

/-- PDF p.21: CE selection hull, including the zero-consumption endpoint and limits. -/
def selectedCEHull (S : Set (ℝ × ℝ)) (f : ℝ → ℝ × ℝ) : Set (ℝ × ℝ) :=
  closure (convexHull ℝ {r | 0 ≤ r.1 ∧ 0 ≤ r.2 ∧ ∃ s : ℝ × ℝ,
    ((∃ lam ∈ Set.Icc (0 : ℝ) 1, s = f lam) ∨ (s ∈ S ∧ s.2 = 0)) ∧
    r.1 ≤ s.1 ∧ s.2 ≤ r.2})

/-! Sanity tests for the local definitions. -/

example : cloneDelta 1 = 1 := by norm_num [cloneDelta]

example (mu : ℝ) : cloneEta 1 mu (0 : Fin 1) = 1 := by simp [cloneEta]

example (rho : Matrix I I ℂ) : diagonal (diagonal rho) = diagonal rho := by
  ext i j
  simp [diagonal]

example : dephasingGamma 0 0 = 1 := by norm_num [dephasingGamma]

example : (binaryEnsemble 0).psi (0 : Fin 2) ((1 : Fin 2), (1 : Fin 2)) = 1 := by
  change (if (1 : Fin 2) = 1 then
    if (1 : Fin 2) = 0 then (Real.sqrt (0 : ℝ) : ℂ)
    else (Real.sqrt (1 - (0 : ℝ)) : ℂ)
    else 0) = 1
  norm_num

example (U : Dilation I B E) : cqScore U 0 =
    (fun e => ensembleHolevoBits e.prob (fun x => receiverChannel U (e.input x))) := by
  funext e
  simp [cqScore]

end QAlgorithms.Papers.Independent.Gap20.P04
Source
Trade-off capacities of the quantum Hadamard channels, arXiv:1001.1732v2, https://arxiv.org/abs/1001.1732v2
Read-back

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

QAlgorithms.Papers.Independent.Gap20.P04.CESupport

For any set S⊆R2S\subseteq\mathbb R^2S⊆R2, real number λ\lambdaλ, and point r=(r1,r2)∈R2r=(r_1,r_2)\in\mathbb R^2r=(r1​,r2​)∈R2, this predicate means that r∈Sr\in Sr∈S and

s1−λs2≤r1−λr2for every s=(s1,s2)∈S.s_1-\lambda s_2\le r_1-\lambda r_2 \quad\text{for every }s=(s_1,s_2)\in S.s1​−λs2​≤r1​−λr2​for every s=(s1​,s2​)∈S.

Thus rrr attains the maximum of this linear expression on SSS. There is no sign restriction on λ\lambdaλ or on either coordinate; if SSS is empty, the predicate is false because it requires r∈Sr\in Sr∈S.

QAlgorithms.Papers.Independent.Gap20.P04.CEUpper

For any set S⊆R2S\subseteq\mathbb R^2S⊆R2 and point r=(r1,r2)∈R2r=(r_1,r_2)\in\mathbb R^2r=(r1​,r2​)∈R2, this property means that r∈Sr\in Sr∈S and every s=(s1,s2)∈Ss=(s_1,s_2)\in Ss=(s1​,s2​)∈S satisfying s2≤r2s_2\le r_2s2​≤r2​ also satisfies s1≤r1s_1\le r_1s1​≤r1​. Both comparisons include equality. If SSS is empty, no point satisfies this property.

QAlgorithms.Papers.Independent.Gap20.P04.CQSupport

For any set S⊆R2S\subseteq\mathbb R^2S⊆R2, any real number λ\lambdaλ, and any pair r=(r1,r2)∈R2r=(r_1,r_2)\in\mathbb R^2r=(r1​,r2​)∈R2, this proposition means

r∈Sand∀(s1,s2)∈S,s1+λs2≤r1+λr2.r\in S \quad\text{and}\quad \forall(s_1,s_2)\in S,\qquad s_1+\lambda s_2\le r_1+\lambda r_2.r∈Sand∀(s1​,s2​)∈S,s1​+λs2​≤r1​+λr2​.

Thus rrr must belong to SSS and attain the greatest value of the displayed linear functional on SSS. The parameter λ\lambdaλ may be negative, zero, or positive; no coordinate nonnegativity or uniqueness is required. For S=∅S=\varnothingS=∅, the proposition is false.

QAlgorithms.Papers.Independent.Gap20.P04.DephasedReplacement

For a type III with decidable equality and two purified input families e,te,te,t, this property means there exists a bijection fff from the labels {0,…,e.labels−1}\{0,\ldots,e.\mathrm{labels}-1\}{0,…,e.labels−1} to {0,…,t.labels−1}\{0,\ldots,t.\mathrm{labels}-1\}{0,…,t.labels−1} such that, for every label xxx, t.probf(x)=e.probxt.\mathrm{prob}_{f(x)}=e.\mathrm{prob}_xt.probf(x)​=e.probx​ and

∑a<t.referencet.ψf(x)(a,i) t.ψf(x)(a,j)‾={∑a<e.reference∣e.ψx(a,i)∣2,i=j,0,i≠jfor all i,j∈I.\sum_{a<t.\mathrm{reference}} t.\psi_{f(x)}(a,i)\,\overline{t.\psi_{f(x)}(a,j)} = \begin{cases} \displaystyle\sum_{a<e.\mathrm{reference}}|e.\psi_x(a,i)|^2,&i=j,\\ 0,&i\ne j \end{cases} \quad\text{for all }i,j\in I.a<t.reference∑​t.ψf(x)​(a,i)t.ψf(x)​(a,j)​=⎩⎨⎧​a<e.reference∑​∣e.ψx​(a,i)∣2,0,​i=j,i=j​for all i,j∈I.

Thus the reduced input matrix at each matched label is the diagonal part of the original reduced input matrix. No validity condition on either family is assumed: weights need not form a probability distribution, vectors need not be normalized, and reference sizes may be zero. When both label sets are empty, the condition is vacuous.

QAlgorithms.Papers.Independent.Gap20.P04.PureInputs

For a finite index type III and a purified input family eee, consisting of natural numbers m,rm,rm,r, weights px∈Rp_x\in\mathbb Rpx​∈R, and vectors ψx∈C{0,…,r−1}×I\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I}ψx​∈C{0,…,r−1}×I, this proposition means that for every label 0≤x<m0\le x<m0≤x<m there exists a vector vx∈CIv_x\in\mathbb C^Ivx​∈CI satisfying

∥vx∥=1,Tr⁡Cr∣ψx⟩⟨ψx∣=∣vx⟩⟨vx∣.\|v_x\|=1,\qquad \operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x| =|v_x\rangle\langle v_x|.∥vx​∥=1,TrCr​∣ψx​⟩⟨ψx​∣=∣vx​⟩⟨vx​∣.

Here ∣v⟩⟨v∣|v\rangle\langle v|∣v⟩⟨v∣ has entries vivj‾v_i\overline{v_j}vi​vj​​. The condition applies to every label, including labels of zero weight, and imposes no validity requirement on the family or probability requirement on its weights. If m=0m=0m=0, it holds vacuously.

QAlgorithms.Papers.Independent.Gap20.P04.PurifiedInputFamily.Valid

For a purified input family eee over a type III, with natural numbers L=e.labelsL=e.\mathrm{labels}L=e.labels and R=e.referenceR=e.\mathrm{reference}R=e.reference, real weights px=e.prob(x)p_x=e.\mathrm{prob}(x)px​=e.prob(x), and complex Euclidean vectors ψx=e.psi(x)\psi_x=e.\mathrm{psi}(x)ψx​=e.psi(x) indexed by {0,…,R−1}×I\{0,\ldots,R-1\}\times I{0,…,R−1}×I, validity means exactly

L>0,R>0,px≥0 for every x,∑x=0L−1px=1,∥ψx∥=1 for every x.L>0,\qquad R>0,\qquad p_x\ge0\ \text{for every }x,\qquad \sum_{x=0}^{L-1}p_x=1,\qquad \|\psi_x\|=1\ \text{for every }x.L>0,R>0,px​≥0 for every x,x=0∑L−1​px​=1,∥ψx​∥=1 for every x.

The norm requirement applies even to labels whose weight is zero; a family with no labels or no reference coordinates cannot be valid.

QAlgorithms.Papers.Independent.Gap20.P04.PurifiedInputFamily.average

For any type III and a purified input family eee with LLL labels, reference size RRR, real weights pxp_xpx​, and vectors ψx\psi_xψx​, the average is the complex matrix

ρ‾(i,j)=∑x=0L−1px∑h=0R−1ψx(h,i) ψx(h,j)‾.\overline\rho(i,j) =\sum_{x=0}^{L-1}p_x \sum_{h=0}^{R-1}\psi_x(h,i)\,\overline{\psi_x(h,j)}.ρ​(i,j)=x=0∑L−1​px​h=0∑R−1​ψx​(h,i)ψx​(h,j)​.

No validity condition is assumed, so the weights need not be nonnegative or sum to one, and the vectors need not be normalized. The matrix is zero if L=0L=0L=0 or R=0R=0R=0.

QAlgorithms.Papers.Independent.Gap20.P04.PurifiedInputFamily.input

For any type III, a purified input family eee with LLL labels, reference size RRR, and vectors ψx\psi_xψx​, and any label x∈{0,…,L−1}x\in\{0,\ldots,L-1\}x∈{0,…,L−1}, its input matrix is defined by

ρx(i,j)=∑h=0R−1ψx(h,i) ψx(h,j)‾(i,j∈I).\rho_x(i,j)=\sum_{h=0}^{R-1}\psi_x(h,i)\,\overline{\psi_x(h,j)} \qquad(i,j\in I).ρx​(i,j)=h=0∑R−1​ψx​(h,i)ψx​(h,j)​(i,j∈I).

Thus it sums the reference coordinate of the matrix whose entries are the corresponding amplitude times the conjugate amplitude. Validity of the family is not assumed. If R=0R=0R=0, this matrix is zero; if L=0L=0L=0, there is no label xxx to which the definition can be applied.

QAlgorithms.Papers.Independent.Gap20.P04.PurifiedInputFamily

For any type III, a purified input family consists of two natural numbers LLL and RRR, a real number pxp_xpx​ for each x∈{0,…,L−1}x\in\{0,\ldots,L-1\}x∈{0,…,L−1}, and a complex Euclidean vector ψx\psi_xψx​ indexed by {0,…,R−1}×I\{0,\ldots,R-1\}\times I{0,…,R−1}×I for each such xxx. This structure alone imposes no positivity, normalization, or nonemptiness requirements: LLL and RRR may be zero, the weights may be negative, and the vectors need not have norm one.

QAlgorithms.Papers.Independent.Gap20.P04.RepeatedMax

For any natural number nnn and any sets S,T⊆RS,T\subseteq\mathbb RS,T⊆R, this proposition means that there exists v∈Rv\in\mathbb Rv∈R such that

v∈S,(∀s∈S, s≤v),nv∈T,(∀t∈T, t≤nv).v\in S,\qquad (\forall s\in S,\ s\le v),\qquad nv\in T,\qquad (\forall t\in T,\ t\le nv).v∈S,(∀s∈S, s≤v),nv∈T,(∀t∈T, t≤nv).

Both greatest values must therefore belong to their respective sets. Neither set may be empty. The definition includes n=0n=0n=0, when it requires SSS to have a greatest element and TTT to have greatest element 000.

QAlgorithms.Papers.Independent.Gap20.P04.basisStatePreparation

For a finite type BBB, a type EEE, and any family vbv_bvb​ of complex Euclidean vectors indexed by EEE, this defines a function taking a complex B×BB\times BB×B matrix ρ\rhoρ to the E×EE\times EE×E matrix

Pv(ρ)=∑b∈Bρbb vbvb†,(Pv(ρ))ef=∑b∈Bρbb vb(e)vb(f)‾.\mathcal P_v(\rho)=\sum_{b\in B}\rho_{bb}\,v_bv_b^\dagger, \qquad \bigl(\mathcal P_v(\rho)\bigr)_{ef} =\sum_{b\in B}\rho_{bb}\,v_b(e)\overline{v_b(f)}.Pv​(ρ)=b∈B∑​ρbb​vb​vb†​,(Pv​(ρ))ef​=b∈B∑​ρbb​vb​(e)vb​(f)​.

Neither normalization of vbv_bvb​ nor a density-matrix condition on ρ\rhoρ is required. If BBB is empty, this is the zero matrix.

QAlgorithms.Papers.Independent.Gap20.P04.binaryCE

For finite types B,EB,EB,E with decidable equality, any complex matrix UUU with rows indexed by B×EB\times EB×E and columns indexed by {0,1}\{0,1\}{0,1}, and any μ∈R\mu\in\mathbb Rμ∈R, let ρx\rho_xρx​, x∈{0,1}x\in\{0,1\}x∈{0,1}, be diagonal with entry (μ)2(\sqrt{\mu})^2(μ​)2 at xxx and (1−μ)2(\sqrt{1-\mu})^2(1−μ​)2 at 1−x1-x1−x. Set ρˉ=(ρ0+ρ1)/2\bar\rho=(\rho_0+\rho_1)/2ρˉ​=(ρ0​+ρ1​)/2, B=Tr⁡E(UρˉU†)B=\operatorname{Tr}_E(U\bar\rho U^\dagger)B=TrE​(Uρˉ​U†), and Ex=Tr⁡B(UρxU†)E_x=\operatorname{Tr}_B(U\rho_xU^\dagger)Ex​=TrB​(Uρx​U†); these partial traces sum diagonal entries over the indicated register. With

S(Z)=−Re⁡tr⁡(cfc⁡[t↦tlog⁡2t](Z)),S(Z)=-\operatorname{Re}\operatorname{tr}\bigl(\operatorname{cfc}[t\mapsto t\log_2t](Z)\bigr),S(Z)=−Retr(cfc[t↦tlog2​t](Z)),

where cfc⁡\operatorname{cfc}cfc denotes continuous functional calculus, this defines

(S(ρ0)+S(ρ1)2+S(B)−S(E0)+S(E1)2,S(ρ0)+S(ρ1)2).\left( \frac{S(\rho_0)+S(\rho_1)}2+S(B)-\frac{S(E_0)+S(E_1)}2, \quad \frac{S(\rho_0)+S(\rho_1)}2 \right).(2S(ρ0​)+S(ρ1​)​+S(B)−2S(E0​)+S(E1​)​,2S(ρ0​)+S(ρ1​)​).

No isometry condition on UUU, nonemptiness condition on B,EB,EB,E, or restriction on μ\muμ is imposed. Real square roots of negative arguments are zero.

QAlgorithms.Papers.Independent.Gap20.P04.binaryCQ

For finite types B,EB,EB,E with decidable equality, any complex matrix UUU with rows indexed by B×EB\times EB×E and columns indexed by {0,1}\{0,1\}{0,1}, and any μ∈R\mu\in\mathbb Rμ∈R, define diagonal input matrices ρx\rho_xρx​, x∈{0,1}x\in\{0,1\}x∈{0,1}, by ρx(x,x)=(μ)2\rho_x(x,x)=(\sqrt{\mu})^2ρx​(x,x)=(μ​)2, ρx(1−x,1−x)=(1−μ)2\rho_x(1-x,1-x)=(\sqrt{1-\mu})^2ρx​(1−x,1−x)=(1−μ​)2, and zero off the diagonal. Put Bx=Tr⁡E(UρxU†)B_x=\operatorname{Tr}_E(U\rho_xU^\dagger)Bx​=TrE​(Uρx​U†) and Ex=Tr⁡B(UρxU†)E_x=\operatorname{Tr}_B(U\rho_xU^\dagger)Ex​=TrB​(Uρx​U†), where, for a matrix ZZZ on B×EB\times EB×E, (Tr⁡EZ)bc=∑eZ(b,e),(c,e)(\operatorname{Tr}_E Z)_{bc}=\sum_e Z_{(b,e),(c,e)}(TrE​Z)bc​=∑e​Z(b,e),(c,e)​ and (Tr⁡BZ)ef=∑bZ(b,e),(b,f)(\operatorname{Tr}_B Z)_{ef}=\sum_b Z_{(b,e),(b,f)}(TrB​Z)ef​=∑b​Z(b,e),(b,f)​. Writing H(Z)=−Re⁡tr⁡(cfc⁡[t↦tln⁡t](Z))H(Z)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[t\mapsto t\ln t](Z))H(Z)=−Retr(cfc[t↦tlnt](Z)) and S(Z)=−Re⁡tr⁡(cfc⁡[t↦tlog⁡2t](Z))S(Z)=-\operatorname{Re}\operatorname{tr}(\operatorname{cfc}[t\mapsto t\log_2t](Z))S(Z)=−Retr(cfc[t↦tlog2​t](Z)), with cfc⁡\operatorname{cfc}cfc denoting continuous functional calculus, this defines the pair

(H((B0+B1)/2)−12H(B0)−12H(B1)ln⁡2,S(B0)+S(B1)−S(E0)−S(E1)2).\left( \frac{H((B_0+B_1)/2)-\tfrac12H(B_0)-\tfrac12H(B_1)}{\ln2}, \quad \frac{S(B_0)+S(B_1)-S(E_0)-S(E_1)}2 \right).(ln2H((B0​+B1​)/2)−21​H(B0​)−21​H(B1​)​,2S(B0​)+S(B1​)−S(E0​)−S(E1​)​).

No isometry condition on UUU, nonemptiness condition on B,EB,EB,E, or restriction on μ\muμ is imposed; negative square-root arguments give zero.

QAlgorithms.Papers.Independent.Gap20.P04.binaryEnsemble

For every real number μ\muμ, this constructs a family with two labels x∈{0,1}x\in\{0,1\}x∈{0,1}, a reference register with two basis indices, weight 1/21/21/2 for each label, and vectors ψx∈C{0,1}×{0,1}\psi_x\in\mathbb C^{\{0,1\}\times\{0,1\}}ψx​∈C{0,1}×{0,1} whose coordinates are

ψx(a,i)={μ,a=i=x,1−μ,a=i≠x,0,a≠i.\psi_x(a,i)= \begin{cases} \sqrt{\mu},&a=i=x,\\ \sqrt{1-\mu},&a=i\ne x,\\ 0,&a\ne i. \end{cases}ψx​(a,i)=⎩⎨⎧​μ​,1−μ​,0,​a=i=x,a=i=x,a=i.​

The displayed real amplitudes are regarded as complex numbers. There is no restriction on μ\muμ; the real square root is zero on negative arguments, and the construction does not require these vectors to have norm one.

QAlgorithms.Papers.Independent.Gap20.P04.capacityCE

For finite index types I,B,EI,B,EI,B,E with decidable equality and any complex matrix U:CI→CB×EU:\mathbb C^I\to\mathbb C^{B\times E}U:CI→CB×E, this defines the Euclidean closure of all nonnegative pairs (C,Erate)(C,E_{\mathrm{rate}})(C,Erate​) admitting a positive natural number nnn, positive natural numbers m,rm,rm,r, nonnegative weights pxp_xpx​ summing to one, and unit vectors ψx∈C{0,…,r−1}×In\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I^n}ψx​∈C{0,…,r−1}×In, indexed by 0≤x<m0\le x<m0≤x<m, such that

nC≤∑xpxH(ρx)+H ⁣(∑xpxβx)−∑xpxH(ϵx),∑xpxH(ρx)≤nErate.nC\le\sum_xp_xH(\rho_x) +H\!\left(\sum_xp_x\beta_x\right)-\sum_xp_xH(\epsilon_x), \qquad \sum_xp_xH(\rho_x)\le nE_{\mathrm{rate}}.nC≤x∑​px​H(ρx​)+H(x∑​px​βx​)−x∑​px​H(ϵx​),x∑​px​H(ρx​)≤nErate​.

Here InI^nIn is the type of length-nnn strings over III,

(Un)(b,e),a=∏i=0n−1U(bi,ei),ai,ρx=Tr⁡Cr∣ψx⟩⟨ψx∣,βx=Tr⁡En(UnρxUn†),ϵx=Tr⁡Bn(UnρxUn†),(U_n)_{(b,e),a}=\prod_{i=0}^{n-1}U_{(b_i,e_i),a_i}, \quad \rho_x=\operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x|, \quad \beta_x=\operatorname{Tr}_{E^n}(U_n\rho_xU_n^\dagger), \quad \epsilon_x=\operatorname{Tr}_{B^n}(U_n\rho_xU_n^\dagger),(Un​)(b,e),a​=i=0∏n−1​U(bi​,ei​),ai​​,ρx​=TrCr​∣ψx​⟩⟨ψx​∣,βx​=TrEn​(Un​ρx​Un†​),ϵx​=TrBn​(Un​ρx​Un†​),

and H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied by continuous functional calculus. Limits of witnessed pairs are included by the closure. Block length zero is excluded; zero-weight labels still require unit vectors, and UUU need not be an isometry. If III is empty, the set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.capacityCQ

For finite index types I,B,EI,B,EI,B,E with decidable equality and any complex matrix U:CI→CB×EU:\mathbb C^I\to\mathbb C^{B\times E}U:CI→CB×E, this defines the Euclidean closure of the following set of pairs (C,Q)∈R2(C,Q)\in\mathbb R^2(C,Q)∈R2: C,Q≥0C,Q\ge0C,Q≥0, and there exist a positive natural number nnn, positive natural numbers m,rm,rm,r, nonnegative weights pxp_xpx​ summing to one, and unit vectors ψx∈C{0,…,r−1}×In\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I^n}ψx​∈C{0,…,r−1}×In, indexed by 0≤x<m0\le x<m0≤x<m, such that

nC≤H ⁣(∑xpxβx)−∑xpxH(βx),nQ≤∑xpx(H(βx)−H(ϵx)).nC\le H\!\left(\sum_xp_x\beta_x\right)-\sum_xp_xH(\beta_x), \qquad nQ\le\sum_xp_x\bigl(H(\beta_x)-H(\epsilon_x)\bigr).nC≤H(x∑​px​βx​)−x∑​px​H(βx​),nQ≤x∑​px​(H(βx​)−H(ϵx​)).

Here InI^nIn denotes the functions {0,…,n−1}→I\{0,\ldots,n-1\}\to I{0,…,n−1}→I,

(Un)(b,e),a=∏i=0n−1U(bi,ei),ai,ρx=Tr⁡Cr∣ψx⟩⟨ψx∣,βx=Tr⁡En(UnρxUn†),ϵx=Tr⁡Bn(UnρxUn†),(U_n)_{(b,e),a}=\prod_{i=0}^{n-1}U_{(b_i,e_i),a_i}, \quad \rho_x=\operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x|, \quad \beta_x=\operatorname{Tr}_{E^n}(U_n\rho_xU_n^\dagger), \quad \epsilon_x=\operatorname{Tr}_{B^n}(U_n\rho_xU_n^\dagger),(Un​)(b,e),a​=i=0∏n−1​U(bi​,ei​),ai​​,ρx​=TrCr​∣ψx​⟩⟨ψx​∣,βx​=TrEn​(Un​ρx​Un†​),ϵx​=TrBn​(Un​ρx​Un†​),

and H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)) for f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t, applied by continuous functional calculus. The closure includes limits of such pairs even when no single witness realizes the limiting pair. Block length zero is excluded, zero weights are allowed, and no isometry assumption on UUU is imposed. If III is empty, the set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.capacityCQE

For finite index types I,B,EI,B,EI,B,E with decidable equality and any complex matrix U:CI→CB×EU:\mathbb C^I\to\mathbb C^{B\times E}U:CI→CB×E, this defines the closure in R3\mathbb R^3R3 of all nonnegative triples (r0,r1,r2)(r_0,r_1,r_2)(r0​,r1​,r2​) admitting a positive natural number nnn, positive natural numbers m,rm,rm,r, nonnegative weights pxp_xpx​ summing to one, and unit vectors ψx∈C{0,…,r−1}×In\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I^n}ψx​∈C{0,…,r−1}×In, indexed by 0≤x<m0\le x<m0≤x<m. Put

(Un)(b,e),a=∏i=0n−1U(bi,ei),ai,ρx=Tr⁡Cr∣ψx⟩⟨ψx∣,βx=Tr⁡En(UnρxUn†),ϵx=Tr⁡Bn(UnρxUn†),(U_n)_{(b,e),a}=\prod_{i=0}^{n-1}U_{(b_i,e_i),a_i}, \quad \rho_x=\operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x|, \quad \beta_x=\operatorname{Tr}_{E^n}(U_n\rho_xU_n^\dagger), \quad \epsilon_x=\operatorname{Tr}_{B^n}(U_n\rho_xU_n^\dagger),(Un​)(b,e),a​=i=0∏n−1​U(bi​,ei​),ai​​,ρx​=TrCr​∣ψx​⟩⟨ψx​∣,βx​=TrEn​(Un​ρx​Un†​),ϵx​=TrBn​(Un​ρx​Un†​),

where In,Bn,EnI^n,B^n,E^nIn,Bn,En denote length-nnn strings, and define

A=∑xpxH(ρx),B=H ⁣(∑xpxβx),Bc=∑xpxH(βx),Ec=∑xpxH(ϵx).A=\sum_xp_xH(\rho_x),\quad B=H\!\left(\sum_xp_x\beta_x\right),\quad B_c=\sum_xp_xH(\beta_x),\quad E_c=\sum_xp_xH(\epsilon_x).A=x∑​px​H(ρx​),B=H(x∑​px​βx​),Bc​=x∑​px​H(βx​),Ec​=x∑​px​H(ϵx​).

The witness must satisfy

n(r0+2r1)≤A+B−Ec,nr1≤Bc−Ec+nr2,n(r0+r1)≤B−Ec+nr2.n(r_0+2r_1)\le A+B-E_c,\qquad nr_1\le B_c-E_c+nr_2,\qquad n(r_0+r_1)\le B-E_c+nr_2.n(r0​+2r1​)≤A+B−Ec​,nr1​≤Bc​−Ec​+nr2​,n(r0​+r1​)≤B−Ec​+nr2​.

Here H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied by continuous functional calculus. The closure also includes limits without a single realizing witness. Block length zero is excluded, zero weights are allowed with unit vectors at every label, and no isometry assumption on UUU is imposed. If III is empty, the set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.ceHull

For any function f:R→R2f:\mathbb R\to\mathbb R^2f:R→R2, this defines the closure, in the usual topology of R2\mathbb R^2R2, of the real convex hull of

{(r1,r2):r1≥0, r2≥0, ∃μ∈[0,12], r1≤f(μ)1, f(μ)2≤r2}.\left\{(r_1,r_2):r_1\ge0,\ r_2\ge0,\ \exists\mu\in[0,\tfrac12],\ r_1\le f(\mu)_1,\ f(\mu)_2\le r_2\right\}.{(r1​,r2​):r1​≥0, r2​≥0, ∃μ∈[0,21​], r1​≤f(μ)1​, f(μ)2​≤r2​}.

The convex hull consists of finite convex combinations of these points, and its closure also includes their limits. No continuity or boundedness assumption is imposed on fff. The second coordinate has a lower bound and no specified upper bound. If f(μ)1<0f(\mu)_1<0f(μ)1​<0 for every μ∈[0,12]\mu\in[0,\tfrac12]μ∈[0,21​], the resulting set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.ceScore

For finite index types I,B,EI,B,EI,B,E with decidable equality, a complex matrix U:CI→CB×EU:\mathbb C^I\to\mathbb C^{B\times E}U:CI→CB×E, a real number λ\lambdaλ, and a family eee consisting of natural numbers m,rm,rm,r, real weights pxp_xpx​, and vectors ψx∈C{0,…,r−1}×I\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I}ψx​∈C{0,…,r−1}×I for 0≤x<m0\le x<m0≤x<m, define

ρx=Tr⁡Cr∣ψx⟩⟨ψx∣,ρˉ=∑xpxρx,BU(ρ)=Tr⁡E(UρU†),EU(ρ)=Tr⁡B(UρU†).\rho_x=\operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x|, \qquad \bar\rho=\sum_xp_x\rho_x, \qquad B_U(\rho)=\operatorname{Tr}_E(U\rho U^\dagger), \qquad E_U(\rho)=\operatorname{Tr}_B(U\rho U^\dagger).ρx​=TrCr​∣ψx​⟩⟨ψx​∣,ρˉ​=x∑​px​ρx​,BU​(ρ)=TrE​(UρU†),EU​(ρ)=TrB​(UρU†).

Writing H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), where f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t is applied by continuous functional calculus, the defined score is

H(BU(ρˉ))−∑xpxH(EU(ρx))+(1−λ)∑xpxH(ρx).H(B_U(\bar\rho))-\sum_xp_xH(E_U(\rho_x)) +(1-\lambda)\sum_xp_xH(\rho_x).H(BU​(ρˉ​))−x∑​px​H(EU​(ρx​))+(1−λ)x∑​px​H(ρx​).

There is no requirement here that UUU be an isometry or that eee be valid: its weights need not form a probability distribution, its vectors need not be normalized, and either natural-number dimension may be zero; sums over no labels are zero.

QAlgorithms.Papers.Independent.Gap20.P04.cloneDelta

For every natural number NNN, including N=0N=0N=0, this defines the real number

N(N+1)2.\frac{N(N+1)}2.2N(N+1)​.

In particular, its value at N=0N=0N=0 is zero.

QAlgorithms.Papers.Independent.Gap20.P04.cloneEta

For every natural number NNN, every real number μ\muμ, and every integer index iii with 0≤i<N0\le i<N0≤i<N, this defines

(N−1−2i)μ+i+1,(N-1-2i)\mu+i+1,(N−1−2i)μ+i+1,

where the subtraction is real subtraction. No restriction is imposed on μ\muμ. When N=0N=0N=0, there are no admissible indices iii.

QAlgorithms.Papers.Independent.Gap20.P04.cloneLambda

For every natural number NNN, every real number μ\muμ, and every integer index iii with 0≤i<N+10\le i<N+10≤i<N+1, this defines

(N−2i)μ+i,(N-2i)\mu+i,(N−2i)μ+i,

with all arithmetic in this expression performed in the real numbers. There is no restriction on μ\muμ; when N=0N=0N=0, the only index is i=0i=0i=0, and the value is zero.

QAlgorithms.Papers.Independent.Gap20.P04.cloningCE

For every natural number NNN and real number μ\muμ, this defines

(log⁡2(N+1)+h(μ)−HE, h(μ)),\left( \log_2(N+1)+h(\mu)-H_E,\ h(\mu) \right),(log2​(N+1)+h(μ)−HE​, h(μ)),

where

h(x)=−xlog⁡x−(1−x)log⁡(1−x)log⁡2,HE=−∑i=0N−1(N−1−2i)μ+i+1N(N+1)/2log⁡2 ⁣((N−1−2i)μ+i+1N(N+1)/2).h(x)=\frac{-x\log x-(1-x)\log(1-x)}{\log 2}, \qquad H_E=-\sum_{i=0}^{N-1} \frac{(N-1-2i)\mu+i+1}{N(N+1)/2} \log_2\!\left(\frac{(N-1-2i)\mu+i+1}{N(N+1)/2}\right).h(x)=log2−xlogx−(1−x)log(1−x)​,HE​=−i=0∑N−1​N(N+1)/2(N−1−2i)μ+i+1​log2​(N(N+1)/2(N−1−2i)μ+i+1​).

No restriction is imposed on μ\muμ. All divisions and logarithms are total, with division by zero and log⁡0\log 0log0 equal to zero and logarithms of negative real arguments taken at their absolute values. At N=0N=0N=0, the sum is empty and the pair is (h(μ),h(μ))(h(\mu),h(\mu))(h(μ),h(μ)).

QAlgorithms.Papers.Independent.Gap20.P04.cloningCQ

For every natural number NNN and real number μ\muμ, put

Δ=N(N+1)2,HB=−∑i=0N(N−2i)μ+iΔlog⁡2 ⁣((N−2i)μ+iΔ),HE=−∑i=0N−1(N−1−2i)μ+i+1Δlog⁡2 ⁣((N−1−2i)μ+i+1Δ).\Delta=\frac{N(N+1)}2,\qquad H_B=-\sum_{i=0}^{N}\frac{(N-2i)\mu+i}{\Delta} \log_2\!\left(\frac{(N-2i)\mu+i}{\Delta}\right), \qquad H_E=-\sum_{i=0}^{N-1}\frac{(N-1-2i)\mu+i+1}{\Delta} \log_2\!\left(\frac{(N-1-2i)\mu+i+1}{\Delta}\right).Δ=2N(N+1)​,HB​=−i=0∑N​Δ(N−2i)μ+i​log2​(Δ(N−2i)μ+i​),HE​=−i=0∑N−1​Δ(N−1−2i)μ+i+1​log2​(Δ(N−1−2i)μ+i+1​).

This defines the pair (log⁡2(N+1)−HB, HB−HE)\bigl(\log_2(N+1)-H_B,\ H_B-H_E\bigr)(log2​(N+1)−HB​, HB​−HE​). There is no restriction on μ\muμ and no hypothesis that the entries in either sum form a probability distribution. Division by zero is defined to be zero, log⁡20=0\log_2 0=0log2​0=0, and logarithms of negative arguments use their absolute values; consequently, at N=0N=0N=0 both sums are zero and the pair is (0,0)(0,0)(0,0).

QAlgorithms.Papers.Independent.Gap20.P04.conditionalEnvironmentEntropy

For finite types I,B,EI,B,EI,B,E, with decidable equality on EEE, an arbitrary complex matrix UUU with rows indexed by B×EB\times EB×E and columns by III, and a purified input family eee over III with LLL labels, reference size RRR, weights pxp_xpx​, and vectors ψx\psi_xψx​, put ρx(i,j)=∑h=0R−1ψx(h,i)ψx(h,j)‾\rho_x(i,j)=\sum_{h=0}^{R-1}\psi_x(h,i)\overline{\psi_x(h,j)}ρx​(i,j)=∑h=0R−1​ψx​(h,i)ψx​(h,j)​. The conditional environment entropy is

∑x=0L−1pxH2(Ex),(Ex)a,a′=∑b∈B(UρxU†)(b,a),(b,a′),\sum_{x=0}^{L-1}p_x H_2(E_x), \qquad (E_x)_{a,a'}=\sum_{b\in B}(U\rho_xU^\dagger)_{(b,a),(b,a')},x=0∑L−1​px​H2​(Ex​),(Ex​)a,a′​=b∈B∑​(Uρx​U†)(b,a),(b,a′)​,

where H2(X)=−Re⁡tr⁡[f(X)]H_2(X)=-\operatorname{Re}\operatorname{tr}[f(X)]H2​(X)=−Retr[f(X)], with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t evaluated by continuous functional calculus. No validity, density-matrix, or isometry hypothesis is imposed; the label sum is zero when L=0L=0L=0.

QAlgorithms.Papers.Independent.Gap20.P04.conditionalReceiverEntropy

For finite types I,B,EI,B,EI,B,E, with decidable equality on BBB, an arbitrary complex matrix UUU with rows indexed by B×EB\times EB×E and columns by III, and a purified input family eee over III with LLL labels, reference size RRR, weights pxp_xpx​, and vectors ψx\psi_xψx​, put ρx(i,j)=∑h=0R−1ψx(h,i)ψx(h,j)‾\rho_x(i,j)=\sum_{h=0}^{R-1}\psi_x(h,i)\overline{\psi_x(h,j)}ρx​(i,j)=∑h=0R−1​ψx​(h,i)ψx​(h,j)​. The conditional receiver entropy is

∑x=0L−1pxH2(Bx),(Bx)b,b′=∑a∈E(UρxU†)(b,a),(b′,a),\sum_{x=0}^{L-1}p_x H_2(B_x), \qquad (B_x)_{b,b'}=\sum_{a\in E}(U\rho_xU^\dagger)_{(b,a),(b',a)},x=0∑L−1​px​H2​(Bx​),(Bx​)b,b′​=a∈E∑​(Uρx​U†)(b,a),(b′,a)​,

where H2(X)=−Re⁡tr⁡[f(X)]H_2(X)=-\operatorname{Re}\operatorname{tr}[f(X)]H2​(X)=−Retr[f(X)], with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t evaluated by continuous functional calculus. No validity, density-matrix, or isometry hypothesis is imposed; the label sum is zero when L=0L=0L=0.

QAlgorithms.Papers.Independent.Gap20.P04.cqHull

For any function f:R→R2f:\mathbb R\to\mathbb R^2f:R→R2, this defines the closure, in the usual topology of R2\mathbb R^2R2, of the real convex hull of

{(r1,r2):r1≥0, r2≥0, ∃μ∈[0,12], r1≤f(μ)1, r2≤f(μ)2}.\left\{(r_1,r_2):r_1\ge0,\ r_2\ge0,\ \exists\mu\in[0,\tfrac12],\ r_1\le f(\mu)_1,\ r_2\le f(\mu)_2\right\}.{(r1​,r2​):r1​≥0, r2​≥0, ∃μ∈[0,21​], r1​≤f(μ)1​, r2​≤f(μ)2​}.

Thus the convex hull consists of finite convex combinations of these points, and the closure additionally includes their limits. No continuity or boundedness assumption is imposed on fff. A parameter contributes points only when both coordinates of f(μ)f(\mu)f(μ) are nonnegative; if no parameter does so, the resulting set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.cqScore

For finite types I,B,EI,B,EI,B,E, with decidable equality on BBB and EEE, let UUU be an arbitrary complex matrix from III to B×EB\times EB×E, let λ∈R\lambda\in\mathbb Rλ∈R, and let eee be a purified input family with LLL labels, reference size RRR, weights pxp_xpx​, and vectors ψx\psi_xψx​. Define ρx(i,j)=∑h=0R−1ψx(h,i)ψx(h,j)‾\rho_x(i,j)=\sum_{h=0}^{R-1}\psi_x(h,i)\overline{\psi_x(h,j)}ρx​(i,j)=∑h=0R−1​ψx​(h,i)ψx​(h,j)​, Bx(b,b′)=∑a∈E(UρxU†)(b,a),(b′,a)B_x(b,b')=\sum_{a\in E}(U\rho_xU^\dagger)_{(b,a),(b',a)}Bx​(b,b′)=∑a∈E​(Uρx​U†)(b,a),(b′,a)​, and Ex(a,a′)=∑b∈B(UρxU†)(b,a),(b,a′)E_x(a,a')=\sum_{b\in B}(U\rho_xU^\dagger)_{(b,a),(b,a')}Ex​(a,a′)=∑b∈B​(Uρx​U†)(b,a),(b,a′)​. The score is

Hnat ⁣(∑xpxBx)−∑xpxHnat(Bx)log⁡2+λ(∑xpxH2(Bx)−∑xpxH2(Ex)),\frac{H_{\mathrm{nat}}\!\left(\sum_xp_xB_x\right)-\sum_xp_xH_{\mathrm{nat}}(B_x)}{\log 2} +\lambda\left(\sum_xp_xH_2(B_x)-\sum_xp_xH_2(E_x)\right),log2Hnat​(∑x​px​Bx​)−∑x​px​Hnat​(Bx​)​+λ(x∑​px​H2​(Bx​)−x∑​px​H2​(Ex​)),

where Hnat(X)=−Re⁡tr⁡[(t↦tlog⁡t)(X)]H_{\mathrm{nat}}(X)=-\operatorname{Re}\operatorname{tr}[(t\mapsto t\log t)(X)]Hnat​(X)=−Retr[(t↦tlogt)(X)] and H2(X)=−Re⁡tr⁡[(t↦tlog⁡2t)(X)]H_2(X)=-\operatorname{Re}\operatorname{tr}[(t\mapsto t\log_2t)(X)]H2​(X)=−Retr[(t↦tlog2​t)(X)], both using continuous functional calculus. There is no restriction on the sign of λ\lambdaλ, no validity requirement on eee, and no isometry requirement on UUU; L=0L=0L=0 is allowed and gives score zero.

QAlgorithms.Papers.Independent.Gap20.P04.degradingKraus

For types B,EB,EB,E, with decidable equality on BBB, any family vbv_bvb​ of complex Euclidean vectors indexed by EEE, and any b∈Bb\in Bb∈B, this defines an E×BE\times BE×B complex matrix KbK_bKb​ by

(Kb)e,c={vb(e),c=b,0,c≠b.(K_b)_{e,c}= \begin{cases} v_b(e),&c=b,\\ 0,&c\ne b. \end{cases}(Kb​)e,c​={vb​(e),0,​c=b,c=b.​

No normalization or completeness condition is imposed on this family of matrices.

QAlgorithms.Papers.Independent.Gap20.P04.dephasingCE

For arbitrary real numbers p,μp,\mup,μ, this defines

(1+h(μ)−h(Γ(μ,p)), h(μ)),Γ(μ,p)=12+121−16p2(1−p2)μ(1−μ),\left(1+h(\mu)-h(\Gamma(\mu,p)),\ h(\mu)\right), \qquad \Gamma(\mu,p)=\frac12+\frac12\sqrt{1-16\frac p2\left(1-\frac p2\right)\mu(1-\mu)},(1+h(μ)−h(Γ(μ,p)), h(μ)),Γ(μ,p)=21​+21​1−162p​(1−2p​)μ(1−μ)​,

where h(x)=[−xlog⁡x−(1−x)log⁡(1−x)]/log⁡2h(x)=[-x\log x-(1-x)\log(1-x)]/\log 2h(x)=[−xlogx−(1−x)log(1−x)]/log2. Neither parameter is restricted to a probability interval. The square root is zero for negative arguments, log⁡0=0\log 0=0log0=0, and logarithms of negative real arguments are interpreted as logarithms of their absolute values.

QAlgorithms.Papers.Independent.Gap20.P04.dephasingCQ

For arbitrary real numbers p,μp,\mup,μ, this defines the ordered pair

(h(μ), h(μ)−h(Γ(μ,p)))\left(h(\mu),\,h(\mu)-h(\Gamma(\mu,p))\right)(h(μ),h(μ)−h(Γ(μ,p)))

with its first coordinate replaced by 1−h(μ)1-h(\mu)1−h(μ); explicitly, the pair is

(1−h(μ), h(μ)−h(Γ(μ,p))),Γ(μ,p)=12+121−16p2(1−p2)μ(1−μ),\left(1-h(\mu),\ h(\mu)-h(\Gamma(\mu,p))\right), \qquad \Gamma(\mu,p)=\frac12+\frac12\sqrt{1-16\frac p2\left(1-\frac p2\right)\mu(1-\mu)},(1−h(μ), h(μ)−h(Γ(μ,p))),Γ(μ,p)=21​+21​1−162p​(1−2p​)μ(1−μ)​,

where h(x)=[−xlog⁡x−(1−x)log⁡(1−x)]/log⁡2h(x)=[-x\log x-(1-x)\log(1-x)]/\log 2h(x)=[−xlogx−(1−x)log(1−x)]/log2. There are no restrictions on ppp or μ\muμ. These expressions use total real functions: the square root of a negative number is zero, log⁡0=0\log 0=0log0=0, and the real logarithm at a negative argument equals the logarithm of its absolute value.

QAlgorithms.Papers.Independent.Gap20.P04.ensembleCoherentBits

For finite types I,B,EI,B,EI,B,E, with decidable equality on BBB and EEE, let UUU be an arbitrary complex matrix from III to B×EB\times EB×E, and let eee be a purified input family with LLL labels, reference size RRR, weights pxp_xpx​, and vectors ψx\psi_xψx​. Define ρx(i,j)=∑h=0R−1ψx(h,i)ψx(h,j)‾\rho_x(i,j)=\sum_{h=0}^{R-1}\psi_x(h,i)\overline{\psi_x(h,j)}ρx​(i,j)=∑h=0R−1​ψx​(h,i)ψx​(h,j)​, Bx(b,b′)=∑a∈E(UρxU†)(b,a),(b′,a)B_x(b,b')=\sum_{a\in E}(U\rho_xU^\dagger)_{(b,a),(b',a)}Bx​(b,b′)=∑a∈E​(Uρx​U†)(b,a),(b′,a)​, and Ex(a,a′)=∑b∈B(UρxU†)(b,a),(b,a′)E_x(a,a')=\sum_{b\in B}(U\rho_xU^\dagger)_{(b,a),(b,a')}Ex​(a,a′)=∑b∈B​(Uρx​U†)(b,a),(b,a′)​. The ensemble coherent bits are

∑xpxH2(Bx)−∑xpxH2(Ex),\sum_xp_xH_2(B_x)-\sum_xp_xH_2(E_x),x∑​px​H2​(Bx​)−x∑​px​H2​(Ex​),

where H2(X)=−Re⁡tr⁡[f(X)]H_2(X)=-\operatorname{Re}\operatorname{tr}[f(X)]H2​(X)=−Retr[f(X)], with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t evaluated by continuous functional calculus. No validity or isometry assumption is required, and the result is zero when L=0L=0L=0.

QAlgorithms.Papers.Independent.Gap20.P04.ensembleReceiverEntropy

For finite types I,B,EI,B,EI,B,E, with decidable equality on BBB, let UUU be a complex matrix with rows indexed by B×EB\times EB×E and columns by III, and let eee be a purified input family over III, with LLL labels, reference size RRR, weights pxp_xpx​, and vectors ψx\psi_xψx​. Set ρx(i,j)=∑h=0R−1ψx(h,i)ψx(h,j)‾\rho_x(i,j)=\sum_{h=0}^{R-1}\psi_x(h,i)\overline{\psi_x(h,j)}ρx​(i,j)=∑h=0R−1​ψx​(h,i)ψx​(h,j)​ and ρ‾=∑xpxρx\overline\rho=\sum_xp_x\rho_xρ​=∑x​px​ρx​. The ensemble receiver entropy is

H2 ⁣(BU(ρ‾)),BU(X)b,b′=∑a∈E(UXU†)(b,a),(b′,a),H_2\!\left(\mathcal B_U(\overline\rho)\right), \qquad \mathcal B_U(X)_{b,b'}=\sum_{a\in E}(UXU^\dagger)_{(b,a),(b',a)},H2​(BU​(ρ​)),BU​(X)b,b′​=a∈E∑​(UXU†)(b,a),(b′,a)​,

where H2(X)=−Re⁡tr⁡[f(X)]H_2(X)=-\operatorname{Re}\operatorname{tr}[f(X)]H2​(X)=−Retr[f(X)], with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t evaluated by continuous functional calculus. Neither validity of eee nor an isometry condition on UUU is assumed. Empty finite index types and zero label or reference sizes are allowed.

QAlgorithms.Papers.Independent.Gap20.P04.entropyVector

For every type KKK equipped with a finite enumeration and every real-valued function p:K→Rp:K\to\mathbb Rp:K→R, this defines

−∑i∈Kpilog⁡2pi.-\sum_{i\in K}p_i\log_2 p_i.−i∈K∑​pi​log2​pi​.

No nonnegativity or normalization condition is imposed on ppp. The logarithm is the total real logarithm divided by log⁡2\log 2log2, so log⁡20=0\log_2 0=0log2​0=0, and for negative arguments it equals log⁡2∣pi∣\log_2|p_i|log2​∣pi​∣. If KKK is empty, the value is zero.

QAlgorithms.Papers.Independent.Gap20.P04.gdDilation

For types I,EI,EI,E, with decidable equality on III, and any family of complex Euclidean vectors viv_ivi​ indexed by EEE, this defines the complex matrix VVV with rows indexed by I×EI\times EI×E and columns indexed by III through

V(b,e),i={vi(e),b=i,0,b≠i.V_{(b,e),i}= \begin{cases} v_i(e),&b=i,\\ 0,&b\ne i. \end{cases}V(b,e),i​={vi​(e),0,​b=i,b=i.​

No normalization of the vectors or isometry condition is required.

QAlgorithms.Papers.Independent.Gap20.P04.hadamardCoefficient

For finite types I,EI,EI,E, a type BBB, families ζb∈CI\zeta_b\in\mathbb C^Iζb​∈CI and ξb∈CE\xi_b\in\mathbb C^Eξb​∈CE indexed by b∈Bb\in Bb∈B, and an arbitrary complex I×II\times II×I matrix ρ\rhoρ, this defines a complex B×BB\times BB×B matrix CCC whose entries are

Cbc=(∑i∈I∑j∈Iζb(i)‾ ρij ζc(j))(∑e∈Eξc(e)‾ ξb(e)).C_{bc} = \left(\sum_{i\in I}\sum_{j\in I} \overline{\zeta_b(i)}\,\rho_{ij}\,\zeta_c(j)\right) \left(\sum_{e\in E}\overline{\xi_c(e)}\,\xi_b(e)\right).Cbc​=​i∈I∑​j∈I∑​ζb​(i)​ρij​ζc​(j)​(e∈E∑​ξc​(e)​ξb​(e)).

There are no normalization, orthogonality, positivity, or trace assumptions. If III or EEE is empty, every entry is zero.

QAlgorithms.Papers.Independent.Gap20.P04.holevoValues

For finite index types I,B,EI,B,EI,B,E with decidable equality and any complex matrix U:CI→CB×EU:\mathbb C^I\to\mathbb C^{B\times E}U:CI→CB×E, this is the set of real numbers

H ⁣(∑xpxβx)−∑xpxH(βx),βx=Tr⁡E(UρxU†),H\!\left(\sum_xp_x\beta_x\right)-\sum_xp_xH(\beta_x), \qquad \beta_x=\operatorname{Tr}_E(U\rho_xU^\dagger),H(x∑​px​βx​)−x∑​px​H(βx​),βx​=TrE​(Uρx​U†),

obtained as follows: choose positive natural numbers m,rm,rm,r, nonnegative real weights pxp_xpx​ summing to one, and unit vectors ψx∈C{0,…,r−1}×I\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I}ψx​∈C{0,…,r−1}×I, for 0≤x<m0\le x<m0≤x<m; set ρx=Tr⁡Cr∣ψx⟩⟨ψx∣\rho_x=\operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x|ρx​=TrCr​∣ψx​⟩⟨ψx​∣, and require, for every xxx, that ρx=∣vx⟩⟨vx∣\rho_x=|v_x\rangle\langle v_x|ρx​=∣vx​⟩⟨vx​∣ for some unit vector vx∈CIv_x\in\mathbb C^Ivx​∈CI. Here H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied by continuous functional calculus; the displayed entropy difference is equivalently the corresponding natural-logarithm entropy difference divided by log⁡2\log2log2. Zero weights are permitted, with the same unit-vector and purity conditions on their labels. No isometry condition on UUU is imposed, so its receiver outputs are not required to have trace one. If III is empty, the set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.inputEntropy

For a finite type III with decidable equality and a purified input family eee with LLL labels, reference size RRR, weights pxp_xpx​, and vectors ψx\psi_xψx​, define ρx(i,j)=∑h=0R−1ψx(h,i)ψx(h,j)‾\rho_x(i,j)=\sum_{h=0}^{R-1}\psi_x(h,i)\overline{\psi_x(h,j)}ρx​(i,j)=∑h=0R−1​ψx​(h,i)ψx​(h,j)​. The input entropy is

∑x=0L−1pxH2(ρx),H2(X)=−Re⁡tr⁡ ⁣[f(X)],f(t)=tlog⁡2t,\sum_{x=0}^{L-1}p_x H_2(\rho_x), \qquad H_2(X)=-\operatorname{Re}\operatorname{tr}\!\left[f(X)\right], \quad f(t)=t\log_2 t,x=0∑L−1​px​H2​(ρx​),H2​(X)=−Retr[f(X)],f(t)=tlog2​t,

where f(X)f(X)f(X) is evaluated using the continuous functional calculus. No validity or density-matrix hypothesis is imposed. The sum is zero when L=0L=0L=0.

QAlgorithms.Papers.Independent.Gap20.P04.jointInfo

For finite types I,B,EI,B,EI,B,E, with decidable equality on each, let UUU be an arbitrary complex matrix from III to B×EB\times EB×E, and let eee be a purified input family with LLL labels, reference size RRR, weights pxp_xpx​, and vectors ψx\psi_xψx​. Define ρx(i,j)=∑h=0R−1ψx(h,i)ψx(h,j)‾\rho_x(i,j)=\sum_{h=0}^{R-1}\psi_x(h,i)\overline{\psi_x(h,j)}ρx​(i,j)=∑h=0R−1​ψx​(h,i)ψx​(h,j)​, ρ‾=∑xpxρx\overline\rho=\sum_xp_x\rho_xρ​=∑x​px​ρx​, B‾(b,b′)=∑a∈E(Uρ‾U†)(b,a),(b′,a)\overline B(b,b')=\sum_{a\in E}(U\overline\rho U^\dagger)_{(b,a),(b',a)}B(b,b′)=∑a∈E​(Uρ​U†)(b,a),(b′,a)​, and Ex(a,a′)=∑b∈B(UρxU†)(b,a),(b,a′)E_x(a,a')=\sum_{b\in B}(U\rho_xU^\dagger)_{(b,a),(b,a')}Ex​(a,a′)=∑b∈B​(Uρx​U†)(b,a),(b,a′)​. The joint information is

∑xpxH2(ρx)+H2(B‾)−∑xpxH2(Ex),\sum_xp_xH_2(\rho_x)+H_2(\overline B)-\sum_xp_xH_2(E_x),x∑​px​H2​(ρx​)+H2​(B)−x∑​px​H2​(Ex​),

where H2(X)=−Re⁡tr⁡[f(X)]H_2(X)=-\operatorname{Re}\operatorname{tr}[f(X)]H2​(X)=−Retr[f(X)], with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t evaluated by continuous functional calculus. No validity or isometry hypothesis is imposed; empty finite index types and zero family sizes are included.

QAlgorithms.Papers.Independent.Gap20.P04.measureBasis

For a type BBB with decidable equality, this defines a function on complex B×BB\times BB×B matrices that retains the diagonal entries and sets every off-diagonal entry to zero:

(M(ρ))bc={ρbb,b=c,0,b≠c.\bigl(\mathcal M(\rho)\bigr)_{bc}= \begin{cases} \rho_{bb},&b=c,\\ 0,&b\ne c. \end{cases}(M(ρ))bc​={ρbb​,0,​b=c,b=c.​

The input is an arbitrary matrix; no positivity or trace condition is assumed.

QAlgorithms.Papers.Independent.Gap20.P04.oneCE

For finite index types I,B,EI,B,EI,B,E with decidable equality and any complex matrix U:CI→CB×EU:\mathbb C^I\to\mathbb C^{B\times E}U:CI→CB×E, this is the set of pairs (C,Erate)∈R2(C,E_{\mathrm{rate}})\in\mathbb R^2(C,Erate​)∈R2 with both coordinates nonnegative for which there exist positive natural numbers m,rm,rm,r, nonnegative weights pxp_xpx​ summing to one, and unit vectors ψx∈C{0,…,r−1}×I\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I}ψx​∈C{0,…,r−1}×I, indexed by 0≤x<m0\le x<m0≤x<m, satisfying the following inequalities:

C≤∑xpxH(ρx)+H ⁣(Tr⁡E(UρˉU†))−∑xpxH ⁣(Tr⁡B(UρxU†)),∑xpxH(ρx)≤Erate,C\le \sum_xp_xH(\rho_x) +H\!\left(\operatorname{Tr}_E(U\bar\rho U^\dagger)\right) -\sum_xp_xH\!\left(\operatorname{Tr}_B(U\rho_xU^\dagger)\right), \qquad \sum_xp_xH(\rho_x)\le E_{\mathrm{rate}},C≤x∑​px​H(ρx​)+H(TrE​(Uρˉ​U†))−x∑​px​H(TrB​(Uρx​U†)),x∑​px​H(ρx​)≤Erate​,

where ρx=Tr⁡Cr∣ψx⟩⟨ψx∣\rho_x=\operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x|ρx​=TrCr​∣ψx​⟩⟨ψx​∣, ρˉ=∑xpxρx\bar\rho=\sum_xp_x\rho_xρˉ​=∑x​px​ρx​, and H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)) for f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t, applied by continuous functional calculus. Zero-weight labels still require unit vectors. No isometry condition on UUU or purity condition on ρx\rho_xρx​ is imposed. If III is empty, the set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.oneCQ

For finite index types I,B,EI,B,EI,B,E with decidable equality and any complex matrix U:CI→CB×EU:\mathbb C^I\to\mathbb C^{B\times E}U:CI→CB×E, this is the set of pairs (C,Q)∈R2(C,Q)\in\mathbb R^2(C,Q)∈R2 with C,Q≥0C,Q\ge0C,Q≥0 for which there exist positive natural numbers m,rm,rm,r, nonnegative weights pxp_xpx​ summing to one, and unit vectors ψx∈C{0,…,r−1}×I\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I}ψx​∈C{0,…,r−1}×I, indexed by 0≤x<m0\le x<m0≤x<m, such that, on putting

ρx=Tr⁡Cr∣ψx⟩⟨ψx∣,βx=Tr⁡E(UρxU†),ϵx=Tr⁡B(UρxU†),\rho_x=\operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x|, \quad \beta_x=\operatorname{Tr}_E(U\rho_xU^\dagger), \quad \epsilon_x=\operatorname{Tr}_B(U\rho_xU^\dagger),ρx​=TrCr​∣ψx​⟩⟨ψx​∣,βx​=TrE​(Uρx​U†),ϵx​=TrB​(Uρx​U†),

one has

C≤H ⁣(∑xpxβx)−∑xpxH(βx),Q≤∑xpx(H(βx)−H(ϵx)).C\le H\!\left(\sum_xp_x\beta_x\right)-\sum_xp_xH(\beta_x), \qquad Q\le\sum_xp_x\bigl(H(\beta_x)-H(\epsilon_x)\bigr).C≤H(x∑​px​βx​)−x∑​px​H(βx​),Q≤x∑​px​(H(βx​)−H(ϵx​)).

Here H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied by continuous functional calculus. Labels of zero weight still require unit vectors. There is no isometry assumption on UUU, and no requirement that the reduced inputs ρx\rho_xρx​ be pure. If III is empty, this set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.oneCQE

For finite index types I,B,EI,B,EI,B,E with decidable equality and any complex matrix U:CI→CB×EU:\mathbb C^I\to\mathbb C^{B\times E}U:CI→CB×E, this is the set of triples (r0,r1,r2)(r_0,r_1,r_2)(r0​,r1​,r2​) of nonnegative real numbers for which there exist positive natural numbers m,rm,rm,r, nonnegative weights pxp_xpx​ summing to one, and unit vectors ψx∈C{0,…,r−1}×I\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I}ψx​∈C{0,…,r−1}×I, indexed by 0≤x<m0\le x<m0≤x<m. Define

ρx=Tr⁡Cr∣ψx⟩⟨ψx∣,βx=Tr⁡E(UρxU†),ϵx=Tr⁡B(UρxU†),\rho_x=\operatorname{Tr}_{\mathbb C^r}|\psi_x\rangle\langle\psi_x|, \quad \beta_x=\operatorname{Tr}_E(U\rho_xU^\dagger), \quad \epsilon_x=\operatorname{Tr}_B(U\rho_xU^\dagger),ρx​=TrCr​∣ψx​⟩⟨ψx​∣,βx​=TrE​(Uρx​U†),ϵx​=TrB​(Uρx​U†), A=∑xpxH(ρx),B=H ⁣(∑xpxβx),Bc=∑xpxH(βx),Ec=∑xpxH(ϵx).A=\sum_xp_xH(\rho_x),\qquad B=H\!\left(\sum_xp_x\beta_x\right),\qquad B_c=\sum_xp_xH(\beta_x),\qquad E_c=\sum_xp_xH(\epsilon_x).A=x∑​px​H(ρx​),B=H(x∑​px​βx​),Bc​=x∑​px​H(βx​),Ec​=x∑​px​H(ϵx​).

The required inequalities are exactly

r0+2r1≤A+B−Ec,r1≤Bc−Ec+r2,r0+r1≤B−Ec+r2.r_0+2r_1\le A+B-E_c,\qquad r_1\le B_c-E_c+r_2,\qquad r_0+r_1\le B-E_c+r_2.r0​+2r1​≤A+B−Ec​,r1​≤Bc​−Ec​+r2​,r0​+r1​≤B−Ec​+r2​.

Here H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), with f(t)=tlog⁡2tf(t)=t\log_2tf(t)=tlog2​t applied by continuous functional calculus. Zero-weight labels still require unit vectors; UUU is not assumed to be an isometry, and the reduced inputs need not be pure. If III is empty, the set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.product

For arbitrary types I,B,E,J,D,FI,B,E,J,D,FI,B,E,J,D,F, let UUU be a complex matrix with rows indexed by B×EB\times EB×E and columns by III, and let VVV have rows indexed by D×FD\times FD×F and columns by JJJ. Their product is the matrix with rows indexed by (B×D)×(E×F)(B\times D)\times(E\times F)(B×D)×(E×F) and columns by I×JI\times JI×J, defined by

product⁡(U,V)((b,d),(e,f)),(i,j)=U(b,e),i V(d,f),j.\operatorname{product}(U,V)_{((b,d),(e,f)),(i,j)} =U_{(b,e),i}\,V_{(d,f),j}.product(U,V)((b,d),(e,f)),(i,j)​=U(b,e),i​V(d,f),j​.

No isometry or normalization condition is imposed, and the index types may be empty.

QAlgorithms.Papers.Independent.Gap20.P04.purifiedValues

For a finite index type III and any real-valued function fff on purified input families over III, this defines the set

{f(e):e is valid}.\{f(e):e\text{ is valid}\}.{f(e):e is valid}.

A family eee specifies natural numbers m,rm,rm,r, weights px∈Rp_x\in\mathbb Rpx​∈R, and vectors ψx∈C{0,…,r−1}×I\psi_x\in\mathbb C^{\{0,\ldots,r-1\}\times I}ψx​∈C{0,…,r−1}×I, indexed by 0≤x<m0\le x<m0≤x<m; validity means exactly

m>0,r>0,px≥0 for every x,∑xpx=1,∥ψx∥=1 for every x.m>0,\qquad r>0,\qquad p_x\ge0\ \text{for every }x,\qquad \sum_xp_x=1,\qquad \|\psi_x\|=1\ \text{for every }x.m>0,r>0,px​≥0 for every x,x∑​px​=1,∥ψx​∥=1 for every x.

Thus a real number vvv belongs precisely when such a valid family exists with v=f(e)v=f(e)v=f(e); no attainment or boundedness property of this set is asserted. Zero weights are allowed, but their associated vectors must still have norm one. If III is empty, no valid family exists and the set is empty.

QAlgorithms.Papers.Independent.Gap20.P04.selectedCEHull

For any set S⊆R2S\subseteq\mathbb R^2S⊆R2 and function f:R→R2f:\mathbb R\to\mathbb R^2f:R→R2, this defines the closure, in the usual topology of R2\mathbb R^2R2, of the real convex hull of

{r∈R2:r1,r2≥0, ∃s∈R2, [(∃λ∈[0,1], s=f(λ)) ∨ (s∈S ∧ s2=0)], r1≤s1, s2≤r2}.\left\{ r\in\mathbb R^2: r_1,r_2\ge0,\ \exists s\in\mathbb R^2,\ \left[ \bigl(\exists\lambda\in[0,1],\ s=f(\lambda)\bigr) \ \lor\ \bigl(s\in S\ \land\ s_2=0\bigr) \right], \ r_1\le s_1,\ s_2\le r_2 \right\}.{r∈R2:r1​,r2​≥0, ∃s∈R2, [(∃λ∈[0,1], s=f(λ)) ∨ (s∈S ∧ s2​=0)], r1​≤s1​, s2​≤r2​}.

There are no additional restrictions on SSS or fff. In particular, the condition on the second coordinate is s2≤r2s_2\le r_2s2​≤r2​, and the branch supplied by fff does not require s2s_2s2​ to be nonnegative.

QAlgorithms.Papers.Independent.Gap20.P04.selectedCQHull

For any set S⊆R2S\subseteq\mathbb R^2S⊆R2 and function f:R→R2f:\mathbb R\to\mathbb R^2f:R→R2, this defines the closure, in the usual topology of R2\mathbb R^2R2, of the real convex hull of

{r∈R2:r1,r2≥0, ∃s∈R2, [(∃λ≥1, s=f(λ)) ∨ (s∈S ∧ (s1=0∨s2=0))], r1≤s1, r2≤s2}.\left\{ r\in\mathbb R^2: r_1,r_2\ge0,\ \exists s\in\mathbb R^2,\ \left[ \bigl(\exists\lambda\ge1,\ s=f(\lambda)\bigr) \ \lor\ \bigl(s\in S\ \land\ (s_1=0\lor s_2=0)\bigr) \right], \ r_1\le s_1,\ r_2\le s_2 \right\}.{r∈R2:r1​,r2​≥0, ∃s∈R2, [(∃λ≥1, s=f(λ)) ∨ (s∈S ∧ (s1​=0∨s2​=0))], r1​≤s1​, r2​≤s2​}.

There are no additional assumptions on SSS or fff; either alternative may supply the point sss, and points with both coordinates zero satisfy the axis condition.

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

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 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