Definitions for Tema Con Variazioni: Quantum Channel Capacity
DefinitionQAlgorithms_Papers_Independent_Gap20_P07The objects the formalized statements of Tema Con Variazioni: Quantum Channel Capacity (arXiv:quant-ph/0311037) are stated in. Each was checked against the paper by a blind read-back and a moderator.
TCChannel: PDF pp.2--3: all CPTP maps on the full trace class, with no assistance.codingSimulationDistance: PDF p.3, (2): actual coding infimum, retaining infinity and the full cb norm.blockError: PDF p.3: block error for independent parallel uses of both channels.rateRatio: PDF p.3: nonnegative extended rate ratios avoid real limsup defaults.AllSequenceRate: PDF p.3, Definition 2.1: every diverging positive block sequence with limsup ratio at most R has vanishing computed error. Positivity of R is separate.errorCapacity: PDF p.3: supremum of positive rates; empty supremum is zero.relativeCapacity: PDF p.3: relative capacity with exactly this paper's limsup convention.qubitReferenceCapacity: PDF p.3: the ideal qubit fixes the unit bit.Sporadic: PDF pp.3--4: sporadic rates use just one diverging block sequence.sporadicCapacity: PDF pp.4,29: supremum, without asserting achievability at its endpoint.finiteErrorCapacity: PDF p.6: eventual full-cb error at most epsilon, including the exact-zero variant.TraceClassBlockCode: PDF pp.4--5: a physical unassisted code for a d-level system through n uses.TraceClassBlockCode.effective: PDF pp.4--5: the corrected channel, computed from its actual maps.TraceClassBlockCode.error: PDF pp.28--29: error of a particular code, not an independent parameter.minimumFidelity: PDF p.4, (4): minimum over the normalized finite unit sphere.minimumFe: PDF p.5, (8): infimum over density matrices, never all trace-class operators.ordinaryNorm: PDF pp.2,13: full induced trace norm, equivalently the dual operator norm.finiteCbNorm: PDF pp.2,13: full stabilized trace norm. In the finite lawful uses below the extended norm is finite, so conversion to a real cannot discard infinity.FidelityCriterion: PDF pp.4--5: the four fidelity criteria on one corrected logical channel.fidelityValue: PDF pp.4--5, (4)--(9): all overlaps are squared.FidelityAchievable: PDF p.4: one code for each positive n; the rate is the printed limsup.fidelityCapacity: PDF pp.4--5: capacity for a specified fidelity criterion.ordinaryCapacity: PDF pp.11--14: capacity from the ordinary induced trace-norm error.ExponentialReliable: PDF pp.6,29: positive exponential decay for all positive block lengths.exponentialCapacity: PDF pp.6,29: supremum of positive rates with some positive exponential exponent.QuantumSource: PDF pp.5--6: arbitrary nonzero finite block spaces, not a fixed tensor source.QuantumSource.entropyRate: PDF p.5, (10): extended limsup bit-entropy per positive block length.QuantumSource.typical: PDF p.19, (66): the full spectral typical window; no global eigenvalue bound.QuantumSource.typicalMass: PDF p.19: mass of the typical spectral restriction.QuantumSource.typicalRestriction: PDF p.19: normalized restriction is used only when its mass is positive, which QAEP guarantees eventually. Its unused zero-mass value is the zero operator.QuantumSource.QAEP: PDF p.19: QAEP means asymptotically all mass in every typical window.QuantumSource.ExponentialDimension: PDF pp.6,19: each source has its own exponential dimension bound.SourceReliable: PDF p.5: one pair of CPTP maps on the whole source space per n.sourceEntropyCapacity: PDF pp.5--6: source-restricted entropy capacity; downward closure of rate witnesses preserves the supremum and includes infinite entropy rates.enlargedMixture: PDF p.19, (67): actual direct-sum mixture, in consecutive coordinate blocks.VariableSourceGenerationRate: PDF pp.5,19--20: arbitrary normalized Gamma, compared with maximally entangled Omega.variableSourceGenerationCapacity: PDF pp.5,19--20: unassisted entanglement-generation capacity.TraceClassBlockCode.Isometric: PDF pp.7,20--22: isometric encoding on every trace-class argument.isometricCapacity: PDF pp.7,22: fidelity capacity restricted only at the encoder.Subchannel: PDF p.22: a CP trace-nonincreasing operation is linear and every finite amplification sends each density to a subnormalized density. The zero branch is allowed.TraceClassForwardBlockCode: PDF pp.22--23: instrument outcomes followed by their CPTP decoders. The branches sum to a channel; the summed unnormalized fidelities preclude postselection.TraceClassForwardBlockCode.fidelity: PDF p.23, (82): sum, with no branch normalization.instrumentForwardCapacity: PDF pp.22--23: the message budget may grow arbitrarily rapidly.classicalIdentity: PDF p.3: ideal classical bits are diagonal quantum channels.compressedChannel: PDF p.17, (54): compression into the actual k-dimensional isometric range.firstCoordinatePinching: PDF p.16, (51): firstCoordinatePinching off the first one-dimensional coordinate.hashingBound: PDF p.29, (107): exact expression, allowed to be negative.hashingSupremum: PDF p.29: supremum over actual prime-dimensional codes; negative bounds contribute zero to the nonnegative capacity lattice.ErrorMonotone: PDF pp.26--27: wasting one physical use or one requested output use.ErrorSubadditive: PDF p.27, (101): tensor blocking is subadditivity.blockingEnvelope: PDF p.27, (102): finite multisets of available blocks, with repetitions. Clipping at one makes the error finite even when no block packing is possible.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_QuditChannelFidelities
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P35
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P29
/-! Kretschmann--Werner, quant-ph/0311037v1. Physical systems have arbitrary
nonempty orthonormal-basis index types, with completed l2 Hilbert spaces and
full nuclear trace class. Logical systems are finite and nonzero. The independent
paper override permits the pinned accepted paper modules imported here.
Only source theorems are admitted. Compilation and independent moderation pending. -/
noncomputable section
open Filter MeasureTheory
open scoped Topology ENNReal NNReal Matrix ComplexOrder ComplexConjugate
attribute [local instance] Classical.propDecidable
attribute [local instance] Classical.decEq
attribute [local instance] IsStarNormal.instContinuousFunctionalCalculus
namespace QAlgorithms.Papers.Independent.Gap20.P07
open QAlgorithms
open QAlgorithms.RealRegisters (Hilbert)
open QAlgorithms.Papers.Independent.Dependency50.P33
(State IsTraceClass IsTraceClassChannel traceSize rankOne tensorApply)
open QAlgorithms.Papers.Independent.Frontier30.P14
(Operation isometryCoeff conjugateKernel)
open QAlgorithms.Papers.Independent.Claimed50.P35
(stabilizedTraceClassNorm traceClassTensorMap traceClassChannelPower
transpose transposeBound TraceLinear tracePair MeasurePrepare)
open QAlgorithms.Papers.Independent.Gap48.P29 (fe FiniteCPMap)
/-! The accepted basenames flagged by the mechanical check denote other concepts:
classical correlation simulation, PPT distillation, finite or zero-error capacities,
energy-constrained entropy, fixed-letter source instruments, and shape-indexed
pinching. They cannot replace Definition 2.1 or its arbitrary-system variations.
The distinct paper-local names below retain the original bodies; accepted trace
class, CPTP, tensor, norm, fidelity and Haar definitions remain imported above.
ASSESSMENT.json records exact declaration/type comparisons for each collision. -/
/-- PDF pp.2--3: all CPTP maps on the full trace class, with no assistance. -/
abbrev TCChannel (I J : Type) := {E : Operation I J // IsTraceClassChannel E}
/-- PDF p.3, (2): actual coding infimum, retaining infinity and the full cb norm. -/
def codingSimulationDistance {I J K L : Type} (T : Operation I J) (S : Operation K L) : ℝ≥0∞ :=
⨅ E : TCChannel K I, ⨅ D : TCChannel J L,
stabilizedTraceClassNorm (fun X => D.val (T (E.val X)) - S X)
/-- PDF p.3: block error for independent parallel uses of both channels. -/
def blockError {I J K L : Type} (T : Operation I J) (S : Operation K L)
(n m : ℕ+) : ℝ≥0∞ :=
codingSimulationDistance (traceClassChannelPower T n) (traceClassChannelPower S m)
/-- PDF p.3: nonnegative extended rate ratios avoid real limsup defaults. -/
def rateRatio (n m : ℕ → ℕ+) (a : ℕ) : ℝ≥0∞ :=
(m a : ℝ≥0∞) / (n a : ℝ≥0∞)
/-- PDF p.3, Definition 2.1: every diverging positive block sequence with
limsup ratio at most R has vanishing computed error. Positivity of R is separate. -/
def AllSequenceRate (delta : ℕ+ → ℕ+ → ℝ≥0∞) (R : ℝ) : Prop :=
∀ n m : ℕ → ℕ+, Tendsto (fun a => (n a : ℕ)) atTop atTop →
Filter.limsup (rateRatio n m) atTop ≤ ENNReal.ofReal R →
Tendsto (fun a => delta (n a) (m a)) atTop (𝓝 0)
/-- PDF p.3: supremum of positive rates; empty supremum is zero. -/
def errorCapacity (delta : ℕ+ → ℕ+ → ℝ≥0∞) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ AllSequenceRate delta R}, ENNReal.ofReal R.val
/-- PDF p.3: relative capacity with exactly this paper's limsup convention. -/
def relativeCapacity {I J K L : Type} (T : Operation I J) (S : Operation K L) : ℝ≥0∞ :=
errorCapacity (blockError T S)
/-- PDF p.3: the ideal qubit fixes the unit bit. -/
def qubitReferenceCapacity {I J : Type} (T : Operation I J) : ℝ≥0∞ :=
relativeCapacity T (id : Operation (Fin 2) (Fin 2))
/-- PDF pp.3--4: sporadic rates use just one diverging block sequence. -/
def Sporadic (delta : ℕ+ → ℕ+ → ℝ≥0∞) (R : ℝ) : Prop :=
∃ n m : ℕ → ℕ+, Tendsto (fun a => (n a : ℕ)) atTop atTop ∧
Filter.limsup (rateRatio n m) atTop = ENNReal.ofReal R ∧
Tendsto (fun a => delta (n a) (m a)) atTop (𝓝 0)
/-- PDF pp.4,29: supremum, without asserting achievability at its endpoint. -/
def sporadicCapacity {I J : Type} (T : Operation I J) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ Sporadic (blockError T (id : Operation (Fin 2) (Fin 2))) R},
ENNReal.ofReal R.val
/-- PDF p.6: eventual full-cb error at most epsilon, including the exact-zero variant. -/
def finiteErrorCapacity {I J : Type} (T : Operation I J) (epsilon : ℝ) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ ∀ n m : ℕ → ℕ+,
Tendsto (fun a => (n a : ℕ)) atTop atTop →
Filter.limsup (rateRatio n m) atTop ≤ ENNReal.ofReal R →
∀ᶠ a in atTop, blockError T (id : Operation (Fin 2) (Fin 2)) (n a) (m a) ≤
ENNReal.ofReal epsilon}, ENNReal.ofReal R.val
/-- PDF pp.4--5: a physical unassisted code for a d-level system through n uses. -/
structure TraceClassBlockCode {I J : Type} (T : Operation I J) (n d : ℕ) where
enc : TCChannel (Fin d) (Fin n → I)
dec : TCChannel (Fin n → J) (Fin d)
/-- PDF pp.4--5: the corrected channel, computed from its actual maps. -/
def TraceClassBlockCode.effective {I J : Type} {T : Operation I J} {n d : ℕ} (C : TraceClassBlockCode T n d) :
Superop (Fin d) (Fin d) :=
C.dec.val ∘ traceClassChannelPower T n ∘ C.enc.val
/-- PDF pp.28--29: error of a particular code, not an independent parameter. -/
def TraceClassBlockCode.error {I J : Type} {T : Operation I J} {n d : ℕ} (C : TraceClassBlockCode T n d) : ℝ≥0∞ :=
stabilizedTraceClassNorm (fun X => C.effective X - X)
/-- PDF p.4, (4): minimum over the normalized finite unit sphere. -/
def minimumFidelity (d : ℕ) (T : Superop (Fin d) (Fin d)) : ℝ :=
sInf {r : ℝ | ∃ psi : EuclideanSpace ℂ (Fin d), IsState psi ∧
r = effectProb (pureDensity psi) (T (pureDensity psi))}
/-- PDF p.5, (8): infimum over density matrices, never all trace-class operators. -/
def minimumFe (d : ℕ) (T : Superop (Fin d) (Fin d)) : ℝ :=
sInf {r : ℝ | ∃ rho : Matrix (Fin d) (Fin d) ℂ, IsDensityMatrix rho ∧ r = fe rho T}
/-- PDF pp.2,13: full induced trace norm, equivalently the dual operator norm. -/
def ordinaryNorm (d : ℕ) (T : Superop (Fin d) (Fin d)) : ℝ :=
sSup {r : ℝ | ∃ X : Matrix (Fin d) (Fin d) ℂ, traceNorm X ≤ 1 ∧ r = traceNorm (T X)}
/-- PDF pp.2,13: full stabilized trace norm. In the finite lawful uses below the
extended norm is finite, so conversion to a real cannot discard infinity. -/
def finiteCbNorm (d : ℕ) (T : Superop (Fin d) (Fin d)) : ℝ :=
(stabilizedTraceClassNorm T).toReal
/-- PDF pp.4--5: the four fidelity criteria on one corrected logical channel. -/
inductive FidelityCriterion where
| minimum | entanglement | average | channel
/-- PDF pp.4--5, (4)--(9): all overlaps are squared. -/
def fidelityValue (c : FidelityCriterion) (d : ℕ+) (T : Superop (Fin d) (Fin d)) : ℝ :=
match c with
| .minimum => minimumFidelity d T
| .entanglement => minimumFe d T
| .average => QuditFidelity.averageFidelity d d.pos T
| .channel => QuditFidelity.entanglementFidelity d d.pos T
/-- PDF p.4: one code for each positive n; the rate is the printed limsup. -/
def FidelityAchievable {I J : Type} (T : Operation I J) (c : FidelityCriterion) (R : ℝ) : Prop :=
∃ d : ℕ → ℕ+, ∃ C : (a : ℕ) → TraceClassBlockCode T (a + 1) (d a),
Filter.limsup (fun a => ENNReal.ofReal (Real.logb 2 (d a : ℝ) / (a + 1 : ℝ))) atTop =
ENNReal.ofReal R ∧
Tendsto (fun a => fidelityValue c (d a) (C a).effective) atTop (𝓝 1)
/-- PDF pp.4--5: capacity for a specified fidelity criterion. -/
def fidelityCapacity {I J : Type} (T : Operation I J) (c : FidelityCriterion) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ FidelityAchievable T c R}, ENNReal.ofReal R.val
/-- PDF pp.11--14: capacity from the ordinary induced trace-norm error. -/
def ordinaryCapacity {I J : Type} (T : Operation I J) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ ∃ d : ℕ → ℕ+,
∃ C : (n : ℕ) → TraceClassBlockCode T (n + 1) (d n),
Filter.limsup (fun n => ENNReal.ofReal (Real.logb 2 (d n : ℝ) / (n + 1 : ℝ))) atTop =
ENNReal.ofReal R ∧
Tendsto (fun n => ordinaryNorm (d n) (fun X => (C n).effective X - X)) atTop (𝓝 0)},
ENNReal.ofReal R.val
/-- PDF pp.6,29: positive exponential decay for all positive block lengths. -/
def ExponentialReliable {I J : Type} (T : Operation I J) (R : ℝ) : Prop :=
∃ (a C : ℝ), 0 < a ∧ 0 < C ∧
∃ codes : (n : ℕ) → TraceClassBlockCode T (n + 1) (2 ^ Nat.floor ((n + 1 : ℝ) * R)),
∀ᶠ n in atTop, (codes n).error ≤ ENNReal.ofReal (C * Real.exp (-a * (n + 1 : ℝ)))
/-- PDF pp.6,29: supremum of positive rates with some positive exponential exponent. -/
def exponentialCapacity {I J : Type} (T : Operation I J) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ ExponentialReliable T R}, ENNReal.ofReal R.val
/-- PDF pp.5--6: arbitrary nonzero finite block spaces, not a fixed tensor source. -/
structure QuantumSource where
dimension : ℕ → ℕ+
rho : (n : ℕ) → Matrix (Fin (dimension n)) (Fin (dimension n)) ℂ
density : ∀ n, IsDensityMatrix (rho n)
/-- PDF p.5, (10): extended limsup bit-entropy per positive block length. -/
def QuantumSource.entropyRate (S : QuantumSource) : ℝ≥0∞ :=
Filter.limsup (fun n => ENNReal.ofReal (vnEntropy (S.rho n) / (n + 1 : ℝ))) atTop
/-- PDF p.19, (66): the full spectral typical window; no global eigenvalue bound. -/
def QuantumSource.typical (S : QuantumSource) (R epsilon : ℝ) (n : ℕ) :=
cfc (fun x : ℝ => if (2 : ℝ) ^ (-(n + 1 : ℝ) * (R + epsilon)) ≤ x ∧
x ≤ (2 : ℝ) ^ (-(n + 1 : ℝ) * (R - epsilon)) then 1 else 0) (S.rho n)
/-- PDF p.19: mass of the typical spectral restriction. -/
def QuantumSource.typicalMass (S : QuantumSource) (R epsilon : ℝ) (n : ℕ) : ℝ :=
((S.typical R epsilon n * S.rho n * S.typical R epsilon n).trace).re
/-- PDF p.19: normalized restriction is used only when its mass is positive,
which QAEP guarantees eventually. Its unused zero-mass value is the zero operator. -/
def QuantumSource.typicalRestriction (S : QuantumSource) (R epsilon : ℝ) (n : ℕ) :=
((S.typicalMass R epsilon n : ℂ)⁻¹) •
(S.typical R epsilon n * S.rho n * S.typical R epsilon n)
/-- PDF p.19: QAEP means asymptotically all mass in every typical window. -/
def QuantumSource.QAEP (S : QuantumSource) : Prop :=
∃ R : ℝ, 0 ≤ R ∧ S.entropyRate = ENNReal.ofReal R ∧
∀ epsilon : ℝ, 0 < epsilon → Tendsto (S.typicalMass R epsilon) atTop (𝓝 1)
/-- PDF pp.6,19: each source has its own exponential dimension bound. -/
def QuantumSource.ExponentialDimension (S : QuantumSource) : Prop :=
∃ tau : ℝ, 0 < tau ∧ ∀ n, (S.dimension n : ℝ) ≤ tau ^ (n + 1)
/-- PDF p.5: one pair of CPTP maps on the whole source space per n. -/
def SourceReliable {I J : Type} (T : Operation I J) (S : QuantumSource) : Prop :=
∃ C : (n : ℕ) → TraceClassBlockCode T (n + 1) (S.dimension n),
Tendsto (fun n => fe (S.rho n) (C n).effective) atTop (𝓝 1)
/-- PDF pp.5--6: source-restricted entropy capacity; downward closure of rate
witnesses preserves the supremum and includes infinite entropy rates. -/
def sourceEntropyCapacity {I J : Type} (T : Operation I J) (P : QuantumSource → Prop) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ ∃ S : QuantumSource,
P S ∧ SourceReliable T S ∧ ENNReal.ofReal R ≤ S.entropyRate}, ENNReal.ofReal R.val
/-- PDF p.19, (67): actual direct-sum mixture, in consecutive coordinate blocks. -/
def enlargedMixture (d k : ℕ+) (epsilon : ℝ) : Matrix (Fin (d + k : ℕ+)) (Fin (d + k : ℕ+)) ℂ :=
Matrix.diagonal fun i => if i.val < (d : ℕ) then
(((1 - epsilon) / (d : ℝ) : ℝ) : ℂ) else ((epsilon / (k : ℝ) : ℝ) : ℂ)
/-- PDF pp.5,19--20: arbitrary normalized Gamma, compared with maximally entangled Omega. -/
def VariableSourceGenerationRate {I J : Type} (T : Operation I J) (R : ℝ) : Prop :=
∃ d : ℕ → ℕ+, ∃ C : (n : ℕ) → TraceClassBlockCode T (n + 1) (d n),
∃ gamma : (n : ℕ) → EuclideanSpace ℂ (Fin (d n) × Fin (d n)),
(∀ n, IsState (gamma n)) ∧
Filter.limsup (fun n => ENNReal.ofReal (Real.logb 2 (d n : ℝ) / (n + 1 : ℝ))) atTop =
ENNReal.ofReal R ∧
Tendsto (fun n => letI : Nonempty (Fin (d n)) := ⟨⟨0,(d n).pos⟩⟩
effectProb (pureDensity (finiteMaxEntangled (Fin (d n))))
(idTensorSuperop (C n).effective (pureDensity (gamma n)))) atTop (𝓝 1)
/-- PDF pp.5,19--20: unassisted entanglement-generation capacity. -/
def variableSourceGenerationCapacity {I J : Type} (T : Operation I J) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ VariableSourceGenerationRate T R}, ENNReal.ofReal R.val
/-- PDF pp.7,20--22: isometric encoding on every trace-class argument. -/
def TraceClassBlockCode.Isometric {I J : Type} {T : Operation I J} {n d : ℕ} (C : TraceClassBlockCode T n d) : Prop :=
∃ V : Hilbert (Fin d) →ₗᵢ[ℂ] Hilbert (Fin n → I),
∀ X, IsTraceClass X → C.enc.val X = conjugateKernel (isometryCoeff V) X
/-- PDF pp.7,22: fidelity capacity restricted only at the encoder. -/
def isometricCapacity {I J : Type} (T : Operation I J) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ ∃ d : ℕ → ℕ+,
∃ C : (n : ℕ) → TraceClassBlockCode T (n + 1) (d n),
(∀ n, (C n).Isometric) ∧
Filter.limsup (fun n => ENNReal.ofReal (Real.logb 2 (d n : ℝ) / (n + 1 : ℝ))) atTop =
ENNReal.ofReal R ∧
Tendsto (fun n => fidelityValue .channel (d n) (C n).effective) atTop (𝓝 1)},
ENNReal.ofReal R.val
/-- PDF p.22: a CP trace-nonincreasing operation is linear and every finite
amplification sends each density to a subnormalized density. The zero branch is allowed. -/
def Subchannel {I J : Type} (E : Operation I J) : Prop :=
TraceLinear E ∧ ∀ k : ℕ, ∀ rho : State (I × Fin k),
∃ p : ℝ, 0 ≤ p ∧ p ≤ 1 ∧ ∃ sigma : State (J × Fin k),
tensorApply E rho.coefficients = (p : ℂ) • sigma.coefficients
/-- PDF pp.22--23: instrument outcomes followed by their CPTP decoders.
The branches sum to a channel; the summed unnormalized fidelities preclude postselection. -/
structure TraceClassForwardBlockCode {I J : Type} (T : Operation I J) (n d messages : ℕ) where
enc : Fin messages → Operation (Fin d) (Fin n → I)
branch : ∀ j, Subchannel (enc j)
total : IsTraceClassChannel (fun X => ∑ j, enc j X)
dec : Fin messages → TCChannel (Fin n → J) (Fin d)
/-- PDF p.23, (82): sum, with no branch normalization. -/
def TraceClassForwardBlockCode.fidelity {I J : Type} {T : Operation I J} {n d messages : ℕ}
(C : TraceClassForwardBlockCode T n d messages) (hd : 0 < d) : ℝ :=
∑ j, QuditFidelity.entanglementFidelity d hd
((C.dec j).val ∘ traceClassChannelPower T n ∘ C.enc j)
/-- PDF pp.22--23: the message budget may grow arbitrarily rapidly. -/
def instrumentForwardCapacity {I J : Type} (T : Operation I J) (budget : ℕ → ℕ+ → Prop) : ℝ≥0∞ :=
⨆ R : {R : ℝ // 0 < R ∧ ∃ d messages : ℕ → ℕ+,
(∀ n, budget n (messages n)) ∧
∃ C : (n : ℕ) → TraceClassForwardBlockCode T (n + 1) (d n) (messages n),
Filter.limsup (fun n => ENNReal.ofReal (Real.logb 2 (d n : ℝ) / (n + 1 : ℝ))) atTop =
ENNReal.ofReal R ∧
Tendsto (fun n => (C n).fidelity (d n).pos) atTop (𝓝 1)}, ENNReal.ofReal R.val
/-- PDF p.3: ideal classical bits are diagonal quantum channels. -/
def classicalIdentity (d : ℕ) : Operation (Fin d) (Fin d) :=
fun X => Matrix.diagonal (Matrix.diag X)
/-- PDF p.17, (54): compression into the actual k-dimensional isometric range. -/
def compressedChannel {d k : ℕ} (V : Matrix (Fin d) (Fin k) ℂ)
(T : Superop (Fin d) (Fin d)) : Superop (Fin k) (Fin k) :=
fun X => let Y := T (V * X * V.conjTranspose)
V.conjTranspose * Y * V + ((((1 - V * V.conjTranspose) * Y).trace / (k : ℂ))) • 1
/-- PDF p.16, (51): firstCoordinatePinching off the first one-dimensional coordinate. -/
def firstCoordinatePinching (d : ℕ+) : Superop (Fin d) (Fin d) :=
let P := pureDensity (ket (⟨0,d.pos⟩ : Fin d))
fun X => P * X * P + (1 - P) * X * (1 - P)
/-- PDF p.29, (107): exact expression, allowed to be negative. -/
def hashingBound (N d : ℕ) (delta : ℝ) : ℝ :=
Real.logb 2 d / N * (1 - 4 * Real.exp 1 * delta) - binEntropy2 (2 * Real.exp 1 * delta) / N
/-- PDF p.29: supremum over actual prime-dimensional codes; negative bounds
contribute zero to the nonnegative capacity lattice. -/
def hashingSupremum {I J : Type} (T : Operation I J) : ℝ≥0∞ :=
⨆ N : ℕ+, ⨆ d : {d : ℕ // Nat.Prime d}, ⨆ C : TraceClassBlockCode T N d.val,
⨆ _h : C.error < ENNReal.ofReal (1 / (2 * Real.exp 1)),
ENNReal.ofReal (hashingBound N d.val C.error.toReal)
/-- PDF pp.26--27: wasting one physical use or one requested output use. -/
def ErrorMonotone (delta : ℕ+ → ℕ+ → ℝ≥0∞) : Prop :=
∀ n m, delta (n + 1) m ≤ delta n m ∧ delta n m ≤ delta n (m + 1)
/-- PDF p.27, (101): tensor blocking is subadditivity. -/
def ErrorSubadditive (delta : ℕ+ → ℕ+ → ℝ≥0∞) : Prop :=
∀ n k m l, delta (n + k) (m + l) ≤ delta n m + delta k l
/-- PDF p.27, (102): finite multisets of available blocks, with repetitions.
Clipping at one makes the error finite even when no block packing is possible. -/
def blockingEnvelope (N : ℕ → ℕ+) (epsilon : ℕ → ℝ≥0) (n m : ℕ+) : ℝ≥0∞ :=
min 1 (sInf {c : ℝ≥0∞ | ∃ blocks : List ℕ,
(m : ℕ) ≤ (blocks.map (fun j => (N j : ℕ))).sum ∧
(blocks.map (fun j => (N j : ℕ))).sum ≤ (n : ℕ) ∧
c = (blocks.map (fun j => (epsilon j : ℝ≥0∞))).sum})
/-! Definitional sanity checks pin tensor powers, dimensions, sums, and zero endpoints.
They prove no paper result. -/
example (n m : ℕ → ℕ+) (a : ℕ) :
rateRatio n m a = (m a : ℝ≥0∞) / (n a : ℝ≥0∞) := rfl
example {I J : Type} {T : Operation I J} {n d : ℕ} (C : TraceClassBlockCode T n d) (X : Matrix (Fin d) (Fin d) ℂ) :
C.effective X = C.dec.val (traceClassChannelPower T n (C.enc.val X)) := rfl
example (S : QuantumSource) (R epsilon : ℝ) (n : ℕ)
(h : S.typicalMass R epsilon n = 0) : S.typicalRestriction R epsilon n = 0 := by
simp [QuantumSource.typicalRestriction, h]
example (d : ℕ) (X : Matrix (Fin d) (Fin d) ℂ) :
classicalIdentity d X = Matrix.diagonal (Matrix.diag X) := rfl
example (d k : ℕ+) (epsilon : ℝ) (i : Fin (d + k : ℕ+)) (h : i.val < (d : ℕ)) :
enlargedMixture d k epsilon i i = (((1 - epsilon) / (d : ℝ) : ℝ) : ℂ) := by
unfold enlargedMixture
rw [Matrix.diagonal_apply_eq, if_pos h]
example (N d : ℕ) : hashingBound N d 0 = Real.logb 2 d / N := by
simp [hashingBound, binEntropy2]
example (N : ℕ → ℕ+) (epsilon : ℕ → ℝ≥0) (n m : ℕ+) :
blockingEnvelope N epsilon n m ≤ 1 := min_le_left _ _
example (d : ℕ) (T : Superop (Fin d) (Fin d)) :
compressedChannel (1 : Matrix (Fin d) (Fin d) ℂ) T = T := by
funext X
simp [compressedChannel]
example : (enlargedMixture 1 1 (1 / 2)).trace = 1 := by
norm_num [enlargedMixture, Matrix.trace, Fin.sum_univ_two]
section HaarTwirlNorm
open scoped Matrix.Norms.L2Operator
end HaarTwirlNorm
end QAlgorithms.Papers.Independent.Gap20.P07
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Gap20.P07.AllSequenceRate
For any function and any real , this property says that, for every pair of sequences , if and , then in . The ratios and their limsup are taken in the extended nonnegative reals. There is no requirement that tend to infinity or that the ratio have a limit. The definition permits every real ; all give the same threshold .
QAlgorithms.Papers.Independent.Gap20.P07.ErrorMonotone
For any function , this property means that, for every pair of positive integers ,
Thus increasing the first argument by one cannot increase the value, and increasing the second argument by one cannot decrease it. The property allows infinite values and imposes no condition at an argument equal to zero.
QAlgorithms.Papers.Independent.Gap20.P07.ErrorSubadditive
For any function , this property means that, for every four positive integers ,
The sum on the right is addition in the extended nonnegative reals, so infinite values are allowed; none of the four quantified arguments can be zero.
QAlgorithms.Papers.Independent.Gap20.P07.ExponentialReliable
For arbitrary types , any map , and any real , exponential reliability means that there exist real constants and , and for every a block code with uses and dimension
such that, for all sufficiently large , its effective map satisfies
Here is the natural-number floor, equal to for ; consequently gives for every . For a matrix , is the infimum of over expansions with vectors and summable products of norms; trace class means such an expansion exists, and an empty infimum is . Amplification is defined by
The power applies to first-coordinate matrix slices and recursively processes the remaining coordinates, with zeroth power copying the sole empty-coordinate entry. Every encoder and decoder preserves trace class, is additive and complex homogeneous on it, and preserves densities under every finite auxiliary amplification. Densities here are trace-class matrices with real nonnegative finite quadratic forms and a summable real diagonal of sum . No channel assumption on , positivity assumption on , or countability or nonemptiness assumption on is imposed. Codes must exist at every index, but the exponential error bound is required only eventually; the auxiliary supremum includes .
QAlgorithms.Papers.Independent.Gap20.P07.FidelityAchievable
For arbitrary types , an arbitrary map , a criterion among the four alternatives, and any real , fidelity achievability means that there exist positive integers and encoding and decoding maps and , for every , such that, writing ,
The power applies to first-coordinate matrix slices and recursively processes the remaining coordinates, with zeroth power copying the sole empty-coordinate entry. Each encoding and decoding must preserve trace class, be additive and complex homogeneous on trace-class inputs, and preserve densities after applying it separately to every block indexed by any finite auxiliary system. A matrix is trace class if it has an expansion with vectors and ; a density has, additionally, real nonnegative finite quadratic forms and a summable real diagonal of sum . For a map on matrices, is, according to , the infimum over unit of ; the infimum over positive semidefinite trace-one of ; the normalized Haar integral of ; or , where , is a matrix unit, , and . Real infima return when unbounded below, and the total integral returns when not integrable. No condition on , countability condition on , or nonnegativity condition on is imposed; all have the same rate requirement. Dimensions are allowed, and the limit conditions impose no finite-index performance requirement.
QAlgorithms.Papers.Independent.Gap20.P07.FidelityCriterion
This declares a type with exactly four distinct alternatives, named minimum, entanglement, average, and channel, with no parameters or additional data attached to any alternative.
QAlgorithms.Papers.Independent.Gap20.P07.QuantumSource.ExponentialDimension
For a source with positive integer dimensions and positive semidefinite, trace-one matrices , this property means that there exists a real such that
The bound must hold at every index, including , rather than merely eventually. Since every , any witness necessarily satisfies ; the case allows only for all . No further condition on the matrices is imposed by this property.
QAlgorithms.Papers.Independent.Gap20.P07.QuantumSource.QAEP
For a source of positive dimensions and positive semidefinite, trace-one matrices, this property means that there exists a real such that
Here , with , and selects exactly the eigenvalues in the inclusive interval . In particular, the entropy-rate limsup must be finite, and the same witness , which may be , is used for every positive window width. The convergence requirements impose no separate condition on any fixed initial index.
QAlgorithms.Papers.Independent.Gap20.P07.QuantumSource.entropyRate
For a source consisting of positive dimensions and positive semidefinite matrices of trace , this defines its entropy rate to be
The matrix function in is formed by continuous functional calculus; for these density matrices, , with zero eigenvalues contributing . The denominator is , including at , and the definition does not require an ordinary limit or a finite limsup.
QAlgorithms.Papers.Independent.Gap20.P07.QuantumSource
A quantum source consists of a positive integer for every , together with a complex matrix for every , and a requirement that each be positive semidefinite and have complex trace exactly . The index is included, the dimensions may vary arbitrarily with , and this structure imposes no relation between different matrices or dimensions.
QAlgorithms.Papers.Independent.Gap20.P07.QuantumSource.typical
For a source , where every is positive and every is positive semidefinite of trace , arbitrary real numbers , and any , this defines the matrix
by functional calculus: it acts as on an eigenvector whose eigenvalue lies between the displayed bounds, including both endpoints, and as otherwise. Neither nor is assumed positive, and is not required to equal an entropy rate. If , the lower bound exceeds the upper bound and the matrix is zero; if , it selects precisely the eigenvalue , if present. The definition includes .
QAlgorithms.Papers.Independent.Gap20.P07.QuantumSource.typicalMass
For a source of positive dimensions and positive semidefinite, trace-one matrices, arbitrary , and , this defines the real number
where is the functional-calculus matrix that selects exactly those eigenvalues of satisfying
Thus it is the sum of the selected eigenvalues, counted with multiplicity, and is when none are selected. Both bounds are inclusive, no sign condition is imposed on , and is included.
QAlgorithms.Papers.Independent.Gap20.P07.QuantumSource.typicalRestriction
For a source of positive dimensions and positive semidefinite, trace-one matrices, arbitrary real , and , this defines
where selects the eigenvalues in the inclusive interval , and is the real part of the trace of the sandwiched matrix. The inverse is taken after regarding as a complex number. No positive-mass hypothesis is required: the inverse of is defined as , so zero retained mass gives the zero matrix. Arbitrary signs of and the index are allowed.
QAlgorithms.Papers.Independent.Gap20.P07.SourceReliable
For arbitrary types , an arbitrary map , and a source with positive dimensions and positive semidefinite, trace-one matrices, this property means that there exist encoders and decoders , for every , such that, writing ,
where is the matrix with its sole nonzero entry at . The power applies to the first coordinate’s matrix slice and recursively applies to the remaining coordinates, with the unique entry retained at power zero. Each encoder and decoder must preserve trace-class matrices, be additive and complex homogeneous on them, and send density matrices to density matrices after extension by every finite ancillary register, where extension means applying the map to each slice with ancillary indices fixed. Here trace class means admitting an entrywise expansion with and ; density additionally means that every finite-coordinate quadratic form is real and nonnegative and that the real diagonal is summable with sum . No countability, nonemptiness, or channel assumption on , no dimension-growth bound, and no typicality condition on is part of this definition.
QAlgorithms.Papers.Independent.Gap20.P07.Sporadic
For any function and any real , this property asserts the existence of sequences such that , the extended nonnegative limsup of equals , and . Only the existence of one such pair of sequences is required. The ratio need not converge, and need not tend to infinity. Negative is permitted and gives the same limsup requirement as .
QAlgorithms.Papers.Independent.Gap20.P07.Subchannel
For arbitrary types and a map from complex matrices on to complex matrices on , this predicate requires that preserve trace-class matrices and be additive and complex homogeneous whenever its matrix arguments are trace class, and that, for every natural number and every density matrix on , there exist a real and a density matrix on such that
A matrix is trace class here when its entries have an expansion , with square-summable vectors and . A density matrix further requires that every finite principal quadratic form have zero imaginary part and nonnegative real part, and that the real diagonal entries be summable with sum one. The choices of may depend on ; a density matrix is required even when . The case is included, but there are no density matrices on its empty product index set, so that part of the universal requirement is vacuous.
QAlgorithms.Papers.Independent.Gap20.P07.TCChannel
For arbitrary types , this is the type of maps satisfying the following conditions. A kernel is called trace class here if it admits sequences such that and . A density kernel is a trace-class kernel whose quadratic forms on every finite set of coordinates are real and nonnegative, whose real diagonal entries form a summable family, and whose real diagonal sum is . The required conditions on are that it sends trace-class kernels to trace-class kernels, is additive and complex homogeneous on trace-class kernels, and, for every and every density kernel indexed by , the kernel with entries , indexed by , is a density kernel. Thus an element consists of a map together with these properties; no restriction is imposed on the types being countable or nonempty, and the finite-ancilla condition includes , where there are no density kernels on the empty index set.
QAlgorithms.Papers.Independent.Gap20.P07.TraceClassBlockCode.Isometric
For arbitrary types , any matrix map , natural numbers , and a block code consisting of an encoding channel from matrices on to matrices on and a decoding channel from matrices on back to matrices on , this predicate says that there exists a complex linear norm-preserving map
such that, for every trace-class matrix on ,
Here is the coordinate unit vector, and trace class means that for sequences of square-summable vectors satisfying . The channel conditions already carried by mean preservation of this trace-class predicate, additivity and complex homogeneity on trace-class matrices, and preservation of density matrices under every finite amplification; an amplification applies the map to each matrix block obtained by fixing the ancillary row and column indices. A density matrix here is trace class, has real nonnegative finite principal quadratic forms, and has summable real diagonal entries totaling one. Both and are included: a zero-length word has one possible value, while the domain of is the zero vector space when .
QAlgorithms.Papers.Independent.Gap20.P07.TraceClassBlockCode.effective
For arbitrary types , an arbitrary map , natural numbers , and a block code consisting of an encoding map and a decoding map , its effective map is
Here denotes functions from to . The coordinate power is defined recursively: has its single entry equal to , and
Both and are required to preserve trace class, be additive and complex homogeneous on trace-class inputs, and send every density matrix to a density matrix after amplification by the identity on any finite auxiliary label set , including ; this amplification applies the map separately to each auxiliary-coordinate block. In these requirements, a matrix is trace class when it admits an expansion , with of its label set and ; a density matrix is such a matrix whose every finite quadratic form is real and nonnegative and whose real diagonal entries form a summable family with sum . Neither nor the label sets have further assumptions. Both and are included whenever such a code exists; at , the effective map uses no application of .
QAlgorithms.Papers.Independent.Gap20.P07.TraceClassBlockCode.error
For arbitrary types , an arbitrary matrix map , natural numbers , and a block code with encoding into and decoding from , define . Its error is the extended nonnegative real number
where
For any label set, is the infimum, over expansions with and , of , regarded in ; trace class means that at least one such expansion exists, and the infimum is if none exists. The power applies to first-coordinate matrix slices and then recursively processes the remaining coordinates; its zeroth power copies the sole entry indexed by empty functions. The code requires to preserve trace class, be additive and complex homogeneous there, and preserve densities under every finite auxiliary amplification. Here densities are trace-class matrices with real nonnegative finite quadratic forms and a summable real diagonal of sum . No channel or linearity assumption is imposed on . The suprema include , the parameters may be zero, and the error may be .
QAlgorithms.Papers.Independent.Gap20.P07.TraceClassBlockCode
For arbitrary types , an arbitrary map , and natural numbers , this structure consists of an encoder from kernels indexed by to kernels indexed by , and a decoder from kernels indexed by to kernels indexed by . Both maps must preserve trace class, be additive and complex homogeneous on trace-class kernels, and preserve density kernels under every finite amplification, where amplification applies the map to each matrix block with fixed ancillary row and column. Here trace class means admitting an expansion by vectors in the appropriate complex space with ; a density kernel is such a kernel with real nonnegative quadratic forms on all finite coordinate sets and summable real diagonal of sum . No performance condition or relation between the two fields and is included, and is not assumed to be a channel. Both and are allowed: a zero-coordinate register has one label, whereas the register with has no labels. The index types may be empty or uncountable; existence of an instance still requires the two maps with their stated properties.
QAlgorithms.Papers.Independent.Gap20.P07.TraceClassForwardBlockCode.fidelity
For arbitrary types , any matrix map , natural numbers , a forward block code with encoder branches and decoders , and a hypothesis , this defines the real number
where is the matrix unit. Each summand is the overlap of the normalized maximally entangled vector with the result of applying the indicated effective branch map to its second factor. The powers are defined by and
The code requires each encoder branch to preserve trace class and be additive and complex homogeneous there, with every finite amplification sending a density matrix to for some and some density matrix ; the sum of its encoder branches and each decoder must instead preserve density matrices under all finite amplifications. An amplification applies the map separately to each block specified by ancillary row and column indices. Trace class means existence of an entrywise expansion with square-summable vectors and ; density additionally means real nonnegative finite principal quadratic forms and summable real diagonal entries totaling one. No channel hypothesis is imposed on , so the definition itself supplies no bound on this real number. It includes ; an empty branch sum would equal zero.
QAlgorithms.Papers.Independent.Gap20.P07.TraceClassForwardBlockCode
For arbitrary types , any matrix map , and natural numbers , this structure consists of encoder branches from matrices on to matrices on , indexed by , together with decoding channels from matrices on to matrices on . Each preserves trace-class matrices, addition and complex scalar multiplication on them; moreover, for every and every density matrix on , its amplification has the form for some and some density matrix on . The sum and every must be channels: they preserve trace class and are additive and complex homogeneous on trace-class arguments, and every finite amplification preserves density matrices. Amplification applies a map to the matrix block obtained by fixing the ancillary row and column indices. Trace class means an entrywise expansion , with and summable products ; density additionally means real nonnegative finite principal quadratic forms and summable real diagonal entries totaling one. No positivity assumptions are imposed on , and no channel assumption is imposed on . In particular, uses the singleton empty-word register; if , the total encoder is the zero map, whose channel requirement cannot hold when .
QAlgorithms.Papers.Independent.Gap20.P07.VariableSourceGenerationRate
For arbitrary types , an arbitrary map , and a real number , this property means that there exist positive integers , encoder and decoder maps for a -dimensional register through uses of , and vectors with , all defined for every , such that
where , , and has entries . The extension applies to each matrix slice with the first-register row and column fixed. The power applies first to the first coordinate’s matrix slice and recursively to the remaining coordinates, retaining the unique entry at power zero. Each encoder and decoder preserves trace-class matrices, is additive and complex homogeneous on them, and preserves density matrices after every finite ancillary extension. Here trace class means an entrywise expansion with and ; density additionally requires real nonnegative finite-coordinate quadratic forms and a summable real diagonal of sum . The vectors are arbitrary unit vectors and are not required to equal . The rate is unrestricted: every gives the same required rate limsup . No countability, nonemptiness, or channel hypothesis on is included.
QAlgorithms.Papers.Independent.Gap20.P07.blockError
For arbitrary types , arbitrary maps and , and positive integers , this defines the infimum of over admissible maps from kernels indexed by to kernels indexed by , and from kernels indexed by to kernels indexed by . Here are defined recursively: the zero-coordinate map returns the single scalar entry of its input, and the next-coordinate construction applies the original map to the first-coordinate matrix blocks and then applies the recursively constructed map to the remaining coordinates. This specifies an order even when the original maps are nonlinear. For a kernel , let be the infimum of over summable nuclear expansions with in the relevant complex space; admitting such an expansion means being trace class. The quantity is the supremum, over all finite ancillary dimensions and all trace-class inputs with , of , where applies separately to each matrix block with fixed ancillary row and column. Admissibility of means preserving trace class, being complex linear there, and preserving density kernels under every finite amplification; density kernels have real nonnegative finite-coordinate quadratic forms and summable real diagonal of sum , in addition to being trace class. Empty infima equal . Neither original map is assumed to be a channel, and neither block length may be .
QAlgorithms.Papers.Independent.Gap20.P07.blockingEnvelope
Given a sequence of positive integers , a sequence of finite nonnegative real numbers , and positive integers , the blocking envelope is
where the infimum is taken in . The indices form an arbitrary finite list: repetitions are permitted, and there is no requirement that the indices be distinct or increasing. The empty list has both sums equal to zero and is therefore inadmissible because . If no list satisfies the length bounds—including whenever —the infimum is , and the envelope is .
QAlgorithms.Papers.Independent.Gap20.P07.classicalIdentity
For every natural number , this defines a map on complex matrices that retains the diagonal entries and sets every off-diagonal entry to zero:
It applies to every input matrix without a positivity or normalization condition. For , it is the unique map on the singleton space of empty matrices.
QAlgorithms.Papers.Independent.Gap20.P07.codingSimulationDistance
For arbitrary types and arbitrary maps and , this defines an extended nonnegative number , where maps -indexed kernels to -indexed kernels and maps -indexed kernels to -indexed kernels. To specify the quantities and restrictions, let be the infimum of over all sequences in the appropriate complex spaces with summable norm products and ; call trace class when such an expansion exists. For any map , let act on -dimensional ancilla blocks by , and set . Each of must preserve trace class, be additive and complex homogeneous on trace-class kernels, and have every finite amplification send density kernels to density kernels; a density kernel here is trace class, has real nonnegative quadratic forms on all finite coordinate sets, and has summable real diagonal with sum . The map difference means . Neither nor is assumed to satisfy any channel or linearity condition. Infima over empty families, including a missing nuclear expansion or missing admissible encoders or decoders, are ; the ancillary supremum includes dimension .
QAlgorithms.Papers.Independent.Gap20.P07.compressedChannel
For any natural numbers , any complex matrix , and any map from complex matrices to themselves, this defines a map on complex matrices by
Here is the conjugate transpose, and division is complex division. The definition assumes neither an isometry condition on nor any linearity, positivity, or channel condition on . It includes and ; division by zero is defined to be zero, and when the output is the unique empty matrix.
QAlgorithms.Papers.Independent.Gap20.P07.enlargedMixture
For positive integers and any real , this defines the complex diagonal matrix of dimension whose first diagonal entries are and whose remaining diagonal entries are :
All off-diagonal entries are zero. The denominators are nonzero because are positive, but is unrestricted, so negative diagonal entries are allowed; at the last block is zero, and at the first block is zero.
QAlgorithms.Papers.Independent.Gap20.P07.errorCapacity
For any function , this is the supremum in of all positive real numbers with the following property: for every , if and the extended nonnegative limsup of is at most , then . The second sequence need not diverge, and convergence of the ratio itself is not required. The supremum is when no positive has this property and may be .
QAlgorithms.Papers.Independent.Gap20.P07.exponentialCapacity
For arbitrary types and an arbitrary map , this defines an extended nonnegative number as the supremum of all strictly positive real rates with the following property: there exist real constants , , and, for every , an encoder and decoder transmitting a register of dimension through uses of , such that, for all sufficiently large ,
Here maps matrices indexed by to matrices indexed by , and maps matrices indexed by back to that finite register. The map is defined by applying first to the first coordinate’s matrix slice and recursively applying to the remaining coordinates; at , it retains the unique matrix entry. The quantity is the supremum, over all and all trace-class matrices indexed by the input labels paired with , with trace size at most , of the trace size of the matrix obtained by applying to each slice with the two ancillary indices fixed; need not be positive. A matrix is trace class here if it admits an entrywise expansion , where and ; its trace size is the infimum of these sums over all such expansions, with value when there is no expansion. Each encoder and decoder must preserve trace-class matrices, be additive and complex homogeneous on them, and send every density matrix on its input paired with any finite ancillary register to a density matrix after this slice-wise extension. In this condition, a density matrix means a trace-class coefficient matrix whose quadratic form on every finite set of coordinates is real and nonnegative, and whose real diagonal is summable with sum . The supremum defining the capacity is taken in , so it is if there are no qualifying positive rates. There is no countability, nonemptiness, or channel assumption on ; existence of all the encoders and decoders, including those for the initial block lengths, is part of the rate condition.
QAlgorithms.Papers.Independent.Gap20.P07.fidelityCapacity
For arbitrary types , any map , and a criterion among minimum, entanglement, average, and channel, the fidelity capacity is the supremum in of the strictly positive real numbers for which there exist positive integers and block encoders into and decoders from , for every , satisfying
The rate limsup is interpreted in . The coordinate power applies to first-coordinate matrix slices and recursively processes the remaining coordinates, with zeroth power copying the unique empty-coordinate entry. Every encoder and decoder preserves trace class, is additive and complex homogeneous on trace-class inputs, and preserves densities under every finite auxiliary amplification, which applies the map separately to auxiliary-coordinate blocks. Trace class means admitting with and ; densities additionally have real nonnegative finite quadratic forms and a summable real diagonal of sum . For a map on matrices, the selected value is respectively
Here , is a matrix unit, is normalized Haar measure, , and . The infima are real infima with value if unbounded below, and the total integral is if not integrable. There is no channel assumption on . The capacity is if no positive rate qualifies and may be ; no claim that its supremum is attained is part of the definition.
QAlgorithms.Papers.Independent.Gap20.P07.fidelityValue
For a criterion among minimum, entanglement, average, and channel, a positive integer , and any map , the fidelity value selects, respectively,
Here , so ; is the matrix unit; is the first standard basis vector; is normalized Haar measure; ; and
The infima are real infima, returning if unbounded below, and the integral is the total Bochner integral, returning if the integrand is not integrable. No assumption on guarantees linearity, positivity, or normalization of these expressions. The dimension is strictly positive, so is excluded and is included.
QAlgorithms.Papers.Independent.Gap20.P07.finiteCbNorm
For every natural number and arbitrary map , the finite completely bounded norm is the real conversion of
Here trace class means admitting an expansion with and , and is the infimum of these sums over all such expansions, with empty infimum . The conversion returns when finite and returns when . No linearity, positivity, or channel assumption is made. Auxiliary dimension and system dimension are included; at , the value is .
QAlgorithms.Papers.Independent.Gap20.P07.finiteErrorCapacity
For arbitrary types , an arbitrary map , and any real , this is the supremum in of positive real such that, for every positive-integer sequences with and , eventually . The eventual bound may begin at a different index for each pair of sequences; convergence of the errors is not required. The encoder maps kernels on binary coordinates to kernels on , and the decoder maps kernels on back to those binary coordinates. The map recursively applies to first-coordinate blocks and then to the remaining coordinates, starting with the identity on a scalar entry at . Define to be the infimum of over complex expansions with summable norm products, and call kernels admitting such expansions trace class. Then is the supremum of over finite ancillary dimensions and trace-class with , with amplification acting separately on each ancillary matrix block. Admissible preserve trace class, are complex linear there, and preserve density kernels under every finite amplification; density kernels have real nonnegative finite-coordinate quadratic forms and summable real diagonal of sum , as well as being trace class. Empty infima are , and the outer supremum is if no positive rate qualifies. There is no channel assumption on , no nonemptiness or countability assumption on the index types, and no requirement that diverge. Every gives threshold ; larger errors, including , are also permitted by the definition.
QAlgorithms.Papers.Independent.Gap20.P07.firstCoordinatePinching
For every positive integer , this defines a map on complex matrices by
Thus entries joining coordinate to a different coordinate are set to zero, while the entry and the entire block on the remaining coordinates are retained. The input matrix is unrestricted. The positivity of ensures that coordinate exists; for , this map is the identity.
QAlgorithms.Papers.Independent.Gap20.P07.hashingBound
For any natural numbers and any real , this defines the real number
There are no restrictions requiring to be positive or to lie in . The real logarithm is total: , and for negative arguments it equals the logarithm of the absolute value; real division by zero is zero. Consequently the expression is defined for every supplied argument, and it equals zero when .
QAlgorithms.Papers.Independent.Gap20.P07.hashingSupremum
For arbitrary types and any matrix map , this defines the extended nonnegative real supremum over all positive block lengths , all prime natural numbers , all block codes with encoding channel from matrices on to matrices on and decoding channel from matrices on back to matrices on , and all instances of the strict inequality , of
Here , the error is
and
For any matrix , trace class means that for square-summable vectors with , and is the infimum in of these sums over all such expansions, with value infinity if there are none. The error bound ensures is finite, so is its ordinary real value. Each channel preserves trace class and is additive and complex homogeneous on trace-class arguments, and every finite amplification preserves density matrices; a density matrix is trace class, has real nonnegative finite principal quadratic forms, and has summable real diagonal entries totaling one. The powers of are defined recursively by and
There is no channel assumption on and no nonemptiness or countability assumption on . Primality forces , the block length excludes zero, and the amplification supremum includes . Negative values of the displayed real bound contribute zero; if no qualifying code exists, the supremum is zero, and otherwise it may be infinite.
QAlgorithms.Papers.Independent.Gap20.P07.instrumentForwardCapacity
For arbitrary types , any matrix map , and any predicate on a natural number and a positive integer , this defines the supremum in of all strictly positive real for which there are sequences of positive integers , satisfying for every , and forward block codes with encoder branches , corresponding decoders , source dimension , and block length , such that
The limsup is taken in , and denotes a matrix unit. The powers of use the recursion and
Each encoder branch preserves trace class, addition and complex scalar multiplication on trace-class arguments, and every finite amplification sends each density matrix to for some and some density matrix , including a required choice of when . The sum of the encoder branches and every decoder are channels, meaning the same trace-class linearity conditions together with preservation of density matrices under every finite amplification. Amplification applies the map to each matrix block obtained by fixing the ancillary row and column indices. Trace class means an expansion , with square-summable vectors and summable products ; density additionally means real nonnegative finite principal quadratic forms and summable real diagonal entries totaling one. The predicate is arbitrary, its index is although the code length is , and is unrestricted. The supremum is zero if no positive rate qualifies and may be infinite.
QAlgorithms.Papers.Independent.Gap20.P07.isometricCapacity
For arbitrary types and any matrix map , this defines the supremum in of all strictly positive real for which there exist positive integers and, for every , encoding and decoding channels forming a code through uses of , with the following properties. Each encoder has a complex linear isometry satisfying, for every trace-class ,
and, writing ,
The limsup is taken in , is the matrix unit, and the second expression is the overlap with the normalized maximally entangled vector after applying to its second factor. The powers used here are defined recursively by and
Trace class means existence of an expansion with and . A density matrix additionally has real nonnegative finite principal quadratic forms and summable real diagonal entries totaling one. Each channel preserves trace class, addition and complex scalar multiplication on trace-class matrices, and density matrices under every finite amplification, where amplification applies the map to the blocks obtained by fixing ancillary row and column indices. No channel property of , nonemptiness of , or countability assumption is imposed. The resulting supremum is zero when the qualifying set is empty and may be infinite.
QAlgorithms.Papers.Independent.Gap20.P07.minimumFe
For every natural number and arbitrary map , the minimum entanglement-fidelity expression is the real infimum
where has entry at and zero elsewhere. Positive semidefiniteness and trace are the only conditions on ; there are no assumptions on . The infimum is taken in , with value if the set is empty or unbounded below. In particular, when , no trace-one matrix exists and the value is .
QAlgorithms.Papers.Independent.Gap20.P07.minimumFidelity
For every natural number and arbitrary map , the minimum fidelity is the real infimum
There is no assumption that is linear, positive, trace preserving, or a channel. The infimum is taken in : its value is for an empty set or a set unbounded below. In particular, is allowed and gives , because there are no unit vectors.
QAlgorithms.Papers.Independent.Gap20.P07.ordinaryCapacity
For arbitrary types and any map , the ordinary capacity is the supremum in of all strictly positive real for which there exist positive integers , encoders into , and decoders from , for every , such that, with ,
The rate limsup is taken in , whereas each displayed supremum over is taken in and is assigned if unbounded above. Here , with the square root defined by continuous functional calculus. The power applies to first-coordinate matrix slices and recursively processes the remaining coordinates, with zeroth power copying the unique empty-coordinate entry. The encoders and decoders must preserve trace class, be additive and complex homogeneous there, and preserve densities under every finite auxiliary amplification, meaning application to each auxiliary-coordinate block. Trace class means admitting an expansion with vectors and ; a density additionally has real nonnegative finite quadratic forms and a summable real diagonal with sum . There is no channel or linearity assumption on , nor a countability or nonemptiness assumption on . The capacity is if no positive rate qualifies and can be ; code dimensions may equal , and only the stated asymptotic conditions govern their performance.
QAlgorithms.Papers.Independent.Gap20.P07.ordinaryNorm
For every natural number and arbitrary map , the ordinary norm is the real supremum
where the square roots are defined by continuous functional calculus. No linearity or channel assumption is imposed on . This real supremum is if its defining set is unbounded above, rather than . The case is included and has value .
QAlgorithms.Papers.Independent.Gap20.P07.qubitReferenceCapacity
For arbitrary types and an arbitrary map , this is the supremum in of positive real such that, for every positive-integer sequences with and , the quantity tends to . The identity acts on matrices indexed by binary coordinates; maps these kernels to kernels indexed by , and maps kernels indexed by back to them. The map recursively applies to first-coordinate matrix blocks and then recurses on the remaining coordinates, with the zero-coordinate map the identity on a scalar entry. Here is the infimum of over expansions by complex vectors with summable norm products; such expandable kernels are called trace class. The quantity is the supremum of over finite ancillary dimensions and trace-class satisfying , where amplification applies to each ancillary matrix block. The admissible preserve trace class, are complex linear there, and preserve density kernels under every finite amplification; a density kernel is trace class, has real nonnegative finite-coordinate quadratic forms, and has summable real diagonal with sum . Empty infima are , and absence of qualifying positive rates gives capacity . The map need not be a channel, the index types may be empty or uncountable, and need not diverge.
QAlgorithms.Papers.Independent.Gap20.P07.rateRatio
For sequences and an index , this is the extended nonnegative quotient , obtained by viewing both positive integer values in . Both values are finite and the denominator is strictly positive, so this quotient is finite and positive; zero block lengths and division by zero are excluded.
QAlgorithms.Papers.Independent.Gap20.P07.relativeCapacity
For arbitrary types and arbitrary maps and , this is the extended nonnegative supremum of positive real such that every pair of positive-integer sequences with and has . For positive , the error is , with and understood as maps between the corresponding matrix-kernel spaces. The maps recursively apply the original map to first-coordinate blocks and then recurse on the remaining coordinates, starting with the identity on the single zero-coordinate scalar entry. To define , let be the infimum of over expansions in complex spaces with summable norm products; kernels admitting an expansion are called trace class. Then is the supremum of over all finite ancillary dimensions and trace-class with , where amplification applies to each block with fixed ancillary coordinates. The admissible preserve trace class, are complex linear there, and preserve density kernels under every finite amplification; a density kernel is trace class, has real nonnegative quadratic forms on all finite coordinate sets, and has summable real diagonal of sum . Empty infima are , and the outer supremum is if no positive rate qualifies. No channel assumption is imposed on , no nonemptiness or countability assumption is imposed on their index types, and need not diverge.
QAlgorithms.Papers.Independent.Gap20.P07.sourceEntropyCapacity
For arbitrary types , an arbitrary map , and an arbitrary predicate on sources, this defines the supremum in of all strictly positive real for which there exists a source satisfying , reliable transmission through , and
A source here has positive integer dimensions and positive semidefinite, trace-one matrices at every . Reliable transmission means that there are encoder and decoder maps for the -dimensional register through uses of , with effective map , such that
Here is a matrix unit, and successively applies to coordinate matrix slices, first to the first coordinate and then recursively to the rest, with the unique entry retained at power zero. The encoders and decoders preserve trace-class matrices, are additive and complex homogeneous on them, and preserve density matrices under every finite ancillary extension. Trace class means an entrywise expansion with square-summable vectors and summable products ; density means, additionally, real nonnegative quadratic forms on every finite coordinate set and a summable real diagonal of sum . No typicality or exponential dimension condition is required unless supplied by , and no channel, countability, or nonemptiness assumption is imposed on . The value is if no positive rate qualifies, and it may be .
QAlgorithms.Papers.Independent.Gap20.P07.sporadicCapacity
For arbitrary types and an arbitrary map , this is the supremum in of positive real for which there exist positive-integer sequences satisfying , , and . Here maps kernels on binary coordinates to kernels on , and maps kernels on back to those binary coordinates. The map applies recursively to first-coordinate matrix blocks and then to the remaining coordinates, beginning with the identity on the single zero-coordinate scalar entry. For any kernel , define as the infimum of over expansions with complex vectors and summable norm products, and call kernels admitting such an expansion trace class. The quantity is the supremum of over all finite ancillary dimensions and trace-class with , where applies to each block with fixed ancillary coordinates. Each admissible encoder or decoder preserves trace class, is complex linear there, and preserves density kernels under every finite amplification; density kernels are trace class, have real nonnegative finite-coordinate quadratic forms, and have summable real diagonal of sum . Empty infima equal ; the capacity is if no positive rate qualifies. No channel, countability, or nonemptiness assumption is made on or its index types, and the witnessing ratio need not converge.
QAlgorithms.Papers.Independent.Gap20.P07.variableSourceGenerationCapacity
For arbitrary types and any map from complex matrices indexed by to complex matrices indexed by , this defines an extended nonnegative real number as the supremum of all strictly positive real rates satisfying the following condition. There exist positive integers , encoding channels from -dimensional matrices to matrices indexed by , decoding channels from matrices indexed by to -dimensional matrices, and unit vectors , such that, writing ,
where the limsup is taken in , , and . The vectors may vary with and are required only to have norm one. Here . For arbitrary , its powers are defined by and
where prepends to the word . A matrix is trace class here precisely when there are sequences of its index type with and . A density matrix is such a matrix whose every finite principal quadratic form is real and nonnegative and whose real diagonal entries are summable with sum one. A channel preserves trace-class matrices, is additive and complex homogeneous on them, and, for every natural number , sends every density matrix on its input index type times to a density matrix under the amplification
There is no channel assumption on , and the types need not be nonempty or countable. The supremum is zero if there are no qualifying positive rates and may be infinite.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.