Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Universal recovery map for approximate Markov chains

Definition
QAlgorithms_Papers_Independent_Support50_P44

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

prove2quantum

The objects the formalized statements of Universal recovery map for approximate Markov chains (arXiv:1504.07251) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • hilbertTrace: PDF pp.23–24: ordinary basis trace, used only on trace-class arguments.
  • IsHilbertDensity: PDF pp.1–3: positive trace-class operators with trace one.
  • hilbertFidelity: PDF p.2 footnote 1: root fidelity Tr sqrt(sqrt(rho) sigma sqrt(rho)). For positive trace-class inputs the operator traced is itself trace class.
  • hilbertTraceNorm: PDF p.24, (143): trace norm Tr sqrt(T-adjoint T), on trace-class arguments.
  • hilbertMix: PDF pp.23–25: convex mixture, with the interval guard in every theorem.
  • OrthogonalBlocks: PDF pp.23–24: all four orthogonality conditions between the two blocks.
  • compressedRelativeEntropy: PDF p.24: generalized relative entropy of compressions, in bits. The trace correction in qRelEntropy is essential on unequal traces. This is the accepted Dependency50.P13 finiteRelativeEntropy construction, converted from nats to bits.
  • hilbertRelativeEntropy: PDF p.24, (147): full normalized Umegaki entropy via finite orthogonal compressions of generalized entropy, following accepted Dependency50.P13. The extended supremum retains infinity; no entropy finiteness is assumed.
  • IsHilbertPOVM: PDF p.24, Definition B.1: finite positive bounded effects summing to identity.
  • measuredRelativeEntropy: PDF p.24, Definition B.1: supremum over all finite POVMs, without attainment.
  • IsFiniteProjector: PDF p.27: finite-rank orthogonal projector, with no nesting requirement.
  • WeaklyExhausts: PDF p.27: weak operator convergence to identity against every pair of vectors.
  • finiteEntropyBits: PDF pp.1,19: finite von Neumann entropy in bits, with 0 log 0 = 0.
  • finiteCMI: PDF p.19, (117): four finite entropies, never used for infinite systems.
  • finiteSupport: PDF pp.2,19: spectral support projection, including a zero kernel.
  • rotatedTranspose: PDF pp.19,22,28, (116),(134): rotated transpose formula on supported inputs. The inverse square root is zero at a zero eigenvalue.
  • mapChoi: PDF p.26: a linear map in Choi coordinates, with input index first.
  • finiteMapTopology: PDF p.26: topology of all Choi entries, a finite map-coordinate topology.
  • FiniteCP: PDF p.26, Remark C.3: complete positivity via its Choi representation.
  • FiniteTNI: PDF p.26: trace nonincrease on every positive, possibly unnormalized input.
  • FiniteTP: PDF p.26: full trace preservation of a complex-linear map.
  • counterexampleState: PDF p.28, (169): the diagonal qubit counterexample, A tensor (B tensor C), false = zero. Its trace is 1/2 + 4/8 = 1.
  • counterexampleRecovery: PDF p.28, (171): measure B in its basis, then prepare the prescribed state. This full linear map kills off-diagonal matrix units.
  • counterexampleTranspose: PDF pp.22,28, (134),(170): full transpose map, with invertible rhoB.
  • finiteRecoveryFidelity: PDF p.2, (3): optimal root fidelity over all full CPTP recovery channels. For density inputs the set is nonempty and bounded by one.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_QuantumInformation
import Definitions.Def_QAlgorithms_Defs_Channel
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Defs_SDP
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P13
import Definitions.Def_QAlgorithms_Papers_Independent_Dependency50_P21
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P37

/-!
Sutter–Fawzi–Renner, arXiv:1504.07251v3; citations use PDF pages.
Infinite systems below are complete complex Hilbert spaces with countable Hilbert
bases, including finite spaces. Nuclearity and compression import accepted
Dependency50.P13 definitions; finite marginalAB imports Dependency50.P21; finite
classical KL in bits imports Renew46.P37. Accepted-library imports follow the
independent-paper workflow override. Compilation and moderation are pending.
-/

noncomputable section

namespace QAlgorithms.Papers.Independent.Support50.P44

-- Reuse the inspected pinned definitions without local aliases or redeclarations.
open QAlgorithms.Papers.Independent.Dependency50.P13 (IsTraceClass compression)
open QAlgorithms.Papers.Independent.Dependency50.P21 (marginalAB)
open QAlgorithms.Papers.Independent.Renew46.P37 (classicalKL)

open Filter
open scoped ENNReal ComplexOrder Matrix

attribute [local instance] Classical.propDecidable
attribute [local instance] Classical.decEq

variable {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℂ H] [CompleteSpace H]

/-- PDF pp.23–24: ordinary basis trace, used only on trace-class arguments. -/
def hilbertTrace {I : Type*} (b : HilbertBasis I ℂ H) (T : H →L[ℂ] H) : ℂ :=
  ∑' i, inner ℂ (b i) (T (b i))

/-- PDF pp.1–3: positive trace-class operators with trace one. -/
def IsHilbertDensity {I : Type*} (b : HilbertBasis I ℂ H) (rho : H →L[ℂ] H) : Prop :=
  IsTraceClass rho ∧ rho.IsPositive ∧ hilbertTrace b rho = 1

/-- PDF p.2 footnote 1: root fidelity Tr sqrt(sqrt(rho) sigma sqrt(rho)).
For positive trace-class inputs the operator traced is itself trace class. -/
def hilbertFidelity {I : Type*} (b : HilbertBasis I ℂ H)
    (rho sigma : H →L[ℂ] H) : ℝ :=
  (hilbertTrace b (cfc Real.sqrt
    ((cfc Real.sqrt rho).comp (sigma.comp (cfc Real.sqrt rho))))).re

/-- PDF p.24, (143): trace norm Tr sqrt(T-adjoint T), on trace-class arguments. -/
def hilbertTraceNorm {I : Type*} (b : HilbertBasis I ℂ H) (T : H →L[ℂ] H) : ℝ :=
  (hilbertTrace b (cfc Real.sqrt (T.adjoint.comp T))).re

/-- PDF pp.23–25: convex mixture, with the interval guard in every theorem. -/
def hilbertMix (p : ℝ) (rho sigma : H →L[ℂ] H) : H →L[ℂ] H :=
  (p : ℂ) • rho + ((1 - p : ℝ) : ℂ) • sigma

/-- PDF pp.23–24: all four orthogonality conditions between the two blocks. -/
def OrthogonalBlocks (rho rho2 sigma sigma2 : H →L[ℂ] H) : Prop :=
  rho.comp rho2 = 0 ∧ rho.comp sigma2 = 0 ∧
    sigma.comp rho2 = 0 ∧ sigma.comp sigma2 = 0

/-- PDF p.24: generalized relative entropy of compressions, in bits. The trace
correction in qRelEntropy is essential on unequal traces. This is the accepted
Dependency50.P13 finiteRelativeEntropy construction, converted from nats to bits. -/
def compressedRelativeEntropy {n : ℕ} (rho sigma : Matrix (Fin n) (Fin n) ℂ) : ℝ≥0∞ :=
  if LinearMap.ker sigma.mulVecLin ≤ LinearMap.ker rho.mulVecLin then
    ENNReal.ofReal (qRelEntropy rho sigma / Real.log 2)
  else ⊤

/-- PDF p.24, (147): full normalized Umegaki entropy via finite orthogonal
compressions of generalized entropy, following accepted Dependency50.P13.
The extended supremum retains infinity; no entropy finiteness is assumed. -/
def hilbertRelativeEntropy (rho sigma : H →L[ℂ] H) : ℝ≥0∞ :=
  ⨆ n : ℕ, ⨆ v : {v : Fin n → H // Orthonormal ℂ v},
    compressedRelativeEntropy (compression v.val rho) (compression v.val sigma)

/-- PDF p.24, Definition B.1: finite positive bounded effects summing to identity. -/
def IsHilbertPOVM {n : ℕ} (M : Fin n → H →L[ℂ] H) : Prop :=
  (∀ i, (M i).IsPositive) ∧ ∑ i, M i = 1

/-- PDF p.24, Definition B.1: supremum over all finite POVMs, without attainment. -/
def measuredRelativeEntropy {I : Type*} (b : HilbertBasis I ℂ H)
    (rho sigma : H →L[ℂ] H) : ℝ≥0∞ :=
  ⨆ n : ℕ, ⨆ M : {M : Fin n → H →L[ℂ] H // IsHilbertPOVM M},
    classicalKL
      (fun i => (hilbertTrace b ((M.val i).comp rho)).re)
      (fun i => (hilbertTrace b ((M.val i).comp sigma)).re)

/-- PDF p.27: finite-rank orthogonal projector, with no nesting requirement. -/
def IsFiniteProjector (P : H →L[ℂ] H) : Prop :=
  P.adjoint = P ∧ P.comp P = P ∧ FiniteDimensional ℂ (LinearMap.range P.toLinearMap)

/-- PDF p.27: weak operator convergence to identity against every pair of vectors. -/
def WeaklyExhausts (P : ℕ → H →L[ℂ] H) : Prop :=
  ∀ x y : H, Tendsto (fun n => inner ℂ x (P n y)) atTop (nhds (inner ℂ x y))

example : IsTraceClass (0 : H →L[ℂ] H) := by
  unfold IsTraceClass QAlgorithms.Papers.Independent.Dependency50.P13.NuclearRepresentation
  refine ⟨fun _ => 0, fun _ => 0, ?_, ?_⟩
  · simp
  · intro x
    simp

example {I : Type*} (b : HilbertBasis I ℂ H) : hilbertTrace b 0 = 0 := by
  simp [hilbertTrace]

example {I : Type*} (b : HilbertBasis I ℂ H) : ¬ IsHilbertDensity b 0 := by
  simp [IsHilbertDensity, hilbertTrace]

example {I : Type*} (b : HilbertBasis I ℂ H) : hilbertFidelity b 0 0 = 0 := by
  simp [hilbertFidelity, hilbertTrace]

example {I : Type*} (b : HilbertBasis I ℂ H) : hilbertTraceNorm b 0 = 0 := by
  simp [hilbertTraceNorm, hilbertTrace]

example : OrthogonalBlocks (0 : H →L[ℂ] H) 0 0 0 := by
  simp [OrthogonalBlocks]

example : WeaklyExhausts (fun _ : ℕ => (1 : H →L[ℂ] H)) := by
  intro x y
  simpa using (tendsto_const_nhds : Tendsto (fun _ : ℕ => inner ℂ x y) atTop
    (nhds (inner ℂ x y)))

example (rho sigma : H →L[ℂ] H) : hilbertMix 0 rho sigma = sigma := by
  simp [hilbertMix]

example (rho sigma : H →L[ℂ] H) : hilbertMix 1 rho sigma = rho := by
  simp [hilbertMix]

example : classicalKL (fun _ : Fin 1 => (1 : ℝ)) (fun _ => 0) = ⊤ := by
  simp [classicalKL]

example : classicalKL (fun _ : Fin 1 => (1 : ℝ)) (fun _ => 1) = 0 := by
  simp [classicalKL]

example {n : ℕ} (rho sigma : Matrix (Fin n) (Fin n) ℂ)
    (h : ¬ LinearMap.ker sigma.mulVecLin ≤ LinearMap.ker rho.mulVecLin) :
    compressedRelativeEntropy rho sigma = ⊤ := by
  simp [compressedRelativeEntropy, h]

example {n : ℕ} (v : Fin n → H) : compression v (0 : H →L[ℂ] H) = 0 := by
  ext i j
  simp [compression]

example : IsHilbertPOVM (fun _ : Fin 1 => (1 : H →L[ℂ] H)) := by
  simp [IsHilbertPOVM, ContinuousLinearMap.isPositive_one]

example : IsFiniteProjector (0 : H →L[ℂ] H) := by
  refine ⟨by simp, by simp, ?_⟩
  change FiniteDimensional ℂ (LinearMap.range (0 : H →ₗ[ℂ] H))
  rw [LinearMap.range_zero]
  infer_instance

variable {A B C E G : Type*}

/-- PDF pp.1,19: finite von Neumann entropy in bits, with 0 log 0 = 0. -/
def finiteEntropyBits {J : Type*} [Fintype J] [DecidableEq J]
    (rho : Matrix J J ℂ) : ℝ :=
  -(cfc (fun x : ℝ => x * Real.logb 2 x) rho).trace.re

/-- PDF p.19, (117): four finite entropies, never used for infinite systems. -/
def finiteCMI [Fintype A] [Fintype B] [Fintype C]
    [DecidableEq A] [DecidableEq B] [DecidableEq C]
    (rho : Matrix (A × (B × C)) (A × (B × C)) ℂ) : ℝ :=
  finiteEntropyBits (marginalAB rho) + finiteEntropyBits (traceLeft rho) -
    finiteEntropyBits (fun b b2 => ∑ c, (traceLeft rho) (b,c) (b2,c)) -
    finiteEntropyBits rho

/-- PDF pp.2,19: spectral support projection, including a zero kernel. -/
def finiteSupport {J : Type*} [Fintype J] [DecidableEq J]
    (rho : Matrix J J ℂ) : Matrix J J ℂ :=
  rho * cfc (fun x : ℝ => x⁻¹) rho

/-- PDF pp.19,22,28, (116),(134): rotated transpose formula on supported inputs.
The inverse square root is zero at a zero eigenvalue. -/
def rotatedTranspose [Fintype B] [Fintype C] [DecidableEq B] [DecidableEq C]
    (rhoBC : Matrix (B × C) (B × C) ℂ) (U : Matrix B B ℂ)
    (V : Matrix (B × C) (B × C) ℂ) (X : Matrix B B ℂ) :
    Matrix (B × C) (B × C) ℂ :=
  let rhoB : Matrix B B ℂ := fun b b2 => ∑ c, rhoBC (b,c) (b2,c)
  let D := cfc (fun x : ℝ => (Real.sqrt x)⁻¹) rhoB
  let S := cfc Real.sqrt rhoBC
  V * S * Matrix.kronecker (D * U * X * Uᴴ * D) (1 : Matrix C C ℂ) * S * Vᴴ

example {J : Type*} [Fintype J] [DecidableEq J] :
    finiteSupport (0 : Matrix J J ℂ) = 0 := by
  simp [finiteSupport]

example {J : Type*} [Fintype J] [DecidableEq J] :
    finiteEntropyBits (0 : Matrix J J ℂ) = 0 := by
  simp [finiteEntropyBits, cfc_zero]

example [Fintype C] : marginalAB (0 : Matrix (A × (B × C)) (A × (B × C)) ℂ) = 0 := by
  ext p q
  simp [marginalAB]

example [Fintype B] [Fintype C] [DecidableEq B] [DecidableEq C]
    (rhoBC : Matrix (B × C) (B × C) ℂ) (U : Matrix B B ℂ)
    (V : Matrix (B × C) (B × C) ℂ) : rotatedTranspose rhoBC U V 0 = 0 := by
  simp [rotatedTranspose]

/-- PDF p.26: a linear map in Choi coordinates, with input index first. -/
def mapChoi [Fintype E] [DecidableEq E]
    (Phi : Matrix E E ℂ →ₗ[ℂ] Matrix G G ℂ) : Matrix (E × G) (E × G) ℂ :=
  fun p q => Phi (Matrix.single p.1 q.1 1) p.2 q.2

/-- PDF p.26: topology of all Choi entries, a finite map-coordinate topology. -/
def finiteMapTopology [Fintype E] [DecidableEq E] :
    TopologicalSpace (Matrix E E ℂ →ₗ[ℂ] Matrix G G ℂ) :=
  TopologicalSpace.induced mapChoi inferInstance

/-- PDF p.26, Remark C.3: complete positivity via its Choi representation. -/
def FiniteCP [Fintype E] [Fintype G] [DecidableEq E]
    (Phi : Matrix E E ℂ →ₗ[ℂ] Matrix G G ℂ) : Prop :=
  (mapChoi Phi).PosSemidef

/-- PDF p.26: trace nonincrease on every positive, possibly unnormalized input. -/
def FiniteTNI [Fintype E] [Fintype G]
    (Phi : Matrix E E ℂ →ₗ[ℂ] Matrix G G ℂ) : Prop :=
  ∀ X, X.PosSemidef → (Phi X).trace.re ≤ X.trace.re

/-- PDF p.26: full trace preservation of a complex-linear map. -/
def FiniteTP [Fintype E] [Fintype G]
    (Phi : Matrix E E ℂ →ₗ[ℂ] Matrix G G ℂ) : Prop :=
  ∀ X, (Phi X).trace = X.trace

example [Fintype E] [DecidableEq E] :
    mapChoi (0 : Matrix E E ℂ →ₗ[ℂ] Matrix G G ℂ) = 0 := by
  ext p q
  simp [mapChoi]

example [Fintype E] :
    FiniteTP (LinearMap.id : Matrix E E ℂ →ₗ[ℂ] Matrix E E ℂ) := by
  intro X
  rfl

/-- PDF p.28, (169): the diagonal qubit counterexample, A tensor (B tensor C),
false = zero. Its trace is 1/2 + 4/8 = 1. -/
def counterexampleState : Matrix (Bool × (Bool × Bool)) (Bool × (Bool × Bool)) ℂ :=
  Matrix.diagonal fun z => if z.1 then (1/8 : ℂ)
    else if z.2 = (false, false) then (1/2 : ℂ) else 0

/-- PDF p.28, (171): measure B in its basis, then prepare the prescribed state.
This full linear map kills off-diagonal matrix units. -/
def counterexampleRecovery : Superop Bool (Bool × Bool) :=
  fun X => Matrix.diagonal fun z =>
    if z = (false, false) then X false false else (1/3 : ℂ) * X true true

/-- PDF pp.22,28, (134),(170): full transpose map, with invertible rhoB. -/
def counterexampleTranspose : Superop Bool (Bool × Bool) :=
  rotatedTranspose (traceLeft counterexampleState) 1 1

/-- PDF p.2, (3): optimal root fidelity over all full CPTP recovery channels.
For density inputs the set is nonempty and bounded by one. -/
def finiteRecoveryFidelity [Fintype A] [Fintype B] [Fintype C]
    [DecidableEq A] [DecidableEq B] [DecidableEq C]
    (rho : Matrix (A × (B × C)) (A × (B × C)) ℂ) : ℝ :=
  ⨆ R : {R : Superop B (B × C) // IsChannel R},
    rootFidelity rho (idTensorSuperop R.val (marginalAB rho))

example : counterexampleState (false, (false, false)) (false, (false, false)) = 1/2 := by
  norm_num [counterexampleState]

example : counterexampleRecovery (Matrix.single false true 1) = 0 := by
  ext p q
  simp [counterexampleRecovery, Matrix.diagonal, Matrix.single]

end QAlgorithms.Papers.Independent.Support50.P44
Source
Universal recovery map for approximate Markov chains, arXiv:1504.07251v3, https://arxiv.org/abs/1504.07251v3
Read-back

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

QAlgorithms.Papers.Independent.Support50.P44.FiniteCP

For finite types E,GE,GE,G, with decidable equality on EEE, and a complex linear map Φ:CE×E→CG×G\Phi:\mathbb C^{E\times E}\to\mathbb C^{G\times G}Φ:CE×E→CG×G, this predicate says that the matrix

(JΦ)(e,g),(e′,g′)=(Φ(∣e⟩⟨e′∣))g,g′(J_\Phi)_{(e,g),(e',g')}=\bigl(\Phi(|e\rangle\langle e'|)\bigr)_{g,g'}(JΦ​)(e,g),(e′,g′)​=(Φ(∣e⟩⟨e′∣))g,g′​

is positive semidefinite, where ∣e⟩⟨e′∣|e\rangle\langle e'|∣e⟩⟨e′∣ denotes the matrix with its only nonzero entry equal to 111 at (e,e′)(e,e')(e,e′). It imposes no trace condition. Either indexing type may be empty, in which case JΦJ_\PhiJΦ​ has an empty indexing type and its positive semidefiniteness condition is vacuous.

QAlgorithms.Papers.Independent.Support50.P44.FiniteTNI

For finite types E,GE,GE,G and a complex linear map Φ:CE×E→CG×G\Phi:\mathbb C^{E\times E}\to\mathbb C^{G\times G}Φ:CE×E→CG×G, this predicate requires that every positive semidefinite matrix XXX satisfy

Re⁡tr⁡(Φ(X))≤Re⁡tr⁡(X).\operatorname{Re}\operatorname{tr}(\Phi(X))\le \operatorname{Re}\operatorname{tr}(X).Retr(Φ(X))≤Retr(X).

There is no requirement here that Φ(X)\Phi(X)Φ(X) be positive semidefinite. Empty indexing types are allowed.

QAlgorithms.Papers.Independent.Support50.P44.FiniteTP

For finite types E,GE,GE,G and a complex linear map Φ:CE×E→CG×G\Phi:\mathbb C^{E\times E}\to\mathbb C^{G\times G}Φ:CE×E→CG×G, this predicate requires

tr⁡(Φ(X))=tr⁡(X)\operatorname{tr}(\Phi(X))=\operatorname{tr}(X)tr(Φ(X))=tr(X)

for every complex matrix XXX indexed by EEE. This is equality of complex traces, and XXX need not be Hermitian or positive semidefinite. Empty indexing types are allowed.

QAlgorithms.Papers.Independent.Support50.P44.IsFiniteProjector

For a complex Hilbert space HHH and a bounded complex-linear operator P:H→HP:H\to HP:H→H, this predicate means that

P∗=P,P2=P,P^*=P,\qquad P^2=P,P∗=P,P2=P,

and the range of PPP, regarded as a complex vector subspace of HHH, is finite dimensional. The zero operator is included; no positive-rank or nonzero requirement is imposed.

QAlgorithms.Papers.Independent.Support50.P44.IsHilbertDensity

For a complex Hilbert space HHH, any index type III, a Hilbert basis b=(bi)i∈Ib=(b_i)_{i\in I}b=(bi​)i∈I​, and a bounded complex-linear operator ρ:H→H\rho:H\to Hρ:H→H, this predicate requires all three of the following: there exist sequences ur,vr∈Hu_r,v_r\in Hur​,vr​∈H, indexed by r∈Nr\in\mathbb Nr∈N, such that ∑r∥ur∥∥vr∥\sum_r\|u_r\|\|v_r\|∑r​∥ur​∥∥vr​∥ is summable and ρx=∑r⟨vr,x⟩ur\rho x=\sum_r\langle v_r,x\rangle u_rρx=∑r​⟨vr​,x⟩ur​ for every x∈Hx\in Hx∈H; ρ\rhoρ is a positive operator; and ∑i⟨bi,ρbi⟩=1\sum_i\langle b_i,\rho b_i\rangle=1∑i​⟨bi​,ρbi​⟩=1 as a complex equality. Thus it cannot hold on the zero Hilbert space.

QAlgorithms.Papers.Independent.Support50.P44.IsHilbertPOVM

For a complex Hilbert space HHH, every natural number nnn, and a family M0,…,Mn−1M_0,\ldots,M_{n-1}M0​,…,Mn−1​ of bounded complex-linear operators on HHH, this predicate requires each MiM_iMi​ to be positive and

∑i=0n−1Mi=id⁡H.\sum_{i=0}^{n-1}M_i=\operatorname{id}_H.i=0∑n−1​Mi​=idH​.

The case n=0n=0n=0 is included: its positivity condition is vacuous, and its sum condition is 0=id⁡H0=\operatorname{id}_H0=idH​, which holds precisely when HHH is the zero space.

QAlgorithms.Papers.Independent.Support50.P44.OrthogonalBlocks

For a complex Hilbert space HHH and four arbitrary bounded complex-linear operators ρ,ρ2,σ,σ2:H→H\rho,\rho_2,\sigma,\sigma_2:H\to Hρ,ρ2​,σ,σ2​:H→H, this predicate means exactly

ρρ2=0,ρσ2=0,σρ2=0,σσ2=0,\rho\rho_2=0,\qquad \rho\sigma_2=0,\qquad \sigma\rho_2=0,\qquad \sigma\sigma_2=0,ρρ2​=0,ρσ2​=0,σρ2​=0,σσ2​=0,

where multiplication denotes composition, with the right-hand operator applied first. No positivity or self-adjointness is assumed, and the reverse-order products are not included among the requirements.

QAlgorithms.Papers.Independent.Support50.P44.WeaklyExhausts

For a complex Hilbert space HHH and a sequence (Pn)n∈N(P_n)_{n\in\mathbb N}(Pn​)n∈N​ of bounded complex-linear operators on HHH, this predicate requires that, for every x,y∈Hx,y\in Hx,y∈H,

lim⁡n→∞⟨x,Pny⟩=⟨x,y⟩\lim_{n\to\infty}\langle x,P_ny\rangle=\langle x,y\ranglen→∞lim​⟨x,Pn​y⟩=⟨x,y⟩

in C\mathbb CC. The operators are not required to be projections, finite rank, positive, or increasing.

QAlgorithms.Papers.Independent.Support50.P44.compressedRelativeEntropy

For every natural number nnn, including 000, and arbitrary complex n×nn\times nn×n matrices ρ,σ\rho,\sigmaρ,σ, this defines an extended nonnegative real number by

Dc(ρ,σ)={max⁡ ⁣{Re⁡tr⁡(f(ρ)−ρ g(σ)−ρ+σ)log⁡2, 0},ker⁡σ⊆ker⁡ρ,+∞,otherwise,D_{\mathrm c}(\rho,\sigma)= \begin{cases} \displaystyle \max\!\left\{ \frac{\operatorname{Re}\operatorname{tr} \bigl(f(\rho)-\rho\,g(\sigma)-\rho+\sigma\bigr)}{\log 2},\,0 \right\}, &\ker\sigma\subseteq\ker\rho,\\[6pt] +\infty,&\text{otherwise}, \end{cases}Dc​(ρ,σ)=⎩⎨⎧​max{log2Retr(f(ρ)−ρg(σ)−ρ+σ)​,0},+∞,​kerσ⊆kerρ,otherwise,​

where f(x)=xlog⁡xf(x)=x\log xf(x)=xlogx and g(x)=log⁡xg(x)=\log xg(x)=logx are applied by real continuous functional calculus. No density-matrix or positivity assumption is imposed; the functional calculus and real logarithm retain their total-function conventions, including log⁡0=0\log 0=0log0=0. For n=0n=0n=0, the kernel condition holds and the value is 000.

QAlgorithms.Papers.Independent.Support50.P44.counterexampleRecovery

This defines a function from complex matrices indexed by {false,true}\{\mathrm{false},\mathrm{true}\}{false,true} to complex matrices indexed by pairs of Booleans. For every input matrix XXX, its output is diagonal, with diagonal entries

(Xfalse,false, 13Xtrue,true, 13Xtrue,true, 13Xtrue,true)\left(X_{\mathrm{false},\mathrm{false}},\ \tfrac13X_{\mathrm{true},\mathrm{true}},\ \tfrac13X_{\mathrm{true},\mathrm{true}},\ \tfrac13X_{\mathrm{true},\mathrm{true}}\right)(Xfalse,false​, 31​Xtrue,true​, 31​Xtrue,true​, 31​Xtrue,true​)

in the pair order (false,false),(false,true),(true,false),(true,true)(\mathrm{false},\mathrm{false}),(\mathrm{false},\mathrm{true}),(\mathrm{true},\mathrm{false}),(\mathrm{true},\mathrm{true})(false,false),(false,true),(true,false),(true,true). All off-diagonal output entries are zero, and the definition applies to arbitrary input matrices without a positivity or normalization hypothesis.

QAlgorithms.Papers.Independent.Support50.P44.counterexampleState

This defines a complex diagonal matrix indexed by triples (a,b,c)∈{false,true}3(a,b,c)\in\{\mathrm{false},\mathrm{true}\}^3(a,b,c)∈{false,true}3. Its diagonal entry is 1/81/81/8 whenever a=truea=\mathrm{true}a=true, is 1/21/21/2 when (a,b,c)=(false,false,false)(a,b,c)=(\mathrm{false},\mathrm{false},\mathrm{false})(a,b,c)=(false,false,false), and is zero otherwise; every off-diagonal entry is zero. Thus, in lexicographic order with false\mathrm{false}false preceding true\mathrm{true}true, its diagonal is

(12,0,0,0,18,18,18,18).\left(\tfrac12,0,0,0,\tfrac18,\tfrac18,\tfrac18,\tfrac18\right).(21​,0,0,0,81​,81​,81​,81​).

QAlgorithms.Papers.Independent.Support50.P44.counterexampleTranspose

This defines a function from Boolean-indexed complex matrices XXX to matrices indexed by Boolean pairs by the formula

X⟼S((DXD)⊗I2)S,D=diag⁡ ⁣(23,2),S=diag⁡ ⁣(58,18,18,18).X\longmapsto S\bigl((DXD)\otimes I_2\bigr)S, \qquad D=\operatorname{diag}\!\left(\frac2{\sqrt3},2\right), \qquad S=\operatorname{diag}\!\left(\sqrt{\tfrac58},\sqrt{\tfrac18},\sqrt{\tfrac18},\sqrt{\tfrac18}\right).X⟼S((DXD)⊗I2​)S,D=diag(3​2​,2),S=diag(85​​,81​​,81​​,81​​).

The Boolean order is false,true\mathrm{false},\mathrm{true}false,true, and the pair order for SSS is lexicographic. This is the specified rotated-transpose construction with both rotation matrices equal to the identity and with reference matrix diag⁡(5/8,1/8,1/8,1/8)\operatorname{diag}(5/8,1/8,1/8,1/8)diag(5/8,1/8,1/8,1/8), obtained by summing the first Boolean coordinate of the diagonal triple matrix having entries 1/2,0,0,0,1/8,1/8,1/8,1/81/2,0,0,0,1/8,1/8,1/8,1/81/2,0,0,0,1/8,1/8,1/8,1/8. No hypothesis is imposed on XXX.

QAlgorithms.Papers.Independent.Support50.P44.finiteCMI

Let A,B,CA,B,CA,B,C be finite types equipped with decidable equality, and let ρ\rhoρ be any complex matrix indexed by A×(B×C)A\times(B\times C)A×(B×C). Define matrices

(ρAB)(a,b),(a′,b′)=∑cρ(a,(b,c)),(a′,(b′,c)),(ρBC)(b,c),(b′,c′)=∑aρ(a,(b,c)),(a,(b′,c′)),(ρB)b,b′=∑c(ρBC)(b,c),(b′,c).\begin{aligned} (\rho_{AB})_{(a,b),(a',b')}&=\sum_c\rho_{(a,(b,c)),(a',(b',c))},\\ (\rho_{BC})_{(b,c),(b',c')}&=\sum_a\rho_{(a,(b,c)),(a,(b',c'))},\\ (\rho_B)_{b,b'}&=\sum_c(\rho_{BC})_{(b,c),(b',c)}. \end{aligned}(ρAB​)(a,b),(a′,b′)​(ρBC​)(b,c),(b′,c′)​(ρB​)b,b′​​=c∑​ρ(a,(b,c)),(a′,(b′,c))​,=a∑​ρ(a,(b,c)),(a,(b′,c′))​,=c∑​(ρBC​)(b,c),(b′,c)​.​

For any finite square complex matrix TTT, put S2(T)=−Re⁡Tr⁡(f(T))S_2(T)=-\operatorname{Re}\operatorname{Tr}(f(T))S2​(T)=−ReTr(f(T)), where f(x)=xlog⁡2xf(x)=x\log_2xf(x)=xlog2​x is evaluated by real continuous functional calculus. The definition assigns

S2(ρAB)+S2(ρBC)−S2(ρB)−S2(ρ).S_2(\rho_{AB})+S_2(\rho_{BC})-S_2(\rho_B)-S_2(\rho).S2​(ρAB​)+S2​(ρBC​)−S2​(ρB​)−S2​(ρ).

There is no density matrix assumption, and any of the index types may be empty. The logarithm is total with value zero at zero; the real functional calculus returns zero for non-Hermitian inputs.

QAlgorithms.Papers.Independent.Support50.P44.finiteEntropyBits

For every finite type JJJ equipped with decidable equality and every complex matrix ρ\rhoρ indexed by J×JJ\times JJ×J, this definition assigns the real number

S2(ρ)=−Re⁡Tr⁡(f(ρ)),f(x)=xlog⁡2x,S_2(\rho)=-\operatorname{Re}\operatorname{Tr}\bigl(f(\rho)\bigr), \qquad f(x)=x\log_2x,S2​(ρ)=−ReTr(f(ρ)),f(x)=xlog2​x,

where f(ρ)f(\rho)f(ρ) is evaluated by real continuous functional calculus. No positivity, Hermitian symmetry, or trace normalization is required. The total logarithm has log⁡20=0\log_2 0=0log2​0=0; on a Hermitian matrix the formula is therefore −∑jλjlog⁡2λj-\sum_j\lambda_j\log_2\lambda_j−∑j​λj​log2​λj​, with zero eigenvalues contributing zero and the total real logarithm used for negative eigenvalues. For a non-Hermitian matrix the real functional calculus here returns zero, so the defined value is zero. An empty index type is permitted and also gives zero.

QAlgorithms.Papers.Independent.Support50.P44.finiteMapTopology

For a finite type EEE with decidable equality and an arbitrary type GGG, this defines a topology on the complex linear maps Φ:CE×E→CG×G\Phi:\mathbb C^{E\times E}\to\mathbb C^{G\times G}Φ:CE×E→CG×G. For such a map, form the matrix JΦJ_\PhiJΦ​, indexed by E×GE\times GE×G, with entries

(JΦ)(e,g),(e′,g′)=(Φ(∣e⟩⟨e′∣))g,g′,(J_\Phi)_{(e,g),(e',g')}=\bigl(\Phi(|e\rangle\langle e'|)\bigr)_{g,g'},(JΦ​)(e,g),(e′,g′)​=(Φ(∣e⟩⟨e′∣))g,g′​,

where ∣e⟩⟨e′∣|e\rangle\langle e'|∣e⟩⟨e′∣ has a single entry 111 at (e,e′)(e,e')(e,e′) and zeros elsewhere. The defined topology is the topology induced by Φ↦JΦ\Phi\mapsto J_\PhiΦ↦JΦ​ from the usual entrywise topology on these complex matrices: it is the coarsest topology making this map continuous. No finiteness or nonemptiness assumption is imposed on GGG, and EEE may be empty.

QAlgorithms.Papers.Independent.Support50.P44.finiteRecoveryFidelity

For finite types A,B,CA,B,CA,B,C, each with decidable equality, and any complex matrix ρ\rhoρ indexed by A×(B×C)A\times(B\times C)A×(B×C), define its A,BA,BA,B marginal by (ρAB)(a,b),(a′,b′)=∑c∈Cρ(a,(b,c)),(a′,(b′,c))(\rho_{AB})_{(a,b),(a',b')}=\sum_{c\in C}\rho_{(a,(b,c)),(a',(b',c))}(ρAB​)(a,b),(a′,b′)​=∑c∈C​ρ(a,(b,c)),(a′,(b′,c))​. This definition takes the real supremum, over all functions R:CB×B→C(B×C)×(B×C)R:\mathbb C^{B\times B}\to\mathbb C^{(B\times C)\times(B\times C)}R:CB×B→C(B×C)×(B×C) admitting a finite representation R(X)=∑j=0m−1KjXKj†R(X)=\sum_{j=0}^{m-1}K_jXK_j^\daggerR(X)=∑j=0m−1​Kj​XKj†​ with ∑jKj†Kj=IB\sum_jK_j^\dagger K_j=I_B∑j​Kj†​Kj​=IB​, of

Re⁡tr⁡ρ ρ^R ρ,(ρ^R)(a,(b,c)),(a′,(b′,c′))=[R ⁣(((ρAB)(a,u),(a′,v))u,v∈B)](b,c),(b′,c′).\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\rho}\,\widehat\rho_R\,\sqrt{\rho}}, \qquad (\widehat\rho_R)_{(a,(b,c)),(a',(b',c'))} = \left[R\!\left(\bigl((\rho_{AB})_{(a,u),(a',v)}\bigr)_{u,v\in B}\right)\right]_{(b,c),(b',c')}.Retrρ​ρ​R​ρ​​,(ρ​R​)(a,(b,c)),(a′,(b′,c′))​=[R(((ρAB​)(a,u),(a′,v)​)u,v∈B​)](b,c),(b′,c′)​.

The square roots are given by continuous functional calculus. No density-matrix, positivity, or normalization hypothesis is imposed on ρ\rhoρ, and the displayed quantity is not squared. Empty indexing types and m=0m=0m=0 are allowed subject to the stated matrix identity; the real supremum used here is zero if its defining set is empty or unbounded above.

QAlgorithms.Papers.Independent.Support50.P44.finiteSupport

For every finite type JJJ equipped with decidable equality and every complex matrix ρ\rhoρ indexed by J×JJ\times JJ×J, this definition returns

ρ f(ρ),f(x)=x−1,\rho\,f(\rho),\qquad f(x)=x^{-1},ρf(ρ),f(x)=x−1,

where f(ρ)f(\rho)f(ρ) uses real continuous functional calculus and 0−1=00^{-1}=00−1=0. No positivity or normalization is assumed. For Hermitian ρ\rhoρ, this is the spectral projection onto the span of its eigenvectors with nonzero eigenvalues, including negative eigenvalues; for non-Hermitian ρ\rhoρ, the real functional calculus returns zero and hence so does this definition. Empty index types are included.

QAlgorithms.Papers.Independent.Support50.P44.hilbertFidelity

For a complex Hilbert space HHH, any index type III, a Hilbert basis b=(bi)i∈Ib=(b_i)_{i\in I}b=(bi​)i∈I​, and arbitrary bounded complex-linear operators ρ,σ:H→H\rho,\sigma:H\to Hρ,σ:H→H, let S=f(ρ)S=f(\rho)S=f(ρ), where f(x)=xf(x)=\sqrt{x}f(x)=x​ is applied through real continuous functional calculus. This defines

Re⁡ ⁣(∑i∈I⟨bi, f(SσS)bi⟩).\operatorname{Re}\!\left(\sum_{i\in I} \left\langle b_i,\ f(S\sigma S)b_i\right\rangle\right).Re(i∈I∑​⟨bi​, f(SσS)bi​⟩).

There are no positivity, normalization, or trace-class hypotheses on ρ\rhoρ or σ\sigmaσ. Functional calculus is interpreted as its total operation, including its default values when its applicability conditions fail, and an unsummable family in the displayed sum gives 000.

QAlgorithms.Papers.Independent.Support50.P44.hilbertMix

For a complex Hilbert space HHH, every real number ppp, and arbitrary bounded complex-linear operators ρ,σ:H→H\rho,\sigma:H\to Hρ,σ:H→H, this defines the bounded complex-linear operator

pρ+(1−p)σ,p\rho+(1-p)\sigma,pρ+(1−p)σ,

with the real coefficients regarded as complex scalars. The parameter ppp is unrestricted, including values outside [0,1][0,1][0,1], and neither operator is required to be positive or normalized.

QAlgorithms.Papers.Independent.Support50.P44.hilbertRelativeEntropy

For a complex Hilbert space HHH and arbitrary bounded complex-linear operators ρ,σ:H→H\rho,\sigma:H\to Hρ,σ:H→H, this defines the supremum in [0,+∞][0,+\infty][0,+∞] over every natural number nnn and every orthonormal family v0,…,vn−1∈Hv_0,\ldots,v_{n-1}\in Hv0​,…,vn−1​∈H of the following value. Form the matrices Rij=⟨vi,ρvj⟩R_{ij}=\langle v_i,\rho v_j\rangleRij​=⟨vi​,ρvj​⟩ and Sij=⟨vi,σvj⟩S_{ij}=\langle v_i,\sigma v_j\rangleSij​=⟨vi​,σvj​⟩; the value is +∞+\infty+∞ if ker⁡S⊈ker⁡R\ker S\not\subseteq\ker RkerS⊆kerR, and otherwise it is

max⁡ ⁣{Re⁡tr⁡(f(R)−R g(S)−R+S)log⁡2, 0},\max\!\left\{ \frac{\operatorname{Re}\operatorname{tr} \bigl(f(R)-R\,g(S)-R+S\bigr)}{\log 2},\,0 \right\},max{log2Retr(f(R)−Rg(S)−R+S)​,0},

with f(x)=xlog⁡xf(x)=x\log xf(x)=xlogx and g(x)=log⁡xg(x)=\log xg(x)=logx interpreted through real continuous functional calculus. Neither operator is assumed positive, normalized, or trace class. The empty orthonormal family n=0n=0n=0 is included and contributes 000; sizes admitting no orthonormal family contribute no values.

QAlgorithms.Papers.Independent.Support50.P44.hilbertTrace

For a complex Hilbert space HHH, any index type III, a Hilbert basis b=(bi)i∈Ib=(b_i)_{i\in I}b=(bi​)i∈I​ of HHH, and a bounded complex-linear operator T:H→HT:H\to HT:H→H, this defines the complex number

Tr⁡b(T)=∑i∈I⟨bi,Tbi⟩.\operatorname{Tr}_b(T)=\sum_{i\in I}\langle b_i,Tb_i\rangle.Trb​(T)=i∈I∑​⟨bi​,Tbi​⟩.

No trace-class or summability assumption is imposed: the sum is the total infinite-sum operation, which returns 000 when the family is not summable. An empty index set also gives 000.

QAlgorithms.Papers.Independent.Support50.P44.hilbertTraceNorm

For a complex Hilbert space HHH, any index type III, a Hilbert basis b=(bi)i∈Ib=(b_i)_{i\in I}b=(bi​)i∈I​, and any bounded complex-linear operator T:H→HT:H\to HT:H→H, this defines the real number

Re⁡ ⁣(∑i∈I⟨bi,T∗T bi⟩),\operatorname{Re}\!\left(\sum_{i\in I} \left\langle b_i,\sqrt{T^*T}\,b_i\right\rangle\right),Re(i∈I∑​⟨bi​,T∗T​bi​⟩),

where the square root is obtained by real continuous functional calculus and T∗T^*T∗ is the adjoint. No trace-class assumption is required; if the family being summed is not summable, the total infinite sum returns 000.

QAlgorithms.Papers.Independent.Support50.P44.mapChoi

Let EEE be a finite type equipped with decidable equality, let GGG be any type, and let Φ\PhiΦ be a complex linear map from complex matrices indexed by E×EE\times EE×E to complex matrices indexed by G×GG\times GG×G. This definition returns the matrix indexed by (E×G)×(E×G)(E\times G)\times(E\times G)(E×G)×(E×G) whose entries are

JΦ((e,g),(e′,g′))=[Φ(Ee,e′)]g,g′,J_\Phi\bigl((e,g),(e',g')\bigr) =\bigl[\Phi(E_{e,e'})\bigr]_{g,g'},JΦ​((e,g),(e′,g′))=[Φ(Ee,e′​)]g,g′​,

where Ee,e′E_{e,e'}Ee,e′​ has entry one at (e,e′)(e,e')(e,e′) and zero elsewhere. There is no dimension normalization factor and no positivity or trace preservation assumption on Φ\PhiΦ. The type GGG need not be finite, and empty index types are permitted.

QAlgorithms.Papers.Independent.Support50.P44.measuredRelativeEntropy

For a complex Hilbert space HHH, any index type III, a Hilbert basis b=(bj)j∈Ib=(b_j)_{j\in I}b=(bj​)j∈I​, and arbitrary bounded complex-linear operators ρ,σ:H→H\rho,\sigma:H\to Hρ,σ:H→H, this defines the supremum in [0,+∞][0,+\infty][0,+∞] over all natural numbers nnn and all positive operator families M0,…,Mn−1M_0,\ldots,M_{n-1}M0​,…,Mn−1​ satisfying ∑iMi=id⁡H\sum_iM_i=\operatorname{id}_H∑i​Mi​=idH​. For each family, set

pi=Re⁡∑j∈I⟨bj,Miρbj⟩,qi=Re⁡∑j∈I⟨bj,Miσbj⟩.p_i=\operatorname{Re}\sum_{j\in I}\langle b_j,M_i\rho b_j\rangle, \qquad q_i=\operatorname{Re}\sum_{j\in I}\langle b_j,M_i\sigma b_j\rangle.pi​=Rej∈I∑​⟨bj​,Mi​ρbj​⟩,qi​=Rej∈I∑​⟨bj​,Mi​σbj​⟩.

Its contribution is +∞+\infty+∞ if some iii satisfies pi>0p_i>0pi​>0 and qi=0q_i=0qi​=0; otherwise its contribution is

max⁡ ⁣{∑i=0n−1{0,pi=0,pilog⁡2(pi/qi),pi≠0, 0}.\max\!\left\{\sum_{i=0}^{n-1} \begin{cases} 0,&p_i=0,\\ p_i\log_2(p_i/q_i),&p_i\ne0, \end{cases}\ 0\right\}.max{i=0∑n−1​{0,pi​log2​(pi​/qi​),​pi​=0,pi​=0,​ 0}.

No assumptions ensure that ppp or qqq are probability laws. Unsummable basis sums return 000, and real division and logarithms use their total-function conventions. The empty family n=0n=0n=0 is admissible only on the zero Hilbert space and contributes 000.

QAlgorithms.Papers.Independent.Support50.P44.rotatedTranspose

Let B,CB,CB,C be finite types equipped with decidable equality. For arbitrary complex matrices ρBC\rho_{BC}ρBC​ and VVV indexed by B×CB\times CB×C, and arbitrary complex matrices U,XU,XU,X indexed by BBB, define

(ρB)b,b′=∑c∈C(ρBC)(b,c),(b′,c),D=f(ρB),f(x)=(x)−1,S=ρBC,(\rho_B)_{b,b'}=\sum_{c\in C}(\rho_{BC})_{(b,c),(b',c)},\qquad D=f(\rho_B),\quad f(x)=(\sqrt x)^{-1},\qquad S=\sqrt{\rho_{BC}},(ρB​)b,b′​=c∈C∑​(ρBC​)(b,c),(b′,c)​,D=f(ρB​),f(x)=(x​)−1,S=ρBC​​,

using real continuous functional calculus. The returned matrix is

VS((DUXU∗D)⊗IC)SV∗.V S\bigl((D U X U^*D)\otimes I_C\bigr)S V^*.VS((DUXU∗D)⊗IC​)SV∗.

There are no positivity, normalization, or unitarity assumptions on the arguments. The scalar functions are total: x=0\sqrt x=0x​=0 for x<0x<0x<0 and 0−1=00^{-1}=00−1=0; the real functional calculus returns zero for non-Hermitian inputs. Either index type may be empty.

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 31, 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