Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for On the communication cost of entanglement transformations

Definition
QAlgorithms_Papers_Independent_Intakenext100_P61

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

prove2quantum

The objects the formalized statements of On the communication cost of entanglement transformations (arXiv:quant-ph/0204092) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • finiteMin: PDF p.3: finite minimum; the empty-set default is unused on valid smoothing inputs.
  • finiteMax: PDF pp.2--3: finite maximum; empty support has value zero.
  • spectralSupport: PDF p.2: support of the positive spectrum, counted with multiplicity.
  • largestWeight: PDF p.2: largest eigenvalue of a positive matrix.
  • entropyZero: PDF p.2: S_0, also for subnormalized positive matrices.
  • entropyOne: PDF p.2: von Neumann entropy in bits; zero weights contribute zero.
  • spread: PDF p.2, (1): spectral spread; no trace renormalization.
  • Flat: PDF p.2: flatness only on positive support, including rank one.
  • spectralRetentions: PDF p.3, (6)--(8): retained spectral subsets with mass at least 1-epsilon. Zero eigenvalues may be removed without changing any of these minima.
  • smoothZero: PDF p.3, (6): smoothed support entropy.
  • smoothInfinity: PDF p.3, (7): smoothed largest-weight entropy.
  • smoothSpread: PDF p.3, (8): joint minimum, rather than a difference of separate minima.
  • RenyiOrder: PDF pp.2,5: nonnegative Renyi orders with a separate infinity endpoint.
  • spectralRenyi: PDF p.2: entropy of a retained positive spectrum. Orders 0,1,infinity are handled separately; zero weights are excluded before exponentiation. The order-one branch is used only on the full normalized spectrum; no continuous order-one extension is claimed for a retained subnormalized spectrum.
  • upperRenyiFactor: PDF p.5, Remark 12: beta/(beta-1) has limiting value one at infinity.
  • eigenvalueRenyiEntropy: PDF p.2: Renyi entropy with the source's endpoint conventions.
  • renyiGap: PDF p.3, Remark 2: Renyi gap.
  • smoothRenyiGap: PDF p.5, Remark 12: joint smoothing of the Renyi gap.
  • BipartiteMatrix: PDF p.2: concrete finite bipartite matrices.
  • aliceApply: PDF p.2: Alice's Kraus operation tensored with Bob's identity, retaining off-diagonal blocks.
  • bobApply: PDF p.2: Bob's local Kraus operation tensored with Alice's identity.
  • transferAB: PDF p.2: an m-dimensional subsystem moves from Alice to Bob by reassociation.
  • transferBA: PDF p.2: an m-dimensional subsystem moves from Bob to Alice.
  • QuantumExecution: PDF p.2 and Fig.1: finite deterministic executions. Local CPTP operations include arbitrary pure ancillary preparation and disposal. Transfers have positive integer dimensions and their costs are summed. No postselection or unconstrained joint-channel constructor is present.
  • ClassicalExecution: PDF p.5, Corollary 10: finite adaptive LOCC trees. Each communicated instrument outcome is available to both parties. Branch states are unnormalized and all final branches are summed. C bounds worst-case total log-alphabet cost; this includes every fixed-length binary-message protocol in the source.
  • pack: PDF pp.1--2: separate local basis identifications with finite index sets.
  • Quantum: PDF p.2: operational quantum communication relation.
  • Classical: PDF p.5: operational classical communication relation.
  • aliceDensity: PDF pp.1--2: Alice's reduced density; the second tensor factor is traced out.
  • QuantumPrepares: PDF p.5: fidelity is tested on the unconditional, possibly mixed, output.
  • ClassicalPrepares: PDF p.5: classical-only preparation, summing every branch.
  • tensorPureStates: PDF p.5: bipartite tensor with all Alice factors before all Bob factors.
  • pureStateCopies: PDF pp.6--7: n copies with bipartite ownership spectralRetentions; the empty product is one.
  • bellRank: PDF pp.1--2: normalized maximally entangled rank-r state when r>0.
  • eprPairs: PDF p.5: k EPR pairs, including k=0.
  • smoothingError: PDF p.5: the eighth root of 4 epsilon.
  • binaryState: PDF p.3: binary Schmidt-diagonal state, with complex amplitudes.
  • harmonicSum: PDF p.7: the ordinary harmonic sum, with indices starting at one.
  • harmonicState: PDF p.7: normalized harmonic embezzling vector for n>0. At n=0 its Hilbert space is empty, and no normalized-state assertion is used.
  • harmonicTailCuts: PDF p.8, (21): feasible integer tail cutoffs, restricted to 1<=k<=n.
  • harmonicHeadCuts: PDF p.8, (22): feasible integer head cutoffs; the upper limit is k-1, inclusive.
  • applyLocalMaps: PDF p.6, (20): action of separate local linear maps on a bipartite vector. Isometricity is required explicitly in the residual-family theorem.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_QuantumInformation
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P63
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P35
import Definitions.Def_QAlgorithms_Papers_Independent_Bridge50_P40
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P53

/-! Hayden--Winter, quant-ph/0204092v3. Page citations are PDF pages.
Exact matching primitives are imported from the pinned accepted library.
All new definitions are local to this paper. Subnormalized spectral truncations
are never renormalized. Protocol costs count physical message dimensions. -/

noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P61

open scoped Matrix ComplexConjugate

open QAlgorithms.Papers.Independent.Information100.P63 (logTwo)
open QAlgorithms.Papers.Independent.Dependency50.P35 (supportRank)
open QAlgorithms.Papers.Independent.Bridge50.P40 (entropyInfinity)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)

attribute [local instance] Classical.propDecidable

/-- PDF p.3: finite minimum; the empty-set default is unused on valid smoothing inputs. -/
def finiteMin {I : Type*} [DecidableEq I] (s : Finset I) (f : I → ℝ) : ℝ :=
  if h : s.Nonempty then s.inf' h f else 0

/-- PDF pp.2--3: finite maximum; empty support has value zero. -/
def finiteMax {I : Type*} [DecidableEq I] (s : Finset I) (f : I → ℝ) : ℝ :=
  if h : s.Nonempty then s.sup' h f else 0

section Spectral

variable {I J : Type} [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J]

/-- PDF p.2: support of the positive spectrum, counted with multiplicity. -/
def spectralSupport (rho : Matrix I I ℂ) : Finset (Fin (Fintype.card I)) :=
  Finset.univ.filter fun i => 0 < ascEigenvalues rho i

/-- PDF p.2: largest eigenvalue of a positive matrix. -/
def largestWeight (rho : Matrix I I ℂ) : ℝ :=
  finiteMax (spectralSupport rho) (ascEigenvalues rho)

/-- PDF p.2: S_0, also for subnormalized positive matrices. -/
def entropyZero (rho : Matrix I I ℂ) : ℝ := logTwo (supportRank rho)

/-- PDF p.2: von Neumann entropy in bits; zero weights contribute zero. -/
def entropyOne (rho : Matrix I I ℂ) : ℝ :=
  -∑ i, ascEigenvalues rho i * logTwo (ascEigenvalues rho i)

/-- PDF p.2, (1): spectral spread; no trace renormalization. -/
def spread (rho : Matrix I I ℂ) : ℝ := entropyZero rho - entropyInfinity rho

/-- PDF p.2: flatness only on positive support, including rank one. -/
def Flat (rho : Matrix I I ℂ) : Prop :=
  ∀ i ∈ spectralSupport rho, ∀ j ∈ spectralSupport rho,
    ascEigenvalues rho i = ascEigenvalues rho j

/-- PDF p.3, (6)--(8): retained spectral subsets with mass at least 1-epsilon.
Zero eigenvalues may be removed without changing any of these minima. -/
def spectralRetentions (rho : Matrix I I ℂ) (epsilon : ℝ) : Finset (Finset (Fin (Fintype.card I))) :=
  (spectralSupport rho).powerset.filter fun s => 1 - epsilon ≤ ∑ i ∈ s, ascEigenvalues rho i

/-- PDF p.3, (6): smoothed support entropy. -/
def smoothZero (rho : Matrix I I ℂ) (epsilon : ℝ) : ℝ :=
  logTwo (finiteMin (spectralRetentions rho epsilon) fun s => (s.card : ℝ))

/-- PDF p.3, (7): smoothed largest-weight entropy. -/
def smoothInfinity (rho : Matrix I I ℂ) (epsilon : ℝ) : ℝ :=
  -logTwo (finiteMin (spectralRetentions rho epsilon) fun s => finiteMax s (ascEigenvalues rho))

/-- PDF p.3, (8): joint minimum, rather than a difference of separate minima. -/
def smoothSpread (rho : Matrix I I ℂ) (epsilon : ℝ) : ℝ :=
  logTwo (finiteMin (spectralRetentions rho epsilon) fun s =>
    (s.card : ℝ) * finiteMax s (ascEigenvalues rho))

end Spectral

/-- PDF pp.2,5: nonnegative Renyi orders with a separate infinity endpoint. -/
abbrev RenyiOrder := WithTop NNReal

/-- PDF p.2: entropy of a retained positive spectrum. Orders 0,1,infinity are
handled separately; zero weights are excluded before exponentiation. The order-one
branch is used only on the full normalized spectrum; no continuous order-one
extension is claimed for a retained subnormalized spectrum. -/
def spectralRenyi {n : ℕ} (r : Fin n → ℝ) (s : Finset (Fin n)) (alpha : RenyiOrder) : ℝ :=
  if alpha = ⊤ then -logTwo (finiteMax s r)
  else let a : ℝ := (alpha.untopD 0 : NNReal)
       if a = 0 then logTwo s.card
       else if a = 1 then -∑ i ∈ s, r i * logTwo (r i)
       else logTwo (∑ i ∈ s, (r i) ^ a) / (1 - a)

/-- PDF p.5, Remark 12: beta/(beta-1) has limiting value one at infinity. -/
def upperRenyiFactor (beta : RenyiOrder) : ℝ :=
  if beta = ⊤ then 1 else
    let b : ℝ := (beta.untopD 0 : NNReal)
    b / (b - 1)

section SpectralResults

variable {I J : Type} [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J]

/-- PDF p.2: Renyi entropy with the source's endpoint conventions. -/
def eigenvalueRenyiEntropy (rho : Matrix I I ℂ) (alpha : RenyiOrder) : ℝ :=
  spectralRenyi (ascEigenvalues rho) (spectralSupport rho) alpha

/-- PDF p.3, Remark 2: Renyi gap. -/
def renyiGap (rho : Matrix I I ℂ) (alpha beta : RenyiOrder) : ℝ :=
  eigenvalueRenyiEntropy rho alpha - eigenvalueRenyiEntropy rho beta

/-- PDF p.5, Remark 12: joint smoothing of the Renyi gap. -/
def smoothRenyiGap (rho : Matrix I I ℂ) (alpha beta : RenyiOrder) (epsilon : ℝ) : ℝ :=
  finiteMin (spectralRetentions rho epsilon) fun s =>
    spectralRenyi (ascEigenvalues rho) s alpha - spectralRenyi (ascEigenvalues rho) s beta

end SpectralResults

/-- PDF p.2: concrete finite bipartite matrices. -/
abbrev BipartiteMatrix (a b : ℕ) := Matrix (Fin a × Fin b) (Fin a × Fin b) ℂ

/-- PDF p.2: Alice's Kraus operation tensored with Bob's identity, retaining off-diagonal blocks. -/
def aliceApply {a b c k : ℕ} (K : Fin k → Matrix (Fin c) (Fin a) ℂ)
    (rho : BipartiteMatrix a b) : BipartiteMatrix c b :=
  krausApply (fun j => Matrix.kronecker (K j) (1 : Matrix (Fin b) (Fin b) ℂ)) rho

/-- PDF p.2: Bob's local Kraus operation tensored with Alice's identity. -/
def bobApply {a b d k : ℕ} (K : Fin k → Matrix (Fin d) (Fin b) ℂ)
    (rho : BipartiteMatrix a b) : BipartiteMatrix a d :=
  krausApply (fun j => Matrix.kronecker (1 : Matrix (Fin a) (Fin a) ℂ) (K j)) rho

/-- PDF p.2: an m-dimensional subsystem moves from Alice to Bob by reassociation. -/
def transferAB {a b m : ℕ} (rho : BipartiteMatrix (a * m) b) : BipartiteMatrix a (m * b) :=
  fun p q => rho
    (finProdFinEquiv (p.1, (finProdFinEquiv.symm p.2).1), (finProdFinEquiv.symm p.2).2)
    (finProdFinEquiv (q.1, (finProdFinEquiv.symm q.2).1), (finProdFinEquiv.symm q.2).2)

/-- PDF p.2: an m-dimensional subsystem moves from Bob to Alice. -/
def transferBA {a b m : ℕ} (rho : BipartiteMatrix a (m * b)) : BipartiteMatrix (a * m) b :=
  fun p q => rho
    ((finProdFinEquiv.symm p.1).1, finProdFinEquiv ((finProdFinEquiv.symm p.1).2, p.2))
    ((finProdFinEquiv.symm q.1).1, finProdFinEquiv ((finProdFinEquiv.symm q.1).2, q.2))

/-- PDF p.2 and Fig.1: finite deterministic executions. Local CPTP operations
include arbitrary pure ancillary preparation and disposal. Transfers have positive
integer dimensions and their costs are summed. No postselection or unconstrained
joint-channel constructor is present. -/
inductive QuantumExecution : {a b c d : ℕ} → BipartiteMatrix a b → BipartiteMatrix c d → ℝ → Prop
  | identity {a b} (rho : BipartiteMatrix a b) : QuantumExecution rho rho 0
  | alice {a b c k} (rho : BipartiteMatrix a b) (K : Fin k → Matrix (Fin c) (Fin a) ℂ)
      (hK : IsKrausFamily K) : QuantumExecution rho (aliceApply K rho) 0
  | bob {a b d k} (rho : BipartiteMatrix a b) (K : Fin k → Matrix (Fin d) (Fin b) ℂ)
      (hK : IsKrausFamily K) : QuantumExecution rho (bobApply K rho) 0
  | sendAB {a b m} (rho : BipartiteMatrix (a * m) b) (hm : 0 < m) :
      QuantumExecution rho (transferAB rho) (logTwo m)
  | sendBA {a b m} (rho : BipartiteMatrix a (m * b)) (hm : 0 < m) :
      QuantumExecution rho (transferBA rho) (logTwo m)
  | compose {a b c d e f} {rho : BipartiteMatrix a b} {sigma : BipartiteMatrix c d}
      {tau : BipartiteMatrix e f} {C D : ℝ} :
      QuantumExecution rho sigma C → QuantumExecution sigma tau D → QuantumExecution rho tau (C + D)

/-- PDF p.5, Corollary 10: finite adaptive LOCC trees. Each communicated
instrument outcome is available to both parties. Branch states are unnormalized
and all final branches are summed. C bounds worst-case total log-alphabet cost;
this includes every fixed-length binary-message protocol in the source. -/
inductive ClassicalExecution : {a b c d : ℕ} → BipartiteMatrix a b → BipartiteMatrix c d → ℝ → Prop
  | identity {a b} (rho : BipartiteMatrix a b) : ClassicalExecution rho rho 0
  | alice {a b c k} (rho : BipartiteMatrix a b) (K : Fin k → Matrix (Fin c) (Fin a) ℂ)
      (hK : IsKrausFamily K) : ClassicalExecution rho (aliceApply K rho) 0
  | bob {a b d k} (rho : BipartiteMatrix a b) (K : Fin k → Matrix (Fin d) (Fin b) ℂ)
      (hK : IsKrausFamily K) : ClassicalExecution rho (bobApply K rho) 0
  | aliceMessage {a b c d e k m} (rho : BipartiteMatrix a b)
      (K : Fin m → Fin k → Matrix (Fin c) (Fin a) ℂ) (hm : 0 < m)
      (hK : (∑ j, ∑ l, (K j l)ᴴ * K j l) = 1)
      (sigma : Fin m → BipartiteMatrix d e) (cost : Fin m → ℝ) (budget : ℝ)
      (hbudget : ∀ j, cost j ≤ budget)
      (next : ∀ j, ClassicalExecution (aliceApply (K j) rho) (sigma j) (cost j)) :
      ClassicalExecution rho (∑ j, sigma j) (logTwo m + budget)
  | bobMessage {a b c d e k m} (rho : BipartiteMatrix a b)
      (K : Fin m → Fin k → Matrix (Fin c) (Fin b) ℂ) (hm : 0 < m)
      (hK : (∑ j, ∑ l, (K j l)ᴴ * K j l) = 1)
      (sigma : Fin m → BipartiteMatrix d e) (cost : Fin m → ℝ) (budget : ℝ)
      (hbudget : ∀ j, cost j ≤ budget)
      (next : ∀ j, ClassicalExecution (bobApply (K j) rho) (sigma j) (cost j)) :
      ClassicalExecution rho (∑ j, sigma j) (logTwo m + budget)
  | compose {a b c d e f} {rho : BipartiteMatrix a b} {sigma : BipartiteMatrix c d}
      {tau : BipartiteMatrix e f} {C D : ℝ} :
      ClassicalExecution rho sigma C → ClassicalExecution sigma tau D → ClassicalExecution rho tau (C + D)

section Operational

variable {A B C D : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
    [Fintype C] [DecidableEq C] [Fintype D] [DecidableEq D]

/-- PDF pp.1--2: separate local basis identifications with finite index sets. -/
def pack (rho : Matrix (A × B) (A × B) ℂ) : BipartiteMatrix (Fintype.card A) (Fintype.card B) :=
  fun p q => rho ((Fintype.equivFin A).symm p.1, (Fintype.equivFin B).symm p.2)
    ((Fintype.equivFin A).symm q.1, (Fintype.equivFin B).symm q.2)

/-- PDF p.2: operational quantum communication relation. -/
def Quantum (rho : Matrix (A × B) (A × B) ℂ) (sigma : Matrix (C × D) (C × D) ℂ)
    (cost : ℝ) : Prop := QuantumExecution (pack rho) (pack sigma) cost

/-- PDF p.5: operational classical communication relation. -/
def Classical (rho : Matrix (A × B) (A × B) ℂ) (sigma : Matrix (C × D) (C × D) ℂ)
    (cost : ℝ) : Prop := ClassicalExecution (pack rho) (pack sigma) cost

/-- PDF pp.1--2: Alice's reduced density; the second tensor factor is traced out. -/
def aliceDensity (phi : EuclideanSpace ℂ (A × B)) : Matrix A A ℂ := traceRight (pureDensity phi)

/-- PDF p.5: fidelity is tested on the unconditional, possibly mixed, output. -/
def QuantumPrepares (phi : EuclideanSpace ℂ (A × B)) (psi : EuclideanSpace ℂ (C × D))
    (epsilon cost : ℝ) : Prop :=
  ∃ sigma : Matrix (C × D) (C × D) ℂ,
    Quantum (pureDensity phi) sigma cost ∧ fidelity sigma (pureDensity psi) ≥ 1 - epsilon

/-- PDF p.5: classical-only preparation, summing every branch. -/
def ClassicalPrepares (phi : EuclideanSpace ℂ (A × B)) (psi : EuclideanSpace ℂ (C × D))
    (epsilon cost : ℝ) : Prop :=
  ∃ sigma : Matrix (C × D) (C × D) ℂ,
    Classical (pureDensity phi) sigma cost ∧ fidelity sigma (pureDensity psi) ≥ 1 - epsilon

/-- PDF p.5: bipartite tensor with all Alice factors before all Bob factors. -/
def tensorPureStates (phi : EuclideanSpace ℂ (A × B)) (psi : EuclideanSpace ℂ (C × D)) :
    EuclideanSpace ℂ ((A × C) × (B × D)) :=
  WithLp.toLp 2 fun p => phi (p.1.1, p.2.1) * psi (p.1.2, p.2.2)

/-- PDF pp.6--7: n copies with bipartite ownership spectralRetentions; the empty product is one. -/
def pureStateCopies (psi : EuclideanSpace ℂ (A × B)) (n : ℕ) :
    EuclideanSpace ℂ ((Fin n → A) × (Fin n → B)) :=
  WithLp.toLp 2 fun p => ∏ j, psi (p.1 j, p.2 j)

/-- PDF pp.1--2: normalized maximally entangled rank-r state when r>0. -/
def bellRank (r : ℕ) : EuclideanSpace ℂ (Fin r × Fin r) :=
  WithLp.toLp 2 fun p => if p.1 = p.2 then ((Real.sqrt (r : ℝ))⁻¹ : ℂ) else 0

/-- PDF p.5: k EPR pairs, including k=0. -/
def eprPairs (k : ℕ) : EuclideanSpace ℂ (Fin (2 ^ k) × Fin (2 ^ k)) := bellRank (2 ^ k)

/-- PDF p.5: the eighth root of 4 epsilon. -/
def smoothingError (epsilon : ℝ) : ℝ := (4 * epsilon) ^ (1 / 8 : ℝ)

end Operational

/-- PDF p.3: binary Schmidt-diagonal state, with complex amplitudes. -/
def binaryState (alpha beta : ℂ) : EuclideanSpace ℂ (Bool × Bool) :=
  WithLp.toLp 2 fun p => if p = (false,false) then alpha else if p = (true,true) then beta else 0

section Dilution

variable {A B : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]

end Dilution

/-- PDF p.7: the ordinary harmonic sum, with indices starting at one. -/
def harmonicSum (n : ℕ) : ℝ := ∑ i ∈ Finset.Icc 1 n, (i : ℝ)⁻¹

/-- PDF p.7: normalized harmonic embezzling vector for n>0.
At n=0 its Hilbert space is empty, and no normalized-state assertion is used. -/
def harmonicState (n : ℕ) : EuclideanSpace ℂ (Fin n × Fin n) :=
  WithLp.toLp 2 fun p => if p.1 = p.2 then
    (Real.sqrt (1 / (((p.1.val + 1 : ℕ) : ℝ) * harmonicSum n)) : ℂ) else 0

/-- PDF p.8, (21): feasible integer tail cutoffs, restricted to 1<=k<=n. -/
def harmonicTailCuts (n : ℕ) (delta : ℝ) : Finset ℕ :=
  (Finset.Icc 1 n).filter fun k =>
    (∑ i ∈ Finset.Icc (k + 1) n, 1 / ((i : ℝ) * harmonicSum n)) ≤ delta

/-- PDF p.8, (22): feasible integer head cutoffs; the upper limit is k-1, inclusive. -/
def harmonicHeadCuts (n : ℕ) (delta : ℝ) : Finset ℕ :=
  (Finset.Icc 1 n).filter fun k =>
    (∑ i ∈ Finset.Icc 1 (k - 1), 1 / ((i : ℝ) * harmonicSum n)) ≤ delta

/-- PDF p.6, (20): action of separate local linear maps on a bipartite vector.
Isometricity is required explicitly in the residual-family theorem. -/
def applyLocalMaps {A B C D : Type} [Fintype A] [Fintype B]
    (U : Matrix C A ℂ) (V : Matrix D B ℂ) (phi : EuclideanSpace ℂ (A × B)) :
    EuclideanSpace ℂ (C × D) :=
  WithLp.toLp 2 fun p => ∑ a, ∑ b, U p.1 a * V p.2 b * phi (a,b)

/-- Sanity examples for the paper-local substrate. These pin definitions rather
than prove the paper's theorem statements. -/

example : logTwo 1 = 0 := by simp [logTwo, Real.logb]

example {I : Type*} [DecidableEq I] (i : I) (f : I → ℝ) : finiteMin {i} f = f i := by
  simp [finiteMin]

example {I : Type*} [DecidableEq I] (i : I) (f : I → ℝ) : finiteMax {i} f = f i := by
  simp [finiteMax]

example {n : ℕ} (r : Fin n → ℝ) (s : Finset (Fin n)) :
    spectralRenyi r s (0 : RenyiOrder) = logTwo s.card := by simp [spectralRenyi]

example : upperRenyiFactor ⊤ = 1 := by simp [upperRenyiFactor]

example {a b : ℕ} (rho : BipartiteMatrix a b) : QuantumExecution rho rho 0 :=
  QuantumExecution.identity rho

example {a b : ℕ} (rho : BipartiteMatrix a b) : ClassicalExecution rho rho 0 :=
  ClassicalExecution.identity rho

example {a b m : ℕ} (rho : BipartiteMatrix (a * m) b) (hm : 0 < m) :
    QuantumExecution rho (transferAB rho) (logTwo m) := QuantumExecution.sendAB rho hm

example {A B : Type} [Fintype A] [Fintype B] (psi : EuclideanSpace ℂ (A × B))
    (p : (Fin 0 → A) × (Fin 0 → B)) : pureStateCopies psi 0 p = 1 := by simp [pureStateCopies]

example : eprPairs 0 (0,0) = 1 := by simp [eprPairs, bellRank]

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

example : harmonicState 1 (0,0) = 1 := by norm_num [harmonicState, harmonicSum]

example {A B C D : Type} [Fintype A] [Fintype B]
    (U : Matrix C A ℂ) (V : Matrix D B ℂ) (phi : EuclideanSpace ℂ (A × B)) (c : C) (d : D) :
    applyLocalMaps U V phi (c,d) = ∑ a, ∑ b, U c a * V d b * phi (a,b) := rfl

example (alpha beta : ℂ) : binaryState alpha beta (false,false) = alpha := by simp [binaryState]

example {I : Type} [Fintype I] [DecidableEq I] (rho : Matrix I I ℂ) :
    spread rho = entropyZero rho - entropyInfinity rho := rfl

example {I : Type} [Fintype I] [DecidableEq I] (rho : Matrix I I ℂ) (e : ℝ) :
    smoothSpread rho e = logTwo (finiteMin (spectralRetentions rho e) fun s =>
      (s.card : ℝ) * finiteMax s (ascEigenvalues rho)) := rfl

example {I : Type} [Fintype I] [DecidableEq I] (rho : Matrix I I ℂ)
    (alpha beta : RenyiOrder) : renyiGap rho alpha beta = eigenvalueRenyiEntropy rho alpha - eigenvalueRenyiEntropy rho beta := rfl

example {a b c k : ℕ} (K : Fin k → Matrix (Fin c) (Fin a) ℂ) (rho : BipartiteMatrix a b) :
    aliceApply K rho = krausApply (fun j => Matrix.kronecker (K j)
      (1 : Matrix (Fin b) (Fin b) ℂ)) rho := rfl

example {a b d k : ℕ} (K : Fin k → Matrix (Fin d) (Fin b) ℂ) (rho : BipartiteMatrix a b) :
    bobApply K rho = krausApply (fun j => Matrix.kronecker
      (1 : Matrix (Fin a) (Fin a) ℂ) (K j)) rho := rfl

example {a b m : ℕ} (rho : BipartiteMatrix a (m * b)) (hm : 0 < m) :
    QuantumExecution rho (transferBA rho) (logTwo m) := QuantumExecution.sendBA rho hm

example {A B : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
    (rho : Matrix (A × B) (A × B) ℂ) : Quantum rho rho 0 := QuantumExecution.identity (pack rho)

example {A B : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
    (rho : Matrix (A × B) (A × B) ℂ) : Classical rho rho 0 := ClassicalExecution.identity (pack rho)

example {A B : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
    (phi : EuclideanSpace ℂ (A × B)) (a a0 : A) :
    aliceDensity phi a a0 = ∑ b, phi (a,b) * conj (phi (a0,b)) := rfl

example {I : Type} [Fintype I] [DecidableEq I] (rho sigma : Matrix I I ℂ) :
    fidelity rho sigma = (rootFidelity rho sigma) ^ 2 := rfl

example : smoothingError 0 = 0 := by norm_num [smoothingError]

example : harmonicTailCuts 1 0 = {1} := by norm_num [harmonicTailCuts, harmonicSum]

example : harmonicHeadCuts 1 0 = {1} := by norm_num [harmonicHeadCuts, harmonicSum]

end QAlgorithms.Papers.Independent.Intakenext100.P61
Source
On the communication cost of entanglement transformations, arXiv:quant-ph/0204092v3, https://arxiv.org/abs/quant-ph/0204092v3
Read-back

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

QAlgorithms.Papers.Independent.Intakenext100.P61.BipartiteMatrix

For any natural numbers a,ba,ba,b, including zero, a bipartite matrix of dimensions (a,b)(a,b)(a,b) is a complex matrix whose rows and columns are indexed by pairs (i,j)(i,j)(i,j) with 0≤i<a0\le i<a0≤i<a and 0≤j<b0\le j<b0≤j<b. It is therefore a square matrix of size ababab. No positivity, Hermitian symmetry, or trace condition is imposed; if either dimension is zero, the index set is empty.

QAlgorithms.Papers.Independent.Intakenext100.P61.Classical

For finite types A,B,C,DA,B,C,DA,B,C,D, arbitrary complex matrices ρ\rhoρ on A×BA\times BA×B and σ\sigmaσ on C×DC\times DC×D, and a real number C0C_0C0​, this proposition says that, after relabeling the four types by their specified enumerations onto initial segments of the natural numbers, the matrices are connected at cost exactly C0C_0C0​ by the least relation with the following rules. Identity costs zero, and local maps X↦∑l<k(Kl⊗I)X(Kl⊗I)†X\mapsto\sum_{l<k}(K_l\otimes I)X(K_l\otimes I)^\daggerX↦∑l<k​(Kl​⊗I)X(Kl​⊗I)† or X↦∑l<k(I⊗Kl)X(I⊗Kl)†X\mapsto\sum_{l<k}(I\otimes K_l)X(I\otimes K_l)^\daggerX↦∑l<k​(I⊗Kl​)X(I⊗Kl​)† cost zero whenever ∑lKl†Kl=I\sum_lK_l^\dagger K_l=I∑l​Kl†​Kl​=I on the affected input factor. A message step chooses natural numbers m>0m>0m>0 and kkk, a family KjlK_{jl}Kjl​ acting on one side with joint completeness ∑j<m,l<kKjl†Kjl=I\sum_{j<m,l<k}K_{jl}^\dagger K_{jl}=I∑j<m,l<k​Kjl†​Kjl​=I, branch output matrices σj\sigma_jσj​ of a common pair of dimensions, real branch costs CjC_jCj​, and a real budget BBB satisfying Cj≤BC_j\le BCj​≤B for every jjj. Each branch input is ∑l<k(Kjl⊗I)X(Kjl⊗I)†\sum_{l<k}(K_{jl}\otimes I)X(K_{jl}\otimes I)^\dagger∑l<k​(Kjl​⊗I)X(Kjl​⊗I)† for an Alice message, or ∑l<k(I⊗Kjl)X(I⊗Kjl)†\sum_{l<k}(I\otimes K_{jl})X(I\otimes K_{jl})^\dagger∑l<k​(I⊗Kjl​)X(I⊗Kjl​)† for a Bob message; if every such input has a derivation to σj\sigma_jσj​ at cost CjC_jCj​, the message step has output ∑j<mσj\sum_{j<m}\sigma_j∑j<m​σj​ and cost log⁡m/log⁡2+B\log m/\log2+Blogm/log2+B. Arbitrary successive derivations compose by adding costs. Dimensions and local family sizes may be zero subject to completeness, m=1m=1m=1 is included, and every message branch requires a derivation even when its input is zero. No positivity or normalization assumptions are imposed on the matrices.

QAlgorithms.Papers.Independent.Intakenext100.P61.ClassicalExecution

This defines the least relation C(ρ,σ,C)\mathcal C(\rho,\sigma,C)C(ρ,σ,C) between arbitrary complex bipartite matrices, possibly of different natural-number dimensions, and real costs, generated by identity, local operations, message branches, and composition as follows. Identity has cost zero. Given ρ\rhoρ of dimensions (a,b)(a,b)(a,b), any family of complex c×ac\times ac×a matrices KlK_lKl​ with ∑l<kKl†Kl=Ia\sum_{l<k}K_l^\dagger K_l=I_a∑l<k​Kl†​Kl​=Ia​ gives the zero-cost output ∑l<k(Kl⊗Ib)ρ(Kl⊗Ib)†\sum_{l<k}(K_l\otimes I_b)\rho(K_l\otimes I_b)^\dagger∑l<k​(Kl​⊗Ib​)ρ(Kl​⊗Ib​)†; any family of complex d×bd\times bd×b matrices with ∑l<kKl†Kl=Ib\sum_{l<k}K_l^\dagger K_l=I_b∑l<k​Kl†​Kl​=Ib​ gives the zero-cost output ∑l<k(Ia⊗Kl)ρ(Ia⊗Kl)†\sum_{l<k}(I_a\otimes K_l)\rho(I_a\otimes K_l)^\dagger∑l<k​(Ia​⊗Kl​)ρ(Ia​⊗Kl​)†. For an Alice message, choose arbitrary natural numbers a,b,c,d,e,k,ma,b,c,d,e,k,ma,b,c,d,e,k,m with m>0m>0m>0, complex c×ac\times ac×a matrices KjlK_{jl}Kjl​ satisfying ∑j<m∑l<kKjl†Kjl=Ia\sum_{j<m}\sum_{l<k}K_{jl}^\dagger K_{jl}=I_a∑j<m​∑l<k​Kjl†​Kjl​=Ia​, branch outputs σj\sigma_jσj​ all of dimensions (d,e)(d,e)(d,e), real branch costs CjC_jCj​, and a real budget BBB with Cj≤BC_j\le BCj​≤B for every j<mj<mj<m. If, for every jjj, the branch input ∑l<k(Kjl⊗Ib)ρ(Kjl⊗Ib)†\sum_{l<k}(K_{jl}\otimes I_b)\rho(K_{jl}\otimes I_b)^\dagger∑l<k​(Kjl​⊗Ib​)ρ(Kjl​⊗Ib​)† is related to σj\sigma_jσj​ at cost CjC_jCj​, then ρ\rhoρ is related to ∑j<mσj\sum_{j<m}\sigma_j∑j<m​σj​ at cost log⁡2m+B\log_2m+Blog2​m+B, where log⁡2m=log⁡m/log⁡2\log_2m=\log m/\log2log2​m=logm/log2. The Bob-message rule has the same quantifiers and conclusion, with KjlK_{jl}Kjl​ complex c×bc\times bc×b matrices, completeness ∑j,lKjl†Kjl=Ib\sum_{j,l}K_{jl}^\dagger K_{jl}=I_b∑j,l​Kjl†​Kjl​=Ib​, and branch inputs ∑l<k(Ia⊗Kjl)ρ(Ia⊗Kjl)†\sum_{l<k}(I_a\otimes K_{jl})\rho(I_a\otimes K_{jl})^\dagger∑l<k​(Ia​⊗Kjl​)ρ(Ia​⊗Kjl​)†. Finally, for matrices of any dimensions (a,b),(c,d),(e,f)(a,b),(c,d),(e,f)(a,b),(c,d),(e,f) and real costs C,DC,DC,D, relations from ρ\rhoρ to σ\sigmaσ at cost CCC and from σ\sigmaσ to τ\tauτ at cost DDD give a relation from ρ\rhoρ to τ\tauτ at cost C+DC+DC+D. Matrices need not be positive or normalized; dimensions and kkk may be zero when the completeness equations hold. Message branches include every jjj, even branches whose input matrix is zero, and m=1m=1m=1 is allowed.

QAlgorithms.Papers.Independent.Intakenext100.P61.ClassicalPrepares

For finite register types A,B,C,DA,B,C,DA,B,C,D, arbitrary complex vectors ϕ\phiϕ on A×BA\times BA×B and ψ\psiψ on C×DC\times DC×D, and arbitrary real numbers ϵ,c\epsilon,cϵ,c, this predicate means that there exists a matrix σ\sigmaσ on C×DC\times DC×D obtainable from ϕϕ†\phi\phi^\daggerϕϕ† by a classical execution of cost exactly ccc, with

(Re⁡tr⁡σ ψψ†σ)2≥1−ϵ.\left(\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\sigma}\,\psi\psi^\dagger\sqrt{\sigma}}\right)^2\ge 1-\epsilon.(Retrσ​ψψ†σ​​)2≥1−ϵ.

Here (vv†)ij=vivj‾(vv^\dagger)_{ij}=v_i\overline{v_j}(vv†)ij​=vi​vj​​. After relabeling finite registers by consecutive integers, a classical execution is generated by identity operations of cost zero; local maps X↦∑jKjXKj†X\mapsto\sum_jK_jXK_j^\daggerX↦∑j​Kj​XKj†​, with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I, of cost zero; and local measurements with m>0m>0m>0 outcomes and matrices KjℓK_{j\ell}Kjℓ​ satisfying ∑j,ℓKjℓ†Kjℓ=I\sum_{j,\ell}K_{j\ell}^\dagger K_{j\ell}=I∑j,ℓ​Kjℓ†​Kjℓ​=I. Each measurement outcome jjj can have a further classical execution of cost cjc_jcj​; if every cj≤bc_j\le bcj​≤b, the combined execution has cost log⁡2m+b\log_2m+blog2​m+b and output equal to the sum of the unnormalized branch outputs. Finite composition adds costs. Neither input vector is required to have norm one, σ\sigmaσ is not separately required to have trace one, and no range restriction is imposed on ϵ\epsilonϵ or ccc.

QAlgorithms.Papers.Independent.Intakenext100.P61.Flat

For a finite type III with decidable equality and any complex matrix ρ\rhoρ indexed by I×II\times II×I, let (λi)i<∣I∣(\lambda_i)_{i<|I|}(λi​)i<∣I∣​ be its ascending eigenvalue list if it is Hermitian, counted with multiplicity, and the identically zero list otherwise. This property requires λi=λj\lambda_i=\lambda_jλi​=λj​ for every pair of indices satisfying λi>0\lambda_i>0λi​>0 and λj>0\lambda_j>0λj​>0. It places no restriction on zero or negative entries. The property holds vacuously if there are no strictly positive entries, including for non-Hermitian matrices and empty III, and also holds when there is just one such index.

QAlgorithms.Papers.Independent.Intakenext100.P61.Quantum

For finite types A,B,C,DA,B,C,DA,B,C,D, arbitrary complex matrices ρ\rhoρ on A×BA\times BA×B and σ\sigmaσ on C×DC\times DC×D, and any real number C0C_0C0​, this proposition says that, after relabeling each type by its specified enumeration onto the integers from zero to its cardinality minus one, there is a finite derivation from ρ\rhoρ to σ\sigmaσ using the following rules with total cost exactly C0C_0C0​: identity at cost zero; local transformations X↦∑j<k(Kj⊗I)X(Kj⊗I)†X\mapsto\sum_{j<k}(K_j\otimes I)X(K_j\otimes I)^\daggerX↦∑j<k​(Kj​⊗I)X(Kj​⊗I)† or X↦∑j<k(I⊗Kj)X(I⊗Kj)†X\mapsto\sum_{j<k}(I\otimes K_j)X(I\otimes K_j)^\daggerX↦∑j<k​(I⊗Kj​)X(I⊗Kj​)† at cost zero, where the rectangular local matrices satisfy ∑j<kKj†Kj=I\sum_{j<k}K_j^\dagger K_j=I∑j<k​Kj†​Kj​=I on the corresponding input factor; and, for a positive natural number mmm, transfer of an mmm-dimensional factor between the two sides at cost log⁡m/log⁡2\log m/\log2logm/log2. A transfer identifies (im+u,v)(im+u,v)(im+u,v) with (i,ub+v)(i,ub+v)(i,ub+v) in both matrix indices, changing dimensions (am,b)(am,b)(am,b) to (a,mb)(a,mb)(a,mb) or conversely. Successive derivations compose by adding their real costs. All intermediate dimensions are natural numbers and may be zero; local families may be empty when their completeness equation holds, and m=1m=1m=1 transfers are included. No positivity or normalization condition is required for ρ\rhoρ, σ\sigmaσ, or intermediate matrices.

QAlgorithms.Papers.Independent.Intakenext100.P61.QuantumExecution

This defines the least relation Q(ρ,σ,C)\mathcal Q(\rho,\sigma,C)Q(ρ,σ,C) between arbitrary complex bipartite matrices, possibly of different natural-number dimensions, and real costs CCC, generated by the following rules. Every matrix ρ\rhoρ of dimensions (a,b)(a,b)(a,b) satisfies Q(ρ,ρ,0)\mathcal Q(\rho,\rho,0)Q(ρ,ρ,0). For any natural number kkk and complex c×ac\times ac×a matrices KjK_jKj​ satisfying ∑j<kKj†Kj=Ia\sum_{j<k}K_j^\dagger K_j=I_a∑j<k​Kj†​Kj​=Ia​, one has Q(ρ,∑j<k(Kj⊗Ib)ρ(Kj⊗Ib)†,0)\mathcal Q(\rho,\sum_{j<k}(K_j\otimes I_b)\rho(K_j\otimes I_b)^\dagger,0)Q(ρ,∑j<k​(Kj​⊗Ib​)ρ(Kj​⊗Ib​)†,0); for complex d×bd\times bd×b matrices satisfying ∑j<kKj†Kj=Ib\sum_{j<k}K_j^\dagger K_j=I_b∑j<k​Kj†​Kj​=Ib​, one similarly has Q(ρ,∑j<k(Ia⊗Kj)ρ(Ia⊗Kj)†,0)\mathcal Q(\rho,\sum_{j<k}(I_a\otimes K_j)\rho(I_a\otimes K_j)^\dagger,0)Q(ρ,∑j<k​(Ia​⊗Kj​)ρ(Ia​⊗Kj​)†,0). For every positive natural number mmm, regrouping dimensions (am,b)(am,b)(am,b) into (a,mb)(a,mb)(a,mb), or conversely, is allowed at cost log⁡2m=log⁡m/log⁡2\log_2m=\log m/\log2log2​m=logm/log2: the regrouping identifies the index (im+u,v)(im+u,v)(im+u,v) with (i,ub+v)(i,ub+v)(i,ub+v) for i<ai<ai<a, u<mu<mu<m, v<bv<bv<b, in both rows and columns. Finally, for all natural numbers a,b,c,d,e,fa,b,c,d,e,fa,b,c,d,e,f, matrices ρ,σ,τ\rho,\sigma,\tauρ,σ,τ of dimensions (a,b),(c,d),(e,f)(a,b),(c,d),(e,f)(a,b),(c,d),(e,f), and real numbers C,DC,DC,D, Q(ρ,σ,C)\mathcal Q(\rho,\sigma,C)Q(ρ,σ,C) and Q(σ,τ,D)\mathcal Q(\sigma,\tau,D)Q(σ,τ,D) imply Q(ρ,τ,C+D)\mathcal Q(\rho,\tau,C+D)Q(ρ,τ,C+D). No positivity or normalization condition is imposed on the matrices. Dimensions and the number kkk of local matrices may be zero, subject to the displayed completeness equations; transfer dimensions must satisfy m>0m>0m>0, and m=1m=1m=1 is included.

QAlgorithms.Papers.Independent.Intakenext100.P61.QuantumPrepares

For finite types A,B,C,DA,B,C,DA,B,C,D, arbitrary vectors ϕ∈CA×B\phi\in\mathbb C^{A\times B}ϕ∈CA×B and ψ∈CC×D\psi\in\mathbb C^{C\times D}ψ∈CC×D, and arbitrary real numbers ϵ,c\epsilon,cϵ,c, this proposition asserts the existence of a complex matrix σ\sigmaσ on C×DC\times DC×D obtainable from the matrix ρx,y=ϕ(x)ϕ(y)‾\rho_{x,y}=\phi(x)\overline{\phi(y)}ρx,y​=ϕ(x)ϕ(y)​ at cost exactly ccc by a finite derivation consisting of identity, complete local Kraus operations at zero cost, positive-dimensional factor transfers at cost log⁡m/log⁡2\log m/\log2logm/log2, and composition with additive costs, after relabeling all finite types by their specified enumerations. Here a local operation is X↦∑j(Kj⊗I)X(Kj⊗I)†X\mapsto\sum_j(K_j\otimes I)X(K_j\otimes I)^\daggerX↦∑j​(Kj​⊗I)X(Kj​⊗I)† or X↦∑j(I⊗Kj)X(I⊗Kj)†X\mapsto\sum_j(I\otimes K_j)X(I\otimes K_j)^\daggerX↦∑j​(I⊗Kj​)X(I⊗Kj​)†, with ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I on the affected input factor; transfers identify (im+u,v)(im+u,v)(im+u,v) with (i,ub+v)(i,ub+v)(i,ub+v) in both matrix indices and allow either direction between dimensions (am,b)(am,b)(am,b) and (a,mb)(a,mb)(a,mb), with m>0m>0m>0. The required approximation condition is

(Re⁡tr⁡σ Pψ σ)2≥1−ϵ,(Pψ)x,y=ψ(x)ψ(y)‾,\left(\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\sigma}\,P_\psi\,\sqrt{\sigma}}\right)^2 \ge 1-\epsilon, \qquad (P_\psi)_{x,y}=\psi(x)\overline{\psi(y)},(Retrσ​Pψ​σ​​)2≥1−ϵ,(Pψ​)x,y​=ψ(x)ψ(y)​,

where each matrix square root is defined by continuous functional calculus using the real square-root function. Neither input vector is assumed normalized, and no separate density-matrix condition is imposed on σ\sigmaσ. Empty finite types and zero intermediate dimensions are included; local families may be empty when completeness holds. Neither ϵ\epsilonϵ nor ccc is restricted to be nonnegative.

QAlgorithms.Papers.Independent.Intakenext100.P61.RenyiOrder

The set of orders consists of all nonnegative real numbers together with one additional greatest element, denoted +∞+\infty+∞. It includes the orders 000 and 111.

QAlgorithms.Papers.Independent.Intakenext100.P61.aliceApply

For arbitrary natural numbers a,b,c,ka,b,c,ka,b,c,k, a family of complex c×ac\times ac×a matrices (Kj)j=0k−1(K_j)_{j=0}^{k-1}(Kj​)j=0k−1​, and an arbitrary complex matrix ρ\rhoρ indexed by {0,…,a−1}×{0,…,b−1}\{0,\ldots,a-1\}\times\{0,\ldots,b-1\}{0,…,a−1}×{0,…,b−1}, this defines the matrix indexed by {0,…,c−1}×{0,…,b−1}\{0,\ldots,c-1\}\times\{0,\ldots,b-1\}{0,…,c−1}×{0,…,b−1} given by

aliceApply⁡(K,ρ)=∑j=0k−1(Kj⊗Ib)ρ(Kj⊗Ib)†.\operatorname{aliceApply}(K,\rho) =\sum_{j=0}^{k-1}(K_j\otimes I_b)\rho(K_j\otimes I_b)^\dagger.aliceApply(K,ρ)=j=0∑k−1​(Kj​⊗Ib​)ρ(Kj​⊗Ib​)†.

Here †\dagger† denotes conjugate transpose. There is no assumption that ∑jKj†Kj=Ia\sum_jK_j^\dagger K_j=I_a∑j​Kj†​Kj​=Ia​, and no state condition on ρ\rhoρ. All dimensions may be zero; in particular, k=0k=0k=0 gives the zero matrix.

QAlgorithms.Papers.Independent.Intakenext100.P61.aliceDensity

For finite types A,BA,BA,B and any vector ϕ\phiϕ in the complex Euclidean space indexed by A×BA\times BA×B, this defines the matrix on AAA whose entries are

aliceDensity⁡(ϕ)a,a′=∑b∈Bϕ(a,b) ϕ(a′,b)‾.\operatorname{aliceDensity}(\phi)_{a,a'} =\sum_{b\in B}\phi(a,b)\,\overline{\phi(a',b)}.aliceDensity(ϕ)a,a′​=b∈B∑​ϕ(a,b)ϕ(a′,b)​.

Thus the definition forms the matrix with entries ϕ(x)ϕ(y)‾\phi(x)\overline{\phi(y)}ϕ(x)ϕ(y)​ and sums over equal BBB indices. No assumption ∥ϕ∥=1\|\phi\|=1∥ϕ∥=1 is made. Empty types are allowed; in particular, if BBB is empty, the resulting matrix is zero.

QAlgorithms.Papers.Independent.Intakenext100.P61.applyLocalMaps

For arbitrary types A,B,C,DA,B,C,DA,B,C,D, with specified finite enumerations of AAA and BBB, matrices U:C×A→CU:C\times A\to\mathbb CU:C×A→C and V:D×B→CV:D\times B\to\mathbb CV:D×B→C, and a vector ϕ∈CA×B\phi\in\mathbb C^{A\times B}ϕ∈CA×B equipped with the Euclidean-space structure, this definition returns the vector on C×DC\times DC×D whose coordinates are

(applyLocalMaps⁡(U,V,ϕ))c,d=∑a∈A∑b∈BUc,aVd,bϕa,b.\bigl(\operatorname{applyLocalMaps}(U,V,\phi)\bigr)_{c,d} =\sum_{a\in A}\sum_{b\in B}U_{c,a}V_{d,b}\phi_{a,b}.(applyLocalMaps(U,V,ϕ))c,d​=a∈A∑​b∈B∑​Uc,a​Vd,b​ϕa,b​.

There are no finiteness assumptions on C,DC,DC,D, no normalization assumption on ϕ\phiϕ, and no isometry or unitarity assumptions on U,VU,VU,V. Empty input index sets give zero sums; an empty output index set gives the unique vector with no coordinates.

QAlgorithms.Papers.Independent.Intakenext100.P61.bellRank

For every natural number rrr, this definition gives the complex vector indexed by {0,…,r−1}2\{0,\ldots,r-1\}^2{0,…,r−1}2 with coordinates

Φr(i,j)={1/r,i=j,0,i≠j.\Phi_r(i,j)= \begin{cases} 1/\sqrt r,&i=j,\\ 0,&i\ne j. \end{cases}Φr​(i,j)={1/r​,0,​i=j,i=j.​

For r>0r>0r>0, it has rrr equal nonzero diagonal amplitudes and norm one. The definition also includes r=0r=0r=0: its index set is empty, so it is the zero vector in the zero-dimensional space.

QAlgorithms.Papers.Independent.Intakenext100.P61.binaryState

For arbitrary complex numbers α,β\alpha,\betaα,β, this defines the vector in C{false,true}2\mathbb C^{\{\mathrm{false},\mathrm{true}\}^2}C{false,true}2 whose coefficient at (false,false)(\mathrm{false},\mathrm{false})(false,false) is α\alphaα, whose coefficient at (true,true)(\mathrm{true},\mathrm{true})(true,true) is β\betaβ, and whose other two coefficients are zero:

α ∣false,false⟩+β ∣true,true⟩.\alpha\,|\mathrm{false},\mathrm{false}\rangle+ \beta\,|\mathrm{true},\mathrm{true}\rangle.α∣false,false⟩+β∣true,true⟩.

No normalization or nonzero condition is imposed.

QAlgorithms.Papers.Independent.Intakenext100.P61.bobApply

For arbitrary natural numbers a,b,d,ka,b,d,ka,b,d,k, a family of complex d×bd\times bd×b matrices (Kj)j=0k−1(K_j)_{j=0}^{k-1}(Kj​)j=0k−1​, and an arbitrary complex matrix ρ\rhoρ indexed by {0,…,a−1}×{0,…,b−1}\{0,\ldots,a-1\}\times\{0,\ldots,b-1\}{0,…,a−1}×{0,…,b−1}, this defines the matrix indexed by {0,…,a−1}×{0,…,d−1}\{0,\ldots,a-1\}\times\{0,\ldots,d-1\}{0,…,a−1}×{0,…,d−1} given by

bobApply⁡(K,ρ)=∑j=0k−1(Ia⊗Kj)ρ(Ia⊗Kj)†.\operatorname{bobApply}(K,\rho) =\sum_{j=0}^{k-1}(I_a\otimes K_j)\rho(I_a\otimes K_j)^\dagger.bobApply(K,ρ)=j=0∑k−1​(Ia​⊗Kj​)ρ(Ia​⊗Kj​)†.

Here †\dagger† denotes conjugate transpose. There is no assumption that ∑jKj†Kj=Ib\sum_jK_j^\dagger K_j=I_b∑j​Kj†​Kj​=Ib​, and no state condition on ρ\rhoρ. All dimensions may be zero; in particular, k=0k=0k=0 gives the zero matrix.

QAlgorithms.Papers.Independent.Intakenext100.P61.eigenvalueRenyiEntropy

For a finite index type III with decidable equality, any complex matrix ρ\rhoρ indexed by I×II\times II×I, and any order α∈[0,∞]\alpha\in[0,\infty]α∈[0,∞], let (λi)i=0∣I∣−1(\lambda_i)_{i=0}^{|I|-1}(λi​)i=0∣I∣−1​ be its eigenvalues in ascending order when ρ\rhoρ is Hermitian, and the all-zero family otherwise, and put S={i:λi>0}S=\{i:\lambda_i>0\}S={i:λi​>0}. Writing L(x)=ln⁡(x)/ln⁡2L(x)=\ln(x)/\ln2L(x)=ln(x)/ln2, the defined entropy is −L(max⁡i∈Sλi)-L(\max_{i\in S}\lambda_i)−L(maxi∈S​λi​) at order +∞+\infty+∞, L(∣S∣)L(|S|)L(∣S∣) at order 000, −∑i∈SλiL(λi)-\sum_{i\in S}\lambda_iL(\lambda_i)−∑i∈S​λi​L(λi​) at order 111, and L(∑i∈Sλiα)/(1−α)L(\sum_{i\in S}\lambda_i^\alpha)/(1-\alpha)L(∑i∈S​λiα​)/(1−α) at every other finite order. The maximum over an empty set is defined here to be zero, and L(0)=0L(0)=0L(0)=0, so an empty positive spectrum gives entropy zero at every order. No density-matrix assumption is imposed; empty III, non-Hermitian matrices, and Hermitian matrices with nonpositive eigenvalues are included.

QAlgorithms.Papers.Independent.Intakenext100.P61.entropyOne

For a finite type III with decidable equality and any complex matrix ρ\rhoρ indexed by I×II\times II×I, let (λi)i<∣I∣(\lambda_i)_{i<|I|}(λi​)i<∣I∣​ be its ascending eigenvalue list, counted with multiplicity if ρ\rhoρ is Hermitian and defined to be identically zero otherwise. This defines −∑i<∣I∣λiL(λi)-\sum_{i<|I|}\lambda_i L(\lambda_i)−∑i<∣I∣​λi​L(λi​), where L(x)=ln⁡x/ln⁡2L(x)=\ln x/\ln 2L(x)=lnx/ln2 uses the total real logarithm: L(0)=0L(0)=0L(0)=0, and L(x)=ln⁡∣x∣/ln⁡2L(x)=\ln|x|/\ln 2L(x)=ln∣x∣/ln2 for x≠0x\ne0x=0. The sum includes negative eigenvalues as well as positive ones; no positivity or trace-one hypothesis is imposed. Its value is 000 for non-Hermitian matrices and for empty III.

QAlgorithms.Papers.Independent.Intakenext100.P61.entropyZero

For a finite type III with decidable equality and any complex matrix ρ\rhoρ indexed by I×II\times II×I, this defines ln⁡r/ln⁡2\ln r/\ln 2lnr/ln2, where rrr is the complex dimension of the range of the linear map v↦ρvv\mapsto\rho vv↦ρv. Thus rrr is the matrix rank, without any Hermitian, positivity, or normalization assumption. When r=0r=0r=0, including when III is empty, the value is 000, using the total logarithm convention ln⁡0=0\ln 0=0ln0=0.

QAlgorithms.Papers.Independent.Intakenext100.P61.eprPairs

For every natural number kkk, this definition gives the vector indexed by {0,…,2k−1}2\{0,\ldots,2^k-1\}^2{0,…,2k−1}2 with amplitude 1/2k1/\sqrt{2^k}1/2k​ at (i,i)(i,i)(i,i) and amplitude zero at (i,j)(i,j)(i,j) when i≠ji\ne ji=j. In particular, k=0k=0k=0 gives a one-coordinate vector with amplitude 111.

QAlgorithms.Papers.Independent.Intakenext100.P61.finiteMax

For any type III with decidable equality, finite subset s⊆Is\subseteq Is⊆I, and function f:I→Rf:I\to\mathbb Rf:I→R, this defines the maximum of f(i)f(i)f(i) over i∈si\in si∈s when sss is nonempty, and defines the value to be 000 when s=∅s=\varnothings=∅. The type III itself need not be finite.

QAlgorithms.Papers.Independent.Intakenext100.P61.finiteMin

For any type III with decidable equality, finite subset s⊆Is\subseteq Is⊆I, and function f:I→Rf:I\to\mathbb Rf:I→R, this defines the minimum of f(i)f(i)f(i) over i∈si\in si∈s when sss is nonempty, and defines the value to be 000 when s=∅s=\varnothings=∅. The type III itself need not be finite.

QAlgorithms.Papers.Independent.Intakenext100.P61.harmonicHeadCuts

For every natural number nnn and every real δ\deltaδ, let Hn=∑i=1n1/iH_n=\sum_{i=1}^{n}1/iHn​=∑i=1n​1/i. This defines the finite set

Un,δ={k∈N:1≤k≤n,∑i=1k−11iHn≤δ}.U_{n,\delta}= \left\{k\in\mathbb N:1\leq k\leq n,\quad \sum_{i=1}^{k-1}\frac1{iH_n}\leq\delta\right\}.Un,δ​={k∈N:1≤k≤n,i=1∑k−1​iHn​1​≤δ}.

The subtraction k−1k-1k−1 is natural-number subtraction, and every candidate here has k≥1k\geq1k≥1. An empty sum is zero, so the set is empty when n=0n=0n=0, and for n>0n>0n>0, k=1k=1k=1 belongs exactly when δ≥0\delta\geq0δ≥0. No restriction on δ\deltaδ is part of the definition.

QAlgorithms.Papers.Independent.Intakenext100.P61.harmonicState

For every natural number nnn, let Hn=∑i=1n1/iH_n=\sum_{i=1}^{n}1/iHn​=∑i=1n​1/i. This defines the vector indexed by pairs i,j∈{0,…,n−1}i,j\in\{0,\ldots,n-1\}i,j∈{0,…,n−1} with coefficients

hn(i,j)={1(i+1)Hn,i=j,0,i≠j.h_n(i,j)= \begin{cases} \displaystyle\sqrt{\frac1{(i+1)H_n}},&i=j,\\ 0,&i\neq j. \end{cases}hn​(i,j)=⎩⎨⎧​(i+1)Hn​1​​,0,​i=j,i=j.​

For n=0n=0n=0 the index set is empty and this is the zero vector in the zero-dimensional space; for n>0n>0n>0, the displayed denominators are positive.

QAlgorithms.Papers.Independent.Intakenext100.P61.harmonicSum

For every natural number nnn, this defines the real number

Hn=∑i=1n1i.H_n=\sum_{i=1}^{n}\frac1i.Hn​=i=1∑n​i1​.

The sum is empty when n=0n=0n=0, so H0=0H_0=0H0​=0.

QAlgorithms.Papers.Independent.Intakenext100.P61.harmonicTailCuts

For every natural number nnn and every real δ\deltaδ, let Hn=∑i=1n1/iH_n=\sum_{i=1}^{n}1/iHn​=∑i=1n​1/i. This defines the finite set

Tn,δ={k∈N:1≤k≤n,∑i=k+1n1iHn≤δ}.T_{n,\delta}= \left\{k\in\mathbb N:1\leq k\leq n,\quad \sum_{i=k+1}^{n}\frac1{iH_n}\leq\delta\right\}.Tn,δ​={k∈N:1≤k≤n,i=k+1∑n​iHn​1​≤δ}.

An empty sum is zero. Thus the set is empty when n=0n=0n=0; when n>0n>0n>0, k=nk=nk=n belongs exactly when δ≥0\delta\geq0δ≥0. No restriction on δ\deltaδ is part of the definition.

QAlgorithms.Papers.Independent.Intakenext100.P61.largestWeight

For a finite type III with decidable equality and any complex matrix ρ\rhoρ indexed by I×II\times II×I, form its ascending eigenvalue list (λi)i<∣I∣(\lambda_i)_{i<|I|}(λi​)i<∣I∣​, counted with multiplicity when ρ\rhoρ is Hermitian and defined to be identically zero otherwise. This defines max⁡{λi:λi>0}\max\{\lambda_i:\lambda_i>0\}max{λi​:λi​>0} if at least one entry is strictly positive, and 000 otherwise. In particular, the value is 000 for a non-Hermitian matrix, a Hermitian matrix with no positive eigenvalues, or empty III; no density-matrix hypothesis is imposed.

QAlgorithms.Papers.Independent.Intakenext100.P61.pack

For finite types A,BA,BA,B, with their specified finite enumerations eA:A→{0,…,∣A∣−1}e_A:A\to\{0,\ldots,|A|-1\}eA​:A→{0,…,∣A∣−1} and eB:B→{0,…,∣B∣−1}e_B:B\to\{0,\ldots,|B|-1\}eB​:B→{0,…,∣B∣−1}, and any complex matrix ρ\rhoρ indexed by A×BA\times BA×B, this defines a bipartite matrix of dimensions (∣A∣,∣B∣)(|A|,|B|)(∣A∣,∣B∣) by

pack⁡(ρ)(i,j),(i′,j′)=ρ(eA−1(i),eB−1(j)),(eA−1(i′),eB−1(j′)).\operatorname{pack}(\rho)_{(i,j),(i',j')} =\rho_{(e_A^{-1}(i),e_B^{-1}(j)),(e_A^{-1}(i'),e_B^{-1}(j'))}.pack(ρ)(i,j),(i′,j′)​=ρ(eA−1​(i),eB−1​(j)),(eA−1​(i′),eB−1​(j′))​.

No state condition is imposed. Empty finite types are allowed and produce an empty matrix index set.

QAlgorithms.Papers.Independent.Intakenext100.P61.pureStateCopies

For types A,BA,BA,B, an arbitrary complex vector ψ\psiψ indexed by A×BA\times BA×B, and every natural number nnn, this definition gives a vector indexed by pairs of tuples a:{0,…,n−1}→Aa:\{0,\ldots,n-1\}\to Aa:{0,…,n−1}→A and b:{0,…,n−1}→Bb:\{0,\ldots,n-1\}\to Bb:{0,…,n−1}→B, with coordinates

Ψn(a,b)=∏j=0n−1ψ(aj,bj).\Psi_n(a,b)=\prod_{j=0}^{n-1}\psi_{(a_j,b_j)}.Ψn​(a,b)=j=0∏n−1​ψ(aj​,bj​)​.

There is no normalization assumption on ψ\psiψ. When n=0n=0n=0, both tuples are empty and the empty product is 111, so the resulting one-coordinate vector has amplitude 111, independently of ψ\psiψ.

QAlgorithms.Papers.Independent.Intakenext100.P61.renyiGap

For a finite index type III with decidable equality, any complex I×II\times II×I matrix ρ\rhoρ, and any orders α,β∈[0,∞]\alpha,\beta\in[0,\infty]α,β∈[0,∞], take λi\lambda_iλi​ to be the ascending eigenvalues of ρ\rhoρ if it is Hermitian and zero otherwise, and let S={i:λi>0}S=\{i:\lambda_i>0\}S={i:λi​>0}. With L(x)=ln⁡(x)/ln⁡2L(x)=\ln(x)/\ln2L(x)=ln(x)/ln2, define HγH_\gammaHγ​ to be L(∣S∣)L(|S|)L(∣S∣) for γ=0\gamma=0γ=0, −∑i∈SλiL(λi)-\sum_{i\in S}\lambda_iL(\lambda_i)−∑i∈S​λi​L(λi​) for γ=1\gamma=1γ=1, −L(max⁡i∈Sλi)-L(\max_{i\in S}\lambda_i)−L(maxi∈S​λi​) for γ=+∞\gamma=+\inftyγ=+∞, and L(∑i∈Sλiγ)/(1−γ)L(\sum_{i\in S}\lambda_i^\gamma)/(1-\gamma)L(∑i∈S​λiγ​)/(1−γ) otherwise. The defined gap is exactly Hα−HβH_\alpha-H_\betaHα​−Hβ​. There is no ordering assumption on α,β\alpha,\betaα,β and no density-matrix assumption on ρ\rhoρ. An empty positive spectrum uses maximum zero and L(0)=0L(0)=0L(0)=0, giving gap zero.

QAlgorithms.Papers.Independent.Intakenext100.P61.smoothInfinity

For a finite type III with decidable equality, any complex matrix ρ\rhoρ indexed by I×II\times II×I, and any real ϵ\epsilonϵ, let (λi)i<∣I∣(\lambda_i)_{i<|I|}(λi​)i<∣I∣​ be its ascending Hermitian eigenvalue list, counted with multiplicity, or zero otherwise. For each subset s⊆{i:λi>0}s\subseteq\{i:\lambda_i>0\}s⊆{i:λi​>0} satisfying ∑i∈sλi≥1−ϵ\sum_{i\in s}\lambda_i\ge1-\epsilon∑i∈s​λi​≥1−ϵ, assign the value max⁡i∈sλi\max_{i\in s}\lambda_imaxi∈s​λi​, defined to be 000 for empty sss. This defines minus the base-two logarithm of the minimum of these assigned values; if there are no qualifying subsets, that minimum is defined to be 000. The total logarithm gives −L(0)=0-L(0)=0−L(0)=0, so the result is 000 both when no subset qualifies and whenever ϵ≥1\epsilon\ge1ϵ≥1, when the empty subset qualifies. It is also 000 for non-Hermitian ρ\rhoρ or empty III; no density-matrix hypothesis is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P61.smoothRenyiGap

For a finite index type III with decidable equality, any complex I×II\times II×I matrix ρ\rhoρ, orders α,β∈[0,∞]\alpha,\beta\in[0,\infty]α,β∈[0,∞], and arbitrary real ϵ\epsilonϵ, let λi\lambda_iλi​ be the ascending eigenvalues if ρ\rhoρ is Hermitian and zero otherwise, and define

Rϵ={s⊆{i:λi>0}:1−ϵ≤∑i∈sλi}.\mathcal R_\epsilon =\left\{s\subseteq\{i:\lambda_i>0\}: 1-\epsilon\le\sum_{i\in s}\lambda_i\right\}.Rϵ​={s⊆{i:λi​>0}:1−ϵ≤i∈s∑​λi​}.

Writing L(x)=ln⁡(x)/ln⁡2L(x)=\ln(x)/\ln2L(x)=ln(x)/ln2, for each such subset define Hγ(s)H_\gamma(s)Hγ​(s) as L(∣s∣)L(|s|)L(∣s∣) at order 000, −∑i∈sλiL(λi)-\sum_{i\in s}\lambda_iL(\lambda_i)−∑i∈s​λi​L(λi​) at order 111, −L(max⁡i∈sλi)-L(\max_{i\in s}\lambda_i)−L(maxi∈s​λi​) at order +∞+\infty+∞, and L(∑i∈sλiγ)/(1−γ)L(\sum_{i\in s}\lambda_i^\gamma)/(1-\gamma)L(∑i∈s​λiγ​)/(1−γ) otherwise. The defined smoothed gap is min⁡s∈Rϵ(Hα(s)−Hβ(s))\min_{s\in\mathcal R_\epsilon}(H_\alpha(s)-H_\beta(s))mins∈Rϵ​​(Hα​(s)−Hβ​(s)) when Rϵ\mathcal R_\epsilonRϵ​ is nonempty, and zero otherwise. Empty-subset maxima are zero and L(0)=0L(0)=0L(0)=0. No density, order-comparison, or tolerance-range assumptions are imposed; in particular, an empty subset is eligible whenever ϵ≥1\epsilon\ge1ϵ≥1.

QAlgorithms.Papers.Independent.Intakenext100.P61.smoothSpread

For a finite type III with decidable equality, any complex matrix ρ\rhoρ indexed by I×II\times II×I, and any real ϵ\epsilonϵ, let (λi)i<∣I∣(\lambda_i)_{i<|I|}(λi​)i<∣I∣​ be its ascending eigenvalue list when Hermitian, counted with multiplicity, and zero otherwise. Consider every subset s⊆{i:λi>0}s\subseteq\{i:\lambda_i>0\}s⊆{i:λi​>0} with ∑i∈sλi≥1−ϵ\sum_{i\in s}\lambda_i\ge1-\epsilon∑i∈s​λi​≥1−ϵ, assigning it the value ∣s∣max⁡i∈sλi|s|\max_{i\in s}\lambda_i∣s∣maxi∈s​λi​, where the maximum over empty sss is defined to be 000. This defines the base-two logarithm of the minimum assigned value, with the minimum defined as 000 when there are no qualifying subsets and the total logarithm satisfying L(0)=0L(0)=0L(0)=0. Thus the result is 000 if no subset qualifies, if ϵ≥1\epsilon\ge1ϵ≥1, if ρ\rhoρ is non-Hermitian, or if III is empty. No positivity, trace normalization, or restriction on ϵ\epsilonϵ is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P61.smoothZero

For a finite type III with decidable equality, any complex matrix ρ\rhoρ indexed by I×II\times II×I, and any real ϵ\epsilonϵ, let (λi)i<∣I∣(\lambda_i)_{i<|I|}(λi​)i<∣I∣​ be its ascending eigenvalue list when Hermitian, counted with multiplicity, and zero otherwise. Consider all subsets sss of the strictly positive indices for which ∑i∈sλi≥1−ϵ\sum_{i\in s}\lambda_i\ge1-\epsilon∑i∈s​λi​≥1−ϵ. This defines L(min⁡s∣s∣)L(\min_s|s|)L(mins​∣s∣) when this collection is nonempty, and L(0)=0L(0)=0L(0)=0 when it is empty, where L(x)=ln⁡x/ln⁡2L(x)=\ln x/\ln2L(x)=lnx/ln2 uses the total real logarithm. In particular, the value is 000 whenever ϵ≥1\epsilon\ge1ϵ≥1, since the empty subset then qualifies, and is also 000 for non-Hermitian ρ\rhoρ or empty III. No density-matrix or error-range hypothesis is imposed.

QAlgorithms.Papers.Independent.Intakenext100.P61.smoothingError

For every real number ϵ\epsilonϵ, this definition assigns

s(ϵ)=(4ϵ)1/8,s(\epsilon)=(4\epsilon)^{1/8},s(ϵ)=(4ϵ)1/8,

using the total real-power operation. No nonnegativity restriction is part of the definition; when ϵ≥0\epsilon\ge0ϵ≥0, this is the nonnegative eighth root of 4ϵ4\epsilon4ϵ, including s(0)=0s(0)=0s(0)=0.

QAlgorithms.Papers.Independent.Intakenext100.P61.spectralRenyi

For every natural number nnn, arbitrary real family r=(ri)i=0n−1r=(r_i)_{i=0}^{n-1}r=(ri​)i=0n−1​, subset s⊆{0,…,n−1}s\subseteq\{0,\ldots,n-1\}s⊆{0,…,n−1}, and order α∈[0,∞]\alpha\in[0,\infty]α∈[0,∞], define L(x)=ln⁡(x)/ln⁡2L(x)=\ln(x)/\ln 2L(x)=ln(x)/ln2 and ms=max⁡i∈srim_s=\max_{i\in s}r_ims​=maxi∈s​ri​, with m∅=0m_\varnothing=0m∅​=0. The defined real number is

Hα(r;s)={−L(ms),α=+∞,L(∣s∣),α=0,−∑i∈sriL(ri),α=1,L ⁣(∑i∈sriα)1−α,0<α<∞, α≠1.H_\alpha(r;s)= \begin{cases} -L(m_s),&\alpha=+\infty,\\ L(|s|),&\alpha=0,\\ -\displaystyle\sum_{i\in s}r_iL(r_i),&\alpha=1,\\ \displaystyle\frac{L\!\left(\sum_{i\in s}r_i^\alpha\right)}{1-\alpha}, &0<\alpha<\infty,\ \alpha\ne1. \end{cases}Hα​(r;s)=⎩⎨⎧​−L(ms​),L(∣s∣),−i∈s∑​ri​L(ri​),1−αL(∑i∈s​riα​)​,​α=+∞,α=0,α=1,0<α<∞, α=1.​

There are no positivity or normalization assumptions on rrr. Powers and logarithms use their total real-valued definitions; in particular, L(0)=0L(0)=0L(0)=0. The case n=0n=0n=0 is included, and an empty sss gives Hα(r;s)=0H_\alpha(r;s)=0Hα​(r;s)=0 at every order.

QAlgorithms.Papers.Independent.Intakenext100.P61.spectralRetentions

For a finite type III with decidable equality, any complex matrix ρ\rhoρ indexed by I×II\times II×I, and any real ϵ\epsilonϵ, let (λi)i<∣I∣(\lambda_i)_{i<|I|}(λi​)i<∣I∣​ be its ascending Hermitian eigenvalue list, counted with multiplicity, or the identically zero list if ρ\rhoρ is not Hermitian. This defines the finite collection of all subsets s⊆{i:λi>0}s\subseteq\{i:\lambda_i>0\}s⊆{i:λi​>0} satisfying 1−ϵ≤∑i∈sλi1-\epsilon\le\sum_{i\in s}\lambda_i1−ϵ≤∑i∈s​λi​. Neither normalization of ρ\rhoρ nor a range restriction on ϵ\epsilonϵ is assumed. The empty subset belongs exactly when ϵ≥1\epsilon\ge1ϵ≥1; the collection can be empty. If the positive-index set is empty, the collection is {∅}\{\varnothing\}{∅} for ϵ≥1\epsilon\ge1ϵ≥1 and empty otherwise.

QAlgorithms.Papers.Independent.Intakenext100.P61.spectralSupport

For a finite type III with decidable equality and any complex matrix ρ\rhoρ indexed by I×II\times II×I, let λ0,…,λ∣I∣−1\lambda_0,\ldots,\lambda_{|I|-1}λ0​,…,λ∣I∣−1​ be its eigenvalues in ascending order, counted with multiplicity, if ρ\rhoρ is Hermitian; if ρ\rhoρ is not Hermitian, set every λi=0\lambda_i=0λi​=0. This defines the finite set {i:0≤i<∣I∣, λi>0}\{i:0\le i<|I|,\ \lambda_i>0\}{i:0≤i<∣I∣, λi​>0}. Thus it includes only strictly positive entries of this eigenvalue list, and is empty for non-Hermitian matrices and for empty III. No positivity or trace normalization of ρ\rhoρ is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P61.spread

For a finite type III with decidable equality and any complex matrix ρ\rhoρ indexed by I×II\times II×I, write rrr for its complex matrix rank and L(x)=ln⁡x/ln⁡2L(x)=\ln x/\ln 2L(x)=lnx/ln2, with the total real logarithm convention L(0)=0L(0)=0L(0)=0. This defines L(r)−H∞(ρ)L(r)-H_\infty(\rho)L(r)−H∞​(ρ), where H∞(ρ)=−L(sup⁡{λ:λ occurs in the Hermitian eigenvalue list of ρ})H_\infty(\rho)=-L(\sup\{\lambda:\lambda\text{ occurs in the Hermitian eigenvalue list of }\rho\})H∞​(ρ)=−L(sup{λ:λ occurs in the Hermitian eigenvalue list of ρ}) when ρ\rhoρ is Hermitian, and H∞(ρ)=0H_\infty(\rho)=0H∞​(ρ)=0 otherwise. For Hermitian ρ\rhoρ, the supremum is over all eigenvalues, including nonpositive ones; for an empty list its real supremum is 000. Consequently the spread is L(r)L(r)L(r) for non-Hermitian ρ\rhoρ, and 000 when III is empty. No density-matrix hypothesis is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P61.tensorPureStates

For types A,B,C,DA,B,C,DA,B,C,D and arbitrary complex vectors ϕ\phiϕ indexed by A×BA\times BA×B and ψ\psiψ indexed by C×DC\times DC×D, this definition produces the vector indexed by (A×C)×(B×D)(A\times C)\times(B\times D)(A×C)×(B×D) whose coordinates are

(ϕ⊗ψ)((a,c),(b,d))=ϕ(a,b)ψ(c,d).(\phi\otimes\psi)_{((a,c),(b,d))}=\phi_{(a,b)}\psi_{(c,d)}.(ϕ⊗ψ)((a,c),(b,d))​=ϕ(a,b)​ψ(c,d)​.

Thus the two first registers are grouped together, as are the two second registers. No normalization hypothesis is imposed.

QAlgorithms.Papers.Independent.Intakenext100.P61.transferAB

For any natural numbers a,b,ma,b,ma,b,m and any complex matrix ρ\rhoρ indexed by {0,…,am−1}×{0,…,b−1}\{0,\ldots,am-1\}\times\{0,\ldots,b-1\}{0,…,am−1}×{0,…,b−1}, this defines a matrix ρ~\widetilde\rhoρ​ indexed by {0,…,a−1}×{0,…,mb−1}\{0,\ldots,a-1\}\times\{0,\ldots,mb-1\}{0,…,a−1}×{0,…,mb−1} by regrouping the indices:

ρ~(i, ub+v),(i′, u′b+v′)=ρ(im+u, v),(i′m+u′, v′)\widetilde\rho_{(i,\,ub+v),(i',\,u'b+v')} =\rho_{(im+u,\,v),(i'm+u',\,v')}ρ​(i,ub+v),(i′,u′b+v′)​=ρ(im+u,v),(i′m+u′,v′)​

for all i,i′<ai,i'<ai,i′<a, u,u′<mu,u'<mu,u′<m, and v,v′<bv,v'<bv,v′<b. No state condition or positivity assumption is imposed. The definition includes m=0m=0m=0 and zero values of aaa or bbb; in these cases the matrix index sets are empty.

QAlgorithms.Papers.Independent.Intakenext100.P61.transferBA

For any natural numbers a,b,ma,b,ma,b,m and any complex matrix ρ\rhoρ indexed by {0,…,a−1}×{0,…,mb−1}\{0,\ldots,a-1\}\times\{0,\ldots,mb-1\}{0,…,a−1}×{0,…,mb−1}, this defines a matrix ρ~\widetilde\rhoρ​ indexed by {0,…,am−1}×{0,…,b−1}\{0,\ldots,am-1\}\times\{0,\ldots,b-1\}{0,…,am−1}×{0,…,b−1} by regrouping the indices:

ρ~(im+u, v),(i′m+u′, v′)=ρ(i, ub+v),(i′, u′b+v′)\widetilde\rho_{(im+u,\,v),(i'm+u',\,v')} =\rho_{(i,\,ub+v),(i',\,u'b+v')}ρ​(im+u,v),(i′m+u′,v′)​=ρ(i,ub+v),(i′,u′b+v′)​

for all i,i′<ai,i'<ai,i′<a, u,u′<mu,u'<mu,u′<m, and v,v′<bv,v'<bv,v′<b. No state condition or positivity assumption is imposed. The definition includes m=0m=0m=0 and zero values of aaa or bbb; in these cases the matrix index sets are empty.

QAlgorithms.Papers.Independent.Intakenext100.P61.upperRenyiFactor

For every order β∈[0,∞]\beta\in[0,\infty]β∈[0,∞], the defined real factor is 111 if β=+∞\beta=+\inftyβ=+∞, and is b/(b−1)b/(b-1)b/(b−1) if β\betaβ is the finite nonnegative real number bbb. In particular, the factor is 000 at both b=0b=0b=0 and b=1b=1b=1, since real division by zero is defined to be zero; it is negative when 0<b<10<b<10<b<1.

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