Definitions for Remote preparation of quantum states
DefinitionQAlgorithms_Papers_Independent_Intakenext100_P54The objects the formalized statements of Remote preparation of quantum states (arXiv:quant-ph/0307100) are stated in. Each was checked against the paper by a blind read-back and a moderator.
RSPVector: Normalized vectors in a specified finite register (PDF pp.1–3).bar: Entrywise conjugation in the entanglement basis (PDF pp.2–3).randomise: Averaging unitary conjugations (PDF p.3, equation (1)).Randomising: The operator-order assertion of equation (1), for every density operator (PDF p.3).randomisingBound: The printed randomisation cardinality bound (PDF p.3), with logarithm base two.piGood: Good effects of protocol Pi. Conjugation is on the target alone (PDF p.3).piEffect: Complete POVM alphabet, including the common failure flag (PDF pp.3–4).piBranch: Unnormalized receiver branch after steering and the announced correction (PDF p.4). On a maximally entangled pair the steered operator is the effect's transpose divided by D.RSPCode: One-way finite RSP code with input-independent maximally entangled rank S resource, input-dependent Alice POVM, and fixed CPTP Bob decoder per message (PDF pp.4–5). The source's support costs are log2 K and log2 S.RSPCode.branch: Unnormalized decoded message branch, without conditioning on its probability (PDF p.5).RSPCode.output: Averaged output of a finite one-way code (PDF p.5).RSPCode.ExactWithError: Probabilistic exact preparation: one input-independent success set, exact conditional good outputs, and a uniform failure bound (PDF p.2).pureWordVector: Product target with the source's ordered tensor factors (PDF p.5).pureAverageOverlap: Global average squared fidelity, equation (2), rather than the local criterion (3) (PDF p.5).RSPPureAchievable: One-way achievable rates with both slacks before the blocklength threshold (PDF p.5).pureOperational: Extended nonnegative operational cost: an infeasible rate has value infinity (PDF pp.5–6).AuxChannel: Finite but arbitrarily large classical auxiliary alphabet (PDF p.6, equation (5)).auxWeight: Auxiliary marginal probability (PDF p.6).conditionalBob: Conditional Bob state; a zero-probability auxiliary uses the maximally mixed state. Its entropy is multiplied by zero, so this convention does not affect any information (PDF p.6).auxiliaryBobEntropy: S(B|C), averaged over the classical auxiliary (PDF pp.6,10).labelAuxInfo: I(X;C) for the source's stochastic auxiliary channel (PDF p.6).labelBobAuxInfo: I(X;BC) = I(X;C)+S(B|C)-S(B|X), evaluated from the specified cq state. For pure Bob targets the last term vanishes; for entangled targets it must be retained (PDF pp.6,10).rspSingleLetter: Single-letter optimisation with no unsupported m+1 cardinality restriction. The empty feasible set has infimum infinity (PDF pp.6,10).rspMinimumAttained: Actual attainment whenever the single-letter feasible value is finite; this records "min" rather than merely replacing it with an infimum (PDF pp.6,10).BipartiteEnsemble: Pure bipartite ensemble: the full chosen purification is the target (PDF p.8).bobStates: Receiver marginals of the fixed purifications (PDF pp.8–10).BipartiteCode: General one-way entangled RSP: input-dependent Alice CP instrument, with only its SUM trace preserving; Bob's decoder is arbitrary CPTP (PDF p.8). Padding permits a common finite number L of Kraus operators per branch.BipartiteCode.output: Full joint output, sum_j (M_j^I tensor T_j)(Phi_S); no Alice output is discarded (PDF p.8).bipWord: IID bipartite target, with Alice factors grouped together and Bob factors grouped together (PDF p.8).bipAverage: Global average overlap with the chosen bipartite purification (PDF pp.8–9).BipartiteAchievable: One-way entangled achievable rates with the source's global criterion (PDF pp.8–9).bipOperational: Entangled operational curve, infinity when no finite rate pair is achievable (PDF p.9).bobAverageEntropy: Entropy of the receiver's average state, not the average of the individual entropies (PDF p.9).bobHolevo: Holevo information of the receiver marginal ensemble (PDF p.9).piRecord: Complete receiver record after replacing Pi's failure message uniformly by a good label. The failure flag stays private to Alice (PDF pp.12–13).piSimulator: Linear CPTP simulator with one ACTUAL receiver output specimen as input. Conjugating U, rather than the unknown specimen, makes this a linear channel (PDF p.13).piApproxOutput: Actual averaged output decoded from the uniformly replaced failure record (PDF p.13).marginalAverageFidelity: Bob's global average mixed-state squared fidelity after discarding Alice's output (PDF p.13).SymmetricGaussian: Independent centered real and imaginary coordinates of a symmetric complex Gaussian. Each real coordinate has variance s2/(2D), so the total expected norm square is s2. Definition 22's printed mu_j is read as zero by its immediately preceding prose (PDF p.14).momentLog: Logarithm of a nonnegative exponential moment, including divergence and zero. It never turns a divergent Bochner integral into zero (PDF p.14).squaredGaussianRate: Cramer transform of a squared real centered Gaussian, defined from the moment integral and supremum, not from the asserted closed form (PDF p.14).elementaryRate: Extended endpoint of A3: ln(0) is minus infinity, not Lean's Real.log 0 = 0 (PDF p.14).VisibleCode: Universal visible quantum-classical compression with a pure quantum codeword and a fixed CPTP decoder per classical message (PDF pp.15–16). All code sizes are fixed support sizes.VisibleCode.output: Decoding the jointly visible quantum and classical description (PDF p.15).
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Defs_QuantumInformation
import Definitions.Def_QAlgorithms_Defs_FiniteRegisters
import Definitions.Def_QAlgorithms_Defs_SchurUnitaryEnsembles
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P03
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P53
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P07
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P08
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P38
/-!
Statements from Bennett, Hayden, Leung, Shor and Winter,
Remote preparation of quantum states, quant-ph/0307100v3.
All logarithms in resource bounds are base two. New definitions are paper-local.
Fidelity, iid probabilities, finite pure ensembles and classical entropy reuse pinned accepted
modules whose exact source bodies were hash-verified before reuse.
Theorem 2 and Lemma 4 use the small-error domains justified by their proofs.
Theorem 5 charges the failure message as well as all good messages.
-/
noncomputable section
open scoped BigOperators Matrix ComplexConjugate ComplexOrder NNReal ENNReal
open MeasureTheory ProbabilityTheory
namespace QAlgorithms.Papers.Independent.Intakenext100.P54
open QAlgorithms.Papers.Independent.Information100.P03 (PureEnsemble)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)
open QAlgorithms.Papers.Independent.Claimed50.P08 (classicalEntropy)
open QAlgorithms.Papers.Independent.Claimed50.P38 (tensorSuperop)
/-- Normalized vectors in a specified finite register (PDF pp.1–3). -/
abbrev RSPVector (O : Type*) [Fintype O] := {v : EuclideanSpace ℂ O // ‖v‖ = 1}
/-- Entrywise conjugation in the entanglement basis (PDF pp.2–3). -/
def bar {O : Type*} (M : Matrix O O ℂ) : Matrix O O ℂ := fun a b => conj (M a b)
/-- Averaging unitary conjugations (PDF p.3, equation (1)). -/
def randomise {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ)
(rho : Matrix (Fin D) (Fin D) ℂ) : Matrix (Fin D) (Fin D) ℂ :=
((K : ℂ)⁻¹) • ∑ k, (U k : Matrix (Fin D) (Fin D) ℂ) * rho *
(U k : Matrix (Fin D) (Fin D) ℂ)ᴴ
/-- The operator-order assertion of equation (1), for every density operator (PDF p.3). -/
def Randomising {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ) (eps : ℝ) : Prop :=
∀ rho : Matrix (Fin D) (Fin D) ℂ, IsDensityMatrix rho →
(randomise U rho - (((1 - eps) / D : ℝ) : ℂ) • 1).PosSemidef ∧
((((1 + eps) / D : ℝ) : ℂ) • 1 - randomise U rho).PosSemidef
/-- The printed randomisation cardinality bound (PDF p.3), with logarithm base two. -/
def randomisingBound (D : ℕ) (eps : ℝ) : ℝ :=
(10 / eps) ^ 2 * D * Real.logb 2 (20 * D / eps)
/-- Good effects of protocol Pi. Conjugation is on the target alone (PDF p.3). -/
def piGood {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ)
(eps : ℝ) (psi : RSPVector (Fin D)) (k : Fin K) : Matrix (Fin D) (Fin D) ℂ :=
((D : ℂ) / (K * (1 + (eps : ℂ)))) •
((U k : Matrix (Fin D) (Fin D) ℂ) * bar (pureDensity psi.val) *
(U k : Matrix (Fin D) (Fin D) ℂ)ᴴ)
/-- Complete POVM alphabet, including the common failure flag (PDF pp.3–4). -/
def piEffect {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ)
(eps : ℝ) (psi : RSPVector (Fin D)) : Option (Fin K) → Matrix (Fin D) (Fin D) ℂ
| some k => piGood U eps psi k
| none => 1 - ∑ k, piGood U eps psi k
/-- Unnormalized receiver branch after steering and the announced correction (PDF p.4).
On a maximally entangled pair the steered operator is the effect's transpose divided by D. -/
def piBranch {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ)
(eps : ℝ) (psi : RSPVector (Fin D)) : Option (Fin K) → Matrix (Fin D) (Fin D) ℂ
| some k => (U k : Matrix (Fin D) (Fin D) ℂ).transpose *
(((D : ℂ)⁻¹) • (piGood U eps psi k).transpose) *
((U k : Matrix (Fin D) (Fin D) ℂ).transpose)ᴴ
| none => ((D : ℂ)⁻¹) • (piEffect U eps psi none).transpose
/-- Sanity: the failure effect completes precisely the family of good effects. -/
example {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ)
(eps : ℝ) (psi : RSPVector (Fin D)) :
piEffect U eps psi none + ∑ k, piEffect U eps psi (some k) = 1 := by
simp only [piEffect]
exact sub_add_cancel _ _
/-- One-way finite RSP code with input-independent maximally entangled rank S resource,
input-dependent Alice POVM, and fixed CPTP Bob decoder per message (PDF pp.4–5).
The source's support costs are log2 K and log2 S. -/
structure RSPCode (Input O : Type*) [Fintype O] [DecidableEq O] where
S : ℕ
Spos : 0 < S
K : ℕ
Kpos : 0 < K
effect : Input → Fin K → Matrix (Fin S) (Fin S) ℂ
povm : ∀ i, IsPOVM (effect i)
decoder : Fin K → Superop (Fin S) O
channel : ∀ j, IsChannel (decoder j)
/-- Unnormalized decoded message branch, without conditioning on its probability (PDF p.5). -/
def RSPCode.branch {Input O : Type*} [Fintype O] [DecidableEq O]
(P : RSPCode Input O) (i : Input) (j : Fin P.K) : Matrix O O ℂ :=
P.decoder j (((P.S : ℂ)⁻¹) • (P.effect i j).transpose)
/-- Averaged output of a finite one-way code (PDF p.5). -/
def RSPCode.output {Input O : Type*} [Fintype O] [DecidableEq O]
(P : RSPCode Input O) (i : Input) : Matrix O O ℂ := ∑ j, P.branch i j
/-- Probabilistic exact preparation: one input-independent success set, exact conditional good
outputs, and a uniform failure bound (PDF p.2). -/
def RSPCode.ExactWithError {O : Type*} [Fintype O] [DecidableEq O]
(P : RSPCode (RSPVector O) O) (eps : ℝ) : Prop :=
∃ good : Finset (Fin P.K), ∀ psi : RSPVector O,
(∀ j ∈ good, P.branch psi j = ((P.branch psi j).trace.re : ℂ) • pureDensity psi.val) ∧
1 - eps ≤ ∑ j ∈ good, (P.branch psi j).trace.re
/-- Product target with the source's ordered tensor factors (PDF p.5). -/
def pureWordVector {d : ℕ} (E : PureEnsemble (Fin d)) (n : ℕ) (w : Fin n → Fin E.count) :
EuclideanSpace ℂ (Fin n → Fin d) :=
WithLp.toLp 2 fun x => ∏ t, E.vector (w t) (x t)
/-- Global average squared fidelity, equation (2), rather than the local criterion (3) (PDF p.5). -/
def pureAverageOverlap {d : ℕ} (E : PureEnsemble (Fin d)) (n : ℕ)
(P : RSPCode (Fin n → Fin E.count) (Fin n → Fin d)) : ℝ :=
∑ w, wordProb E.weight n w * (pureDensity (pureWordVector E n w) * P.output w).trace.re
/-- One-way achievable rates with both slacks before the blocklength threshold (PDF p.5). -/
def RSPPureAchievable {d : ℕ} (E : PureEnsemble (Fin d)) (R ent : ℝ) : Prop :=
0 ≤ R ∧ 0 ≤ ent ∧ ∀ eps : ℝ, 0 < eps → ∀ delta : ℝ, 0 < delta →
∃ nzero : ℕ, 0 < nzero ∧ ∀ n ≥ nzero,
∃ P : RSPCode (Fin n → Fin E.count) (Fin n → Fin d),
1 - eps ≤ pureAverageOverlap E n P ∧
Real.logb 2 P.K / n ≤ R + delta ∧ Real.logb 2 P.S / n ≤ ent + delta
/-- Extended nonnegative operational cost: an infeasible rate has value infinity (PDF pp.5–6). -/
def pureOperational {d : ℕ} (E : PureEnsemble (Fin d)) (R : ℝ) : ℝ≥0∞ :=
sInf {v | ∃ ent : ℝ, RSPPureAchievable E R ent ∧ v = ENNReal.ofReal ent}
/-- Finite but arbitrarily large classical auxiliary alphabet (PDF p.6, equation (5)). -/
structure AuxChannel (m k : ℕ) where
prob : Fin m → Fin k → ℝ
nonneg : ∀ i j, 0 ≤ prob i j
total : ∀ i, ∑ j, prob i j = 1
/-- Auxiliary marginal probability (PDF p.6). -/
def auxWeight {m k : ℕ} (p : Fin m → ℝ) (c : AuxChannel m k) (j : Fin k) : ℝ :=
∑ i, p i * c.prob i j
/-- Conditional Bob state; a zero-probability auxiliary uses the maximally mixed state.
Its entropy is multiplied by zero, so this convention does not affect any information (PDF p.6). -/
def conditionalBob {m k d : ℕ} (p : Fin m → ℝ)
(rho : Fin m → Matrix (Fin d) (Fin d) ℂ) (c : AuxChannel m k) (j : Fin k) :
Matrix (Fin d) (Fin d) ℂ :=
if auxWeight p c j = 0 then ((d : ℂ)⁻¹) • 1
else ∑ i, ((p i * c.prob i j / auxWeight p c j : ℝ) : ℂ) • rho i
/-- S(B|C), averaged over the classical auxiliary (PDF pp.6,10). -/
def auxiliaryBobEntropy {m k d : ℕ} (p : Fin m → ℝ)
(rho : Fin m → Matrix (Fin d) (Fin d) ℂ) (c : AuxChannel m k) : ℝ :=
∑ j, auxWeight p c j * vnEntropy (conditionalBob p rho c j)
/-- I(X;C) for the source's stochastic auxiliary channel (PDF p.6). -/
def labelAuxInfo {m k : ℕ} (p : Fin m → ℝ) (c : AuxChannel m k) : ℝ :=
classicalEntropy p - ∑ j, auxWeight p c j *
classicalEntropy (fun i => p i * c.prob i j / auxWeight p c j)
/-- I(X;BC) = I(X;C)+S(B|C)-S(B|X), evaluated from the specified cq state.
For pure Bob targets the last term vanishes; for entangled targets it must be retained (PDF pp.6,10). -/
def labelBobAuxInfo {m k d : ℕ} (p : Fin m → ℝ)
(rho : Fin m → Matrix (Fin d) (Fin d) ℂ) (c : AuxChannel m k) : ℝ :=
labelAuxInfo p c + auxiliaryBobEntropy p rho c - ∑ i, p i * vnEntropy (rho i)
/-- Single-letter optimisation with no unsupported m+1 cardinality restriction.
The empty feasible set has infimum infinity (PDF pp.6,10). -/
def rspSingleLetter {m d : ℕ} (p : Fin m → ℝ)
(rho : Fin m → Matrix (Fin d) (Fin d) ℂ) (R : ℝ) : ℝ≥0∞ :=
sInf {v | ∃ k : ℕ, ∃ c : AuxChannel m k,
labelBobAuxInfo p rho c ≤ R ∧ v = ENNReal.ofReal (auxiliaryBobEntropy p rho c)}
/-- Actual attainment whenever the single-letter feasible value is finite; this records
"min" rather than merely replacing it with an infimum (PDF pp.6,10). -/
def rspMinimumAttained {m d : ℕ} (p : Fin m → ℝ)
(rho : Fin m → Matrix (Fin d) (Fin d) ℂ) (R : ℝ) : Prop :=
rspSingleLetter p rho R ≠ ⊤ → ∃ k : ℕ, ∃ c : AuxChannel m k,
labelBobAuxInfo p rho c ≤ R ∧
ENNReal.ofReal (auxiliaryBobEntropy p rho c) = rspSingleLetter p rho R
/-- Pure bipartite ensemble: the full chosen purification is the target (PDF p.8). -/
structure BipartiteEnsemble (m a b : ℕ) where
prob : Fin m → ℝ
nonneg : ∀ i, 0 ≤ prob i
total : ∑ i, prob i = 1
state : Fin m → RSPVector (Fin a × Fin b)
/-- Receiver marginals of the fixed purifications (PDF pp.8–10). -/
def bobStates {m a b : ℕ} (E : BipartiteEnsemble m a b) (i : Fin m) :
Matrix (Fin b) (Fin b) ℂ := traceLeft (pureDensity (E.state i).val)
/-- General one-way entangled RSP: input-dependent Alice CP instrument, with only its SUM
trace preserving; Bob's decoder is arbitrary CPTP (PDF p.8). Padding permits a common finite
number L of Kraus operators per branch. -/
structure BipartiteCode (Input A B : Type*) [Fintype A] [Fintype B] [DecidableEq B] where
S : ℕ
Spos : 0 < S
K : ℕ
Kpos : 0 < K
L : ℕ
alice : Input → Fin K → Fin L → Matrix A (Fin S) ℂ
complete : ∀ i, ∑ j, ∑ l, (alice i j l)ᴴ * alice i j l = 1
bob : Fin K → Superop (Fin S) B
channel : ∀ j, IsChannel (bob j)
/-- Full joint output, sum_j (M_j^I tensor T_j)(Phi_S); no Alice output is discarded (PDF p.8). -/
def BipartiteCode.output {Input A B : Type*} [Fintype A] [Fintype B] [DecidableEq B]
(P : BipartiteCode Input A B) (i : Input) : Matrix (A × B) (A × B) ℂ :=
letI : Nonempty (Fin P.S) := ⟨⟨0, P.Spos⟩⟩
let s : Fin P.S := ⟨0, P.Spos⟩
-- The frozen tensor operation has square registers. Extract each rectangular output
-- coefficient through constant-entry square maps; its matrix-unit expansion is unchanged.
∑ j, fun u v =>
tensorSuperop
(fun X (_ _ : Fin P.S) => krausApply (P.alice i j) X u.1 v.1)
(fun X (_ _ : Fin P.S) => P.bob j X u.2 v.2)
(pureDensity (finiteMaxEntangled (Fin P.S))) (s, s) (s, s)
/-- Coefficient extraction through the imported square tensor operation retains every
matrix unit, including off-diagonal entries of entangled inputs (PDF p.8). -/
example {S A B : Type*} [Fintype S] [DecidableEq S]
(left : Superop S A) (right : Superop S B)
(X : Matrix (S × S) (S × S) ℂ) (s : S) (u v : A × B) :
tensorSuperop (fun Y (_ _ : S) => left Y u.1 v.1)
(fun Y (_ _ : S) => right Y u.2 v.2) X (s, s) (s, s) =
∑ x : S × S, ∑ y : S × S, X x y *
left (Matrix.single x.1 y.1 1) u.1 v.1 *
right (Matrix.single x.2 y.2 1) u.2 v.2 := by
rfl
/-- IID bipartite target, with Alice factors grouped together and Bob factors grouped together
(PDF p.8). -/
def bipWord {m a b : ℕ} (E : BipartiteEnsemble m a b) (n : ℕ) (w : Fin n → Fin m) :
EuclideanSpace ℂ ((Fin n → Fin a) × (Fin n → Fin b)) :=
WithLp.toLp 2 fun x => ∏ t, (E.state (w t)).val (x.1 t, x.2 t)
/-- Global average overlap with the chosen bipartite purification (PDF pp.8–9). -/
def bipAverage {m a b : ℕ} (E : BipartiteEnsemble m a b) (n : ℕ)
(P : BipartiteCode (Fin n → Fin m) (Fin n → Fin a) (Fin n → Fin b)) : ℝ :=
∑ w, wordProb E.prob n w * (pureDensity (bipWord E n w) * P.output w).trace.re
/-- One-way entangled achievable rates with the source's global criterion (PDF pp.8–9). -/
def BipartiteAchievable {m a b : ℕ} (E : BipartiteEnsemble m a b) (R ent : ℝ) : Prop :=
0 ≤ R ∧ 0 ≤ ent ∧ ∀ eps : ℝ, 0 < eps → ∀ delta : ℝ, 0 < delta →
∃ nzero : ℕ, 0 < nzero ∧ ∀ n ≥ nzero,
∃ P : BipartiteCode (Fin n → Fin m) (Fin n → Fin a) (Fin n → Fin b),
1 - eps ≤ bipAverage E n P ∧
Real.logb 2 P.K / n ≤ R + delta ∧ Real.logb 2 P.S / n ≤ ent + delta
/-- Entangled operational curve, infinity when no finite rate pair is achievable (PDF p.9). -/
def bipOperational {m a b : ℕ} (E : BipartiteEnsemble m a b) (R : ℝ) : ℝ≥0∞ :=
sInf {v | ∃ ent : ℝ, BipartiteAchievable E R ent ∧ v = ENNReal.ofReal ent}
/-- Entropy of the receiver's average state, not the average of the individual entropies (PDF p.9). -/
def bobAverageEntropy {m a b : ℕ} (E : BipartiteEnsemble m a b) : ℝ :=
vnEntropy (∑ i, (E.prob i : ℂ) • bobStates E i)
/-- Holevo information of the receiver marginal ensemble (PDF p.9). -/
def bobHolevo {m a b : ℕ} (E : BipartiteEnsemble m a b) : ℝ :=
bobAverageEntropy E - ∑ i, E.prob i * vnEntropy (bobStates E i)
/-- Complete receiver record after replacing Pi's failure message uniformly by a good label.
The failure flag stays private to Alice (PDF pp.12–13). -/
def piRecord {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ)
(eps : ℝ) (psi : RSPVector (Fin D)) : Matrix (Fin K × Fin D) (Fin K × Fin D) ℂ :=
fun x y => if x.1 = y.1 then
(((D : ℂ)⁻¹) • (piGood U eps psi x.1).transpose +
(((K : ℂ) * D)⁻¹) • (piEffect U eps psi none).transpose) x.2 y.2
else 0
/-- Linear CPTP simulator with one ACTUAL receiver output specimen as input.
Conjugating U, rather than the unknown specimen, makes this a linear channel (PDF p.13). -/
def piSimulator {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ) :
Superop (Fin D) (Fin K × Fin D) :=
fun rho x y => if x.1 = y.1 then
(((K : ℂ)⁻¹) • (bar (U x.1 : Matrix (Fin D) (Fin D) ℂ) * rho *
(U x.1 : Matrix (Fin D) (Fin D) ℂ).transpose)) x.2 y.2 else 0
/-- Actual averaged output decoded from the uniformly replaced failure record (PDF p.13). -/
def piApproxOutput {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ)
(eps : ℝ) (psi : RSPVector (Fin D)) : Matrix (Fin D) (Fin D) ℂ :=
∑ k, (U k : Matrix (Fin D) (Fin D) ℂ).transpose *
(Matrix.of fun a b => piRecord U eps psi (k, a) (k, b)) *
((U k : Matrix (Fin D) (Fin D) ℂ).transpose)ᴴ
/-- Bob's global average mixed-state squared fidelity after discarding Alice's output (PDF p.13). -/
def marginalAverageFidelity {m a b : ℕ} (E : BipartiteEnsemble m a b) (n : ℕ)
(P : BipartiteCode (Fin n → Fin m) (Fin n → Fin a) (Fin n → Fin b)) : ℝ :=
∑ w, wordProb E.prob n w * fidelity (traceLeft (pureDensity (bipWord E n w)))
(traceLeft (P.output w))
/-- Independent centered real and imaginary coordinates of a symmetric complex Gaussian.
Each real coordinate has variance s2/(2D), so the total expected norm square is s2.
Definition 22's printed mu_j is read as zero by its immediately preceding prose (PDF p.14). -/
def SymmetricGaussian {Omega : Type*} [MeasurableSpace Omega] (mu : Measure Omega)
(D : ℕ) (s2 : ℝ≥0) (G : Omega → EuclideanSpace ℂ (Fin D)) : Prop :=
Measurable G ∧
let coord : (Fin D × Bool) → Omega → ℝ := fun j w =>
if j.2 then (G w j.1).im else (G w j.1).re
iIndepFun coord mu ∧
∀ j, Measure.map (coord j) mu = gaussianReal 0 (s2 / (2 * D))
/-- Logarithm of a nonnegative exponential moment, including divergence and zero.
It never turns a divergent Bochner integral into zero (PDF p.14). -/
def momentLog (z : ℝ≥0∞) : EReal :=
if z = ⊤ then ⊤ else if z = 0 then ⊥ else (Real.log z.toReal : EReal)
/-- Cramer transform of a squared real centered Gaussian, defined from the moment integral
and supremum, not from the asserted closed form (PDF p.14). -/
def squaredGaussianRate (s2 : ℝ≥0) (x : ℝ) : EReal :=
⨆ y : ℝ, ((y * x : ℝ) : EReal) - momentLog
(∫⁻ t : ℝ, ENNReal.ofReal (Real.exp (y * t ^ 2)) ∂gaussianReal 0 s2)
/-- Sanity: a divergent moment has infinite logarithm. -/
example : momentLog ⊤ = ⊤ := by simp [momentLog]
/-- Sanity: the unit moment has zero logarithm. -/
example : momentLog 1 = 0 := by simp [momentLog]
/-- Extended endpoint of A3: ln(0) is minus infinity, not Lean's Real.log 0 = 0 (PDF p.14). -/
def elementaryRate (xi : ℝ) : EReal :=
if xi = -1 then ⊤ else (((xi - Real.log (1 + xi)) / (2 * Real.log 2) : ℝ) : EReal)
/-- Sanity: the left endpoint is infinite. -/
example : elementaryRate (-1) = ⊤ := by simp [elementaryRate]
/-- Universal visible quantum-classical compression with a pure quantum codeword and a fixed
CPTP decoder per classical message (PDF pp.15–16). All code sizes are fixed support sizes. -/
structure VisibleCode (D : ℕ) where
S : ℕ
Spos : 0 < S
K : ℕ
Kpos : 0 < K
quantum : RSPVector (Fin D) → RSPVector (Fin S)
message : RSPVector (Fin D) → Fin K
decoder : Fin K → Superop (Fin S) (Fin D)
channel : ∀ j, IsChannel (decoder j)
/-- Decoding the jointly visible quantum and classical description (PDF p.15). -/
def VisibleCode.output {D : ℕ} (P : VisibleCode D) (psi : RSPVector (Fin D)) :
Matrix (Fin D) (Fin D) ℂ := P.decoder (P.message psi) (pureDensity (P.quantum psi).val)
/-- Sanity: tensor-product word probability on the empty word is one. -/
example {m : ℕ} (p : Fin m → ℝ) (w : Fin 0 → Fin m) : wordProb p 0 w = 1 := by
simp [wordProb]
/-- Sanity: the auxiliary register's impossible outcome contributes zero conditional entropy. -/
example {m k d : ℕ} (p : Fin m → ℝ) (rho : Fin m → Matrix (Fin d) (Fin d) ℂ)
(c : AuxChannel m k) (j : Fin k) (h : auxWeight p c j = 0) :
auxWeight p c j * vnEntropy (conditionalBob p rho c j) = 0 := by rw [h, zero_mul]
/-- Sanity: entrywise conjugation is an involution, including on non-real targets. -/
example {O : Type*} (M : Matrix O O ℂ) : bar (bar M) = M := by
ext a b
simp [bar]
/-- Sanity: the invalid empty randomising family is zero; the theorem excludes K = 0. -/
example {D : ℕ} (U : Fin 0 → Matrix.unitaryGroup (Fin D) ℂ)
(rho : Matrix (Fin D) (Fin D) ℂ) : randomise U rho = 0 := by
simp [randomise]
/-- Sanity: the record simulator is linear at zero, rather than conjugating its unknown input. -/
example {D K : ℕ} (U : Fin K → Matrix.unitaryGroup (Fin D) ℂ) : piSimulator U 0 = 0 := by
ext x y
simp [piSimulator]
/-- Sanity: the empty product target is the unit scalar. -/
example {d : ℕ} (E : PureEnsemble (Fin d)) (w : Fin 0 → Fin E.count) (x : Fin 0 → Fin d) :
pureWordVector E 0 w x = 1 := by simp [pureWordVector]
/-- Sanity: the rate estimate at the mean is zero. -/
example : elementaryRate 0 = 0 := by simp [elementaryRate]
end QAlgorithms.Papers.Independent.Intakenext100.P54
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Intakenext100.P54.AuxChannel
For arbitrary natural numbers , an element of this structure is an array of real numbers , indexed by and , together with the requirements
There is no explicit positivity assumption on or . If , all requirements are vacuous, including when ; if and , the row-sum requirement would be , so no such array exists.
QAlgorithms.Papers.Independent.Intakenext100.P54.BipartiteAchievable
For natural numbers , let consist of probabilities with and unit vectors , and let . The predicate asserts , , and the following: for every and , there is a positive integer such that for every natural number there is a code with positive integers , a natural number , matrices satisfying for each length- word over labels, and maps with finitely many Kraus matrices satisfying , such that
Here and
The code may depend on . No upper bound on or is imposed, and only positive block lengths are required. Zero label or local dimensions cannot satisfy the ensemble requirements.
QAlgorithms.Papers.Independent.Intakenext100.P54.BipartiteCode
For an arbitrary input type , finite types , and a specified decidable equality on , this structure consists of positive natural numbers , an arbitrary natural number , complex matrices with rows indexed by and columns indexed by , for every , , and , satisfying
and maps from complex matrices to complex matrices indexed by . For every , the map must admit a finite Kraus representation: there exist a natural number and matrices with rows indexed by and columns such that
No finiteness or nonemptiness is assumed for , and nonemptiness of or is not an explicit assumption. The stated conditions force to be nonempty; if is nonempty, they also force to be nonempty and . When is empty, the conditions indexed by are vacuous.
QAlgorithms.Papers.Independent.Intakenext100.P54.BipartiteCode.output
For an arbitrary input type , finite types with decidable equality on , a code , and , write and for the code’s parameters, for its matrices from to , and for its maps from matrices to matrices on . These satisfy for every input , and each has a finite Kraus representation with . The definition returns the matrix on whose entries, after expanding the tensor operation, Kraus application, and maximally entangled vector, are
where is the matrix with a single in position . The maximally entangled vector used in the definition has amplitude at and zero elsewhere; the evaluation of the constant-entry square maps at the distinguished index gives the displayed coefficients. There is no distribution on inputs and no averaging over . The selected input and the code’s conditions force to be nonempty and .
QAlgorithms.Papers.Independent.Intakenext100.P54.BipartiteEnsemble
For natural numbers , this structure consists of real numbers indexed by , proofs that every and , and, for each , a vector satisfying . Zero probabilities are permitted, and the unit-vector requirement applies even at indices of zero probability. Although the parameters are arbitrary natural numbers, such a structure cannot exist when , or when either or .
QAlgorithms.Papers.Independent.Intakenext100.P54.RSPCode.ExactWithError
Let be a finite type with decidable equality, let , and let be a code whose inputs are all vectors with Euclidean norm . Thus has positive integers , positive semidefinite matrices summing to for each unit vector , and decoder maps with finite Kraus families satisfying . Write . The defined property holds exactly when there exists a single subset , chosen independently of , such that for every unit vector ,
The matrix has entries . There is no imposed range restriction on , and may be empty; in particular, every such code satisfies this property with when .
QAlgorithms.Papers.Independent.Intakenext100.P54.RSPCode.branch
For any input type , finite output type with decidable equality, and code with positive dimensions , input-dependent positive semidefinite matrices summing to , and decoder maps admitting finite representations with , the branch matrix for an input and an index is defined by
Here denotes ordinary transpose, without complex conjugation; the result is an complex matrix and is not divided by its trace.
QAlgorithms.Papers.Independent.Intakenext100.P54.RSPCode
For an arbitrary input type and a finite output type with decidable equality, an element of this structure consists of positive integers , matrices for every and , and functions . For each input , every is positive semidefinite and . For each , the function has a finite Kraus representation: there are a natural number and matrices such that and for every matrix . No finiteness or nonemptiness assumption is imposed on ; its requirements are vacuous when is empty. Although is not explicitly assumed nonempty, an empty cannot satisfy the decoder requirements because .
QAlgorithms.Papers.Independent.Intakenext100.P54.RSPCode.output
For any input type , finite output type with decidable equality, and code consisting of positive integers , positive semidefinite matrices satisfying for each , and decoder maps with finite Kraus families satisfying , the output matrix at is defined to be
where is ordinary transpose.
QAlgorithms.Papers.Independent.Intakenext100.P54.RSPPureAchievable
For a natural number , an ensemble of unit vectors with nonnegative weights summing to , and real numbers , this property means that , , and for every real and , there exists a natural number such that for every natural number there is a code with positive integers , input words , positive semidefinite effects summing to , and decoders into matrices indexed by having finite Kraus representations , , for which
where . The same code must satisfy both rate inequalities and the overlap inequality, but may depend on ; no uniform construction is required. The quantified block lengths are positive, so these divisions never use .
QAlgorithms.Papers.Independent.Intakenext100.P54.RSPVector
For any finite type , this denotes the set of complex vectors with Euclidean norm , equivalently . If is empty, this set is empty.
QAlgorithms.Papers.Independent.Intakenext100.P54.Randomising
For any natural numbers , any family of unitary complex matrices, and any real , this predicate means that every positive semidefinite complex matrix with satisfies
where means that is positive semidefinite. The predicate itself imposes no positivity assumptions on . Division by zero is interpreted as zero. For , there is no trace-one matrix, so the universal condition is vacuous; for , the middle matrix is zero.
QAlgorithms.Papers.Independent.Intakenext100.P54.SymmetricGaussian
For an arbitrary measurable space , a measure on it, a natural number , a nonnegative real number , and a function with its Euclidean structure, this predicate means that is measurable and its real coordinate functions
are jointly independent with respect to , with each pushforward measure equal to the real Gaussian measure of mean and variance . The definition does not assume that is a probability measure and permits , giving zero-variance Gaussian coordinate laws. It also permits , when there are no coordinate functions and the independence and coordinate-law conditions are vacuous.
QAlgorithms.Papers.Independent.Intakenext100.P54.VisibleCode
For a natural number , a value of this structure consists of positive natural numbers , a function assigning to every unit vector a unit vector , a function assigning to every such a message , and a family of maps from complex matrices to complex matrices. Each must admit a finite Kraus representation
No measurability, continuity, or accuracy condition is imposed on the two functions of . The parameter is not explicitly required to be positive; when , its unit-vector input set is empty, but the required channels from positive dimension to dimension zero cannot exist.
QAlgorithms.Papers.Independent.Intakenext100.P54.VisibleCode.output
For a natural number , let consist of positive integers , functions and assigning each unit vector of respectively a unit vector of and a message in , and maps admitting finite Kraus representations with . For every unit input vector , this definition returns the complex matrix
where the input matrix to the selected map has entries .
QAlgorithms.Papers.Independent.Intakenext100.P54.auxWeight
For any natural numbers , any real-valued function , any array satisfying for every , and any index , the defined real number is
No nonnegativity or normalization requirement is imposed on . If , the sum equals ; if , there is no index to which this definition can be applied.
QAlgorithms.Papers.Independent.Intakenext100.P54.auxiliaryBobEntropy
For arbitrary natural numbers , a real vector , complex matrices , and a real array with for every , set , and let if , and otherwise. Writing
where is evaluated by continuous functional calculus, the definition returns
Neither normalization or nonnegativity of , nor positivity or trace normalization of , is required. A zero contributes zero. Empty sums are zero, is permitted, and all inverses use the convention ; if , the assumptions on exclude .
QAlgorithms.Papers.Independent.Intakenext100.P54.bar
For any type and any complex matrix with rows and columns indexed by , this defines its entrywise complex conjugate:
There is no finiteness assumption on .
QAlgorithms.Papers.Independent.Intakenext100.P54.bipAverage
Let be natural numbers. An ensemble consists of nonnegative weights summing to and unit vectors , indexed by . For a word , put and . The code consists of positive integers , a natural number , matrices satisfying for every , and maps from matrices to matrices on , each admitting a finite Kraus representation with . Its output has entries
The definition is the real number
Here has entries . The definition includes : there is one empty word, its weight and vector amplitude are both , and the output registers are one dimensional. Although are not explicitly required to be positive, the ensemble’s weight and normalization requirements exclude their being zero.
QAlgorithms.Papers.Independent.Intakenext100.P54.bipOperational
For natural numbers , an ensemble consists of probabilities summing to and unit vectors , indexed by . For any real , this definition takes the infimum in of over real numbers satisfying the following condition: , and for every , all sufficiently large positive integers admit positive integers , a natural number , matrices with for every word , and maps with finite Kraus families satisfying , for which
Here and
Because eligible are nonnegative, their conversion to simply preserves their value. An empty feasible set has infimum ; in particular, the value is when . The infimum’s definition does not itself assert attainment.
QAlgorithms.Papers.Independent.Intakenext100.P54.bipWord
For arbitrary natural numbers , an ensemble consisting of real probabilities with and unit vectors , any natural number , and any word , the definition returns the vector on pairs of words , with amplitudes
The probabilities do not appear in these amplitudes, and may use indices of zero probability. When , both word registers have one empty word and the empty product gives amplitude . The existence of forces .
QAlgorithms.Papers.Independent.Intakenext100.P54.bobAverageEntropy
For natural numbers , let consist of probabilities summing to and unit vectors , indexed by . Define the matrices
Then , where
and is evaluated by continuous functional calculus. In particular, the scalar expression at is . The ensemble requirements exclude , , or .
QAlgorithms.Papers.Independent.Intakenext100.P54.bobHolevo
For natural numbers , let consist of probabilities summing to and unit vectors , indexed by . With
where the matrix function uses continuous functional calculus and , the definition is
Zero probabilities are allowed. Zero label or local dimensions cannot satisfy the ensemble requirements.
QAlgorithms.Papers.Independent.Intakenext100.P54.bobStates
For arbitrary natural numbers , an ensemble consisting of with and unit vectors , and an index , the definition returns the complex matrix
Thus it takes the matrix and sums its entries over equal first-register indices. The probabilities do not enter this formula, and the selected index need not have positive probability. The existence of forces .
QAlgorithms.Papers.Independent.Intakenext100.P54.conditionalBob
For arbitrary natural numbers , arbitrary real numbers , arbitrary complex matrices , and a real array satisfying and for every , define . For each , the definition returns
Real coefficients are regarded as complex scalars. There is no assumption that is a probability distribution or that the are density matrices; in particular, a nonzero may be negative. Zero dimensions are allowed, with ; when , the row normalization of makes impossible. When , every is zero and the first branch applies.
QAlgorithms.Papers.Independent.Intakenext100.P54.elementaryRate
For every real number , this definition returns the extended real value
There is no domain restriction on : for , the logarithm is the total real logarithm, which equals at the negative argument .
QAlgorithms.Papers.Independent.Intakenext100.P54.labelAuxInfo
For arbitrary natural numbers , arbitrary , and a real array whose rows satisfy , put . Define , using continuous functional calculus with , and define for a real vector . The definition returns
There is no probability-distribution assumption on . Division by zero is zero, so when , the vector inside that term is the zero vector and the term contributes zero. Empty index sets are allowed; row normalization excludes when .
QAlgorithms.Papers.Independent.Intakenext100.P54.labelBobAuxInfo
For arbitrary natural numbers , real , complex matrices , and satisfying for every , set and . Let when , and otherwise. With defined through continuous functional calculus for , and , the definition returns
No distribution assumption on or density-matrix assumption on is imposed. Zero dimensions and empty sums are included; division by zero is zero, and terms multiplied by vanish. The row conditions on cannot hold with and .
QAlgorithms.Papers.Independent.Intakenext100.P54.marginalAverageFidelity
For natural numbers , let consist of probabilities with and unit vectors . For any natural number , write and for each word . Let be a code consisting of positive integers , a natural number , matrices satisfying for every , and channels from -dimensional matrices to matrices on . Here a channel means a map admitting a finite representation with . Define its output by
The declared quantity is
where sums over the first tensor factor and the matrix square roots use the continuous functional calculus. The definition includes , when there is one empty word, its weight is , and its tensor vector has its sole coordinate equal to . Although are not explicitly required to be positive, the conditions on cannot be satisfied if any of them is zero.
QAlgorithms.Papers.Independent.Intakenext100.P54.momentLog
For any extended nonnegative real number , this definition returns the extended real value
where the last case uses the ordinary finite real value of and the natural logarithm.
QAlgorithms.Papers.Independent.Intakenext100.P54.piApproxOutput
For natural numbers , any family of unitary matrices , any real , and any unit vector , put
The definition is the matrix
Overlines mean entrywise complex conjugation, means ordinary transpose, and means conjugate transpose. No restriction on or randomising assumption is imposed, and no positivity or normalization is asserted here. Inverses of zero are zero, so the expression remains defined at and ; at the sum is the zero matrix. A unit vector cannot exist when .
QAlgorithms.Papers.Independent.Intakenext100.P54.piBranch
For any natural numbers , any family of unitary complex matrices , any real , and any unit vector , put
This defines matrices indexed by the labels and as
Here is transpose, is conjugate transpose, the overline is entrywise conjugation, and . No randomising or positivity assumption is imposed. All scalar inverses are total, with ; if , there are no indexed branches and . The unit-vector argument excludes .
QAlgorithms.Papers.Independent.Intakenext100.P54.piEffect
For any natural numbers , any family of unitary complex matrices , any real , and any unit vector , this defines a matrix for each label in by
Here denotes conjugate transpose, the overline denotes entrywise conjugation, and . This definition assumes neither positivity of these matrices nor a randomising property. Division by zero is zero; if , the only label is and its matrix is . A unit vector is unavailable when .
QAlgorithms.Papers.Independent.Intakenext100.P54.piGood
For any natural numbers , any unitary complex matrices , any real , any unit vector , and any index , this defines
where the scalar division takes place in , , and the overline means entrywise complex conjugation. No restriction on or randomising property of the family is assumed. If , the scalar is zero by the convention for division by zero. The required index cannot exist when , and the required unit vector cannot exist when .
QAlgorithms.Papers.Independent.Intakenext100.P54.piRecord
For natural numbers , any family of unitary matrices , any real , and any vector with , write , let an overline mean entrywise complex conjugation, and define
The definition is the matrix on given by
The transpose is ordinary transpose. No bound on , randomising condition, or positivity of is assumed. All divisions are total, with inverse zero equal to zero, including when or ; for the resulting matrix has an empty index set. When , no unit vector exists.
QAlgorithms.Papers.Independent.Intakenext100.P54.piSimulator
For natural numbers and any family of unitary matrices , this definition gives a function from arbitrary complex matrices to matrices indexed by with and :
Here is entrywise complex conjugation and is ordinary transpose. The input need not be a density matrix. Neither nor is required to be positive; when the output index set is empty, and the scalar inverse convention is . This definition alone makes no channel assertion.
QAlgorithms.Papers.Independent.Intakenext100.P54.pureAverageOverlap
For any natural numbers , let consist of unit vectors and nonnegative weights summing to . Let be a code with positive integers , input words , and output space indexed by ; for each , its effects are positive semidefinite and sum to , and each decoder has a finite representation with . Define and . The defined real number is
When , both word sets are singletons, all displayed products are empty products equal to , and the expression is the real trace of the output matrix for the empty input word.
QAlgorithms.Papers.Independent.Intakenext100.P54.pureOperational
For any natural number , an ensemble of unit vectors with nonnegative weights summing to , and any real number , this definition takes the infimum in of all nonnegative real numbers with the following property: , and for every real and , there is a natural number such that every natural number admits positive integers , positive semidefinite effects summing to for each word , and decoder maps into matrices indexed by of the form for finite families satisfying , such that, with and ,
Each admissible is embedded into the extended nonnegative reals before taking the infimum. If no such exists, the result is ; in particular this happens when . The definition does not assert that the infimum is attained.
QAlgorithms.Papers.Independent.Intakenext100.P54.pureWordVector
For any natural number , let be a finite ensemble consisting of a natural number , weights with , and vectors with . For any natural number and word , the defined vector belongs to and has coordinate
The weights do not enter this formula. When , there is one empty coordinate word and the empty product gives its amplitude as . Although are natural numbers without explicit positivity hypotheses, the ensemble requirements cannot be satisfied if either is zero.
QAlgorithms.Papers.Independent.Intakenext100.P54.randomise
For any natural numbers , any family of unitary complex matrices , and any complex matrix , this defines
where denotes conjugate transpose and the scalar is interpreted in . No positivity or normalization of is required. The definition includes , when the empty sum and the inverse of zero are both zero, so the result is the zero matrix; it also includes .
QAlgorithms.Papers.Independent.Intakenext100.P54.randomisingBound
For any natural number and any real , this defines the real number
There are no restrictions on these arguments. The real division and logarithm are total functions, with division by zero and interpreted as zero; in particular, the defined value is zero if or .
QAlgorithms.Papers.Independent.Intakenext100.P54.rspMinimumAttained
For arbitrary natural numbers , real , complex matrices , and real , define by continuous functional calculus for , and . For each natural and real array with , set , , and if , otherwise . Put
and let be the infimum in of over these arrays satisfying . The defined proposition says: if , then there exist such a finite and array with and . It imposes no requirement when , including when the feasible set is empty. There are no distribution or density-matrix hypotheses; zero dimensions are allowed and division by zero is zero.
QAlgorithms.Papers.Independent.Intakenext100.P54.rspSingleLetter
For arbitrary natural numbers , real , complex matrices , and , consider every natural number and every real array satisfying for every . For each such array, set , , and if , otherwise . Define by continuous functional calculus for , and . Put
The definition is the infimum, in , of
The infimum of an empty feasible set is . No normalization or positivity conditions are imposed on or , and may be negative. Zero dimensions and are included wherever the row conditions permit them, and division by zero is zero.
QAlgorithms.Papers.Independent.Intakenext100.P54.squaredGaussianRate
For every nonnegative real variance parameter and every real number , this definition is the extended real supremum
where is the real Gaussian measure of mean and variance , the integral is the extended nonnegative integral, and equals at , at , and at finite positive . The exponential integrand is converted to an extended nonnegative real before integration. The supremum includes every real , including those for which the integral is infinite; and arbitrary, possibly nonpositive, are allowed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.