Definitions for On the communication cost of entanglement transformations
DefinitionQAlgorithms_Papers_Independent_Intakenext100_P61The objects the formalized statements of On the communication cost of entanglement transformations (arXiv:quant-ph/0204092) are stated in. Each was checked against the paper by a blind read-back and a moderator.
finiteMin: PDF p.3: finite minimum; the empty-set default is unused on valid smoothing inputs.finiteMax: PDF pp.2--3: finite maximum; empty support has value zero.spectralSupport: PDF p.2: support of the positive spectrum, counted with multiplicity.largestWeight: PDF p.2: largest eigenvalue of a positive matrix.entropyZero: PDF p.2: S_0, also for subnormalized positive matrices.entropyOne: PDF p.2: von Neumann entropy in bits; zero weights contribute zero.spread: PDF p.2, (1): spectral spread; no trace renormalization.Flat: PDF p.2: flatness only on positive support, including rank one.spectralRetentions: PDF p.3, (6)--(8): retained spectral subsets with mass at least 1-epsilon. Zero eigenvalues may be removed without changing any of these minima.smoothZero: PDF p.3, (6): smoothed support entropy.smoothInfinity: PDF p.3, (7): smoothed largest-weight entropy.smoothSpread: PDF p.3, (8): joint minimum, rather than a difference of separate minima.RenyiOrder: PDF pp.2,5: nonnegative Renyi orders with a separate infinity endpoint.spectralRenyi: PDF p.2: entropy of a retained positive spectrum. Orders 0,1,infinity are handled separately; zero weights are excluded before exponentiation. The order-one branch is used only on the full normalized spectrum; no continuous order-one extension is claimed for a retained subnormalized spectrum.upperRenyiFactor: PDF p.5, Remark 12: beta/(beta-1) has limiting value one at infinity.eigenvalueRenyiEntropy: PDF p.2: Renyi entropy with the source's endpoint conventions.renyiGap: PDF p.3, Remark 2: Renyi gap.smoothRenyiGap: PDF p.5, Remark 12: joint smoothing of the Renyi gap.BipartiteMatrix: PDF p.2: concrete finite bipartite matrices.aliceApply: PDF p.2: Alice's Kraus operation tensored with Bob's identity, retaining off-diagonal blocks.bobApply: PDF p.2: Bob's local Kraus operation tensored with Alice's identity.transferAB: PDF p.2: an m-dimensional subsystem moves from Alice to Bob by reassociation.transferBA: PDF p.2: an m-dimensional subsystem moves from Bob to Alice.QuantumExecution: PDF p.2 and Fig.1: finite deterministic executions. Local CPTP operations include arbitrary pure ancillary preparation and disposal. Transfers have positive integer dimensions and their costs are summed. No postselection or unconstrained joint-channel constructor is present.ClassicalExecution: PDF p.5, Corollary 10: finite adaptive LOCC trees. Each communicated instrument outcome is available to both parties. Branch states are unnormalized and all final branches are summed. C bounds worst-case total log-alphabet cost; this includes every fixed-length binary-message protocol in the source.pack: PDF pp.1--2: separate local basis identifications with finite index sets.Quantum: PDF p.2: operational quantum communication relation.Classical: PDF p.5: operational classical communication relation.aliceDensity: PDF pp.1--2: Alice's reduced density; the second tensor factor is traced out.QuantumPrepares: PDF p.5: fidelity is tested on the unconditional, possibly mixed, output.ClassicalPrepares: PDF p.5: classical-only preparation, summing every branch.tensorPureStates: PDF p.5: bipartite tensor with all Alice factors before all Bob factors.pureStateCopies: PDF pp.6--7: n copies with bipartite ownership spectralRetentions; the empty product is one.bellRank: PDF pp.1--2: normalized maximally entangled rank-r state when r>0.eprPairs: PDF p.5: k EPR pairs, including k=0.smoothingError: PDF p.5: the eighth root of 4 epsilon.binaryState: PDF p.3: binary Schmidt-diagonal state, with complex amplitudes.harmonicSum: PDF p.7: the ordinary harmonic sum, with indices starting at one.harmonicState: PDF p.7: normalized harmonic embezzling vector for n>0. At n=0 its Hilbert space is empty, and no normalized-state assertion is used.harmonicTailCuts: PDF p.8, (21): feasible integer tail cutoffs, restricted to 1<=k<=n.harmonicHeadCuts: PDF p.8, (22): feasible integer head cutoffs; the upper limit is k-1, inclusive.applyLocalMaps: PDF p.6, (20): action of separate local linear maps on a bipartite vector. Isometricity is required explicitly in the residual-family theorem.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_QuantumInformation
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P63
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P35
import Definitions.Def_QAlgorithms_Papers_Independent_Bridge50_P40
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P53
/-! Hayden--Winter, quant-ph/0204092v3. Page citations are PDF pages.
Exact matching primitives are imported from the pinned accepted library.
All new definitions are local to this paper. Subnormalized spectral truncations
are never renormalized. Protocol costs count physical message dimensions. -/
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakenext100.P61
open scoped Matrix ComplexConjugate
open QAlgorithms.Papers.Independent.Information100.P63 (logTwo)
open QAlgorithms.Papers.Independent.Dependency50.P35 (supportRank)
open QAlgorithms.Papers.Independent.Bridge50.P40 (entropyInfinity)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
attribute [local instance] Classical.propDecidable
/-- PDF p.3: finite minimum; the empty-set default is unused on valid smoothing inputs. -/
def finiteMin {I : Type*} [DecidableEq I] (s : Finset I) (f : I → ℝ) : ℝ :=
if h : s.Nonempty then s.inf' h f else 0
/-- PDF pp.2--3: finite maximum; empty support has value zero. -/
def finiteMax {I : Type*} [DecidableEq I] (s : Finset I) (f : I → ℝ) : ℝ :=
if h : s.Nonempty then s.sup' h f else 0
section Spectral
variable {I J : Type} [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J]
/-- PDF p.2: support of the positive spectrum, counted with multiplicity. -/
def spectralSupport (rho : Matrix I I ℂ) : Finset (Fin (Fintype.card I)) :=
Finset.univ.filter fun i => 0 < ascEigenvalues rho i
/-- PDF p.2: largest eigenvalue of a positive matrix. -/
def largestWeight (rho : Matrix I I ℂ) : ℝ :=
finiteMax (spectralSupport rho) (ascEigenvalues rho)
/-- PDF p.2: S_0, also for subnormalized positive matrices. -/
def entropyZero (rho : Matrix I I ℂ) : ℝ := logTwo (supportRank rho)
/-- PDF p.2: von Neumann entropy in bits; zero weights contribute zero. -/
def entropyOne (rho : Matrix I I ℂ) : ℝ :=
-∑ i, ascEigenvalues rho i * logTwo (ascEigenvalues rho i)
/-- PDF p.2, (1): spectral spread; no trace renormalization. -/
def spread (rho : Matrix I I ℂ) : ℝ := entropyZero rho - entropyInfinity rho
/-- PDF p.2: flatness only on positive support, including rank one. -/
def Flat (rho : Matrix I I ℂ) : Prop :=
∀ i ∈ spectralSupport rho, ∀ j ∈ spectralSupport rho,
ascEigenvalues rho i = ascEigenvalues rho j
/-- PDF p.3, (6)--(8): retained spectral subsets with mass at least 1-epsilon.
Zero eigenvalues may be removed without changing any of these minima. -/
def spectralRetentions (rho : Matrix I I ℂ) (epsilon : ℝ) : Finset (Finset (Fin (Fintype.card I))) :=
(spectralSupport rho).powerset.filter fun s => 1 - epsilon ≤ ∑ i ∈ s, ascEigenvalues rho i
/-- PDF p.3, (6): smoothed support entropy. -/
def smoothZero (rho : Matrix I I ℂ) (epsilon : ℝ) : ℝ :=
logTwo (finiteMin (spectralRetentions rho epsilon) fun s => (s.card : ℝ))
/-- PDF p.3, (7): smoothed largest-weight entropy. -/
def smoothInfinity (rho : Matrix I I ℂ) (epsilon : ℝ) : ℝ :=
-logTwo (finiteMin (spectralRetentions rho epsilon) fun s => finiteMax s (ascEigenvalues rho))
/-- PDF p.3, (8): joint minimum, rather than a difference of separate minima. -/
def smoothSpread (rho : Matrix I I ℂ) (epsilon : ℝ) : ℝ :=
logTwo (finiteMin (spectralRetentions rho epsilon) fun s =>
(s.card : ℝ) * finiteMax s (ascEigenvalues rho))
end Spectral
/-- PDF pp.2,5: nonnegative Renyi orders with a separate infinity endpoint. -/
abbrev RenyiOrder := WithTop NNReal
/-- PDF p.2: entropy of a retained positive spectrum. Orders 0,1,infinity are
handled separately; zero weights are excluded before exponentiation. The order-one
branch is used only on the full normalized spectrum; no continuous order-one
extension is claimed for a retained subnormalized spectrum. -/
def spectralRenyi {n : ℕ} (r : Fin n → ℝ) (s : Finset (Fin n)) (alpha : RenyiOrder) : ℝ :=
if alpha = ⊤ then -logTwo (finiteMax s r)
else let a : ℝ := (alpha.untopD 0 : NNReal)
if a = 0 then logTwo s.card
else if a = 1 then -∑ i ∈ s, r i * logTwo (r i)
else logTwo (∑ i ∈ s, (r i) ^ a) / (1 - a)
/-- PDF p.5, Remark 12: beta/(beta-1) has limiting value one at infinity. -/
def upperRenyiFactor (beta : RenyiOrder) : ℝ :=
if beta = ⊤ then 1 else
let b : ℝ := (beta.untopD 0 : NNReal)
b / (b - 1)
section SpectralResults
variable {I J : Type} [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J]
/-- PDF p.2: Renyi entropy with the source's endpoint conventions. -/
def eigenvalueRenyiEntropy (rho : Matrix I I ℂ) (alpha : RenyiOrder) : ℝ :=
spectralRenyi (ascEigenvalues rho) (spectralSupport rho) alpha
/-- PDF p.3, Remark 2: Renyi gap. -/
def renyiGap (rho : Matrix I I ℂ) (alpha beta : RenyiOrder) : ℝ :=
eigenvalueRenyiEntropy rho alpha - eigenvalueRenyiEntropy rho beta
/-- PDF p.5, Remark 12: joint smoothing of the Renyi gap. -/
def smoothRenyiGap (rho : Matrix I I ℂ) (alpha beta : RenyiOrder) (epsilon : ℝ) : ℝ :=
finiteMin (spectralRetentions rho epsilon) fun s =>
spectralRenyi (ascEigenvalues rho) s alpha - spectralRenyi (ascEigenvalues rho) s beta
end SpectralResults
/-- PDF p.2: concrete finite bipartite matrices. -/
abbrev BipartiteMatrix (a b : ℕ) := Matrix (Fin a × Fin b) (Fin a × Fin b) ℂ
/-- PDF p.2: Alice's Kraus operation tensored with Bob's identity, retaining off-diagonal blocks. -/
def aliceApply {a b c k : ℕ} (K : Fin k → Matrix (Fin c) (Fin a) ℂ)
(rho : BipartiteMatrix a b) : BipartiteMatrix c b :=
krausApply (fun j => Matrix.kronecker (K j) (1 : Matrix (Fin b) (Fin b) ℂ)) rho
/-- PDF p.2: Bob's local Kraus operation tensored with Alice's identity. -/
def bobApply {a b d k : ℕ} (K : Fin k → Matrix (Fin d) (Fin b) ℂ)
(rho : BipartiteMatrix a b) : BipartiteMatrix a d :=
krausApply (fun j => Matrix.kronecker (1 : Matrix (Fin a) (Fin a) ℂ) (K j)) rho
/-- PDF p.2: an m-dimensional subsystem moves from Alice to Bob by reassociation. -/
def transferAB {a b m : ℕ} (rho : BipartiteMatrix (a * m) b) : BipartiteMatrix a (m * b) :=
fun p q => rho
(finProdFinEquiv (p.1, (finProdFinEquiv.symm p.2).1), (finProdFinEquiv.symm p.2).2)
(finProdFinEquiv (q.1, (finProdFinEquiv.symm q.2).1), (finProdFinEquiv.symm q.2).2)
/-- PDF p.2: an m-dimensional subsystem moves from Bob to Alice. -/
def transferBA {a b m : ℕ} (rho : BipartiteMatrix a (m * b)) : BipartiteMatrix (a * m) b :=
fun p q => rho
((finProdFinEquiv.symm p.1).1, finProdFinEquiv ((finProdFinEquiv.symm p.1).2, p.2))
((finProdFinEquiv.symm q.1).1, finProdFinEquiv ((finProdFinEquiv.symm q.1).2, q.2))
/-- PDF p.2 and Fig.1: finite deterministic executions. Local CPTP operations
include arbitrary pure ancillary preparation and disposal. Transfers have positive
integer dimensions and their costs are summed. No postselection or unconstrained
joint-channel constructor is present. -/
inductive QuantumExecution : {a b c d : ℕ} → BipartiteMatrix a b → BipartiteMatrix c d → ℝ → Prop
| identity {a b} (rho : BipartiteMatrix a b) : QuantumExecution rho rho 0
| alice {a b c k} (rho : BipartiteMatrix a b) (K : Fin k → Matrix (Fin c) (Fin a) ℂ)
(hK : IsKrausFamily K) : QuantumExecution rho (aliceApply K rho) 0
| bob {a b d k} (rho : BipartiteMatrix a b) (K : Fin k → Matrix (Fin d) (Fin b) ℂ)
(hK : IsKrausFamily K) : QuantumExecution rho (bobApply K rho) 0
| sendAB {a b m} (rho : BipartiteMatrix (a * m) b) (hm : 0 < m) :
QuantumExecution rho (transferAB rho) (logTwo m)
| sendBA {a b m} (rho : BipartiteMatrix a (m * b)) (hm : 0 < m) :
QuantumExecution rho (transferBA rho) (logTwo m)
| compose {a b c d e f} {rho : BipartiteMatrix a b} {sigma : BipartiteMatrix c d}
{tau : BipartiteMatrix e f} {C D : ℝ} :
QuantumExecution rho sigma C → QuantumExecution sigma tau D → QuantumExecution rho tau (C + D)
/-- PDF p.5, Corollary 10: finite adaptive LOCC trees. Each communicated
instrument outcome is available to both parties. Branch states are unnormalized
and all final branches are summed. C bounds worst-case total log-alphabet cost;
this includes every fixed-length binary-message protocol in the source. -/
inductive ClassicalExecution : {a b c d : ℕ} → BipartiteMatrix a b → BipartiteMatrix c d → ℝ → Prop
| identity {a b} (rho : BipartiteMatrix a b) : ClassicalExecution rho rho 0
| alice {a b c k} (rho : BipartiteMatrix a b) (K : Fin k → Matrix (Fin c) (Fin a) ℂ)
(hK : IsKrausFamily K) : ClassicalExecution rho (aliceApply K rho) 0
| bob {a b d k} (rho : BipartiteMatrix a b) (K : Fin k → Matrix (Fin d) (Fin b) ℂ)
(hK : IsKrausFamily K) : ClassicalExecution rho (bobApply K rho) 0
| aliceMessage {a b c d e k m} (rho : BipartiteMatrix a b)
(K : Fin m → Fin k → Matrix (Fin c) (Fin a) ℂ) (hm : 0 < m)
(hK : (∑ j, ∑ l, (K j l)ᴴ * K j l) = 1)
(sigma : Fin m → BipartiteMatrix d e) (cost : Fin m → ℝ) (budget : ℝ)
(hbudget : ∀ j, cost j ≤ budget)
(next : ∀ j, ClassicalExecution (aliceApply (K j) rho) (sigma j) (cost j)) :
ClassicalExecution rho (∑ j, sigma j) (logTwo m + budget)
| bobMessage {a b c d e k m} (rho : BipartiteMatrix a b)
(K : Fin m → Fin k → Matrix (Fin c) (Fin b) ℂ) (hm : 0 < m)
(hK : (∑ j, ∑ l, (K j l)ᴴ * K j l) = 1)
(sigma : Fin m → BipartiteMatrix d e) (cost : Fin m → ℝ) (budget : ℝ)
(hbudget : ∀ j, cost j ≤ budget)
(next : ∀ j, ClassicalExecution (bobApply (K j) rho) (sigma j) (cost j)) :
ClassicalExecution rho (∑ j, sigma j) (logTwo m + budget)
| compose {a b c d e f} {rho : BipartiteMatrix a b} {sigma : BipartiteMatrix c d}
{tau : BipartiteMatrix e f} {C D : ℝ} :
ClassicalExecution rho sigma C → ClassicalExecution sigma tau D → ClassicalExecution rho tau (C + D)
section Operational
variable {A B C D : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
[Fintype C] [DecidableEq C] [Fintype D] [DecidableEq D]
/-- PDF pp.1--2: separate local basis identifications with finite index sets. -/
def pack (rho : Matrix (A × B) (A × B) ℂ) : BipartiteMatrix (Fintype.card A) (Fintype.card B) :=
fun p q => rho ((Fintype.equivFin A).symm p.1, (Fintype.equivFin B).symm p.2)
((Fintype.equivFin A).symm q.1, (Fintype.equivFin B).symm q.2)
/-- PDF p.2: operational quantum communication relation. -/
def Quantum (rho : Matrix (A × B) (A × B) ℂ) (sigma : Matrix (C × D) (C × D) ℂ)
(cost : ℝ) : Prop := QuantumExecution (pack rho) (pack sigma) cost
/-- PDF p.5: operational classical communication relation. -/
def Classical (rho : Matrix (A × B) (A × B) ℂ) (sigma : Matrix (C × D) (C × D) ℂ)
(cost : ℝ) : Prop := ClassicalExecution (pack rho) (pack sigma) cost
/-- PDF pp.1--2: Alice's reduced density; the second tensor factor is traced out. -/
def aliceDensity (phi : EuclideanSpace ℂ (A × B)) : Matrix A A ℂ := traceRight (pureDensity phi)
/-- PDF p.5: fidelity is tested on the unconditional, possibly mixed, output. -/
def QuantumPrepares (phi : EuclideanSpace ℂ (A × B)) (psi : EuclideanSpace ℂ (C × D))
(epsilon cost : ℝ) : Prop :=
∃ sigma : Matrix (C × D) (C × D) ℂ,
Quantum (pureDensity phi) sigma cost ∧ fidelity sigma (pureDensity psi) ≥ 1 - epsilon
/-- PDF p.5: classical-only preparation, summing every branch. -/
def ClassicalPrepares (phi : EuclideanSpace ℂ (A × B)) (psi : EuclideanSpace ℂ (C × D))
(epsilon cost : ℝ) : Prop :=
∃ sigma : Matrix (C × D) (C × D) ℂ,
Classical (pureDensity phi) sigma cost ∧ fidelity sigma (pureDensity psi) ≥ 1 - epsilon
/-- PDF p.5: bipartite tensor with all Alice factors before all Bob factors. -/
def tensorPureStates (phi : EuclideanSpace ℂ (A × B)) (psi : EuclideanSpace ℂ (C × D)) :
EuclideanSpace ℂ ((A × C) × (B × D)) :=
WithLp.toLp 2 fun p => phi (p.1.1, p.2.1) * psi (p.1.2, p.2.2)
/-- PDF pp.6--7: n copies with bipartite ownership spectralRetentions; the empty product is one. -/
def pureStateCopies (psi : EuclideanSpace ℂ (A × B)) (n : ℕ) :
EuclideanSpace ℂ ((Fin n → A) × (Fin n → B)) :=
WithLp.toLp 2 fun p => ∏ j, psi (p.1 j, p.2 j)
/-- PDF pp.1--2: normalized maximally entangled rank-r state when r>0. -/
def bellRank (r : ℕ) : EuclideanSpace ℂ (Fin r × Fin r) :=
WithLp.toLp 2 fun p => if p.1 = p.2 then ((Real.sqrt (r : ℝ))⁻¹ : ℂ) else 0
/-- PDF p.5: k EPR pairs, including k=0. -/
def eprPairs (k : ℕ) : EuclideanSpace ℂ (Fin (2 ^ k) × Fin (2 ^ k)) := bellRank (2 ^ k)
/-- PDF p.5: the eighth root of 4 epsilon. -/
def smoothingError (epsilon : ℝ) : ℝ := (4 * epsilon) ^ (1 / 8 : ℝ)
end Operational
/-- PDF p.3: binary Schmidt-diagonal state, with complex amplitudes. -/
def binaryState (alpha beta : ℂ) : EuclideanSpace ℂ (Bool × Bool) :=
WithLp.toLp 2 fun p => if p = (false,false) then alpha else if p = (true,true) then beta else 0
section Dilution
variable {A B : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
end Dilution
/-- PDF p.7: the ordinary harmonic sum, with indices starting at one. -/
def harmonicSum (n : ℕ) : ℝ := ∑ i ∈ Finset.Icc 1 n, (i : ℝ)⁻¹
/-- PDF p.7: normalized harmonic embezzling vector for n>0.
At n=0 its Hilbert space is empty, and no normalized-state assertion is used. -/
def harmonicState (n : ℕ) : EuclideanSpace ℂ (Fin n × Fin n) :=
WithLp.toLp 2 fun p => if p.1 = p.2 then
(Real.sqrt (1 / (((p.1.val + 1 : ℕ) : ℝ) * harmonicSum n)) : ℂ) else 0
/-- PDF p.8, (21): feasible integer tail cutoffs, restricted to 1<=k<=n. -/
def harmonicTailCuts (n : ℕ) (delta : ℝ) : Finset ℕ :=
(Finset.Icc 1 n).filter fun k =>
(∑ i ∈ Finset.Icc (k + 1) n, 1 / ((i : ℝ) * harmonicSum n)) ≤ delta
/-- PDF p.8, (22): feasible integer head cutoffs; the upper limit is k-1, inclusive. -/
def harmonicHeadCuts (n : ℕ) (delta : ℝ) : Finset ℕ :=
(Finset.Icc 1 n).filter fun k =>
(∑ i ∈ Finset.Icc 1 (k - 1), 1 / ((i : ℝ) * harmonicSum n)) ≤ delta
/-- PDF p.6, (20): action of separate local linear maps on a bipartite vector.
Isometricity is required explicitly in the residual-family theorem. -/
def applyLocalMaps {A B C D : Type} [Fintype A] [Fintype B]
(U : Matrix C A ℂ) (V : Matrix D B ℂ) (phi : EuclideanSpace ℂ (A × B)) :
EuclideanSpace ℂ (C × D) :=
WithLp.toLp 2 fun p => ∑ a, ∑ b, U p.1 a * V p.2 b * phi (a,b)
/-- Sanity examples for the paper-local substrate. These pin definitions rather
than prove the paper's theorem statements. -/
example : logTwo 1 = 0 := by simp [logTwo, Real.logb]
example {I : Type*} [DecidableEq I] (i : I) (f : I → ℝ) : finiteMin {i} f = f i := by
simp [finiteMin]
example {I : Type*} [DecidableEq I] (i : I) (f : I → ℝ) : finiteMax {i} f = f i := by
simp [finiteMax]
example {n : ℕ} (r : Fin n → ℝ) (s : Finset (Fin n)) :
spectralRenyi r s (0 : RenyiOrder) = logTwo s.card := by simp [spectralRenyi]
example : upperRenyiFactor ⊤ = 1 := by simp [upperRenyiFactor]
example {a b : ℕ} (rho : BipartiteMatrix a b) : QuantumExecution rho rho 0 :=
QuantumExecution.identity rho
example {a b : ℕ} (rho : BipartiteMatrix a b) : ClassicalExecution rho rho 0 :=
ClassicalExecution.identity rho
example {a b m : ℕ} (rho : BipartiteMatrix (a * m) b) (hm : 0 < m) :
QuantumExecution rho (transferAB rho) (logTwo m) := QuantumExecution.sendAB rho hm
example {A B : Type} [Fintype A] [Fintype B] (psi : EuclideanSpace ℂ (A × B))
(p : (Fin 0 → A) × (Fin 0 → B)) : pureStateCopies psi 0 p = 1 := by simp [pureStateCopies]
example : eprPairs 0 (0,0) = 1 := by simp [eprPairs, bellRank]
example : harmonicSum 1 = 1 := by norm_num [harmonicSum]
example : harmonicState 1 (0,0) = 1 := by norm_num [harmonicState, harmonicSum]
example {A B C D : Type} [Fintype A] [Fintype B]
(U : Matrix C A ℂ) (V : Matrix D B ℂ) (phi : EuclideanSpace ℂ (A × B)) (c : C) (d : D) :
applyLocalMaps U V phi (c,d) = ∑ a, ∑ b, U c a * V d b * phi (a,b) := rfl
example (alpha beta : ℂ) : binaryState alpha beta (false,false) = alpha := by simp [binaryState]
example {I : Type} [Fintype I] [DecidableEq I] (rho : Matrix I I ℂ) :
spread rho = entropyZero rho - entropyInfinity rho := rfl
example {I : Type} [Fintype I] [DecidableEq I] (rho : Matrix I I ℂ) (e : ℝ) :
smoothSpread rho e = logTwo (finiteMin (spectralRetentions rho e) fun s =>
(s.card : ℝ) * finiteMax s (ascEigenvalues rho)) := rfl
example {I : Type} [Fintype I] [DecidableEq I] (rho : Matrix I I ℂ)
(alpha beta : RenyiOrder) : renyiGap rho alpha beta = eigenvalueRenyiEntropy rho alpha - eigenvalueRenyiEntropy rho beta := rfl
example {a b c k : ℕ} (K : Fin k → Matrix (Fin c) (Fin a) ℂ) (rho : BipartiteMatrix a b) :
aliceApply K rho = krausApply (fun j => Matrix.kronecker (K j)
(1 : Matrix (Fin b) (Fin b) ℂ)) rho := rfl
example {a b d k : ℕ} (K : Fin k → Matrix (Fin d) (Fin b) ℂ) (rho : BipartiteMatrix a b) :
bobApply K rho = krausApply (fun j => Matrix.kronecker
(1 : Matrix (Fin a) (Fin a) ℂ) (K j)) rho := rfl
example {a b m : ℕ} (rho : BipartiteMatrix a (m * b)) (hm : 0 < m) :
QuantumExecution rho (transferBA rho) (logTwo m) := QuantumExecution.sendBA rho hm
example {A B : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
(rho : Matrix (A × B) (A × B) ℂ) : Quantum rho rho 0 := QuantumExecution.identity (pack rho)
example {A B : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
(rho : Matrix (A × B) (A × B) ℂ) : Classical rho rho 0 := ClassicalExecution.identity (pack rho)
example {A B : Type} [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
(phi : EuclideanSpace ℂ (A × B)) (a a0 : A) :
aliceDensity phi a a0 = ∑ b, phi (a,b) * conj (phi (a0,b)) := rfl
example {I : Type} [Fintype I] [DecidableEq I] (rho sigma : Matrix I I ℂ) :
fidelity rho sigma = (rootFidelity rho sigma) ^ 2 := rfl
example : smoothingError 0 = 0 := by norm_num [smoothingError]
example : harmonicTailCuts 1 0 = {1} := by norm_num [harmonicTailCuts, harmonicSum]
example : harmonicHeadCuts 1 0 = {1} := by norm_num [harmonicHeadCuts, harmonicSum]
end QAlgorithms.Papers.Independent.Intakenext100.P61
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Intakenext100.P61.BipartiteMatrix
For any natural numbers , including zero, a bipartite matrix of dimensions is a complex matrix whose rows and columns are indexed by pairs with and . It is therefore a square matrix of size . No positivity, Hermitian symmetry, or trace condition is imposed; if either dimension is zero, the index set is empty.
QAlgorithms.Papers.Independent.Intakenext100.P61.Classical
For finite types , arbitrary complex matrices on and on , and a real number , this proposition says that, after relabeling the four types by their specified enumerations onto initial segments of the natural numbers, the matrices are connected at cost exactly by the least relation with the following rules. Identity costs zero, and local maps or cost zero whenever on the affected input factor. A message step chooses natural numbers and , a family acting on one side with joint completeness , branch output matrices of a common pair of dimensions, real branch costs , and a real budget satisfying for every . Each branch input is for an Alice message, or for a Bob message; if every such input has a derivation to at cost , the message step has output and cost . Arbitrary successive derivations compose by adding costs. Dimensions and local family sizes may be zero subject to completeness, is included, and every message branch requires a derivation even when its input is zero. No positivity or normalization assumptions are imposed on the matrices.
QAlgorithms.Papers.Independent.Intakenext100.P61.ClassicalExecution
This defines the least relation between arbitrary complex bipartite matrices, possibly of different natural-number dimensions, and real costs, generated by identity, local operations, message branches, and composition as follows. Identity has cost zero. Given of dimensions , any family of complex matrices with gives the zero-cost output ; any family of complex matrices with gives the zero-cost output . For an Alice message, choose arbitrary natural numbers with , complex matrices satisfying , branch outputs all of dimensions , real branch costs , and a real budget with for every . If, for every , the branch input is related to at cost , then is related to at cost , where . The Bob-message rule has the same quantifiers and conclusion, with complex matrices, completeness , and branch inputs . Finally, for matrices of any dimensions and real costs , relations from to at cost and from to at cost give a relation from to at cost . Matrices need not be positive or normalized; dimensions and may be zero when the completeness equations hold. Message branches include every , even branches whose input matrix is zero, and is allowed.
QAlgorithms.Papers.Independent.Intakenext100.P61.ClassicalPrepares
For finite register types , arbitrary complex vectors on and on , and arbitrary real numbers , this predicate means that there exists a matrix on obtainable from by a classical execution of cost exactly , with
Here . After relabeling finite registers by consecutive integers, a classical execution is generated by identity operations of cost zero; local maps , with , of cost zero; and local measurements with outcomes and matrices satisfying . Each measurement outcome can have a further classical execution of cost ; if every , the combined execution has cost and output equal to the sum of the unnormalized branch outputs. Finite composition adds costs. Neither input vector is required to have norm one, is not separately required to have trace one, and no range restriction is imposed on or .
QAlgorithms.Papers.Independent.Intakenext100.P61.Flat
For a finite type with decidable equality and any complex matrix indexed by , let be its ascending eigenvalue list if it is Hermitian, counted with multiplicity, and the identically zero list otherwise. This property requires for every pair of indices satisfying and . It places no restriction on zero or negative entries. The property holds vacuously if there are no strictly positive entries, including for non-Hermitian matrices and empty , and also holds when there is just one such index.
QAlgorithms.Papers.Independent.Intakenext100.P61.Quantum
For finite types , arbitrary complex matrices on and on , and any real number , this proposition says that, after relabeling each type by its specified enumeration onto the integers from zero to its cardinality minus one, there is a finite derivation from to using the following rules with total cost exactly : identity at cost zero; local transformations or at cost zero, where the rectangular local matrices satisfy on the corresponding input factor; and, for a positive natural number , transfer of an -dimensional factor between the two sides at cost . A transfer identifies with in both matrix indices, changing dimensions to or conversely. Successive derivations compose by adding their real costs. All intermediate dimensions are natural numbers and may be zero; local families may be empty when their completeness equation holds, and transfers are included. No positivity or normalization condition is required for , , or intermediate matrices.
QAlgorithms.Papers.Independent.Intakenext100.P61.QuantumExecution
This defines the least relation between arbitrary complex bipartite matrices, possibly of different natural-number dimensions, and real costs , generated by the following rules. Every matrix of dimensions satisfies . For any natural number and complex matrices satisfying , one has ; for complex matrices satisfying , one similarly has . For every positive natural number , regrouping dimensions into , or conversely, is allowed at cost : the regrouping identifies the index with for , , , in both rows and columns. Finally, for all natural numbers , matrices of dimensions , and real numbers , and imply . No positivity or normalization condition is imposed on the matrices. Dimensions and the number of local matrices may be zero, subject to the displayed completeness equations; transfer dimensions must satisfy , and is included.
QAlgorithms.Papers.Independent.Intakenext100.P61.QuantumPrepares
For finite types , arbitrary vectors and , and arbitrary real numbers , this proposition asserts the existence of a complex matrix on obtainable from the matrix at cost exactly by a finite derivation consisting of identity, complete local Kraus operations at zero cost, positive-dimensional factor transfers at cost , and composition with additive costs, after relabeling all finite types by their specified enumerations. Here a local operation is or , with on the affected input factor; transfers identify with in both matrix indices and allow either direction between dimensions and , with . The required approximation condition is
where each matrix square root is defined by continuous functional calculus using the real square-root function. Neither input vector is assumed normalized, and no separate density-matrix condition is imposed on . Empty finite types and zero intermediate dimensions are included; local families may be empty when completeness holds. Neither nor is restricted to be nonnegative.
QAlgorithms.Papers.Independent.Intakenext100.P61.RenyiOrder
The set of orders consists of all nonnegative real numbers together with one additional greatest element, denoted . It includes the orders and .
QAlgorithms.Papers.Independent.Intakenext100.P61.aliceApply
For arbitrary natural numbers , a family of complex matrices , and an arbitrary complex matrix indexed by , this defines the matrix indexed by given by
Here denotes conjugate transpose. There is no assumption that , and no state condition on . All dimensions may be zero; in particular, gives the zero matrix.
QAlgorithms.Papers.Independent.Intakenext100.P61.aliceDensity
For finite types and any vector in the complex Euclidean space indexed by , this defines the matrix on whose entries are
Thus the definition forms the matrix with entries and sums over equal indices. No assumption is made. Empty types are allowed; in particular, if is empty, the resulting matrix is zero.
QAlgorithms.Papers.Independent.Intakenext100.P61.applyLocalMaps
For arbitrary types , with specified finite enumerations of and , matrices and , and a vector equipped with the Euclidean-space structure, this definition returns the vector on whose coordinates are
There are no finiteness assumptions on , no normalization assumption on , and no isometry or unitarity assumptions on . Empty input index sets give zero sums; an empty output index set gives the unique vector with no coordinates.
QAlgorithms.Papers.Independent.Intakenext100.P61.bellRank
For every natural number , this definition gives the complex vector indexed by with coordinates
For , it has equal nonzero diagonal amplitudes and norm one. The definition also includes : its index set is empty, so it is the zero vector in the zero-dimensional space.
QAlgorithms.Papers.Independent.Intakenext100.P61.binaryState
For arbitrary complex numbers , this defines the vector in whose coefficient at is , whose coefficient at is , and whose other two coefficients are zero:
No normalization or nonzero condition is imposed.
QAlgorithms.Papers.Independent.Intakenext100.P61.bobApply
For arbitrary natural numbers , a family of complex matrices , and an arbitrary complex matrix indexed by , this defines the matrix indexed by given by
Here denotes conjugate transpose. There is no assumption that , and no state condition on . All dimensions may be zero; in particular, gives the zero matrix.
QAlgorithms.Papers.Independent.Intakenext100.P61.eigenvalueRenyiEntropy
For a finite index type with decidable equality, any complex matrix indexed by , and any order , let be its eigenvalues in ascending order when is Hermitian, and the all-zero family otherwise, and put . Writing , the defined entropy is at order , at order , at order , and at every other finite order. The maximum over an empty set is defined here to be zero, and , so an empty positive spectrum gives entropy zero at every order. No density-matrix assumption is imposed; empty , non-Hermitian matrices, and Hermitian matrices with nonpositive eigenvalues are included.
QAlgorithms.Papers.Independent.Intakenext100.P61.entropyOne
For a finite type with decidable equality and any complex matrix indexed by , let be its ascending eigenvalue list, counted with multiplicity if is Hermitian and defined to be identically zero otherwise. This defines , where uses the total real logarithm: , and for . The sum includes negative eigenvalues as well as positive ones; no positivity or trace-one hypothesis is imposed. Its value is for non-Hermitian matrices and for empty .
QAlgorithms.Papers.Independent.Intakenext100.P61.entropyZero
For a finite type with decidable equality and any complex matrix indexed by , this defines , where is the complex dimension of the range of the linear map . Thus is the matrix rank, without any Hermitian, positivity, or normalization assumption. When , including when is empty, the value is , using the total logarithm convention .
QAlgorithms.Papers.Independent.Intakenext100.P61.eprPairs
For every natural number , this definition gives the vector indexed by with amplitude at and amplitude zero at when . In particular, gives a one-coordinate vector with amplitude .
QAlgorithms.Papers.Independent.Intakenext100.P61.finiteMax
For any type with decidable equality, finite subset , and function , this defines the maximum of over when is nonempty, and defines the value to be when . The type itself need not be finite.
QAlgorithms.Papers.Independent.Intakenext100.P61.finiteMin
For any type with decidable equality, finite subset , and function , this defines the minimum of over when is nonempty, and defines the value to be when . The type itself need not be finite.
QAlgorithms.Papers.Independent.Intakenext100.P61.harmonicHeadCuts
For every natural number and every real , let . This defines the finite set
The subtraction is natural-number subtraction, and every candidate here has . An empty sum is zero, so the set is empty when , and for , belongs exactly when . No restriction on is part of the definition.
QAlgorithms.Papers.Independent.Intakenext100.P61.harmonicState
For every natural number , let . This defines the vector indexed by pairs with coefficients
For the index set is empty and this is the zero vector in the zero-dimensional space; for , the displayed denominators are positive.
QAlgorithms.Papers.Independent.Intakenext100.P61.harmonicSum
For every natural number , this defines the real number
The sum is empty when , so .
QAlgorithms.Papers.Independent.Intakenext100.P61.harmonicTailCuts
For every natural number and every real , let . This defines the finite set
An empty sum is zero. Thus the set is empty when ; when , belongs exactly when . No restriction on is part of the definition.
QAlgorithms.Papers.Independent.Intakenext100.P61.largestWeight
For a finite type with decidable equality and any complex matrix indexed by , form its ascending eigenvalue list , counted with multiplicity when is Hermitian and defined to be identically zero otherwise. This defines if at least one entry is strictly positive, and otherwise. In particular, the value is for a non-Hermitian matrix, a Hermitian matrix with no positive eigenvalues, or empty ; no density-matrix hypothesis is imposed.
QAlgorithms.Papers.Independent.Intakenext100.P61.pack
For finite types , with their specified finite enumerations and , and any complex matrix indexed by , this defines a bipartite matrix of dimensions by
No state condition is imposed. Empty finite types are allowed and produce an empty matrix index set.
QAlgorithms.Papers.Independent.Intakenext100.P61.pureStateCopies
For types , an arbitrary complex vector indexed by , and every natural number , this definition gives a vector indexed by pairs of tuples and , with coordinates
There is no normalization assumption on . When , both tuples are empty and the empty product is , so the resulting one-coordinate vector has amplitude , independently of .
QAlgorithms.Papers.Independent.Intakenext100.P61.renyiGap
For a finite index type with decidable equality, any complex matrix , and any orders , take to be the ascending eigenvalues of if it is Hermitian and zero otherwise, and let . With , define to be for , for , for , and otherwise. The defined gap is exactly . There is no ordering assumption on and no density-matrix assumption on . An empty positive spectrum uses maximum zero and , giving gap zero.
QAlgorithms.Papers.Independent.Intakenext100.P61.smoothInfinity
For a finite type with decidable equality, any complex matrix indexed by , and any real , let be its ascending Hermitian eigenvalue list, counted with multiplicity, or zero otherwise. For each subset satisfying , assign the value , defined to be for empty . This defines minus the base-two logarithm of the minimum of these assigned values; if there are no qualifying subsets, that minimum is defined to be . The total logarithm gives , so the result is both when no subset qualifies and whenever , when the empty subset qualifies. It is also for non-Hermitian or empty ; no density-matrix hypothesis is assumed.
QAlgorithms.Papers.Independent.Intakenext100.P61.smoothRenyiGap
For a finite index type with decidable equality, any complex matrix , orders , and arbitrary real , let be the ascending eigenvalues if is Hermitian and zero otherwise, and define
Writing , for each such subset define as at order , at order , at order , and otherwise. The defined smoothed gap is when is nonempty, and zero otherwise. Empty-subset maxima are zero and . No density, order-comparison, or tolerance-range assumptions are imposed; in particular, an empty subset is eligible whenever .
QAlgorithms.Papers.Independent.Intakenext100.P61.smoothSpread
For a finite type with decidable equality, any complex matrix indexed by , and any real , let be its ascending eigenvalue list when Hermitian, counted with multiplicity, and zero otherwise. Consider every subset with , assigning it the value , where the maximum over empty is defined to be . This defines the base-two logarithm of the minimum assigned value, with the minimum defined as when there are no qualifying subsets and the total logarithm satisfying . Thus the result is if no subset qualifies, if , if is non-Hermitian, or if is empty. No positivity, trace normalization, or restriction on is assumed.
QAlgorithms.Papers.Independent.Intakenext100.P61.smoothZero
For a finite type with decidable equality, any complex matrix indexed by , and any real , let be its ascending eigenvalue list when Hermitian, counted with multiplicity, and zero otherwise. Consider all subsets of the strictly positive indices for which . This defines when this collection is nonempty, and when it is empty, where uses the total real logarithm. In particular, the value is whenever , since the empty subset then qualifies, and is also for non-Hermitian or empty . No density-matrix or error-range hypothesis is imposed.
QAlgorithms.Papers.Independent.Intakenext100.P61.smoothingError
For every real number , this definition assigns
using the total real-power operation. No nonnegativity restriction is part of the definition; when , this is the nonnegative eighth root of , including .
QAlgorithms.Papers.Independent.Intakenext100.P61.spectralRenyi
For every natural number , arbitrary real family , subset , and order , define and , with . The defined real number is
There are no positivity or normalization assumptions on . Powers and logarithms use their total real-valued definitions; in particular, . The case is included, and an empty gives at every order.
QAlgorithms.Papers.Independent.Intakenext100.P61.spectralRetentions
For a finite type with decidable equality, any complex matrix indexed by , and any real , let be its ascending Hermitian eigenvalue list, counted with multiplicity, or the identically zero list if is not Hermitian. This defines the finite collection of all subsets satisfying . Neither normalization of nor a range restriction on is assumed. The empty subset belongs exactly when ; the collection can be empty. If the positive-index set is empty, the collection is for and empty otherwise.
QAlgorithms.Papers.Independent.Intakenext100.P61.spectralSupport
For a finite type with decidable equality and any complex matrix indexed by , let be its eigenvalues in ascending order, counted with multiplicity, if is Hermitian; if is not Hermitian, set every . This defines the finite set . Thus it includes only strictly positive entries of this eigenvalue list, and is empty for non-Hermitian matrices and for empty . No positivity or trace normalization of is assumed.
QAlgorithms.Papers.Independent.Intakenext100.P61.spread
For a finite type with decidable equality and any complex matrix indexed by , write for its complex matrix rank and , with the total real logarithm convention . This defines , where when is Hermitian, and otherwise. For Hermitian , the supremum is over all eigenvalues, including nonpositive ones; for an empty list its real supremum is . Consequently the spread is for non-Hermitian , and when is empty. No density-matrix hypothesis is assumed.
QAlgorithms.Papers.Independent.Intakenext100.P61.tensorPureStates
For types and arbitrary complex vectors indexed by and indexed by , this definition produces the vector indexed by whose coordinates are
Thus the two first registers are grouped together, as are the two second registers. No normalization hypothesis is imposed.
QAlgorithms.Papers.Independent.Intakenext100.P61.transferAB
For any natural numbers and any complex matrix indexed by , this defines a matrix indexed by by regrouping the indices:
for all , , and . No state condition or positivity assumption is imposed. The definition includes and zero values of or ; in these cases the matrix index sets are empty.
QAlgorithms.Papers.Independent.Intakenext100.P61.transferBA
For any natural numbers and any complex matrix indexed by , this defines a matrix indexed by by regrouping the indices:
for all , , and . No state condition or positivity assumption is imposed. The definition includes and zero values of or ; in these cases the matrix index sets are empty.
QAlgorithms.Papers.Independent.Intakenext100.P61.upperRenyiFactor
For every order , the defined real factor is if , and is if is the finite nonnegative real number . In particular, the factor is at both and , since real division by zero is defined to be zero; it is negative when .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.