Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for The private classical capacity with a symmetric side channel and its application to quantum cryptography

Definition
QAlgorithms_Papers_Independent_Support50_P07

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

The objects the formalized statements of The private classical capacity with a symmetric side channel and its application to quantum cryptography (arXiv:0705.3838) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • KeyCode: PDF p.3: one-use code data for any block channel; arbitrary mixed messages and a POVM.
  • decodedJoint: PDF p.3: joint uniform message, decoded classical message and full environment. The contraction Tr(M_j rho) is applied only to the receiverChannel block.
  • keyError: PDF p.3: strict FULL trace norm, with the ACTUAL environment marginal and no factor 1/2.
  • FullTracePrivateAchievable: PDF p.3: nonnegative unassisted achievable rates, all sufficiently large positive n, arbitrarily small errors and rate slacks. No public feedback or preshared resource. This full-trace-norm criterion differs from the accepted fidelity and leakage criteria.
  • fullTracePrivateCapacity: PDF p.3: operational private capacity. On finite nonempty isometric channels the rate set contains zero and is bounded; no entropy formula is used in this definition. Distinct from Information100.P67.privateCapacity, whose error is infidelity.
  • assistedDilation: PDF p.3: identity on two auxiliary factors, regrouped as BF and EG.
  • SymmetricSupport: PDF p.3: support in A tensor the +1 SWAP eigenspace. Separate row and column invariance excludes the antisymmetric subspace (conjugation invariance alone would not).
  • SSPrivateAchievable: PDF p.3: one arbitrary positive-dimensional free symmetric channel per block. Its mixed input states are represented after its isometric embedding into symmetric FG. Every density operator with this support is an allowed input to A_d, and conversely.
  • ssPrivateCapacity: PDF p.3: operational ss-private capacity, with no charge for auxiliary dimension. For physical finite nonempty channels the rate set is nonempty and bounded independently of d.
  • ProcessedEnsemble: PDF p.2: all finite normalized pure-signal ensembles and classical X-to-T channels. The alphabets and stochastic map are optimized, not quantum auxiliary registers.
  • processedState: PDF p.2: the cq state of the processed classical variable T and a quantum output.
  • privateInformationValue: PDF p.2: I(T;B)-I(T;E) for a particular ensemble and classical processing.
  • processedPrivateInformation: PDF p.2: one-letter private information, optimized over ALL finite pure ensembles and stochastic postprocessings. Nonempty and bounded on physical nonzero systems. Distinct from Dependency50.P48.privateInformation U rho, a fixed-input quantity.
  • purificationCoherentInformation: Theorem 2, PDF p.2: the equivalent pure-PURIFICATION variational expression. A reference copy of A suffices by Schmidt decomposition; this is not a pure-input restriction.
  • ssInformationValues: Equation (3), PDF p.3: all symmetric pure AFG ensembles, unrestricted positive d.
  • ssPrivateInformation: Equation (3), PDF p.3: C^(1)_(p,ss) as a variational quantity. Although the auxiliary dimension is unbounded, the value set is bounded for a fixed finite channel.
  • SymmetricInput: PDF p.3: a basis label for the d(d+1)/2-dimensional symmetric input space.
  • symmetricSubspaceEmbedding: PDF p.3: canonical isometry onto the symmetric subspace; diagonal basis vectors map to |ii>, off-diagonal ones to (|ij>+|ji>)/sqrt(2). Information100.P67.symmetricDilation instead composes two supplied dilations.
  • degradableMixingCosts: Definition 10, PDF p.5: all costs of finite degradable/antidegradable mixtures, INCLUDING branchwise CPTP postprocessors and arbitrary positive intermediate dimensions.
  • degradableMixingCost: Definition 10, PDF p.5: infimum cost. The identity branch followed by N makes the set nonempty, and each Q^(1) is nonnegative; hence no empty/unbounded infimum default.
  • pauliMatrices: PDF pp.6–7: Pauli matrices in the computational basis, including the identity branch.
  • qubitPauliProbabilityChannel: Theorem 12, PDF p.7: actual Pauli receiverChannel map; arguments are probabilities, not Kraus amplitudes. Validity is imposed by the theorem's full-simplex hypotheses. The frozen Frontier18.P17.pauliChannel takes a full Weyl probability array instead.
  • twoKrausChannel: Section IV.A, PDF p.6: two-Kraus qubit family, with physical parameters in [0,1].
  • amplitudeDampingChannel: Section IV.B, PDF p.6: standard amplitude damping, excited |1> decays to |0>.
  • qubitPhaseFlipChannel: Section IV.A, PDF pp.6–7 and note [28]: Z dephasing with error probability p. Dependency50.P11.dephasingChannel fixes the fair p=1/2 channel, so cannot supply this family.
  • erasureMap: Section IV.A, PDF p.6: genuine orthogonal erasure flag, linear on ALL operators.
  • independentPauliChannel: Section IV.B, PDF p.6: independent X/Z-error probabilities; Y has probability q^2.
  • depolarizingChannel: Section IV.C, PDF pp.6–7: depolarizing error probability is TOTAL Pauli error, so QBER = 2p/3.
  • twoKrausValue: Section IV.A, PDF p.6: diagonal-input coherent information for the two-Kraus family.
  • dampingBound: Section IV.B, PDF p.6: amplitude-damping scalar optimized on the compact interval. It includes t=0 with value zero. The capacity theorem also asserts attainment.
  • depolarizingDampingParameter: Section IV.C, PDF p.6, checked on rendered page: only 1-p is under each square root.
  • depolarizingEnvelope: Section IV.C, PDF pp.6,8: lower convex envelope on the physical depolarizing parameter interval [0,1]. Affinity of the receiverChannel map in p justifies this interpolation.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_Ensemble
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P67
import Definitions.Def_QAlgorithms_Papers_Independent_Claimed50_P24
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P19
import Definitions.Def_QAlgorithms_Papers_Independent_Information100_P80

noncomputable section

open scoped BigOperators Matrix ComplexConjugate ComplexOrder
open Filter

namespace QAlgorithms.Papers.Independent.Support50.P07

open QAlgorithms.Papers.Independent.Information100.P67
  (IsIsometry receiverChannel complementaryChannel IsDegradable IsAntidegradable
    dilationPower idealJoint maximumCoherentInformation)
open QAlgorithms.Papers.Independent.Claimed50.P24 (productDilation)
open QAlgorithms.Papers.Independent.Dependency50.P19 (mutualInformation)

/-! Source-specific definitions below are local to Smith, arXiv:0705.3838v1.
Accepted dilation and information primitives are imported. Private capacities
are operational suprema, not definitions by the formulas asserted as theorems.
Finite index types are used throughout; theorems require nonempty registers. -/

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

/-- PDF p.3: one-use code data for any block channel; arbitrary mixed messages and a POVM. -/
structure KeyCode (I O : Type*) [Fintype I] [Fintype O] [DecidableEq O] where
  messages : ℕ
  positive : 0 < messages
  inputs : Fin messages → Matrix I I ℂ
  normalized : ∀ m, IsDensityMatrix (inputs m)
  measurement : Fin messages → Matrix O O ℂ
  povm : IsPOVM measurement

/-- PDF p.3: joint uniform message, decoded classical message and full environment.
The contraction Tr(M_j rho) is applied only to the receiverChannel block. -/
def decodedJoint (U : Matrix (B × E) A ℂ) (code : KeyCode A B) :
    Matrix (Fin code.messages × (Fin code.messages × E))
      (Fin code.messages × (Fin code.messages × E)) ℂ :=
  fun i j => if i.1 = j.1 ∧ i.2.1 = j.2.1 then
    (code.messages : ℂ)⁻¹ *
      ∑ b, ∑ c, code.measurement i.2.1 c b *
        (U * code.inputs i.1 * Uᴴ) (b, i.2.2) (c, j.2.2)
    else 0

/-- PDF p.3: strict FULL trace norm, with the ACTUAL environment marginal and no factor 1/2. -/
def keyError (U : Matrix (B × E) A ℂ) (code : KeyCode A B) : ℝ :=
  let omega := decodedJoint U code
  traceNorm (omega - idealJoint code.messages (traceLeft (traceLeft omega)))

/-- PDF p.3: nonnegative unassisted achievable rates, all sufficiently large positive n,
arbitrarily small errors and rate slacks. No public feedback or preshared resource.
This full-trace-norm criterion differs from the accepted fidelity and leakage criteria. -/
def FullTracePrivateAchievable (U : Matrix (B × E) A ℂ) (rate : ℝ) : Prop :=
  0 ≤ rate ∧ ∀ eps : ℝ, 0 < eps → ∀ slack : ℝ, 0 < slack →
    ∃ n0 : ℕ, 0 < n0 ∧ ∀ n ≥ n0,
      ∃ code : KeyCode (Fin n → A) (Fin n → B),
        keyError (dilationPower U n) code < eps ∧
        rate - slack ≤ Real.logb 2 code.messages / (n : ℝ)

/-- PDF p.3: operational private capacity. On finite nonempty isometric channels the
rate set contains zero and is bounded; no entropy formula is used in this definition.
Distinct from Information100.P67.privateCapacity, whose error is infidelity. -/
def fullTracePrivateCapacity (U : Matrix (B × E) A ℂ) : ℝ :=
  sSup {r | FullTracePrivateAchievable U r}

/-- PDF p.3: identity on two auxiliary factors, regrouped as BF and EG. -/
def assistedDilation (U : Matrix (B × E) A ℂ) (d : ℕ) :
    Matrix ((B × Fin d) × (E × Fin d)) (A × (Fin d × Fin d)) ℂ :=
  fun be a => U (be.1.1, be.2.1) a.1 *
    if be.1.2 = a.2.1 ∧ be.2.2 = a.2.2 then 1 else 0

/-- PDF p.3: support in A tensor the +1 SWAP eigenspace. Separate row and column
invariance excludes the antisymmetric subspace (conjugation invariance alone would not). -/
def SymmetricSupport {d : ℕ}
    (rho : Matrix (A × (Fin d × Fin d)) (A × (Fin d × Fin d)) ℂ) : Prop :=
  (∀ a f g j, rho (a, (f, g)) j = rho (a, (g, f)) j) ∧
  (∀ i a f g, rho i (a, (f, g)) = rho i (a, (g, f)))

/-- PDF p.3: one arbitrary positive-dimensional free symmetric channel per block.
Its mixed input states are represented after its isometric embedding into symmetric FG.
Every density operator with this support is an allowed input to A_d, and conversely. -/
def SSPrivateAchievable (U : Matrix (B × E) A ℂ) (rate : ℝ) : Prop :=
  0 ≤ rate ∧ ∀ eps : ℝ, 0 < eps → ∀ slack : ℝ, 0 < slack →
    ∃ n0 : ℕ, 0 < n0 ∧ ∀ n ≥ n0, ∃ d : ℕ, 0 < d ∧
      ∃ code : KeyCode ((Fin n → A) × (Fin d × Fin d)) ((Fin n → B) × Fin d),
        (∀ m, SymmetricSupport (code.inputs m)) ∧
        keyError (assistedDilation (dilationPower U n) d) code < eps ∧
        rate - slack ≤ Real.logb 2 code.messages / (n : ℝ)

/-- PDF p.3: operational ss-private capacity, with no charge for auxiliary dimension.
For physical finite nonempty channels the rate set is nonempty and bounded independently of d. -/
def ssPrivateCapacity (U : Matrix (B × E) A ℂ) : ℝ :=
  sSup {r | SSPrivateAchievable U r}

/-- PDF p.2: all finite normalized pure-signal ensembles and classical X-to-T channels.
The alphabets and stochastic map are optimized, not quantum auxiliary registers. -/
structure ProcessedEnsemble (I : Type*) [Fintype I] where
  xsize : ℕ
  tsize : ℕ
  xpositive : 0 < xsize
  tpositive : 0 < tsize
  weight : Fin xsize → ℝ
  nonnegative : ∀ x, 0 ≤ weight x
  total : ∑ x, weight x = 1
  signal : Fin xsize → EuclideanSpace ℂ I
  unit : ∀ x, ‖signal x‖ = 1
  processing : Fin xsize → Fin tsize → ℝ
  stochasticNonnegative : ∀ x t, 0 ≤ processing x t
  stochasticTotal : ∀ x, ∑ t, processing x t = 1

/-- PDF p.2: the cq state of the processed classical variable T and a quantum output. -/
def processedState (ens : ProcessedEnsemble A) (channel : Superop A B) :
    Matrix (Fin ens.tsize × B) (Fin ens.tsize × B) ℂ :=
  fun i j => if i.1 = j.1 then
    ∑ x, ((ens.weight x * ens.processing x i.1 : ℝ) : ℂ) *
      channel (pureDensity (ens.signal x)) i.2 j.2 else 0

/-- PDF p.2: I(T;B)-I(T;E) for a particular ensemble and classical processing. -/
def privateInformationValue (U : Matrix (B × E) A ℂ) (ens : ProcessedEnsemble A) : ℝ :=
  mutualInformation (processedState ens (receiverChannel U)) -
    mutualInformation (processedState ens (complementaryChannel U))

/-- PDF p.2: one-letter private information, optimized over ALL finite pure ensembles
and stochastic postprocessings. Nonempty and bounded on physical nonzero systems.
Distinct from Dependency50.P48.privateInformation U rho, a fixed-input quantity. -/
def processedPrivateInformation (U : Matrix (B × E) A ℂ) : ℝ :=
  sSup {r | ∃ ens : ProcessedEnsemble A, r = privateInformationValue U ens}

/-- Theorem 2, PDF p.2: the equivalent pure-PURIFICATION variational expression.
A reference copy of A suffices by Schmidt decomposition; this is not a pure-input restriction. -/
def purificationCoherentInformation (U : Matrix (B × E) A ℂ) : ℝ :=
  sSup {r | ∃ psi : EuclideanSpace ℂ (A × A), ‖psi‖ = 1 ∧
    let rho := idTensorSuperop (R := A) (receiverChannel U) (pureDensity psi)
    r = vnEntropy (traceLeft rho) - vnEntropy rho}

/-- Equation (3), PDF p.3: all symmetric pure AFG ensembles, unrestricted positive d. -/
def ssInformationValues (U : Matrix (B × E) A ℂ) : Set ℝ :=
  {r | ∃ d : ℕ, 0 < d ∧ ∃ ens : ProcessedEnsemble (A × (Fin d × Fin d)),
    (∀ x a f g, ens.signal x (a, (f, g)) = ens.signal x (a, (g, f))) ∧
    r = privateInformationValue (assistedDilation U d) ens}

/-- Equation (3), PDF p.3: C^(1)_(p,ss) as a variational quantity. Although the
auxiliary dimension is unbounded, the value set is bounded for a fixed finite channel. -/
def ssPrivateInformation (U : Matrix (B × E) A ℂ) : ℝ :=
  sSup (ssInformationValues U)

/-- PDF p.3: a basis label for the d(d+1)/2-dimensional symmetric input space. -/
abbrev SymmetricInput (d : ℕ) := {ij : Fin d × Fin d // ij.1 ≤ ij.2}

/-- PDF p.3: canonical isometry onto the symmetric subspace; diagonal basis vectors
map to |ii>, off-diagonal ones to (|ij>+|ji>)/sqrt(2).
Information100.P67.symmetricDilation instead composes two supplied dilations. -/
def symmetricSubspaceEmbedding (d : ℕ) : Matrix (Fin d × Fin d) (SymmetricInput d) ℂ :=
  fun fg ij => if ij.val.1 = ij.val.2 then
    if fg = ij.val then 1 else 0
  else if fg = ij.val ∨ fg = (ij.val.2, ij.val.1) then
    ((Real.sqrt 2)⁻¹ : ℝ) else 0

/-- Definition 10, PDF p.5: all costs of finite degradable/antidegradable mixtures,
INCLUDING branchwise CPTP postprocessors and arbitrary positive intermediate dimensions. -/
def degradableMixingCosts (U : Matrix (B × E) A ℂ) : Set ℝ :=
  {r | ∃ k : ℕ, 0 < k ∧ ∃ p : Fin k → ℝ,
    (∀ i, 0 ≤ p i) ∧ (∑ i, p i = 1) ∧
    ∃ bo eo : Fin k → ℕ, (∀ i, 0 < bo i ∧ 0 < eo i) ∧
    ∃ v : (i : Fin k) → Matrix (Fin (bo i) × Fin (eo i)) A ℂ,
    ∃ post : (i : Fin k) → Superop (Fin (bo i)) B,
    (∀ i, IsIsometry (v i) ∧ (IsDegradable (v i) ∨ IsAntidegradable (v i)) ∧
      IsChannel (post i)) ∧
    (∀ rho, receiverChannel U rho = ∑ i, (p i : ℂ) • post i (receiverChannel (v i) rho)) ∧
    r = ∑ i, p i * maximumCoherentInformation (v i)}

/-- Definition 10, PDF p.5: infimum cost. The identity branch followed by N makes the
set nonempty, and each Q^(1) is nonnegative; hence no empty/unbounded infimum default. -/
def degradableMixingCost (U : Matrix (B × E) A ℂ) : ℝ :=
  sInf (degradableMixingCosts U)

/-- PDF pp.6–7: Pauli matrices in the computational basis, including the identity branch. -/
def pauliMatrices : Fin 4 → Matrix (Fin 2) (Fin 2) ℂ :=
  ![1, !![0, 1; 1, 0], !![0, -Complex.I; Complex.I, 0], !![1, 0; 0, -1]]

/-- Theorem 12, PDF p.7: actual Pauli receiverChannel map; arguments are probabilities,
not Kraus amplitudes. Validity is imposed by the theorem's full-simplex hypotheses.
The frozen Frontier18.P17.pauliChannel takes a full Weyl probability array instead. -/
def qubitPauliProbabilityChannel (p : Fin 3 → ℝ) : Superop (Fin 2) (Fin 2) :=
  fun rho => ((1 - ∑ i, p i : ℝ) : ℂ) • rho +
    ∑ i : Fin 3, (p i : ℂ) •
      (pauliMatrices (Fin.succ i) * rho * (pauliMatrices (Fin.succ i))ᴴ)

/-- Section IV.A, PDF p.6: two-Kraus qubit family, with physical parameters in [0,1]. -/
def twoKrausChannel (gamma delta : ℝ) : Superop (Fin 2) (Fin 2) :=
  krausApply ![!![(Real.sqrt (1 - gamma) : ℂ), 0; 0, (Real.sqrt (1 - delta) : ℂ)],
    !![0, (Real.sqrt delta : ℂ); (Real.sqrt gamma : ℂ), 0]]

/-- Section IV.B, PDF p.6: standard amplitude damping, excited |1> decays to |0>. -/
def amplitudeDampingChannel (gamma : ℝ) : Superop (Fin 2) (Fin 2) :=
  twoKrausChannel 0 gamma

/-- Section IV.A, PDF pp.6–7 and note [28]: Z dephasing with error probability p.
Dependency50.P11.dephasingChannel fixes the fair p=1/2 channel, so cannot supply this family. -/
def qubitPhaseFlipChannel (p : ℝ) : Superop (Fin 2) (Fin 2) :=
  fun rho => ((1 - p : ℝ) : ℂ) • rho + (p : ℂ) •
    (pauliMatrices 3 * rho * (pauliMatrices 3)ᴴ)

/-- Section IV.A, PDF p.6: genuine orthogonal erasure flag, linear on ALL operators. -/
def erasureMap (d : ℕ) (p : ℝ) : Superop (Fin d) (Option (Fin d)) :=
  fun rho i j => match i, j with
    | some a, some b => ((1 - p : ℝ) : ℂ) * rho a b
    | none, none => (p : ℂ) * rho.trace
    | _, _ => 0

/-- Section IV.B, PDF p.6: independent X/Z-error probabilities; Y has probability q^2. -/
def independentPauliChannel (q : ℝ) : Superop (Fin 2) (Fin 2) :=
  qubitPauliProbabilityChannel ![q * (1 - q), q ^ 2, q * (1 - q)]

/-- Section IV.C, PDF pp.6–7: depolarizing error probability is TOTAL Pauli error,
so QBER = 2p/3. -/
def depolarizingChannel (p : ℝ) : Superop (Fin 2) (Fin 2) :=
  qubitPauliProbabilityChannel (fun _ => p / 3)

/-- Section IV.A, PDF p.6: diagonal-input coherent information for the two-Kraus family. -/
def twoKrausValue (gamma delta t : ℝ) : ℝ :=
  binEntropy2 (t * (1 - gamma) + (1 - t) * delta) -
    binEntropy2 (t * gamma + (1 - t) * delta)

/-- Section IV.B, PDF p.6: amplitude-damping scalar optimized on the compact interval.
It includes t=0 with value zero. The capacity theorem also asserts attainment. -/
def dampingBound (gamma : ℝ) : ℝ :=
  sSup {r | ∃ t : ℝ, t ∈ Set.Icc 0 1 ∧
    r = binEntropy2 (t * (1 - gamma)) - binEntropy2 (t * gamma)}

/-- Section IV.C, PDF p.6, checked on rendered page: only 1-p is under each square root. -/
def depolarizingDampingParameter (p : ℝ) : ℝ :=
  4 * Real.sqrt (1 - p) * (1 - Real.sqrt (1 - p))

/-- Section IV.C, PDF pp.6,8: lower convex envelope on the physical depolarizing
parameter interval [0,1]. Affinity of the receiverChannel map in p justifies this interpolation. -/
def depolarizingEnvelope (p : ℝ) : ℝ :=
  sInf {r | ∃ k : ℕ, 0 < k ∧ ∃ w x : Fin k → ℝ,
    (∀ i, 0 ≤ w i ∧ x i ∈ Set.Icc 0 1) ∧ (∑ i, w i = 1) ∧
    (∑ i, w i * x i = p) ∧
    r = ∑ i, w i * min (1 - binEntropy2 (x i))
      (min (dampingBound (depolarizingDampingParameter (x i))) (max (1 - 4 * x i) 0))}

/-! Sanity checks of local conventions; these are not proofs of the paper's results. -/

example (U : Matrix (B × E) A ℂ) (be : (Fin 0 → B) × (Fin 0 → E))
    (a : Fin 0 → A) : dilationPower U 0 be a = 1 := by
  simp [dilationPower]

example (U : Matrix (B × E) A ℂ) (rho : Matrix A A ℂ) :
    receiverChannel U rho = traceRight (U * rho * Uᴴ) := rfl

example (U : Matrix (B × E) A ℂ) (rho : Matrix A A ℂ) :
    complementaryChannel U rho = traceLeft (U * rho * Uᴴ) := rfl

example (m : ℕ) (sigma : Matrix E E ℂ) (i : Fin m) (e f : E) :
    idealJoint m sigma (i, (i, e)) (i, (i, f)) = (m : ℂ)⁻¹ * sigma e f := by
  simp [idealJoint]

example : symmetricSubspaceEmbedding 1 (0, 0) ⟨(0, 0), le_refl _⟩ = 1 := by
  simp [symmetricSubspaceEmbedding]

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

example : pauliMatrices 1 0 1 = 1 ∧ pauliMatrices 2 0 1 = -Complex.I := by
  constructor <;> rfl

example (q : ℝ) : independentPauliChannel q =
    qubitPauliProbabilityChannel ![q * (1 - q), q ^ 2, q * (1 - q)] := rfl

end QAlgorithms.Papers.Independent.Support50.P07
Source
The private classical capacity with a symmetric side channel and its application to quantum cryptography, arXiv:0705.3838v1, https://arxiv.org/abs/0705.3838v1
Read-back

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

QAlgorithms.Papers.Independent.Support50.P07.FullTracePrivateAchievable

For finite index types A,B,EA,B,EA,B,E, an arbitrary complex matrix U:A→B×EU:A\to B\times EU:A→B×E, and a real number rrr, this predicate means that r≥0r\ge0r≥0 and, for every ε>0\varepsilon>0ε>0 and every s>0s>0s>0, there is a natural number n0>0n_0>0n0​>0 such that every natural number n≥n0n\ge n_0n≥n0​ admits a code with M>0M>0M>0 input density matrices ρm\rho_mρm​ on AnA^nAn and measurement matrices Dj⪰0D_j\succeq0Dj​⪰0 on BnB^nBn satisfying ∑jDj=IBn\sum_jD_j=I_{B^n}∑j​Dj​=IBn​, for which

∥Ω−J∥1<ε,r−s≤log⁡2Mn.\|\Omega-J\|_1<\varepsilon,\qquad r-s\le \frac{\log_2 M}{n}.∥Ω−J∥1​<ε,r−s≤nlog2​M​.

Here AnA^nAn denotes functions from {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} to AAA, similarly for Bn,EnB^n,E^nBn,En, and

(Un)(b,e),a=∏i=0n−1U(bi,ei),ai,Ω(m,j,e),(m′,j′,e′)={M−1∑b,c∈Bn(Dj)c,b(UnρmUn†)(b,e),(c,e′),m=m′, j=j′,0,otherwise.(U_n)_{(b,e),a}=\prod_{i=0}^{n-1}U_{(b_i,e_i),a_i},\qquad \Omega_{(m,j,e),(m',j',e')}= \begin{cases} \displaystyle M^{-1}\sum_{b,c\in B^n}(D_j)_{c,b} (U_n\rho_mU_n^\dagger)_{(b,e),(c,e')},&m=m',\ j=j',\\ 0,&\text{otherwise}. \end{cases}(Un​)(b,e),a​=i=0∏n−1​U(bi​,ei​),ai​​,Ω(m,j,e),(m′,j′,e′)​=⎩⎨⎧​M−1b,c∈Bn∑​(Dj​)c,b​(Un​ρm​Un†​)(b,e),(c,e′)​,0,​m=m′, j=j′,otherwise.​

Writing σe,e′=∑m,jΩ(m,j,e),(m,j,e′)\sigma_{e,e'}=\sum_{m,j}\Omega_{(m,j,e),(m,j,e')}σe,e′​=∑m,j​Ω(m,j,e),(m,j,e′)​, the matrix JJJ has entry M−1σe,e′M^{-1}\sigma_{e,e'}M−1σe,e′​ when m=j=m′=j′m=j=m'=j'm=j=m′=j′, and zero otherwise; ∥X∥1=Re⁡tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}∥X∥1​=RetrX†X​. The code may depend on ε,s,n\varepsilon,s,nε,s,n, and the positive threshold excludes division by zero in the rate condition. No isometry condition on UUU is included.

QAlgorithms.Papers.Independent.Support50.P07.KeyCode

For finite types III and OOO, with decidable equality on OOO, a key code consists of a natural number M>0M>0M>0, matrices ρm∈CI×I\rho_m\in\mathbb C^{I\times I}ρm​∈CI×I for m=0,…,M−1m=0,\ldots,M-1m=0,…,M−1, and matrices Dm∈CO×OD_m\in\mathbb C^{O\times O}Dm​∈CO×O for the same indices, subject to

ρm⪰0,tr⁡ρm=1,Dm⪰0,∑m=0M−1Dm=IO.\rho_m\succeq0,\qquad \operatorname{tr}\rho_m=1,\qquad D_m\succeq0,\qquad \sum_{m=0}^{M-1}D_m=I_O.ρm​⪰0,trρm​=1,Dm​⪰0,m=0∑M−1​Dm​=IO​.

Thus every input matrix is a density matrix and the measurement matrices form a positive operator valued measurement. There is no requirement that the inputs be pure or distinct. The message set cannot be empty; an empty input type III makes the density matrix requirements impossible, whereas an empty output type OOO is allowed.

QAlgorithms.Papers.Independent.Support50.P07.ProcessedEnsemble

For a finite type III, a processed ensemble consists of positive natural numbers NX,NTN_X,N_TNX​,NT​, real weights pxp_xpx​ for 0≤x<NX0\le x<N_X0≤x<NX​, vectors ψx∈CI\psi_x\in\mathbb C^Iψx​∈CI, and real numbers qx,tq_{x,t}qx,t​ for 0≤x<NX0\le x<N_X0≤x<NX​, 0≤t<NT0\le t<N_T0≤t<NT​, satisfying

px≥0,∑xpx=1,∥ψx∥2=1,qx,t≥0,∑tqx,t=1for every x.p_x\ge0,\qquad \sum_xp_x=1,\qquad \|\psi_x\|_2=1,\qquad q_{x,t}\ge0,\qquad \sum_tq_{x,t}=1\quad\text{for every }x.px​≥0,x∑​px​=1,∥ψx​∥2​=1,qx,t​≥0,t∑​qx,t​=1for every x.

Weights and processing probabilities may vanish, and different labels may have identical vectors. Every vector must have norm one, including vectors with zero weight; consequently no such ensemble exists when III is empty.

QAlgorithms.Papers.Independent.Support50.P07.SSPrivateAchievable

For finite index types A,B,EA,B,EA,B,E, an arbitrary complex matrix U:A→B×EU:A\to B\times EU:A→B×E, and a real number rrr, this predicate means that r≥0r\ge0r≥0 and, for every ε>0\varepsilon>0ε>0 and s>0s>0s>0, there is a positive integer n0n_0n0​ such that every n≥n0n\ge n_0n≥n0​ admits a positive integer ddd and a code with M>0M>0M>0 density matrices ρm\rho_mρm​ on An×(Fd×Fd)A^n\times(F_d\times F_d)An×(Fd​×Fd​) and measurement matrices Dj⪰0D_j\succeq0Dj​⪰0 on Bn×FdB^n\times F_dBn×Fd​ summing to the identity, where Fd={0,…,d−1}F_d=\{0,\ldots,d-1\}Fd​={0,…,d−1}. Each ρm\rho_mρm​ must be unchanged by swapping the two FdF_dFd​ coordinates separately in either its row or its column, and the code must satisfy

∥Ω−J∥1<ε,r−s≤log⁡2Mn.\|\Omega-J\|_1<\varepsilon,\qquad r-s\le\frac{\log_2M}{n}.∥Ω−J∥1​<ε,r−s≤nlog2​M​.

Here the matrix used by the code is

V((b,f),(e,g)),(a,(h,k))=(∏i=0n−1U(bi,ei),ai)1{f=h, g=k},V_{((b,f),(e,g)),(a,(h,k))} =\left(\prod_{i=0}^{n-1}U_{(b_i,e_i),a_i}\right) \mathbf1_{\{f=h,\ g=k\}},V((b,f),(e,g)),(a,(h,k))​=(i=0∏n−1​U(bi​,ei​),ai​​)1{f=h, g=k}​,

with receiver index β∈Bn×Fd\beta\in B^n\times F_dβ∈Bn×Fd​ and environment index ξ∈En×Fd\xi\in E^n\times F_dξ∈En×Fd​; its decoded matrix is

Ω(m,j,ξ),(m′,j′,ξ′)={M−1∑β,γ(Dj)γ,β(VρmV†)(β,ξ),(γ,ξ′),m=m′, j=j′,0,otherwise.\Omega_{(m,j,\xi),(m',j',\xi')}= \begin{cases} \displaystyle M^{-1}\sum_{\beta,\gamma}(D_j)_{\gamma,\beta} (V\rho_mV^\dagger)_{(\beta,\xi),(\gamma,\xi')},&m=m',\ j=j',\\ 0,&\text{otherwise}. \end{cases}Ω(m,j,ξ),(m′,j′,ξ′)​=⎩⎨⎧​M−1β,γ∑​(Dj​)γ,β​(Vρm​V†)(β,ξ),(γ,ξ′)​,0,​m=m′, j=j′,otherwise.​

Writing σξ,ξ′=∑m,jΩ(m,j,ξ),(m,j,ξ′)\sigma_{\xi,\xi'}=\sum_{m,j}\Omega_{(m,j,\xi),(m,j,\xi')}σξ,ξ′​=∑m,j​Ω(m,j,ξ),(m,j,ξ′)​, the entry of JJJ is M−1σξ,ξ′M^{-1}\sigma_{\xi,\xi'}M−1σξ,ξ′​ when m=j=m′=j′m=j=m'=j'm=j=m′=j′, and zero otherwise, and ∥X∥1=Re⁡tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}∥X∥1​=RetrX†X​. Both ddd and the code may depend on ε,s,n\varepsilon,s,nε,s,n; there is no upper bound on ddd and no isometry assumption on UUU.

QAlgorithms.Papers.Independent.Support50.P07.SymmetricInput

For every natural number ddd, this abbreviates the type of pairs (i,j)(i,j)(i,j) of integers satisfying 0≤i<d0\le i<d0≤i<d, 0≤j<d0\le j<d0≤j<d, and i≤ji\le ji≤j. Diagonal pairs are included; when d=0d=0d=0, the type is empty.

QAlgorithms.Papers.Independent.Support50.P07.SymmetricSupport

For a type AAA, a natural number ddd, and any complex matrix ρ\rhoρ indexed by A×({0,…,d−1}×{0,…,d−1})A\times(\{0,\ldots,d-1\}\times\{0,\ldots,d-1\})A×({0,…,d−1}×{0,…,d−1}), this predicate requires invariance under exchanging the two ddd-valued coordinates separately in the row and in the column:

ρ(a,(f,g)),j=ρ(a,(g,f)),jfor every a,f,g,j,ρi,(a,(f,g))=ρi,(a,(g,f))for every i,a,f,g.\rho_{(a,(f,g)),j}=\rho_{(a,(g,f)),j} \quad\text{for every }a,f,g,j, \qquad \rho_{i,(a,(f,g))}=\rho_{i,(a,(g,f))} \quad\text{for every }i,a,f,g.ρ(a,(f,g)),j​=ρ(a,(g,f)),j​for every a,f,g,j,ρi,(a,(f,g))​=ρi,(a,(g,f))​for every i,a,f,g.

No positivity, Hermitian symmetry, or trace condition is required. For d=0d=0d=0 the conditions are vacuous, and for d=1d=1d=1 they hold automatically.

QAlgorithms.Papers.Independent.Support50.P07.amplitudeDampingChannel

For every real number γ\gammaγ, this defines the map on complex 2×22\times22×2 matrices

ρ⟼K0ρK0†+K1ρK1†,K0=(1001−γ),K1=(0γ00).\rho\longmapsto K_0\rho K_0^\dagger+K_1\rho K_1^\dagger, \qquad K_0=\begin{pmatrix}1&0\\0&\sqrt{1-\gamma}\end{pmatrix}, \qquad K_1=\begin{pmatrix}0&\sqrt\gamma\\0&0\end{pmatrix}.ρ⟼K0​ρK0†​+K1​ρK1†​,K0​=(10​01−γ​​),K1​=(00​γ​0​).

The square roots are real square roots embedded into C\mathbb CC, and equal 000 for negative arguments. The definition includes γ=0\gamma=0γ=0, γ=1\gamma=1γ=1, and values outside [0,1][0,1][0,1]; it imposes no density condition on ρ\rhoρ.

QAlgorithms.Papers.Independent.Support50.P07.assistedDilation

For finite types A,B,EA,B,EA,B,E, an arbitrary complex matrix U∈C(B×E)×AU\in\mathbb C^{(B\times E)\times A}U∈C(B×E)×A, and any natural number ddd, this definition produces a complex matrix VVV from A×({0,…,d−1}×{0,…,d−1})A\times(\{0,\ldots,d-1\}\times\{0,\ldots,d-1\})A×({0,…,d−1}×{0,…,d−1}) to (B×{0,…,d−1})×(E×{0,…,d−1})(B\times\{0,\ldots,d-1\})\times(E\times\{0,\ldots,d-1\})(B×{0,…,d−1})×(E×{0,…,d−1}), given by

V((b,f),(e,g)),(a,(h,k))={U(b,e),a,f=h and g=k,0,otherwise.V_{((b,f),(e,g)),(a,(h,k))} = \begin{cases} U_{(b,e),a},&f=h\ \text{and }g=k,\\ 0,&\text{otherwise}. \end{cases}V((b,f),(e,g)),(a,(h,k))​={U(b,e),a​,0,​f=h and g=k,otherwise.​

There are no isometry or positivity requirements on UUU, and d=0d=0d=0 is permitted, in which case both matrix index types are empty.

QAlgorithms.Papers.Independent.Support50.P07.dampingBound

For every real number γ\gammaγ, this defines

D(γ)=sup⁡ 0≤t≤1[H2 ⁣(t(1−γ))−H2(tγ)],H2(x)=−xL(x)−(1−x)L(1−x)ln⁡2,D(\gamma)= \sup_{\,0\le t\le1} \left[H_2\!\left(t(1-\gamma)\right)-H_2(t\gamma)\right], \qquad H_2(x)=\frac{-xL(x)-(1-x)L(1-x)}{\ln2},D(γ)=0≤t≤1sup​[H2​(t(1−γ))−H2​(tγ)],H2​(x)=ln2−xL(x)−(1−x)L(1−x)​,

where L(x)=ln⁡∣x∣L(x)=\ln|x|L(x)=ln∣x∣ for x≠0x\ne0x=0 and L(0)=0L(0)=0L(0)=0. The supremum is taken in the real numbers over the entire closed interval, including t=0,1t=0,1t=0,1; no restriction on γ\gammaγ is imposed, so the entropy formula is also used outside its usual probability range.

QAlgorithms.Papers.Independent.Support50.P07.decodedJoint

For finite index types A,B,EA,B,EA,B,E, with decidable equality on BBB, an arbitrary complex matrix U∈C(B×E)×AU\in\mathbb C^{(B\times E)\times A}U∈C(B×E)×A, and a key code consisting of M>0M>0M>0 density matrices ρm\rho_mρm​ on AAA and positive semidefinite matrices DjD_jDj​ on BBB satisfying ∑jDj=IB\sum_jD_j=I_B∑j​Dj​=IB​, this definition produces the matrix Ω\OmegaΩ indexed by triples (m,j,e)(m,j,e)(m,j,e), where m,j∈{0,…,M−1}m,j\in\{0,\ldots,M-1\}m,j∈{0,…,M−1} and e∈Ee\in Ee∈E, with entries

Ω(m,j,e),(m′,j′,e′)={1M∑b,c∈B(Dj)c,b(UρmU†)(b,e),(c,e′),m=m′ and j=j′,0,otherwise.\Omega_{(m,j,e),(m',j',e')}= \begin{cases} \displaystyle \frac1M\sum_{b,c\in B}(D_j)_{c,b} (U\rho_mU^\dagger)_{(b,e),(c,e')}, &m=m'\ \text{and }j=j',\\ 0,&\text{otherwise}. \end{cases}Ω(m,j,e),(m′,j′,e′)​=⎩⎨⎧​M1​b,c∈B∑​(Dj​)c,b​(Uρm​U†)(b,e),(c,e′)​,0,​m=m′ and j=j′,otherwise.​

No isometry or normalization condition is imposed on UUU.

QAlgorithms.Papers.Independent.Support50.P07.degradableMixingCost

For finite index types A,B,EA,B,EA,B,E with decidable equality and any complex matrix U:CA→CB×EU:\mathbb C^A\to\mathbb C^{B\times E}U:CA→CB×E, this defines the real infimum of

∑i<kpisup⁡σ⪰0, tr⁡σ=1[H ⁣(Tr⁡ei(viσvi†))−H ⁣(Tr⁡bi(viσvi†))].\sum_{i<k}p_i \sup_{\sigma\succeq0,\ \operatorname{tr}\sigma=1} \left[ H\!\left(\operatorname{Tr}_{e_i}(v_i\sigma v_i^\dagger)\right) -H\!\left(\operatorname{Tr}_{b_i}(v_i\sigma v_i^\dagger)\right) \right].i<k∑​pi​σ⪰0, trσ=1sup​[H(Trei​​(vi​σvi†​))−H(Trbi​​(vi​σvi†​))].

The infimum ranges over positive integers kkk, nonnegative weights pip_ipi​ summing to 111, positive integers bi,eib_i,e_ibi​,ei​, isometries vi:CA→Cbi×eiv_i:\mathbb C^A\to\mathbb C^{b_i\times e_i}vi​:CA→Cbi​×ei​, and maps PiP_iPi​ such that

Tr⁡E(UρU†)=∑i<kpiPi ⁣(Tr⁡ei(viρvi†))for every complex matrix ρ.\operatorname{Tr}_E(U\rho U^\dagger) =\sum_{i<k}p_iP_i\!\left(\operatorname{Tr}_{e_i}(v_i\rho v_i^\dagger)\right) \quad\text{for every complex matrix }\rho.TrE​(UρU†)=i<k∑​pi​Pi​(Trei​​(vi​ρvi†​))for every complex matrix ρ.

Each PiP_iPi​ must have a finite representation Pi(X)=∑jKijXKij†P_i(X)=\sum_jK_{ij}XK_{ij}^\daggerPi​(X)=∑j​Kij​XKij†​, with ∑jKij†Kij=Ibi\sum_jK_{ij}^\dagger K_{ij}=I_{b_i}∑j​Kij†​Kij​=Ibi​​. In addition, for each iii, there must be a map with a finite Kraus representation and the corresponding identity normalization that transforms the receiver marginal Tr⁡ei(viρvi†)\operatorname{Tr}_{e_i}(v_i\rho v_i^\dagger)Trei​​(vi​ρvi†​) into the environment marginal Tr⁡bi(viρvi†)\operatorname{Tr}_{b_i}(v_i\rho v_i^\dagger)Trbi​​(vi​ρvi†​) for every ρ\rhoρ, or a map of that form performing the reverse transformation. Here isometry means vi†vi=IAv_i^\dagger v_i=I_Avi†​vi​=IA​, and H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), using continuous functional calculus for f(s)=slog⁡2sf(s)=s\log_2sf(s)=slog2​s. Zero weights are permitted without removing any component conditions. The definition asserts neither existence of an admissible decomposition nor attainment of the infimum; if the defining set is empty, its real infimum is 000.

QAlgorithms.Papers.Independent.Support50.P07.degradableMixingCosts

For finite index types A,B,EA,B,EA,B,E with decidable equality and any complex matrix U:CA→CB×EU:\mathbb C^A\to\mathbb C^{B\times E}U:CA→CB×E, this defines a set of real numbers rrr. Membership means that there exist an integer k>0k>0k>0, nonnegative real weights pip_ipi​ with ∑i<kpi=1\sum_{i<k}p_i=1∑i<k​pi​=1, positive integers bi,eib_i,e_ibi​,ei​, matrices vi:CA→Cbi×eiv_i:\mathbb C^A\to\mathbb C^{b_i\times e_i}vi​:CA→Cbi​×ei​, and maps PiP_iPi​ from bi×bib_i\times b_ibi​×bi​ matrices to B×BB\times BB×B matrices, satisfying

vi†vi=IA,Tr⁡E(UρU†)=∑i<kpiPi ⁣(Tr⁡ei(viρvi†))for every complex matrix ρ.v_i^\dagger v_i=I_A,\qquad \operatorname{Tr}_E(U\rho U^\dagger) =\sum_{i<k}p_iP_i\!\left(\operatorname{Tr}_{e_i}(v_i\rho v_i^\dagger)\right) \quad\text{for every complex matrix }\rho.vi†​vi​=IA​,TrE​(UρU†)=i<k∑​pi​Pi​(Trei​​(vi​ρvi†​))for every complex matrix ρ.

Each PiP_iPi​ must admit a finite Kraus representation Pi(X)=∑jKijXKij†P_i(X)=\sum_jK_{ij}XK_{ij}^\daggerPi​(X)=∑j​Kij​XKij†​ with ∑jKij†Kij=Ibi\sum_jK_{ij}^\dagger K_{ij}=I_{b_i}∑j​Kij†​Kij​=Ibi​​. For each iii, at least one of the following must hold: a map of this same Kraus form sends Tr⁡ei(viρvi†)\operatorname{Tr}_{e_i}(v_i\rho v_i^\dagger)Trei​​(vi​ρvi†​) to Tr⁡bi(viρvi†)\operatorname{Tr}_{b_i}(v_i\rho v_i^\dagger)Trbi​​(vi​ρvi†​) for every ρ\rhoρ; or such a map sends the latter marginal to the former for every ρ\rhoρ. Finally,

r=∑i<kpisup⁡σ⪰0, tr⁡σ=1[H ⁣(Tr⁡ei(viσvi†))−H ⁣(Tr⁡bi(viσvi†))],r=\sum_{i<k}p_i \sup_{\sigma\succeq0,\ \operatorname{tr}\sigma=1} \left[ H\!\left(\operatorname{Tr}_{e_i}(v_i\sigma v_i^\dagger)\right) -H\!\left(\operatorname{Tr}_{b_i}(v_i\sigma v_i^\dagger)\right) \right],r=i<k∑​pi​σ⪰0, trσ=1sup​[H(Trei​​(vi​σvi†​))−H(Trbi​​(vi​σvi†​))],

where H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), with f(s)=slog⁡2sf(s)=s\log_2sf(s)=slog2​s evaluated by continuous functional calculus. Every component must satisfy these conditions even when pi=0p_i=0pi​=0, and both alternatives may hold. No isometry hypothesis on UUU itself is imposed.

QAlgorithms.Papers.Independent.Support50.P07.depolarizingChannel

For every real number ppp, this defines a map on all complex 2×22\times22×2 matrices by

ρ⟼(1−p)ρ+p3(XρX†+YρY†+ZρZ†),\rho\longmapsto (1-p)\rho+\frac p3\bigl(X\rho X^\dagger+Y\rho Y^\dagger+Z\rho Z^\dagger\bigr),ρ⟼(1−p)ρ+3p​(XρX†+YρY†+ZρZ†),

where

X=(0110),Y=(0−ii0),Z=(100−1).X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.X=(01​10​),Y=(0i​−i0​),Z=(10​0−1​).

The parameter ppp is unrestricted, and the map is defined on every matrix, without requiring positivity or trace one.

QAlgorithms.Papers.Independent.Support50.P07.depolarizingDampingParameter

For every real number ppp, this defines

41−p(1−1−p).4\sqrt{1-p}\left(1-\sqrt{1-p}\right).41−p​(1−1−p​).

The square root is the total real square root, which is zero on negative arguments; consequently the defined value is zero whenever p≥1p\ge1p≥1. No interval restriction on ppp is assumed.

QAlgorithms.Papers.Independent.Support50.P07.depolarizingEnvelope

For every real number ppp, this defines the real infimum

inf⁡{∑i=0k−1wimin⁡ ⁣{1−H2(xi), D ⁣(41−xi(1−1−xi)), max⁡(1−4xi,0)} | k∈N, k>0,wi≥0,0≤xi≤1,∑iwi=1,∑iwixi=p},\inf\left\{ \sum_{i=0}^{k-1}w_i \min\!\left\{1-H_2(x_i),\, D\!\left(4\sqrt{1-x_i}(1-\sqrt{1-x_i})\right),\, \max(1-4x_i,0)\right\} \ \middle|\ \begin{array}{l} k\in\mathbb N,\ k>0,\quad w_i\ge0,\quad 0\le x_i\le1,\\ \sum_iw_i=1,\quad \sum_iw_ix_i=p \end{array} \right\},inf{i=0∑k−1​wi​min{1−H2​(xi​),D(41−xi​​(1−1−xi​​)),max(1−4xi​,0)} ​ k∈N, k>0,wi​≥0,0≤xi​≤1,∑i​wi​=1,∑i​wi​xi​=p​},

where

H2(x)=−xL(x)−(1−x)L(1−x)ln⁡2,D(g)=sup⁡0≤t≤1[H2(t(1−g))−H2(tg)],H_2(x)=\frac{-xL(x)-(1-x)L(1-x)}{\ln2}, \qquad D(g)=\sup_{0\le t\le1}\bigl[H_2(t(1-g))-H_2(tg)\bigr],H2​(x)=ln2−xL(x)−(1−x)L(1−x)​,D(g)=0≤t≤1sup​[H2​(t(1−g))−H2​(tg)],

and L(x)=ln⁡∣x∣L(x)=\ln|x|L(x)=ln∣x∣ for x≠0x\ne0x=0, with L(0)=0L(0)=0L(0)=0. Zero weights and repeated values of xix_ixi​ are allowed. The parameter ppp is unrestricted; if p∉[0,1]p\notin[0,1]p∈/[0,1], the set under the infimum is empty and its real infimum, under the convention used here, is zero.

QAlgorithms.Papers.Independent.Support50.P07.erasureMap

For every natural number ddd and real number ppp, this defines a map from complex matrices indexed by {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1} to complex matrices indexed by those same labels together with an additional label ⊥\bot⊥. For every input matrix ρ\rhoρ, its output is specified by

Ed,p(ρ)a,b=(1−p)ρa,b,Ed,p(ρ)⊥,⊥=p tr⁡ρ,Ed,p(ρ)a,⊥=Ed,p(ρ)⊥,a=0.\mathcal E_{d,p}(\rho)_{a,b}=(1-p)\rho_{a,b},\qquad \mathcal E_{d,p}(\rho)_{\bot,\bot}=p\,\operatorname{tr}\rho,\qquad \mathcal E_{d,p}(\rho)_{a,\bot} =\mathcal E_{d,p}(\rho)_{\bot,a}=0.Ed,p​(ρ)a,b​=(1−p)ρa,b​,Ed,p​(ρ)⊥,⊥​=ptrρ,Ed,p​(ρ)a,⊥​=Ed,p​(ρ)⊥,a​=0.

No restriction on ppp or normalization condition on ρ\rhoρ is imposed. The definition includes d=0d=0d=0, when the input has no entries and the output is the zero matrix on the single label ⊥\bot⊥.

QAlgorithms.Papers.Independent.Support50.P07.fullTracePrivateCapacity

For finite index types A,B,EA,B,EA,B,E and an arbitrary complex matrix U:A→B×EU:A\to B\times EU:A→B×E, this definition is the real supremum of all r≥0r\ge0r≥0 with the following property: for every ε>0\varepsilon>0ε>0 and s>0s>0s>0, every sufficiently large positive integer nnn admits M>0M>0M>0 density matrices ρm\rho_mρm​ on AnA^nAn and measurement matrices Dj⪰0D_j\succeq0Dj​⪰0 on BnB^nBn summing to the identity, such that log⁡2(M)/n≥r−s\log_2(M)/n\ge r-slog2​(M)/n≥r−s and ∥Ω−J∥1<ε\|\Omega-J\|_1<\varepsilon∥Ω−J∥1​<ε. Explicitly, setting (Un)(b,e),a=∏i=0n−1U(bi,ei),ai(U_n)_{(b,e),a}=\prod_{i=0}^{n-1}U_{(b_i,e_i),a_i}(Un​)(b,e),a​=∏i=0n−1​U(bi​,ei​),ai​​,

Ω(m,j,e),(m′,j′,e′)={M−1∑b,c∈Bn(Dj)c,b(UnρmUn†)(b,e),(c,e′),m=m′, j=j′,0,otherwise,\Omega_{(m,j,e),(m',j',e')}= \begin{cases} \displaystyle M^{-1}\sum_{b,c\in B^n}(D_j)_{c,b} (U_n\rho_mU_n^\dagger)_{(b,e),(c,e')},&m=m',\ j=j',\\ 0,&\text{otherwise}, \end{cases}Ω(m,j,e),(m′,j′,e′)​=⎩⎨⎧​M−1b,c∈Bn∑​(Dj​)c,b​(Un​ρm​Un†​)(b,e),(c,e′)​,0,​m=m′, j=j′,otherwise,​

and, with σe,e′=∑m,jΩ(m,j,e),(m,j,e′)\sigma_{e,e'}=\sum_{m,j}\Omega_{(m,j,e),(m,j,e')}σe,e′​=∑m,j​Ω(m,j,e),(m,j,e′)​, the entry of JJJ is M−1σe,e′M^{-1}\sigma_{e,e'}M−1σe,e′​ when m=j=m′=j′m=j=m'=j'm=j=m′=j′, and zero otherwise; ∥X∥1=Re⁡tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}∥X∥1​=RetrX†X​. Here An,Bn,EnA^n,B^n,E^nAn,Bn,En are the corresponding length nnn function spaces. The supremum is taken in R\mathbb RR, with the real supremum convention giving zero for an empty or unbounded-above set. No isometry condition on UUU is part of the definition.

QAlgorithms.Papers.Independent.Support50.P07.independentPauliChannel

For every real number qqq, this defines a map on all complex 2×22\times22×2 matrices by

ρ⟼(1−q)2ρ+q(1−q)XρX†+q2YρY†+q(1−q)ZρZ†,\rho\longmapsto (1-q)^2\rho +q(1-q)X\rho X^\dagger +q^2Y\rho Y^\dagger +q(1-q)Z\rho Z^\dagger,ρ⟼(1−q)2ρ+q(1−q)XρX†+q2YρY†+q(1−q)ZρZ†,

where

X=(0110),Y=(0−ii0),Z=(100−1).X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.X=(01​10​),Y=(0i​−i0​),Z=(10​0−1​).

There is no restriction 0≤q≤10\le q\le10≤q≤1, and the input need not be a density matrix.

QAlgorithms.Papers.Independent.Support50.P07.keyError

For finite index types A,B,EA,B,EA,B,E, an arbitrary complex matrix U:A→B×EU:A\to B\times EU:A→B×E, and a key code with M>0M>0M>0, input density matrices ρm\rho_mρm​, and measurement matrices Dj⪰0D_j\succeq0Dj​⪰0 summing to IBI_BIB​, define

Ω(m,j,e),(m′,j′,e′)={M−1∑b,c∈B(Dj)c,b(UρmU†)(b,e),(c,e′),m=m′, j=j′,0,otherwise,σe,e′=∑m,jΩ(m,j,e),(m,j,e′).\Omega_{(m,j,e),(m',j',e')}= \begin{cases} \displaystyle M^{-1}\sum_{b,c\in B}(D_j)_{c,b} (U\rho_mU^\dagger)_{(b,e),(c,e')},&m=m',\ j=j',\\ 0,&\text{otherwise}, \end{cases} \qquad \sigma_{e,e'}=\sum_{m,j}\Omega_{(m,j,e),(m,j,e')}.Ω(m,j,e),(m′,j′,e′)​=⎩⎨⎧​M−1b,c∈B∑​(Dj​)c,b​(Uρm​U†)(b,e),(c,e′)​,0,​m=m′, j=j′,otherwise,​σe,e′​=m,j∑​Ω(m,j,e),(m,j,e′)​.

The key error is ∥Ω−J∥1\|\Omega-J\|_1∥Ω−J∥1​, where

J(m,j,e),(m′,j′,e′)={M−1σe,e′,m=j, m′=j′, m=m′,0,otherwise,∥X∥1=Re⁡tr⁡X†X.J_{(m,j,e),(m',j',e')}= \begin{cases} M^{-1}\sigma_{e,e'},&m=j,\ m'=j',\ m=m',\\ 0,&\text{otherwise}, \end{cases} \qquad \|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}.J(m,j,e),(m′,j′,e′)​={M−1σe,e′​,0,​m=j, m′=j′, m=m′,otherwise,​∥X∥1​=RetrX†X​.

The square root is defined by continuous functional calculus. This definition uses the full trace norm, with no factor of 1/21/21/2, and imposes no isometry condition on UUU.

QAlgorithms.Papers.Independent.Support50.P07.pauliMatrices

This defines four complex 2×22\times22×2 matrices, with rows and columns ordered 0,10,10,1:

P0=(1001),P1=(0110),P2=(0−ii0),P3=(100−1),P_0=\begin{pmatrix}1&0\\0&1\end{pmatrix},\qquad P_1=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad P_2=\begin{pmatrix}0&-\mathrm i\\\mathrm i&0\end{pmatrix},\qquad P_3=\begin{pmatrix}1&0\\0&-1\end{pmatrix},P0​=(10​01​),P1​=(01​10​),P2​=(0i​−i0​),P3​=(10​0−1​),

where i2=−1\mathrm i^2=-1i2=−1.

QAlgorithms.Papers.Independent.Support50.P07.privateInformationValue

For finite index types A,B,EA,B,EA,B,E, an arbitrary complex matrix U:A→B×EU:A\to B\times EU:A→B×E, and a processed ensemble with positive label counts NX,NTN_X,N_TNX​,NT​, probabilities pxp_xpx​, unit vectors ψx∈CA\psi_x\in\mathbb C^Aψx​∈CA, and processing probabilities qx,tq_{x,t}qx,t​ satisfying px,qx,t≥0p_x,q_{x,t}\ge0px​,qx,t​≥0, ∑xpx=1\sum_xp_x=1∑x​px​=1, and ∑tqx,t=1\sum_tq_{x,t}=1∑t​qx,t​=1 for every xxx, form matrices ΘB\Theta_BΘB​ on {0,…,NT−1}×B\{0,\ldots,N_T-1\}\times B{0,…,NT​−1}×B and ΘE\Theta_EΘE​ on {0,…,NT−1}×E\{0,\ldots,N_T-1\}\times E{0,…,NT​−1}×E by

(ΘB)(t,b),(t′,b′)=1{t=t′}∑xpxqx,t∑e∈E(Uψxψx†U†)(b,e),(b′,e),(ΘE)(t,e),(t′,e′)=1{t=t′}∑xpxqx,t∑b∈B(Uψxψx†U†)(b,e),(b,e′).(\Theta_B)_{(t,b),(t',b')}= \mathbf1_{\{t=t'\}}\sum_xp_xq_{x,t}\sum_{e\in E} (U\psi_x\psi_x^\dagger U^\dagger)_{(b,e),(b',e)}, \qquad (\Theta_E)_{(t,e),(t',e')}= \mathbf1_{\{t=t'\}}\sum_xp_xq_{x,t}\sum_{b\in B} (U\psi_x\psi_x^\dagger U^\dagger)_{(b,e),(b,e')}.(ΘB​)(t,b),(t′,b′)​=1{t=t′}​x∑​px​qx,t​e∈E∑​(Uψx​ψx†​U†)(b,e),(b′,e)​,(ΘE​)(t,e),(t′,e′)​=1{t=t′}​x∑​px​qx,t​b∈B∑​(Uψx​ψx†​U†)(b,e),(b,e′)​.

The defined value is

[H(tr⁡BΘB)+H(tr⁡TΘB)−H(ΘB)]−[H(tr⁡EΘE)+H(tr⁡TΘE)−H(ΘE)],\bigl[H(\operatorname{tr}_B\Theta_B)+H(\operatorname{tr}_T\Theta_B)-H(\Theta_B)\bigr] - \bigl[H(\operatorname{tr}_E\Theta_E)+H(\operatorname{tr}_T\Theta_E)-H(\Theta_E)\bigr],[H(trB​ΘB​)+H(trT​ΘB​)−H(ΘB​)]−[H(trE​ΘE​)+H(trT​ΘE​)−H(ΘE​)],

where each partial trace sums over the indicated coordinate, (ψxψx†)a,a′=ψx(a)ψx(a′)‾(\psi_x\psi_x^\dagger)_{a,a'}=\psi_x(a)\overline{\psi_x(a')}(ψx​ψx†​)a,a′​=ψx​(a)ψx​(a′)​, and H(X)=−Re⁡tr⁡f(X)H(X)=-\operatorname{Re}\operatorname{tr}f(X)H(X)=−Retrf(X), with f(u)=ulog⁡2uf(u)=u\log_2uf(u)=ulog2​u applied by continuous functional calculus and the real logarithm convention log⁡20=0\log_2 0=0log2​0=0. No isometry condition on UUU, or trace-one condition on the two resulting matrices, is assumed.

QAlgorithms.Papers.Independent.Support50.P07.processedPrivateInformation

For finite index types A,B,EA,B,EA,B,E with decidable equality and any complex matrix UUU with rows indexed by B×EB\times EB×E and columns by AAA, define NU(X)=Tr⁡E(UXU†)N_U(X)=\operatorname{Tr}_E(UXU^\dagger)NU​(X)=TrE​(UXU†) and NUc(X)=Tr⁡B(UXU†)N_U^c(X)=\operatorname{Tr}_B(UXU^\dagger)NUc​(X)=TrB​(UXU†). The quantity defined here is the real supremum of

I(ΩTB)−I(ΩTE)I(\Omega_{TB})-I(\Omega_{TE})I(ΩTB​)−I(ΩTE​)

over all positive integers nx,ntn_x,n_tnx​,nt​, nonnegative weights wxw_xwx​ summing to 111, unit vectors ψx∈CA\psi_x\in\mathbb C^Aψx​∈CA, and nonnegative numbers p(t∣x)p(t\mid x)p(t∣x) satisfying ∑tp(t∣x)=1\sum_t p(t\mid x)=1∑t​p(t∣x)=1 for every xxx. Here x=0,…,nx−1x=0,\ldots,n_x-1x=0,…,nx​−1, t=0,…,nt−1t=0,\ldots,n_t-1t=0,…,nt​−1, and, for N=NUN=N_UN=NU​ or NUcN_U^cNUc​, the corresponding block matrix is

ΩTN((t,b),(t′,b′))={∑xwxp(t∣x) [N(ψxψx†)]b,b′,t=t′,0,t≠t′.\Omega_{TN}\bigl((t,b),(t',b')\bigr) =\begin{cases} \displaystyle\sum_x w_xp(t\mid x)\,[N(\psi_x\psi_x^\dagger)]_{b,b'},&t=t',\\ 0,&t\ne t'. \end{cases}ΩTN​((t,b),(t′,b′))=⎩⎨⎧​x∑​wx​p(t∣x)[N(ψx​ψx†​)]b,b′​,0,​t=t′,t=t′.​

For a matrix Ω\OmegaΩ indexed by a product, I(Ω)=H(Tr⁡2Ω)+H(Tr⁡1Ω)−H(Ω)I(\Omega)=H(\operatorname{Tr}_2\Omega)+H(\operatorname{Tr}_1\Omega)-H(\Omega)I(Ω)=H(Tr2​Ω)+H(Tr1​Ω)−H(Ω), where H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), f(s)=slog⁡2sf(s)=s\log_2sf(s)=slog2​s, and f(X)f(X)f(X) is evaluated by continuous functional calculus. All signals, including those with zero weight, must be unit vectors, and every processing row must sum to 111. No isometry assumption on UUU is imposed, and the definition does not assert attainment of the supremum.

QAlgorithms.Papers.Independent.Support50.P07.processedState

For finite types A,BA,BA,B, a processed ensemble on AAA with positive label counts NX,NTN_X,N_TNX​,NT​, weights px≥0p_x\ge0px​≥0 summing to one, unit vectors ψx\psi_xψx​, and numbers qx,t≥0q_{x,t}\ge0qx,t​≥0 satisfying ∑tqx,t=1\sum_tq_{x,t}=1∑t​qx,t​=1 for each xxx, and any function Φ:CA×A→CB×B\Phi:\mathbb C^{A\times A}\to\mathbb C^{B\times B}Φ:CA×A→CB×B, this definition produces the matrix

Θ(t,b),(t′,b′)={∑x=0NX−1pxqx,t Φ(ψxψx†)b,b′,t=t′,0,t≠t′,(ψxψx†)a,a′=ψx(a)ψx(a′)‾.\Theta_{(t,b),(t',b')}= \begin{cases} \displaystyle\sum_{x=0}^{N_X-1}p_xq_{x,t}\, \Phi(\psi_x\psi_x^\dagger)_{b,b'},&t=t',\\ 0,&t\ne t', \end{cases} \qquad (\psi_x\psi_x^\dagger)_{a,a'}=\psi_x(a)\overline{\psi_x(a')}.Θ(t,b),(t′,b′)​=⎩⎨⎧​x=0∑NX​−1​px​qx,t​Φ(ψx​ψx†​)b,b′​,0,​t=t′,t=t′,​(ψx​ψx†​)a,a′​=ψx​(a)ψx​(a′)​.

The function Φ\PhiΦ, despite the argument name “channel,” is not required to be linear, positive, or trace preserving, so the definition itself does not require Θ\ThetaΘ to be a density matrix.

QAlgorithms.Papers.Independent.Support50.P07.purificationCoherentInformation

For finite index types A,B,EA,B,EA,B,E with decidable equality and any complex matrix U:CA→CB×EU:\mathbb C^A\to\mathbb C^{B\times E}U:CA→CB×E, this defines the real supremum

sup⁡ψ∈CA×A, ∥ψ∥=1[H(Tr⁡Aρψ)−H(ρψ)].\sup_{\psi\in\mathbb C^{A\times A},\ \|\psi\|=1} \left[H(\operatorname{Tr}_A\rho_\psi)-H(\rho_\psi)\right].ψ∈CA×A, ∥ψ∥=1sup​[H(TrA​ρψ​)−H(ρψ​)].

Here ψψ†\psi\psi^\daggerψψ† has entries ψ(a,i)ψ(a′,j)‾\psi(a,i)\overline{\psi(a',j)}ψ(a,i)ψ(a′,j)​, and ρψ\rho_\psiρψ​, indexed by A×BA\times BA×B, is obtained by applying NU(X)=Tr⁡E(UXU†)N_U(X)=\operatorname{Tr}_E(UXU^\dagger)NU​(X)=TrE​(UXU†) to each block belonging to the second AAA factor:

ρψ((a,b),(a′,b′))=∑e∈E∑i,j∈AU((b,e),i) ψ(a,i)ψ(a′,j)‾ U((b′,e),j)‾.\rho_\psi((a,b),(a',b')) = \sum_{e\in E}\sum_{i,j\in A} U((b,e),i)\,\psi(a,i)\overline{\psi(a',j)}\, \overline{U((b',e),j)}.ρψ​((a,b),(a′,b′))=e∈E∑​i,j∈A∑​U((b,e),i)ψ(a,i)ψ(a′,j)​U((b′,e),j)​.

The partial trace in the objective removes the first, reference AAA factor. For any matrix XXX, H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), with f(s)=slog⁡2sf(s)=s\log_2sf(s)=slog2​s evaluated by continuous functional calculus. No isometry condition on UUU is required, so the definition itself does not require ρψ\rho_\psiρψ​ to be a density matrix. If AAA is empty, there are no unit vectors in the indicated space and the defining real supremum is 000.

QAlgorithms.Papers.Independent.Support50.P07.qubitPauliProbabilityChannel

For every triple of real numbers p0,p1,p2p_0,p_1,p_2p0​,p1​,p2​, this defines a map on all complex 2×22\times22×2 matrices by

ρ⟼(1−p0−p1−p2)ρ+p0XρX†+p1YρY†+p2ZρZ†,\rho\longmapsto (1-p_0-p_1-p_2)\rho +p_0X\rho X^\dagger +p_1Y\rho Y^\dagger +p_2Z\rho Z^\dagger,ρ⟼(1−p0​−p1​−p2​)ρ+p0​XρX†+p1​YρY†+p2​ZρZ†,

where

X=(0110),Y=(0−ii0),Z=(100−1).X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Y=\begin{pmatrix}0&-\mathrm i\\\mathrm i&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.X=(01​10​),Y=(0i​−i0​),Z=(10​0−1​).

There are no assumptions that the pip_ipi​ are nonnegative or that their sum is at most 111, and the input ρ\rhoρ need not be a density matrix.

QAlgorithms.Papers.Independent.Support50.P07.qubitPhaseFlipChannel

For every real number ppp, this defines a map on all complex 2×22\times22×2 matrices by

ρ⟼(1−p)ρ+pZρZ†,Z=(100−1).\rho\longmapsto (1-p)\rho+pZ\rho Z^\dagger, \qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.ρ⟼(1−p)ρ+pZρZ†,Z=(10​0−1​).

There is no restriction 0≤p≤10\le p\le10≤p≤1, and the input matrix need not be a density matrix.

QAlgorithms.Papers.Independent.Support50.P07.ssInformationValues

For finite index types A,B,EA,B,EA,B,E with decidable equality and any complex matrix U:CA→CB×EU:\mathbb C^A\to\mathbb C^{B\times E}U:CA→CB×E, this is the set of real numbers obtained as follows. Choose an integer d>0d>0d>0, positive integers nx,ntn_x,n_tnx​,nt​, nonnegative weights wxw_xwx​ with ∑xwx=1\sum_xw_x=1∑x​wx​=1, unit vectors ψx∈CA×({0,…,d−1}2)\psi_x\in\mathbb C^{A\times(\{0,\ldots,d-1\}^2)}ψx​∈CA×({0,…,d−1}2), and nonnegative processing probabilities p(t∣x)p(t\mid x)p(t∣x) with ∑tp(t∣x)=1\sum_t p(t\mid x)=1∑t​p(t∣x)=1 for every xxx. Require, for every signal label xxx, every a∈Aa\in Aa∈A, and every f,g<df,g<df,g<d,

ψx(a,f,g)=ψx(a,g,f).\psi_x(a,f,g)=\psi_x(a,g,f).ψx​(a,f,g)=ψx​(a,g,f).

Define the matrix VVV by

V(((b,f),(e,g)),(a,f′,g′))={U((b,e),a),f=f′ and g=g′,0,otherwise,V\bigl(((b,f),(e,g)),(a,f',g')\bigr) = \begin{cases} U((b,e),a),&f=f'\text{ and }g=g',\\ 0,&\text{otherwise}, \end{cases}V(((b,f),(e,g)),(a,f′,g′))={U((b,e),a),0,​f=f′ and g=g′,otherwise,​

and put N(X)=Tr⁡E×{0,…,d−1}(VXV†)N(X)=\operatorname{Tr}_{E\times\{0,\ldots,d-1\}}(VXV^\dagger)N(X)=TrE×{0,…,d−1}​(VXV†) and Nc(X)=Tr⁡B×{0,…,d−1}(VXV†)N^c(X)=\operatorname{Tr}_{B\times\{0,\ldots,d-1\}}(VXV^\dagger)Nc(X)=TrB×{0,…,d−1}​(VXV†). Form block matrices ΩN=∑x,twxp(t∣x)∣t⟩⟨t∣⊗N(ψxψx†)\Omega_N=\sum_{x,t}w_xp(t\mid x)|t\rangle\langle t|\otimes N(\psi_x\psi_x^\dagger)ΩN​=∑x,t​wx​p(t∣x)∣t⟩⟨t∣⊗N(ψx​ψx†​), and likewise ΩNc\Omega_{N^c}ΩNc​. The chosen number is I(ΩN)−I(ΩNc)I(\Omega_N)-I(\Omega_{N^c})I(ΩN​)−I(ΩNc​), where I(Ω)=H(Tr⁡2Ω)+H(Tr⁡1Ω)−H(Ω)I(\Omega)=H(\operatorname{Tr}_2\Omega)+H(\operatorname{Tr}_1\Omega)-H(\Omega)I(Ω)=H(Tr2​Ω)+H(Tr1​Ω)−H(Ω) and H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), with f(s)=slog⁡2sf(s)=s\log_2sf(s)=slog2​s evaluated by continuous functional calculus. The symmetry condition applies even to zero-weight signals; d=1d=1d=1 is allowed and makes it automatic. No isometry condition is imposed on UUU.

QAlgorithms.Papers.Independent.Support50.P07.ssPrivateCapacity

For finite index types A,B,EA,B,EA,B,E and an arbitrary complex matrix U:A→B×EU:A\to B\times EU:A→B×E, this definition is the real supremum of all r≥0r\ge0r≥0 such that, for every ε>0\varepsilon>0ε>0 and s>0s>0s>0, every sufficiently large positive integer nnn admits d>0d>0d>0, M>0M>0M>0, input density matrices ρm\rho_mρm​ on An×(Fd×Fd)A^n\times(F_d\times F_d)An×(Fd​×Fd​), and measurement matrices Dj⪰0D_j\succeq0Dj​⪰0 on Bn×FdB^n\times F_dBn×Fd​ summing to the identity, with log⁡2M/n≥r−s\log_2M/n\ge r-slog2​M/n≥r−s. Here Fd={0,…,d−1}F_d=\{0,\ldots,d-1\}Fd​={0,…,d−1}, each ρm\rho_mρm​ is invariant under swapping its two FdF_dFd​ coordinates separately in rows and columns, and the required error is ∥Ω−J∥1<ε\|\Omega-J\|_1<\varepsilon∥Ω−J∥1​<ε, defined using

V((b,f),(e,g)),(a,(h,k))=(∏i=0n−1U(bi,ei),ai)1{f=h, g=k},Ω(m,j,ξ),(m′,j′,ξ′)={M−1∑β,γ(Dj)γ,β(VρmV†)(β,ξ),(γ,ξ′),m=m′, j=j′,0,otherwise.V_{((b,f),(e,g)),(a,(h,k))} =\left(\prod_{i=0}^{n-1}U_{(b_i,e_i),a_i}\right)\mathbf1_{\{f=h,\ g=k\}}, \qquad \Omega_{(m,j,\xi),(m',j',\xi')}= \begin{cases} \displaystyle M^{-1}\sum_{\beta,\gamma}(D_j)_{\gamma,\beta} (V\rho_mV^\dagger)_{(\beta,\xi),(\gamma,\xi')},&m=m',\ j=j',\\ 0,&\text{otherwise}. \end{cases}V((b,f),(e,g)),(a,(h,k))​=(i=0∏n−1​U(bi​,ei​),ai​​)1{f=h, g=k}​,Ω(m,j,ξ),(m′,j′,ξ′)​=⎩⎨⎧​M−1β,γ∑​(Dj​)γ,β​(Vρm​V†)(β,ξ),(γ,ξ′)​,0,​m=m′, j=j′,otherwise.​

The indices β,γ\beta,\gammaβ,γ range over Bn×FdB^n\times F_dBn×Fd​, and ξ,ξ′\xi,\xi'ξ,ξ′ over En×FdE^n\times F_dEn×Fd​. Set σξ,ξ′=∑m,jΩ(m,j,ξ),(m,j,ξ′)\sigma_{\xi,\xi'}=\sum_{m,j}\Omega_{(m,j,\xi),(m,j,\xi')}σξ,ξ′​=∑m,j​Ω(m,j,ξ),(m,j,ξ′)​; then JJJ has entry M−1σξ,ξ′M^{-1}\sigma_{\xi,\xi'}M−1σξ,ξ′​ when m=j=m′=j′m=j=m'=j'm=j=m′=j′, and zero otherwise, and ∥X∥1=Re⁡tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}∥X∥1​=RetrX†X​. There is no bound on ddd and no isometry requirement on UUU. This is a supremum in R\mathbb RR, whose convention gives zero if the defining set is empty or unbounded above.

QAlgorithms.Papers.Independent.Support50.P07.ssPrivateInformation

For finite index types A,B,EA,B,EA,B,E with decidable equality and any complex matrix U:CA→CB×EU:\mathbb C^A\to\mathbb C^{B\times E}U:CA→CB×E, this defines the real supremum of I(ΩN)−I(ΩNc)I(\Omega_N)-I(\Omega_{N^c})I(ΩN​)−I(ΩNc​) over the following choices: an integer d>0d>0d>0; positive finite numbers of signal and processing labels x,tx,tx,t; nonnegative weights wxw_xwx​ summing to 111; unit vectors ψx∈CA×({0,…,d−1}2)\psi_x\in\mathbb C^{A\times(\{0,\ldots,d-1\}^2)}ψx​∈CA×({0,…,d−1}2) satisfying ψx(a,f,g)=ψx(a,g,f)\psi_x(a,f,g)=\psi_x(a,g,f)ψx​(a,f,g)=ψx​(a,g,f) for every x,a,f,gx,a,f,gx,a,f,g; and nonnegative p(t∣x)p(t\mid x)p(t∣x) with each row summing to 111. Define

V(((b,f),(e,g)),(a,f′,g′))=U((b,e),a) 1f=f′1g=g′,V\bigl(((b,f),(e,g)),(a,f',g')\bigr) =U((b,e),a)\,\mathbf1_{f=f'}\mathbf1_{g=g'},V(((b,f),(e,g)),(a,f′,g′))=U((b,e),a)1f=f′​1g=g′​,

let N(X)=Tr⁡E×{0,…,d−1}(VXV†)N(X)=\operatorname{Tr}_{E\times\{0,\ldots,d-1\}}(VXV^\dagger)N(X)=TrE×{0,…,d−1}​(VXV†) and Nc(X)=Tr⁡B×{0,…,d−1}(VXV†)N^c(X)=\operatorname{Tr}_{B\times\{0,\ldots,d-1\}}(VXV^\dagger)Nc(X)=TrB×{0,…,d−1}​(VXV†), and set ΩN=∑x,twxp(t∣x)∣t⟩⟨t∣⊗N(ψxψx†)\Omega_N=\sum_{x,t}w_xp(t\mid x)|t\rangle\langle t|\otimes N(\psi_x\psi_x^\dagger)ΩN​=∑x,t​wx​p(t∣x)∣t⟩⟨t∣⊗N(ψx​ψx†​), with the analogous definition for ΩNc\Omega_{N^c}ΩNc​. Here I(Ω)=H(Tr⁡2Ω)+H(Tr⁡1Ω)−H(Ω)I(\Omega)=H(\operatorname{Tr}_2\Omega)+H(\operatorname{Tr}_1\Omega)-H(\Omega)I(Ω)=H(Tr2​Ω)+H(Tr1​Ω)−H(Ω), and H(X)=−Re⁡tr⁡(f(X))H(X)=-\operatorname{Re}\operatorname{tr}(f(X))H(X)=−Retr(f(X)), using continuous functional calculus for f(s)=slog⁡2sf(s)=s\log_2sf(s)=slog2​s. The choice d=1d=1d=1 is included. No isometry condition on UUU, upper bound on ddd, or attainment of the supremum is asserted.

QAlgorithms.Papers.Independent.Support50.P07.symmetricSubspaceEmbedding

For every natural number ddd, this defines a complex matrix JdJ_dJd​ whose rows are pairs (f,g)(f,g)(f,g) with 0≤f,g<d0\le f,g<d0≤f,g<d, and whose columns are pairs (i,j)(i,j)(i,j) with 0≤i≤j<d0\le i\le j<d0≤i≤j<d, by

Jd((f,g),(i,j))={1,i=j and (f,g)=(i,j),1/2,i≠j and (f,g)∈{(i,j),(j,i)},0,otherwise.J_d((f,g),(i,j)) = \begin{cases} 1,&i=j\text{ and }(f,g)=(i,j),\\ 1/\sqrt2,&i\ne j\text{ and }(f,g)\in\{(i,j),(j,i)\},\\ 0,&\text{otherwise}. \end{cases}Jd​((f,g),(i,j))=⎩⎨⎧​1,1/2​,0,​i=j and (f,g)=(i,j),i=j and (f,g)∈{(i,j),(j,i)},otherwise.​

Thus a diagonal column has one nonzero entry, while a column with i<ji<ji<j has the two displayed entries. For d=0d=0d=0, both index types are empty.

QAlgorithms.Papers.Independent.Support50.P07.twoKrausChannel

For all real numbers γ,δ\gamma,\deltaγ,δ, this defines the map on complex 2×22\times22×2 matrices

ρ⟼K0ρK0†+K1ρK1†,K0=(1−γ001−δ),K1=(0δγ0).\rho\longmapsto K_0\rho K_0^\dagger+K_1\rho K_1^\dagger, \qquad K_0=\begin{pmatrix}\sqrt{1-\gamma}&0\\0&\sqrt{1-\delta}\end{pmatrix}, \qquad K_1=\begin{pmatrix}0&\sqrt\delta\\\sqrt\gamma&0\end{pmatrix}.ρ⟼K0​ρK0†​+K1​ρK1†​,K0​=(1−γ​0​01−δ​​),K1​=(0γ​​δ​0​).

All square roots are real square roots, embedded into C\mathbb CC, with the real square root of a negative number defined as 000. No bounds on γ,δ\gamma,\deltaγ,δ, normalization identity for the two matrices, or density condition on the input are required.

QAlgorithms.Papers.Independent.Support50.P07.twoKrausValue

For all real numbers γ,δ,t\gamma,\delta,tγ,δ,t, this defines the real number

H2 ⁣(t(1−γ)+(1−t)δ)−H2 ⁣(tγ+(1−t)δ),H2(x)=−xL(x)−(1−x)L(1−x)ln⁡2,H_2\!\left(t(1-\gamma)+(1-t)\delta\right) -H_2\!\left(t\gamma+(1-t)\delta\right), \qquad H_2(x)=\frac{-xL(x)-(1-x)L(1-x)}{\ln2},H2​(t(1−γ)+(1−t)δ)−H2​(tγ+(1−t)δ),H2​(x)=ln2−xL(x)−(1−x)L(1−x)​,

where L(x)=ln⁡∣x∣L(x)=\ln|x|L(x)=ln∣x∣ for x≠0x\ne0x=0 and L(0)=0L(0)=0L(0)=0. Thus all three parameters are unrestricted, and the expression is defined even when either entropy argument lies outside [0,1][0,1][0,1].

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by Gohan · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me