Definitions for Quantum Coding with Finite Resources
DefinitionQAlgorithms_Papers_Independent_Support50_P04The objects the formalized statements of Quantum Coding with Finite Resources (arXiv:1504.04617) are stated in. Each was checked against the paper by a blind read-back and a moderator.
sourcePurification: PDF p.8: source purification has coefficients sqrt(rho)[i,j], with the square root on the FIRST factor. Its first marginal is rho; no full-rank assumption is imposed.sourcePurifiedOutput: PDF p.9, Eq.(21): actual purified channel output in reference:receiver order.localEmbedding: PDF p.10: embed Alice and Bob separately into fixed larger local registers. The product embedding introduces only local pure ancillas, with no shared resource.pairConfiguration: PDF p.10: dependent two-party coordinates, with potentially UNEQUAL local dimensions.receiverConfigurationMarginal: PDF p.10: read the receiver register after an LOCC map on two enlarged local registers.IsReceiverLOCC: PDF p.10, Fig.5: an LOCC decoder with output at Bob. The accepted InLOCC predicate requires linked actual local instruments, rather than independently approximating finite protocols (the larger closure). Ancilla embeddings and final local disposal are explicit. All local dimensions are finite and positive.CppCode: PDF p.10: cpp entanglement transmission, for one (possibly blocked) channel. The encoder retains finite sender memory; the only communication after channel uses is LOCC. No preshared entanglement is an input field.cppEffective: PDF p.10: apply N to the channel input, preserve memory, then decode at Bob.cppFidelity: PDF pp.2,8,10: squared fidelity to normalized Phi_M of the actual cpp output.unassistedFeasible: PDF pp.2–3: exact finite-block unassisted feasibility with positive INTEGER messages.cppFeasible: PDF pp.3,10: exact cpp finite-block feasibility, not feasibility in a closure of codes.unassistedBoundary: PDF p.3, Eq.(2): per-use rate boundary. Extrema are extended before optimization. For n>=1, CPTP N on positive finite systems and epsilon<1, feasible integer message sizes are nonempty and bounded, so this is the source's attained maximum rate.cppBoundary: PDF pp.3,10: cpp boundary over actual feasible codes. Same finite-integer maximum convention as unassistedBoundary; a supremum of fidelity is not substituted for feasibility.optimalCppFidelity: PDF pp.5,18: fixed-message optimal cpp fidelity; the exact erasure theorem also asserts attainment by an actual code. Positive M is a theorem hypothesis.binaryVariance: PDF p.4: binary information variance in bits squared, including zero dispersion.normalRate: PDF pp.3,8: normal approximation per use, with standard Gaussian quantile.thirdOrderExpansion: PDF p.4, Eq.(6): two-sided eventual O(1/n), constants fixed before n.constantRemainderExpansion: PDF p.6, Eq.(9): two-sided O(1/n), with no log(n)/n third-order term.dispersionUpper: PDF pp.7,13: one-sided converse with an eventual O(log n/n) remainder.dispersionLower: PDF pp.8,14: one-sided achievability; this does not assert a two-sided expansion.channelTestingRains: PDF p.9, Eq.(21): sup over input states BEFORE the statewise inf over PPT-prime.FullUnitaryCovariant: PDF pp.12–13: full input-unitary covariance, with an output unitary representation. This is not arbitrary-group or trivial-group covariance.choiState: PDF p.8: normalized Choi state, as distinct from the unnormalized SDP Choi matrix.rainsInformation: PDF p.13, Eq.(41): Rains information at the constructed maximally entangled input.rainsOptimizers: PDF p.13: ALL actual Rains minimizers, not freely supplied optimization data.rainsVariance: PDF p.13, Eq.(42): maximum below epsilon=1/2; minimum at or above it.channelCoherentBits: PDF p.14, Eq.(48): optimized coherent information, in bits, over ALL density inputs.coherentOptimizers: PDF p.14: constructed coherent-information maximizing inputs, including rank-deficient ones.coherentInformationVariance: PDF p.14, Eq.(49): minimum variance below epsilon=1/2; maximum at or above it.smoothMinEntropy: PDF pp.13–14, Eq.(44), corrected named purified-distance ball: F>=1-delta^2. The exponent supremum is extended first; zero subnormalized states have infinite min-entropy, but are excluded by this ball at normalized center and delta<1.smoothInner: PDF p.14, Eq.(46): optimized blocked smooth-entropy inner bound, including rounding.productSmoothInner: PDF p.14, Eq.(47): eta=1/sqrt(n), with the square root applied AFTER subtraction. The theorem requires 1/sqrt(n)<epsilon, correcting the printed domain.erasureFidelityFormula: PDF p.18, Eqs.(69)–(70): exact fixed-integer-message fidelity, with all erasure counts. Since l<=n, n-l never truncates an intended negative number; M is positive in results.dephasingAlternative: PDF p.16, Eq.(61): fixed dephasing testing pair.depolarizingAlternative: PDF p.19, Eq.(73): Bell weights (1/2,1/6,1/6,1/6), a normalized PPT alternative.bscJoint: PDF p.16, Eq.(63): the BSC joint law, uniform input; comparison law is uniform on pairs.bscAlternative: PDF p.16: fixed product of uniform binary marginals.PptChoiTP: PDF pp.9,12: comparison-channel Choi operators are PSD, PPT, and trace preserving.PptChoiTNI: PDF pp.21–22: the appendix uses trace-NONINCREASING comparison maps. For PSD tests this has the same supremum, by product-PPT completion of the deficit.GammaTests: PDF p.12, Eq.(33): Gamma constraints with Loewner, not entrywise, inequalities.comparisonValue: PDF p.12, Eq.(33): inner supremum over actual PPT-binding channel Choi matrices.metaValue: PDF p.12, Eq.(33): inf_rho inf_Lambda sup_PPT in exactly that order. The feasible pair set is nonempty for CPTP N and epsilon in (0,1); objective lies in [0,1].SdpMinFeasible: PDF p.21, Eq.(A3): full minimization feasibility, with all identity tensor factors.sdpMinValue: PDF p.21, Eq.(A3): infimum of the trace objective over the constructed program.SdpMaxFeasible: PDF pp.21–22, Eq.(A4): scalar nu consistently replaces the printed n/nu typo. Tr_B R<=nu I is equivalent under transpose to Tr_B(R^{T_A})<=nu I.sdpMaxValue: PDF p.21, Eq.(A4): the dual supremum, not an assumed optimization value.BinaryWord: PDF p.16: binary vectors with the field addition used in parity checks.xKet: PDF p.16: Fourier-character ket |c>_X in the physical Z basis.cssIsometry: PDF pp.16–17: the CSS encoder sends message m to the X-basis word indexed by c_m.syndromeProjector: PDF p.17: the syndrome-s projector, retaining EVERY syndrome outcome.zError: PDF p.17: correction Z^u is diagonal with signs (-1)^(u dot z).cssDecoder: PDF p.17: explicit syndrome measurement, phase correction, and inverse CSS isometry.phaseErrorProbability: PDF pp.16–17: independent phase-error law, including endpoint probabilities.classicalLinearSuccess: PDF p.16: actual uniform-message average success for the syndrome decoder. The received word is c_m+u, and decoding subtracts the estimated error.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_BipartiteSeparability
import Definitions.Def_QAlgorithms_Defs_FiniteRegisters
import Definitions.Def_QAlgorithms_Defs_QuditChannelFidelities
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P22
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P36
import Definitions.Def_QAlgorithms_Papers_Independent_Frontier18_P07
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P27
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P34
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P60
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P63
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P67
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P80
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P36
/-!
Statements from Quantum Coding with Finite Resources, arXiv:1504.04617v2.
All newly introduced objects are confined to this paper. Operational extrema use
EReal before optimization. Explicit source corrections are recorded in the unit's
MODERATION_NOTES.md; source-domain deferrals are in HARD.md. Compilation pending.
-/
noncomputable section
open scoped Matrix ComplexConjugate ComplexOrder
open QAlgorithms
namespace QAlgorithms.Papers.Independent.Support50.P04
variable {A B E : Type} [Fintype A] [DecidableEq A]
variable [Fintype B] [DecidableEq B] [Fintype E] [DecidableEq E]
/-- PDF p.8: source purification has coefficients sqrt(rho)[i,j], with the square root
on the FIRST factor. Its first marginal is rho; no full-rank assumption is imposed. -/
def sourcePurification (rho : Matrix A A ℂ) : Matrix (A × A) (A × A) ℂ :=
let S := cfc Real.sqrt rho
fun p q => S p.1 p.2 * conj (S q.1 q.2)
/-- PDF p.9, Eq.(21): actual purified channel output in reference:receiver order. -/
def sourcePurifiedOutput (N : Superop A B) (rho : Matrix A A ℂ) :
Matrix (A × B) (A × B) ℂ := idTensorSuperop N (sourcePurification rho)
/-- PDF p.10: embed Alice and Bob separately into fixed larger local registers.
The product embedding introduces only local pure ancillas, with no shared resource. -/
def localEmbedding {Q T : Type} [Fintype Q] [Fintype T] {a b : ℕ}
(W : Matrix (Fin a) Q ℂ) (V : Matrix (Fin b) T ℂ) :
Matrix (QAlgorithms.Papers.Independent.Information100.P27.Config ![a,b]) (Q × T) ℂ :=
fun x y => W (x 0) y.1 * V (x 1) y.2
/-- PDF p.10: dependent two-party coordinates, with potentially UNEQUAL local dimensions. -/
def pairConfiguration {a b : ℕ} (i : Fin a) (j : Fin b) :
QAlgorithms.Papers.Independent.Information100.P27.Config ![a,b] :=
Fin.cases i (Fin.cases j (fun k => Fin.elim0 k))
/-- PDF p.10: read the receiver register after an LOCC map on two enlarged local registers. -/
def receiverConfigurationMarginal {a b : ℕ}
(X : Matrix (QAlgorithms.Papers.Independent.Information100.P27.Config ![a,b])
(QAlgorithms.Papers.Independent.Information100.P27.Config ![a,b]) ℂ) :
Matrix (Fin b) (Fin b) ℂ :=
fun j k => ∑ i : Fin a, X (pairConfiguration i j) (pairConfiguration i k)
/-- PDF p.10, Fig.5: an LOCC decoder with output at Bob. The accepted InLOCC
predicate requires linked actual local instruments, rather than independently
approximating finite protocols (the larger closure). Ancilla embeddings and final
local disposal are explicit. All local dimensions are finite and positive. -/
def IsReceiverLOCC {Q T : Type} [Fintype Q] [DecidableEq Q]
[Fintype T] [DecidableEq T] {M : ℕ} (D : Superop (Q × T) (Fin M)) : Prop :=
∃ a b : ℕ, 0 < a ∧ 0 < b ∧
∃ W : Matrix (Fin a) Q ℂ, ∃ V : Matrix (Fin b) T ℂ,
Wᴴ * W = 1 ∧ Vᴴ * V = 1 ∧
∃ L : Superop (QAlgorithms.Papers.Independent.Information100.P27.Config ![a,b])
(QAlgorithms.Papers.Independent.Information100.P27.Config ![a,b]),
QAlgorithms.Papers.Independent.Dependency50.P22.InLOCC ![a,b] (fun _ : Unit => L) ∧
∃ F : Superop (Fin b) (Fin M), IsChannel F ∧
∀ X, D X = F (receiverConfigurationMarginal (L (conjSuperop (localEmbedding W V) X)))
/-- PDF p.10: cpp entanglement transmission, for one (possibly blocked) channel.
The encoder retains finite sender memory; the only communication after channel
uses is LOCC. No preshared entanglement is an input field. -/
structure CppCode (A B : Type) [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B] where
M : ℕ
positive : 0 < M
q : ℕ
memory_positive : 0 < q
encoder : Superop (Fin M) (A × Fin q)
encoder_channel : IsChannel encoder
decoder : Superop (Fin q × B) (Fin M)
decoder_channel : IsChannel decoder
decoder_locc : IsReceiverLOCC decoder
/-- PDF p.10: apply N to the channel input, preserve memory, then decode at Bob. -/
def cppEffective (N : Superop A B) (C : CppCode A B) : Superop (Fin C.M) (Fin C.M) :=
fun X => C.decoder (idTensorSuperop (R := Fin C.q) N
(fun p q => C.encoder X (p.2,p.1) (q.2,q.1)))
/-- PDF pp.2,8,10: squared fidelity to normalized Phi_M of the actual cpp output. -/
def cppFidelity (N : Superop A B) (C : CppCode A B) : ℝ :=
effectProb (QAlgorithms.Papers.Independent.Dependency50.P36.target C.M) (idTensorSuperop (cppEffective N C) (QAlgorithms.Papers.Independent.Dependency50.P36.target C.M))
/-- PDF pp.2–3: exact finite-block unassisted feasibility with positive INTEGER messages. -/
def unassistedFeasible (N : Superop A B) (n : ℕ) (epsilon R : ℝ) : Prop :=
∃ C : QAlgorithms.Papers.Independent.Information100.P80.TransmissionCode (Fin n → A) (Fin n → B),
R ≤ QAlgorithms.Papers.Independent.Information100.P80.log2 C.M / n ∧ 1 - epsilon ≤ QAlgorithms.Papers.Independent.Information100.P80.transmissionFidelity (piSuperop (fun _ : Fin n => N)) C
/-- PDF pp.3,10: exact cpp finite-block feasibility, not feasibility in a closure of codes. -/
def cppFeasible (N : Superop A B) (n : ℕ) (epsilon R : ℝ) : Prop :=
∃ C : CppCode (Fin n → A) (Fin n → B),
R ≤ QAlgorithms.Papers.Independent.Information100.P80.log2 C.M / n ∧ 1 - epsilon ≤ cppFidelity (piSuperop (fun _ : Fin n => N)) C
/-- PDF p.3, Eq.(2): per-use rate boundary. Extrema are extended before optimization.
For n>=1, CPTP N on positive finite systems and epsilon<1, feasible integer message
sizes are nonempty and bounded, so this is the source's attained maximum rate. -/
def unassistedBoundary (N : Superop A B) (n : ℕ) (epsilon : ℝ) : EReal :=
sSup {r | ∃ R : ℝ, unassistedFeasible N n epsilon R ∧ r = (R : EReal)}
/-- PDF pp.3,10: cpp boundary over actual feasible codes. Same finite-integer maximum
convention as unassistedBoundary; a supremum of fidelity is not substituted for feasibility. -/
def cppBoundary (N : Superop A B) (n : ℕ) (epsilon : ℝ) : EReal :=
sSup {r | ∃ R : ℝ, cppFeasible N n epsilon R ∧ r = (R : EReal)}
/-- PDF pp.5,18: fixed-message optimal cpp fidelity; the exact erasure theorem also
asserts attainment by an actual code. Positive M is a theorem hypothesis. -/
def optimalCppFidelity (N : Superop A B) (n M : ℕ) : EReal :=
sSup {f | ∃ C : CppCode (Fin n → A) (Fin n → B), C.M = M ∧
f = (cppFidelity (piSuperop (fun _ : Fin n => N)) C : EReal)}
/-- PDF p.4: binary information variance in bits squared, including zero dispersion. -/
def binaryVariance (p : ℝ) : ℝ :=
p * (QAlgorithms.Papers.Independent.Information100.P80.log2 p + QAlgorithms.Papers.Independent.Frontier18.P07.binaryEntropyBits p)^2 +
(1-p) * (QAlgorithms.Papers.Independent.Information100.P80.log2 (1-p) + QAlgorithms.Papers.Independent.Frontier18.P07.binaryEntropyBits p)^2
/-- PDF pp.3,8: normal approximation per use, with standard Gaussian quantile. -/
def normalRate (a v epsilon : ℝ) (n : ℕ) : ℝ :=
a + Real.sqrt (v / n) * QAlgorithms.Papers.Independent.Information100.P63.normalQuantile epsilon
/-- PDF p.4, Eq.(6): two-sided eventual O(1/n), constants fixed before n. -/
def thirdOrderExpansion (R : ℕ → EReal) (a v epsilon : ℝ) : Prop :=
∃ C : ℝ, 0 < C ∧ ∃ n0 : ℕ, 2 ≤ n0 ∧ ∀ n ≥ n0,
let t := normalRate a v epsilon n + QAlgorithms.Papers.Independent.Information100.P80.log2 n / (2*n)
((t - C/n : ℝ) : EReal) ≤ R n ∧ R n ≤ ((t + C/n : ℝ) : EReal)
/-- PDF p.6, Eq.(9): two-sided O(1/n), with no log(n)/n third-order term. -/
def constantRemainderExpansion (R : ℕ → EReal) (a v epsilon : ℝ) : Prop :=
∃ C : ℝ, 0 < C ∧ ∃ n0 : ℕ, 2 ≤ n0 ∧ ∀ n ≥ n0,
((normalRate a v epsilon n - C/n : ℝ) : EReal) ≤ R n ∧
R n ≤ ((normalRate a v epsilon n + C/n : ℝ) : EReal)
/-- PDF pp.7,13: one-sided converse with an eventual O(log n/n) remainder. -/
def dispersionUpper (R : ℕ → EReal) (a v epsilon : ℝ) : Prop :=
∃ C : ℝ, 0 < C ∧ ∃ n0 : ℕ, 2 ≤ n0 ∧ ∀ n ≥ n0,
R n ≤ ((normalRate a v epsilon n + C * QAlgorithms.Papers.Independent.Information100.P80.log2 n / n : ℝ) : EReal)
/-- PDF pp.8,14: one-sided achievability; this does not assert a two-sided expansion. -/
def dispersionLower (R : ℕ → EReal) (a v epsilon : ℝ) : Prop :=
∃ C : ℝ, 0 < C ∧ ∃ n0 : ℕ, 2 ≤ n0 ∧ ∀ n ≥ n0,
((normalRate a v epsilon n - C * QAlgorithms.Papers.Independent.Information100.P80.log2 n / n : ℝ) : EReal) ≤ R n
/-- PDF p.9, Eq.(21): sup over input states BEFORE the statewise inf over PPT-prime. -/
def channelTestingRains (N : Superop A B) (epsilon : ℝ) : EReal :=
sSup {r | ∃ rho : Matrix A A ℂ, IsDensityMatrix rho ∧
r = sInf {d | ∃ sigma : Matrix (A × B) (A × B) ℂ,
QAlgorithms.Papers.Independent.Dependency50.P36.pptPrime sigma ∧ d = QAlgorithms.Papers.Independent.Dependency50.P36.testingEntropy (sourcePurifiedOutput N rho) sigma epsilon}}
/-- PDF pp.12–13: full input-unitary covariance, with an output unitary representation.
This is not arbitrary-group or trivial-group covariance. -/
def FullUnitaryCovariant (N : Superop A B) : Prop :=
∃ V : Matrix.unitaryGroup A ℂ →* Matrix.unitaryGroup B ℂ,
∀ U : Matrix.unitaryGroup A ℂ, ∀ X,
N (conjSuperop (U : Matrix A A ℂ) X) =
conjSuperop (V U : Matrix B B ℂ) (N X)
/-- PDF p.8: normalized Choi state, as distinct from the unnormalized SDP Choi matrix. -/
def choiState (N : Superop A B) : Matrix (A × B) (A × B) ℂ :=
((Fintype.card A : ℂ)⁻¹) • QAlgorithms.Papers.Independent.Information100.P34.choi N
/-- PDF p.13, Eq.(41): Rains information at the constructed maximally entangled input. -/
def rainsInformation (N : Superop A B) : EReal :=
sInf {r | ∃ sigma : Matrix (A × B) (A × B) ℂ,
QAlgorithms.Papers.Independent.Dependency50.P36.pptPrime sigma ∧ r = QAlgorithms.Papers.Independent.Dependency50.P36.relativeEntropy (choiState N) sigma}
/-- PDF p.13: ALL actual Rains minimizers, not freely supplied optimization data. -/
def rainsOptimizers (N : Superop A B) : Set (Matrix (A × B) (A × B) ℂ) :=
{sigma | QAlgorithms.Papers.Independent.Dependency50.P36.pptPrime sigma ∧
QAlgorithms.Papers.Independent.Dependency50.P36.relativeEntropy (choiState N) sigma = rainsInformation N}
/-- PDF p.13, Eq.(42): maximum below epsilon=1/2; minimum at or above it. -/
def rainsVariance (N : Superop A B) (epsilon : ℝ) : ℝ :=
let vs := {v | ∃ sigma ∈ rainsOptimizers N, v = QAlgorithms.Papers.Independent.Dependency50.P36.pairInformationVariance (choiState N) sigma}
if epsilon < 1/2 then sSup vs else sInf vs
/-- PDF p.14, Eq.(48): optimized coherent information, in bits, over ALL density inputs. -/
def channelCoherentBits (N : Superop A B) : ℝ :=
sSup {v | ∃ rho : Matrix A A ℂ, IsDensityMatrix rho ∧
v = QAlgorithms.Papers.Independent.Dependency50.P36.stateCoherentInformationBits (sourcePurifiedOutput N rho)}
/-- PDF p.14: constructed coherent-information maximizing inputs, including rank-deficient ones. -/
def coherentOptimizers (N : Superop A B) : Set (Matrix A A ℂ) :=
{rho | IsDensityMatrix rho ∧ QAlgorithms.Papers.Independent.Dependency50.P36.stateCoherentInformationBits (sourcePurifiedOutput N rho) = channelCoherentBits N}
/-- PDF p.14, Eq.(49): minimum variance below epsilon=1/2; maximum at or above it. -/
def coherentInformationVariance (N : Superop A B) (epsilon : ℝ) : ℝ :=
let vs := {v | ∃ rho ∈ coherentOptimizers N,
v = QAlgorithms.Papers.Independent.Dependency50.P36.coherentVariance (sourcePurifiedOutput N rho)}
if epsilon < 1/2 then sInf vs else sSup vs
/-- PDF pp.13–14, Eq.(44), corrected named purified-distance ball: F>=1-delta^2.
The exponent supremum is extended first; zero subnormalized states have infinite
min-entropy, but are excluded by this ball at normalized center and delta<1. -/
def smoothMinEntropy {I J : Type} [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J]
(rho : Matrix (I × J) (I × J) ℂ) (delta : ℝ) : EReal :=
sSup {h | ∃ tau : Matrix (I × J) (I × J) ℂ,
tau.PosSemidef ∧ tau.trace.re ≤ 1 ∧
1 - delta^2 ≤ rootFidelity tau rho ^ 2 ∧
∃ sigma : Matrix J J ℂ, IsDensityMatrix sigma ∧
∃ lambda : ℝ, h = (lambda : EReal) ∧
((Real.rpow 2 (-lambda) : ℂ) • Matrix.kronecker (1 : Matrix I I ℂ) sigma - tau).PosSemidef}
/-- PDF p.14, Eq.(46): optimized blocked smooth-entropy inner bound, including rounding. -/
def smoothInner (Nc : Superop A E) (n : ℕ) (epsilon : ℝ) : EReal :=
sSup {v | ∃ eta : ℝ, 0 < eta ∧ eta < epsilon ∧
∃ rho : Matrix (Fin n → A) (Fin n → A) ℂ, IsDensityMatrix rho ∧
v = (smoothMinEntropy (sourcePurifiedOutput (piSuperop (fun _ : Fin n => Nc)) rho) (Real.sqrt (epsilon-eta)) -
((4 * QAlgorithms.Papers.Independent.Information100.P80.log2 (1/eta) + 1 : ℝ) : EReal)) / (n : EReal)}
/-- PDF p.14, Eq.(47): eta=1/sqrt(n), with the square root applied AFTER subtraction.
The theorem requires 1/sqrt(n)<epsilon, correcting the printed domain. -/
def productSmoothInner (Nc : Superop A E) (n : ℕ) (epsilon : ℝ) : EReal :=
sSup {v | ∃ rho : Matrix A A ℂ, IsDensityMatrix rho ∧
v = (smoothMinEntropy
(QAlgorithms.Papers.Independent.Information100.P80.groupedPower (sourcePurifiedOutput Nc rho) n)
(Real.sqrt (epsilon - 1/Real.sqrt n)) -
((2 * QAlgorithms.Papers.Independent.Information100.P80.log2 n + 1 : ℝ) : EReal)) / (n : EReal)}
/-- PDF p.18, Eqs.(69)–(70): exact fixed-integer-message fidelity, with all erasure counts.
Since l<=n, n-l never truncates an intended negative number; M is positive in results. -/
def erasureFidelityFormula (beta : ℝ) (n M : ℕ) : ℝ :=
∑ l ∈ Finset.range (n+1), (n.choose l : ℝ) * beta^l * (1-beta)^(n-l) *
min 1 ((2 : ℝ)^(n-l) / M)
/-- PDF p.16, Eq.(61): fixed dephasing testing pair. -/
def dephasingAlternative : Matrix (Fin 2 × Fin 2) (Fin 2 × Fin 2) ℂ :=
choiState (QAlgorithms.Papers.Independent.Information100.P27.qubitDephasing (1-2*(1/2)))
/-- PDF p.19, Eq.(73): Bell weights (1/2,1/6,1/6,1/6), a normalized PPT alternative. -/
def depolarizingAlternative : Matrix (Fin 2 × Fin 2) (Fin 2 × Fin 2) ℂ :=
choiState (QuditFidelity.depolarizingMap 2 (by norm_num) (4*(1/2)/3))
/-- PDF p.16, Eq.(63): the BSC joint law, uniform input; comparison law is uniform on pairs. -/
def bscJoint (gamma : ℝ) : Matrix (Fin 2 × Fin 2) (Fin 2 × Fin 2) ℂ :=
Matrix.diagonal fun p => (if p.1 = p.2 then ((1-gamma)/2 : ℂ) else (gamma/2 : ℂ))
/-- PDF p.16: fixed product of uniform binary marginals. -/
def bscAlternative : Matrix (Fin 2 × Fin 2) (Fin 2 × Fin 2) ℂ :=
(1/4 : ℂ) • 1
/-- PDF pp.9,12: comparison-channel Choi operators are PSD, PPT, and trace preserving. -/
def PptChoiTP (J : Matrix (A × B) (A × B) ℂ) : Prop :=
J.PosSemidef ∧ (QAlgorithms.Entanglement.partialTransposeFirst J).PosSemidef ∧ traceRight J = 1
/-- PDF pp.21–22: the appendix uses trace-NONINCREASING comparison maps.
For PSD tests this has the same supremum, by product-PPT completion of the deficit. -/
def PptChoiTNI (J : Matrix (A × B) (A × B) ℂ) : Prop :=
J.PosSemidef ∧ (QAlgorithms.Entanglement.partialTransposeFirst J).PosSemidef ∧ (1 - traceRight J).PosSemidef
/-- PDF p.12, Eq.(33): Gamma constraints with Loewner, not entrywise, inequalities. -/
def GammaTests (N : Superop A B) (epsilon : ℝ)
(rho : Matrix A A ℂ) (Lambda : Matrix (A × B) (A × B) ℂ) : Prop :=
Lambda.PosSemidef ∧
(Matrix.kronecker rho.transpose (1 : Matrix B B ℂ) - Lambda).PosSemidef ∧
1 - epsilon ≤ (Lambda * QAlgorithms.Papers.Independent.Information100.P34.choi N).trace.re
/-- PDF p.12, Eq.(33): inner supremum over actual PPT-binding channel Choi matrices. -/
def comparisonValue (Lambda : Matrix (A × B) (A × B) ℂ) (tni : Bool) : ℝ :=
sSup {v | ∃ J : Matrix (A × B) (A × B) ℂ,
(if tni then PptChoiTNI J else PptChoiTP J) ∧ v = (Lambda * J).trace.re}
/-- PDF p.12, Eq.(33): inf_rho inf_Lambda sup_PPT in exactly that order.
The feasible pair set is nonempty for CPTP N and epsilon in (0,1); objective lies in [0,1]. -/
def metaValue (N : Superop A B) (epsilon : ℝ) (tni : Bool := false) : ℝ :=
sInf {v | ∃ rho : Matrix A A ℂ, IsDensityMatrix rho ∧
∃ Lambda : Matrix (A × B) (A × B) ℂ,
GammaTests N epsilon rho Lambda ∧ v = comparisonValue Lambda tni}
/-- PDF p.21, Eq.(A3): full minimization feasibility, with all identity tensor factors. -/
def SdpMinFeasible (N : Superop A B) (epsilon : ℝ)
(rho xi : Matrix A A ℂ) (Lambda Theta : Matrix (A × B) (A × B) ℂ) : Prop :=
IsDensityMatrix rho ∧ GammaTests N epsilon rho Lambda ∧
xi.PosSemidef ∧ Theta.PosSemidef ∧
(Matrix.kronecker xi (1 : Matrix B B ℂ) - Lambda - QAlgorithms.Entanglement.partialTransposeFirst Theta).PosSemidef
/-- PDF p.21, Eq.(A3): infimum of the trace objective over the constructed program. -/
def sdpMinValue (N : Superop A B) (epsilon : ℝ) : ℝ :=
sInf {v | ∃ rho xi : Matrix A A ℂ,
∃ Lambda Theta : Matrix (A × B) (A × B) ℂ,
SdpMinFeasible N epsilon rho xi Lambda Theta ∧ v = xi.trace.re}
/-- PDF pp.21–22, Eq.(A4): scalar nu consistently replaces the printed n/nu typo.
Tr_B R<=nu I is equivalent under transpose to Tr_B(R^{T_A})<=nu I. -/
def SdpMaxFeasible (N : Superop A B) (mu nu : ℝ)
(J R : Matrix (A × B) (A × B) ℂ) : Prop :=
0 ≤ mu ∧ 0 ≤ nu ∧ PptChoiTNI J ∧ R.PosSemidef ∧
(J + R - (mu : ℂ) • QAlgorithms.Papers.Independent.Information100.P34.choi N).PosSemidef ∧
((nu : ℂ) • (1 : Matrix A A ℂ) - traceRight R).PosSemidef
/-- PDF p.21, Eq.(A4): the dual supremum, not an assumed optimization value. -/
def sdpMaxValue (N : Superop A B) (epsilon : ℝ) : ℝ :=
sSup {v | ∃ mu nu : ℝ, ∃ J R : Matrix (A × B) (A × B) ℂ,
SdpMaxFeasible N mu nu J R ∧ v = mu * (1-epsilon) - nu}
/-- PDF p.16: binary vectors with the field addition used in parity checks. -/
abbrev BinaryWord (n : ℕ) := Fin n → ZMod 2
/-- PDF p.16: Fourier-character ket |c>_X in the physical Z basis. -/
def xKet {n : ℕ} (c : BinaryWord n) : EuclideanSpace ℂ (Fin n → Fin 2) :=
WithLp.toLp 2 fun z => ((Real.sqrt ((2 : ℝ)^n))⁻¹ : ℂ) *
(-1 : ℂ) ^ (∑ i, (c i).val * (z i).val)
/-- PDF pp.16–17: the CSS encoder sends message m to the X-basis word indexed by c_m. -/
def cssIsometry {n k : ℕ} (word : BinaryWord k →ₗ[ZMod 2] BinaryWord n) :
Matrix (Fin n → Fin 2) (Fin (2^k)) ℂ :=
fun z m => xKet (word ((Fintype.equivFin (BinaryWord k)).symm
(Fin.cast (by simp [BinaryWord]) m))) z
/-- PDF p.17: the syndrome-s projector, retaining EVERY syndrome outcome. -/
def syndromeProjector {n k : ℕ} (H : BinaryWord n →ₗ[ZMod 2] BinaryWord (n-k))
(s : BinaryWord (n-k)) : Matrix (Fin n → Fin 2) (Fin n → Fin 2) ℂ :=
∑ c : BinaryWord n, if H c = s then pureDensity (xKet c) else 0
/-- PDF p.17: correction Z^u is diagonal with signs (-1)^(u dot z). -/
def zError {n : ℕ} (u : BinaryWord n) : Matrix (Fin n → Fin 2) (Fin n → Fin 2) ℂ :=
Matrix.diagonal fun z => (-1 : ℂ) ^ (∑ i, (u i).val * (z i).val)
/-- PDF p.17: explicit syndrome measurement, phase correction, and inverse CSS isometry. -/
def cssDecoder {n k : ℕ} (H : BinaryWord n →ₗ[ZMod 2] BinaryWord (n-k))
(word : BinaryWord k →ₗ[ZMod 2] BinaryWord n) (estimate : BinaryWord (n-k) → BinaryWord n) :
Superop (Fin n → Fin 2) (Fin (2^k)) :=
krausApply fun s : BinaryWord (n-k) =>
(cssIsometry word)ᴴ * zError (estimate s) * syndromeProjector H s
/-- PDF pp.16–17: independent phase-error law, including endpoint probabilities. -/
def phaseErrorProbability {n : ℕ} (gamma : ℝ) (u : BinaryWord n) : ℝ :=
∏ i, if u i = 0 then 1-gamma else gamma
/-- PDF p.16: actual uniform-message average success for the syndrome decoder.
The received word is c_m+u, and decoding subtracts the estimated error. -/
def classicalLinearSuccess {n k : ℕ} (gamma : ℝ)
(H : BinaryWord n →ₗ[ZMod 2] BinaryWord (n-k)) (word : BinaryWord k →ₗ[ZMod 2] BinaryWord n)
(estimate : BinaryWord (n-k) → BinaryWord n) : ℝ :=
((2 : ℝ)^k)⁻¹ * ∑ m : BinaryWord k, ∑ u : BinaryWord n,
if word m + u - estimate (H (word m + u)) = word m
then phaseErrorProbability gamma u else 0
/-! Sanity examples pin the source conventions, without proving the target results. -/
example (M : ℕ) (x y : Fin M) : QAlgorithms.Papers.Independent.Dependency50.P36.target M (x,x) (y,y) = (M : ℂ)⁻¹ := by
simp [QAlgorithms.Papers.Independent.Dependency50.P36.target]
example (rho : Matrix A A ℂ) (i j k l : A) :
sourcePurification rho (i,j) (k,l) =
(cfc Real.sqrt rho) i j * conj ((cfc Real.sqrt rho) k l) := rfl
example (X : Matrix (A × B) (A × B) ℂ) (i k : A) (j l : B) :
QAlgorithms.Entanglement.partialTransposeFirst X (i,j) (k,l) = X (k,j) (i,l) := rfl
example : QAlgorithms.Papers.Independent.Frontier18.P07.binaryEntropyBits 0 = 0 ∧ binaryVariance 0 = 0 := by
norm_num [QAlgorithms.Papers.Independent.Frontier18.P07.binaryEntropyBits, binaryVariance, QAlgorithms.Papers.Independent.Information100.P80.log2]
example (gamma : ℝ) (X : Matrix (Fin 2) (Fin 2) ℂ) :
QAlgorithms.Papers.Independent.Information100.P27.qubitDephasing (1-2*gamma) X 0 1 = ((1-2*gamma : ℝ) : ℂ) * X 0 1 := by
simp [QAlgorithms.Papers.Independent.Information100.P27.qubitDephasing]
example (beta : ℝ) (X : Matrix (Fin 2) (Fin 2) ℂ) :
QAlgorithms.Papers.Independent.Renew46.P36.flaggedErasure (A := Fin 2) beta X none none = (beta : ℂ) * X.trace := rfl
example (X : Matrix A A ℂ) : QAlgorithms.Papers.Independent.Information100.P60.copies 0 X = 1 := by
ext x y
simp [QAlgorithms.Papers.Independent.Information100.P60.copies, Matrix.one_apply, Subsingleton.elim x y]
example {n k : ℕ} (H : BinaryWord n →ₗ[ZMod 2] BinaryWord (n-k))
(word : BinaryWord k →ₗ[ZMod 2] BinaryWord n) (estimate : BinaryWord (n-k) → BinaryWord n) :
cssDecoder H word estimate = krausApply (fun s : BinaryWord (n-k) =>
(cssIsometry word)ᴴ * zError (estimate s) * syndromeProjector H s) := rfl
/-- PDF p.8: a dimension-one target is the unit scalar density. -/
example : QAlgorithms.Papers.Independent.Dependency50.P36.target 1 (0,0) (0,0) = 1 := by norm_num [QAlgorithms.Papers.Independent.Dependency50.P36.target]
/-- PDF p.10: dependent coordinates retain the two unequal-dimensional local indices. -/
example {a b : ℕ} (i : Fin a) (j : Fin b) :
pairConfiguration i j 0 = i ∧ pairConfiguration i j 1 = j := by
constructor <;> rfl
/-- PDF p.10: channel noise acts on A and leaves the retained Q index unchanged. -/
example (N : Superop A B) (C : CppCode A B) (X : Matrix (Fin C.M) (Fin C.M) ℂ) :
cppEffective N C X = C.decoder (idTensorSuperop (R := Fin C.q) N
(fun p q => C.encoder X (p.2,p.1) (q.2,q.1))) := rfl
/-- PDF p.12: the test upper bound uses ordinary transpose on rho, not conjugate transpose. -/
example (N : Superop A B) (epsilon : ℝ) (rho : Matrix A A ℂ)
(L : Matrix (A × B) (A × B) ℂ) (h : GammaTests N epsilon rho L) :
(Matrix.kronecker rho.transpose (1 : Matrix B B ℂ) - L).PosSemidef := h.2.1
/-- PDF p.14: variance selection reverses between converse and achievability. -/
example (N : Superop A B) (epsilon : ℝ) (h : epsilon < 1/2) :
coherentInformationVariance N epsilon = sInf
{v | ∃ rho ∈ coherentOptimizers N,
v = QAlgorithms.Papers.Independent.Dependency50.P36.coherentVariance (sourcePurifiedOutput N rho)} := by
simp only [coherentInformationVariance, if_pos h]
/-- PDF p.18: no-use edge of the formula, outside theorem domain, has only l=0. -/
example (beta : ℝ) (M : ℕ) : erasureFidelityFormula beta 0 M = min 1 (1/(M : ℝ)) := by
simp [erasureFidelityFormula]
/-- PDF pp.16–17: zero error pattern never changes a computational-basis phase. -/
example {n : ℕ} (z : Fin n → Fin 2) : zError (0 : BinaryWord n) z z = 1 := by
simp [zError]
/-! One theorem for each nondeferred plan node. -/
end QAlgorithms.Papers.Independent.Support50.P04
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Support50.P04.BinaryWord
For every natural number , this abbreviates the type of functions from to , equivalently length- words over the two-element residue ring. The case is included and has exactly one word, the empty function.
QAlgorithms.Papers.Independent.Support50.P04.CppCode
For finite types with decidable equality, this structure consists of positive natural numbers , an encoder channel from matrices to matrices on , and a decoder channel from matrices on to matrices. Each channel must admit a finite Kraus representation with . The decoder must additionally have this form: locally embed its two input factors isometrically into positive finite dimensions , apply a singleton-outcome operation on the resulting configuration space, sum over the first configuration coordinate, and apply another finite-Kraus channel to the second coordinate. The required operation is a completely positive, trace-preserving instrument with one outcome and is the limit of the total maps of a compatible sequence of countable-history protocols, each having a positive finite number of rounds and each extending its predecessor by one round. At each history, a round consists of a countable-outcome instrument on one party and outcome-dependent channels on the other, combined by the matrix-unit tensor extension; instrument branches have completely positive complex-linear realizations, are summable on every input, and preserve trace after summation. Convergence means that the supremum, over density matrices on a reference copy and the configuration space, of the trace norm of the identity-amplified difference from tends to zero, with trace norm . No nonemptiness assumption on is separately included, but and are excluded by the structure’s positivity fields.
QAlgorithms.Papers.Independent.Support50.P04.FullUnitaryCovariant
For finite types with decidable equality and any function , this property means that there exists a group homomorphism such that, for every unitary matrix on and every complex matrix on ,
The homomorphism preserves multiplication and identity. No continuity assumption on , channel or linearity assumption on , or nonemptiness assumption on is imposed.
QAlgorithms.Papers.Independent.Support50.P04.GammaTests
For finite index types , an arbitrary function from complex matrices on to complex matrices on , an arbitrary real , a complex matrix on , and a complex matrix on , this predicate means
Here is the ordinary transpose without conjugation, and is defined entrywise by
where has a single entry at and zero elsewhere. No channel or linearity assumption on , density-matrix assumption on , or range restriction on is included. Empty index types are allowed; if is empty, the trace inequality reduces to .
QAlgorithms.Papers.Independent.Support50.P04.IsReceiverLOCC
For finite types with decidable equality, a natural number , and any function from complex matrices on to complex matrices, this predicate means that there exist positive natural numbers , matrices and satisfying and , a function on matrices indexed by configurations with , and a channel from matrices to matrices, such that, with ,
A channel here has finitely many Kraus matrices , acts as , and satisfies . The additional requirement on is precisely the following countable-history limit condition: its singleton-outcome family is an instrument, and there is a sequence of natural-number-outcome families, each generated by a positive finite number of rounds, with extending every history of by one further round. In one round, one of the two parties applies a countable-outcome instrument and the other applies an outcome-dependent channel; their product acts by the matrix-unit tensor extension. An instrument consists of maps admitting complex-linear realizations whose every finite identity amplification preserves positive semidefiniteness, whose output family is summable for every input matrix, and whose summed trace equals the input trace. An extension has branches , indexed by the natural-number encoding of . For each , all branches of are summed into a singleton-outcome instrument , and
where is indexed by two copies of the configuration space and . The predicate itself does not separately assume that is a channel, and and empty are not explicitly excluded.
QAlgorithms.Papers.Independent.Support50.P04.PptChoiTNI
For finite index types and , possibly empty, and a complex matrix indexed by , this predicate means
where means positive semidefinite,
Thus the partial trace is bounded above by the identity; equality and trace-one normalization are not required. The zero matrix satisfies this predicate, including when either index type is empty.
QAlgorithms.Papers.Independent.Support50.P04.PptChoiTP
For finite index types and , possibly empty, and a complex matrix indexed by , this predicate means that is positive semidefinite, its partial transpose on the first factor is positive semidefinite, and its partial trace over is the identity on . Explicitly, defining
the conditions are
There is no separate requirement that . If is empty, these conditions hold for the unique matrix; if is nonempty and is empty, the partial-trace condition cannot hold.
QAlgorithms.Papers.Independent.Support50.P04.SdpMaxFeasible
For finite index types , an arbitrary function from complex matrices on to complex matrices on , real numbers , and complex matrices on , this predicate means
Here means positive semidefinite, , is a matrix unit, , and . No channel assumption on or upper bounds on are imposed. Empty index types are allowed, and , always satisfies the predicate.
QAlgorithms.Papers.Independent.Support50.P04.SdpMinFeasible
For finite index types , an arbitrary function from complex matrices on to complex matrices on , a real , complex matrices on , and complex matrices on , this predicate means precisely
Here , is a matrix unit, denotes ordinary transpose, and . No channel assumption on , restriction on , or normalization of or is imposed. Empty index types are allowed, although no feasible tuple exists when is empty because is then impossible.
QAlgorithms.Papers.Independent.Support50.P04.binaryVariance
For every real , this defines
There is no assumption that . All expressions use the total real logarithm, with and for negative ; in particular the definition gives zero at both and .
QAlgorithms.Papers.Independent.Support50.P04.bscAlternative
This defines the complex matrix indexed by pairs in to be : each diagonal entry is , and every off-diagonal entry is zero.
QAlgorithms.Papers.Independent.Support50.P04.bscJoint
For every real , this declaration defines a diagonal complex matrix indexed by , whose diagonal entry at is if , and otherwise. Thus, in the order , it is
No restriction on is imposed; values outside , including those producing negative diagonal entries, are included.
QAlgorithms.Papers.Independent.Support50.P04.channelCoherentBits
For finite types with decidable equality and any function , this declaration defines
Here , interpreted using continuous functional calculus, and is defined as follows: put , form , and set . The marginal is . No channel assumption on , nonemptiness assumption on , or attainment assertion is included. The supremum is taken in , with value if its defining set is empty or unbounded above.
QAlgorithms.Papers.Independent.Support50.P04.channelTestingRains
For finite types with decidable equality, an arbitrary function , and any real , this defines
Writing , the source matrix has entries , and ; explicitly, its entry is . The partial transpose is , and . For matrices , let
This infimum is real, with value zero for an empty feasible set or a set unbounded below; is embedded into the extended reals when , and otherwise. The definition imposes neither a channel assumption on nor a restriction on , and does not require to have trace one. Empty types are included; if there are no input density matrices, the outer extended real supremum is .
QAlgorithms.Papers.Independent.Support50.P04.choiState
For finite types with decidable equality and any function , this defines the matrix on by
where has entry one at row , column , and zero elsewhere. No channel assumption on , positivity or trace normalization conclusion for , or nonemptiness assumption on is included. The inverse of zero is zero, including when .
QAlgorithms.Papers.Independent.Support50.P04.classicalLinearSuccess
For arbitrary natural numbers , any real , arbitrary -linear maps and , and any function , where , the declaration defines the real number
The vector additions, subtraction, and equality in the indicator are over . No restriction on , injectivity of , relation between and , or syndrome condition on is assumed. The sums include zero-dimensional spaces, each of which has one element, and the product is when ; the definition also includes .
QAlgorithms.Papers.Independent.Support50.P04.coherentInformationVariance
For finite types with decidable equality, any function , and any real , define , where , and put . Consider all positive semidefinite, trace-one inputs whose value equals the real supremum of those values over all positive semidefinite, trace-one inputs. For each such , put and
The declaration defines if , and otherwise. All matrix functions use continuous functional calculus, with no support-inclusion condition in this variance formula. The parameter is unrestricted, need not be a channel, and optimizing inputs need not exist. The real extrema use for empty sets or failure of the corresponding boundedness condition.
QAlgorithms.Papers.Independent.Support50.P04.coherentOptimizers
For finite types with decidable equality and any function , this declaration defines the set of positive semidefinite, trace-one matrices on for which
Here , with matrix functions interpreted by continuous functional calculus. For each input , put and define ; tracing out sums the entries with . No channel assumption on , nonemptiness assumption on the index types, or existence of such an optimizing is asserted. The real supremum on the right is for an empty or unbounded-above defining set.
QAlgorithms.Papers.Independent.Support50.P04.comparisonValue
For finite index types , an arbitrary complex matrix on , and a Boolean flag , this defines the real supremum of over complex matrices on satisfying and , together with when is true, or when is false. Here positive semidefiniteness is denoted by , , and . No positivity assumption on or attainment assertion is included. Empty index types are allowed; in particular, the feasible set is empty when is false, is nonempty, and is empty. The real supremum uses the total convention that an empty set, or a set unbounded above, has supremum .
QAlgorithms.Papers.Independent.Support50.P04.constantRemainderExpansion
For every sequence and arbitrary real numbers , this property means that there exist and a natural number such that, for every natural ,
The real bounds are viewed as extended real numbers, and , with the real infimum equal to zero for an empty set or a set unbounded below. No restriction on or is assumed; the square root term is zero when . The sequence must be finite eventually, but its terms below are unrestricted.
QAlgorithms.Papers.Independent.Support50.P04.cppBoundary
For finite types with decidable equality, any function , any natural number , and any real , this defines an extended real number as the supremum of all real rates for which there is a code with positive message dimension , positive memory dimension , a channel , and a channel , satisfying and . Here when and , and is zero otherwise; , where the tilde interchanges the input and memory coordinates, and is the linear extension determined by applying separately to matrix units in each coordinate. Each channel mentioned means a map with finitely many matrices satisfying . The decoder must additionally have the following realization: embed its two input registers isometrically into positive dimensions , apply a map on their joint configuration space, trace out the first register, and apply a channel from the second register to the -dimensional output. The singleton instrument with branch must satisfy the supplied countable local protocol condition: it is an instrument and is approached, in instrument distance, by coarse grainings of an increasing sequence of finite histories, each extended by one local round. An instrument has completely positive complex linear branches, summable branch outputs on every matrix, and a trace preserving total; complete positivity means positivity after adjoining every finite dimensional identity register. In one local round one party uses an instrument and the other uses an outcome dependent channel; history extension composes such rounds with preceding branches, and coarse graining sums branches assigned the same output. Instrument distance is the supremum over joint input–reference density matrices of the sum over outcomes of the trace norms of the amplified branch differences, where . No channel assumption on , nonemptiness assumption on , bound on , or positivity assumption on is imposed; at the real quotient is zero. The supremum is taken in the extended reals, so an empty feasible set gives .
QAlgorithms.Papers.Independent.Support50.P04.cppEffective
For finite types with decidable equality, any function from matrices on to matrices on , and a code with positive message and memory dimensions , encoder , and decoder , the definition returns the function on matrices given by
The code requires both and to have finite Kraus representations with Kraus completeness . Its decoder also admits local isometric embeddings into positive dimensions, followed by an operation , tracing out the first embedded factor, and a finite-Kraus channel on the second. Here is a singleton-outcome completely positive trace-preserving instrument approached by totals of compatible countable-history, positive finite-round local protocols, each extending the preceding protocol by one round; a round uses one party’s countable-outcome instrument and the other party’s outcome-dependent channel. Instrument branches are completely positive complex-linear maps, summable on every input, with total trace preserved. The convergence is in the supremum of over density matrices on a reference copy and the embedded space, where . No channel or linearity assumption is imposed on , so the definition alone does not require to be a channel.
QAlgorithms.Papers.Independent.Support50.P04.cppFeasible
For finite types with decidable equality, any function from matrices on to matrices on , a natural number , and real numbers , this predicate means that there exists a code with positive message dimension , positive memory dimension , a finite-Kraus encoder channel , and a finite-Kraus decoder channel , such that
The notation for channels indicates their matrix index spaces; finite-Kraus channels act as with . The matrix has entry at and zero elsewhere. Set
where , and identity extensions act on blocks. The decoder must also admit local isometric embeddings into positive finite dimensions, followed by a singleton-outcome operation , tracing out the first embedded factor, and a finite-Kraus channel on the second. This is a completely positive trace-preserving instrument approached by totals of compatible countable-history protocols with positive finite round counts, each extending its predecessor by one round; each round uses a countable-outcome instrument on one party and outcome-dependent channels on the other. Instrument branches are completely positive complex-linear maps, summable for every input, with summed trace preserved. Convergence is measured by the supremum trace norm of the identity-amplified difference over density matrices on a reference copy and the embedded space, where . No channel assumption on or range restriction on is imposed. The case is included, with empty products equal to , the scalar identity, and the rate inequality interpreted as .
QAlgorithms.Papers.Independent.Support50.P04.cppFidelity
For finite types with decidable equality, any function from matrices on to matrices on , and a code with positive dimensions , define
If are its encoder and decoder, set
The definition returns
where the identity extension applies separately to each block indexed by fixed reference coordinates. The code requires finite-Kraus encoder and decoder channels, with , and requires the decoder to arise from local isometric embeddings into positive finite dimensions, an operation , tracing out the first embedded factor, and a finite-Kraus channel on the second. The operation is a singleton-outcome completely positive trace-preserving instrument obtained as a limit of totals of compatible countable-history protocols of positive finite round count, each extending its predecessor by one local round. Each round uses a countable-outcome instrument on one party and outcome-dependent channels on the other; the instrument branches are completely positive complex-linear maps, summable for every input, and preserve total trace. The limit uses the supremum trace norm of the identity-amplified difference on density matrices, with . No channel assumption is imposed on .
QAlgorithms.Papers.Independent.Support50.P04.cssDecoder
For arbitrary natural numbers , arbitrary -linear maps and , and any function , where , define for , . Let be the inverse of the specified enumeration of , put , put , and let be diagonal with . The declaration defines the map from complex matrices on to complex matrices on by
No injectivity of , condition , surjectivity of , or condition is imposed, and the declaration does not assert that preserves trace. Zero values of and are included, with the indicated truncated subtraction and empty-sum conventions.
QAlgorithms.Papers.Independent.Support50.P04.cssIsometry
For arbitrary natural numbers , let , and let be any -linear map. Choose the enumeration given by the inverse of the specified finite-type equivalence; the intervening cast merely identifies the cardinality of with . The declaration defines a complex matrix , whose rows are indexed by and columns by , by
Here takes the representative or , and the exponent is a sum in the natural numbers. No injectivity of , relation , or isometry equation is required. Both and are included, with empty sums equal to .
QAlgorithms.Papers.Independent.Support50.P04.dephasingAlternative
This declaration defines the complex matrix on obtained by taking one half of the Choi matrix of the map that retains a matrix’s diagonal entries and sets its off-diagonal entries to zero: the dephasing parameter is exactly . Explicitly, in the order , the matrix is
where the Choi convention is .
QAlgorithms.Papers.Independent.Support50.P04.depolarizingAlternative
This declaration defines one half of the Choi matrix of the map , obtained from the given depolarizing-map formula at dimension and parameter . With Choi entries , its explicit matrix in the order is
QAlgorithms.Papers.Independent.Support50.P04.dispersionLower
For every sequence and arbitrary real numbers , this property means that there exist and a natural number such that every natural satisfies
Here the left side is embedded into the extended reals, , and , with zero used for an empty set or a set unbounded below. There is no restriction on or ; the square root term vanishes for . This is only a lower bound: eventual values are permitted, and terms before are unrestricted.
QAlgorithms.Papers.Independent.Support50.P04.dispersionUpper
For every sequence and arbitrary real numbers , this property means that there exist and a natural number such that every natural satisfies
Here the right side is embedded into the extended reals, , and is the real infimum of the set of with , taking zero for an empty set or a set unbounded below. No restriction on or is imposed, and the square root term is zero for . This is only an upper bound: eventual values are permitted, and terms before are unrestricted.
QAlgorithms.Papers.Independent.Support50.P04.erasureFidelityFormula
For every real and natural numbers , this declaration defines the real number
There is no assumption that or that are positive. All exponents are natural numbers, including , with . Real division by is , so the value is when ; when , it is .
QAlgorithms.Papers.Independent.Support50.P04.localEmbedding
For finite types , natural numbers , and arbitrary complex matrices with rows indexed by and columns by , and with rows indexed by and columns by , the definition returns a matrix whose rows are configurations consisting of a coordinate and a coordinate , and whose columns are pairs , with
No isometry or normalization condition is imposed on . The values and are permitted; either makes the configuration row set empty.
QAlgorithms.Papers.Independent.Support50.P04.metaValue
For finite index types , an arbitrary function from complex matrices on to complex matrices on , a real , and a Boolean flag defaulting to false, this defines
The outer feasible matrices satisfy
where and is the corresponding matrix unit. The inner feasible matrices satisfy , , and either if is true or otherwise, with and . No channel assumption on , restriction on , or attainment assertion is included. Both optimizations are real-valued total infima or suprema: an empty set, or a set unbounded in the relevant direction, gives . In particular, an empty makes the outer density-matrix constraint impossible.
QAlgorithms.Papers.Independent.Support50.P04.normalRate
For arbitrary real numbers and every natural number , this defines
No positivity assumption on or , or interval restriction on , is imposed. Division and square root are total real operations: division by zero gives zero and the square root of a nonpositive number is zero, so the defined rate is when or . The infimum defining uses the real infimum operation, which gives zero for an empty set or a set unbounded below.
QAlgorithms.Papers.Independent.Support50.P04.optimalCppFidelity
For finite types with decidable equality, any function , and natural numbers , this defines the extended real supremum of
over codes with message dimension exactly , positive memory dimension , a channel encoder , and a channel decoder . Here if and , and is zero otherwise, while ; the tilde swaps the encoder’s two registers, and is the linear extension specified by applying to matrix units in each coordinate. A channel is a finite Kraus sum with . The decoder must admit isometric embeddings of its two inputs into positive dimensions , followed by a joint map , tracing out the first embedded register, and a channel acting on the second register. The singleton instrument must be an instrument obtainable as an instrument-distance limit of coarse grainings of successive finite local histories, with every history extended to the next by one local round. Instruments have completely positive complex linear branches, summable outputs on every matrix, and a trace preserving sum; complete positivity requires positivity after every finite identity amplification. Each local round consists of an instrument on one party and outcome dependent channels on the other; coarse graining sums branches, and instrument distance is the supremum over joint input–reference density matrices of the sum of amplified branch-difference trace norms . The code requires , so gives the supremum of the empty set, namely . The definition includes , imposes no channel assumption on , and imposes no nonemptiness assumption on .
QAlgorithms.Papers.Independent.Support50.P04.pairConfiguration
For natural numbers , an index , and an index , the definition returns the configuration on two coordinates of respective sizes whose coordinate is and whose coordinate is . There are no other coordinates. If or , the corresponding required index does not exist, so there are no such inputs.
QAlgorithms.Papers.Independent.Support50.P04.phaseErrorProbability
For every natural number , every real number , and every , the declaration defines
There is no hypothesis that , so nonnegativity is not part of this declaration. For , the empty product is . The endpoint values are included.
QAlgorithms.Papers.Independent.Support50.P04.productSmoothInner
For finite types with decidable equality, any function , any natural number , and any real , this declaration defines
Here , , and . For a matrix on , is the extended-real supremum of real for which there exist with and with , satisfying and ; matrix functions use continuous functional calculus. No channel assumption, nonempty-index assumption, or restriction on is imposed. A negative argument of the real square root gives . For , the matrix product is the empty product , the real conventions give and , and the final denominator is in extended-real arithmetic. An empty input optimization has value .
QAlgorithms.Papers.Independent.Support50.P04.rainsInformation
For finite types with decidable equality and any function , this defines the extended real infimum
where is the corresponding matrix unit, , and . For arbitrary matrices , the quantity used here is
with and applied through the supplied continuous functional calculus, using the total real logarithm . No channel assumption on , density matrix assumption on , trace-one requirement on , or nonemptiness assumption on is imposed; when is empty.
QAlgorithms.Papers.Independent.Support50.P04.rainsOptimizers
For finite types , each with decidable equality, and any function , define its normalized Choi matrix by , where has a single entry at . This declaration defines the set of all matrices on such that is positive semidefinite, , and
Here transposes the indices, , and is unless ; when that inclusion holds, it is the extended-real embedding of , with the matrix functions interpreted by continuous functional calculus. No channel assumption on , nonemptiness assumption on , trace-one condition on , or assertion that this set contains an optimizer is imposed; equality of two infinite values is permitted.
QAlgorithms.Papers.Independent.Support50.P04.rainsVariance
For finite types with decidable equality, any function , and any real , let . Form the set of real numbers over all with satisfying
Here is a matrix unit, transposes the second subsystem, , and . The extended-real equals when , and otherwise; all matrix functions use continuous functional calculus. The defined value is if , and if . The parameter is unrestricted, need not be a channel, and the optimizer set need not be nonempty. These are real-valued supremum and infimum operations, whose empty-set values—and whose values when the required boundedness fails—are .
QAlgorithms.Papers.Independent.Support50.P04.receiverConfigurationMarginal
For natural numbers and any complex matrix indexed by configurations with and , the definition returns the complex matrix
Here denotes the two-coordinate configuration with those values. No positivity or normalization condition is imposed on . If , the sum is empty and ; if , the output matrix has an empty index set.
QAlgorithms.Papers.Independent.Support50.P04.sdpMaxValue
For finite index types , an arbitrary function from complex matrices on to complex matrices on , and a real , this defines the real supremum of over real and complex matrices on satisfying
Here , is a matrix unit, , and . No channel assumption on , restriction on , or attainment assertion is included. The zero tuple is feasible, even for empty index types. If the objective values are unbounded above, the total real-supremum convention returns .
QAlgorithms.Papers.Independent.Support50.P04.sdpMinValue
For finite index types , an arbitrary function from complex matrices on to complex matrices on , and any real , this defines the real infimum of over complex matrices on and on satisfying
Here , is a matrix unit, and . No channel assumption on , restriction on , or attainment assertion is included. The infimum is if the feasible set is empty, including when is empty; the total real-infimum convention also assigns to a set unbounded below.
QAlgorithms.Papers.Independent.Support50.P04.smoothInner
For finite types with decidable equality, any function , any natural number , and any real , this declaration defines
The input is indexed by . The map used here is defined literally by . Writing , the matrix has entries . For a matrix on , is the extended-real supremum of real admitting , , and a positive semidefinite trace-one on , such that and ; all matrix functions use continuous functional calculus. No channel assumption on or positivity assumption on is imposed. If , there is no admissible , so the value is . The case is included, with empty tensor products and division by interpreted by the formal extended-real arithmetic.
QAlgorithms.Papers.Independent.Support50.P04.smoothMinEntropy
For any finite types with decidable equality, any complex matrix on , and any real , this declaration defines the extended-real supremum of all real for which there exist matrices on and on satisfying
The square roots are continuous-functional-calculus matrix functions, and is the real power of . No positivity or normalization hypothesis on , sign or upper bound on , or nonemptiness assumption on is imposed. The choice is allowed when the inequalities permit it. The supremum is if there are no feasible real , and may be .
QAlgorithms.Papers.Independent.Support50.P04.sourcePurification
For a finite type with decidable equality and any complex matrix indexed by , let , where the square root denotes the total real continuous functional calculus applied to . The definition returns the matrix indexed by whose entries are
Thus it is the outer product of the vector with coordinates with its conjugate. No positivity, Hermiticity, trace, or normalization condition is imposed on ; the definition also applies when is empty.
QAlgorithms.Papers.Independent.Support50.P04.sourcePurifiedOutput
For a finite type with decidable equality, a type , any function from complex matrices to complex matrices, and any complex matrix , let be the total real continuous-functional-calculus square root of . The definition returns the matrix
This applies separately to each block obtained by fixing the first coordinates of the matrix with entries . Neither linearity nor the channel property is assumed for , and no density-matrix condition is assumed for ; empty index types are included.
QAlgorithms.Papers.Independent.Support50.P04.syndromeProjector
For arbitrary natural numbers , any -linear map , and any , where , the declaration defines a complex matrix indexed by as
Thus each summand has entry . No surjectivity or rank condition on is assumed; if the fiber is empty, the matrix is zero. The definition includes , , and ; in the last case the syndrome space is the one-element space .
QAlgorithms.Papers.Independent.Support50.P04.thirdOrderExpansion
For every sequence and arbitrary real numbers , this property means that there exist a real and a natural number such that, for every natural ,
Here the real bounds are embedded into the extended reals, , and is the real infimum of all satisfying , using zero when this set is empty or unbounded below. There is no restriction on or ; for the square root term is zero. The property forces to be finite eventually and places no condition on terms before .
QAlgorithms.Papers.Independent.Support50.P04.unassistedBoundary
For finite types with decidable equality, any function from matrices on to matrices on , a natural number , and a real number , the definition returns the supremum in the extended real numbers of all real for which there exist a positive natural number , a finite-Kraus encoder channel , and a finite-Kraus decoder channel , satisfying
Here each channel acts as with ; if and , and is zero otherwise; identity extensions act separately on blocks; and
where is a matrix unit. No channel or linearity condition is imposed on , and is unrestricted. If the feasible set is empty, the value is ; if it is unbounded above, the value is . The case is included, with empty-word index spaces, empty products equal to , and division by zero equal to zero, so any feasible rate then satisfies .
QAlgorithms.Papers.Independent.Support50.P04.unassistedFeasible
For finite types with decidable equality, any function from matrices on to matrices on , a natural number , and real numbers , this predicate means that there exist a positive natural number , an encoder channel from matrices to matrices on , and a decoder channel from matrices on to matrices, such that
Here and are function spaces on , when and , and is zero otherwise, and
with the matrix having a single in entry . Identity extensions act on matrix blocks. Each encoder and decoder channel has a finite Kraus representation with . There are no restrictions on , and is not assumed to be linear or a channel. The case is included: the product is empty, is the identity on the one-dimensional empty-word space, and division by is defined to be zero, so the rate inequality becomes .
QAlgorithms.Papers.Independent.Support50.P04.xKet
For every natural number and every word , this defines a vector in the complex Euclidean space indexed by functions . Its coordinate at is
where both values are natural-number representatives in and the sum in the exponent is a natural-number sum. When , both indexing functions are empty, the exponent is , and the vector’s unique coordinate is .
QAlgorithms.Papers.Independent.Support50.P04.zError
For every natural number and every , the declaration defines the diagonal complex matrix , indexed by , by
The values in the exponent are the natural-number representatives , and the sum is a natural-number sum. When , there is one row and one column, the exponent is the empty sum , and the resulting matrix is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.