Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Remark 5, (34): positive-map decoder converse

Open
QAlgorithms.Papers.Independent.Intakenext100.P20.positive_decoder_converse

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let Ξ\XiΞ be an arbitrary discrete label set, let ρi\rho_iρi​ be normalized pure source states on a nonzero finite-dimensional complex space H\mathcal HH, and let pi≥0p_i\ge0pi​≥0 sum to one. Write ρp=∑ipiρi\rho_p=\sum_i p_i\rho_iρp​=∑i​pi​ρi​. Let K\mathcal KK be finite and nonzero, F:Ξ→S(K)F:\Xi\to\mathcal S(\mathcal K)F:Ξ→S(K) any visible encoder, and DDD a positive, trace-preserving complex-linear decoder. For ϵ=∑ipi(1−Tr⁡(D(F(i))ρi))\epsilon=\sum_i p_i(1-\operatorname{Tr}(D(F(i))\rho_i))ϵ=∑i​pi​(1−Tr(D(F(i))ρi​)) and every real λ\lambdaλ,

1−ϵ≤2eλdim⁡K+2Tr⁡(ρp{ρp−eλI≥0}).1-\epsilon\le2e^\lambda\dim\mathcal K+2\operatorname{Tr}\bigl(\rho_p\{\rho_p-e^\lambda I\ge0\}\bigr).1−ϵ≤2eλdimK+2Tr(ρp​{ρp​−eλI≥0}).

Complete positivity is not required for this factor-two spectral converse.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P20
Formal statement
noncomputable section

open scoped Matrix ENNReal ComplexOrder Topology

namespace QAlgorithms.Papers.Independent.Intakenext100.P20

open QAlgorithms.Papers.Independent.Information100.P08 (IsPure)

open QAlgorithms.Papers.Independent.Information100.P47 (IsProbability)

open QAlgorithms.Papers.Independent.Information100.P53 (SpectralData)

open QAlgorithms.Papers.Independent.Gap48.P19 (shannonNats)

open QAlgorithms.Papers.Independent.Dependency50.P28 (classicalD)

attribute [local instance] Classical.propDecidable

/-- Remark 5, PDF p.6, (34), Appendix D p.11: positivity suffices when
both right-hand terms are multiplied by two; trace preservation is retained. -/
theorem positive_decoder_converse {L : Type*} {d m : ℕ} (S : DiscretePureSource L d)
    (hm : 0 < m) (F : L → Matrix (Fin m) (Fin m) ℂ)
    (hF : ∀ i, IsDensityMatrix (F i))
    (D : Matrix (Fin m) (Fin m) ℂ →ₗ[ℂ] Matrix (Fin d) (Fin d) ℂ)
    (hD : IsPositiveTracePreserving D) (lambda : ℝ) :
    1 - averageLoss S.weight S.state (fun i => D (F i)) false ≤
      2 * Real.exp lambda * m +
      2 * (S.average * thresholdProjection S.average lambda true).trace.re := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P20

end
Source
Exponents of quantum fixed-length pure state source coding, arXiv:quant-ph/0202002v6, PDF p. 6, Remark 5, (34): positive-map decoder converse
Read-back

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

Let LLL be any type, let d,md,md,m be natural numbers, and let SSS specify d>0d>0d>0, nonnegative summable weights wiw_iwi​ with ∑i′wi=1\sum'_iw_i=1∑i′​wi​=1, and density matrices ρi=vivi†\rho_i=v_iv_i^\daggerρi​=vi​vi†​ for unit vectors viv_ivi​, where density matrices are positive semidefinite and have trace 111. Assume m>0m>0m>0, let Fi∈Cm×mF_i\in\mathbb C^{m\times m}Fi​∈Cm×m be a density matrix for every i∈Li\in Li∈L, and let D:Cm×m→Cd×dD:\mathbb C^{m\times m}\to\mathbb C^{d\times d}D:Cm×m→Cd×d be a complex-linear map taking every positive semidefinite matrix to a positive semidefinite matrix and satisfying Tr⁡D(X)=Tr⁡X\operatorname{Tr}D(X)=\operatorname{Tr}XTrD(X)=TrX for every matrix XXX. For every real λ\lambdaλ, set ρˉ=∑i′wiρi\bar\rho=\sum'_iw_i\rho_iρˉ​=∑i′​wi​ρi​ and let P≥P_\geP≥​ be the functional-calculus projection of ρˉ\bar\rhoρˉ​ associated with the scalar condition eλ≤xe^\lambda\le xeλ≤x. Then

1−∑i′wi ⁣[1−Re⁡Tr⁡(D(Fi)ρi)]≤2eλm+2Re⁡Tr⁡(ρˉP≥).1-\sum'_i w_i\!\left[1-\operatorname{Re}\operatorname{Tr}(D(F_i)\rho_i)\right] \le 2e^\lambda m+2\operatorname{Re}\operatorname{Tr}(\bar\rho P_\ge).1−i∑′​wi​[1−ReTr(D(Fi​)ρi​)]≤2eλm+2ReTr(ρˉ​P≥​).

No finiteness or countability assumption is imposed on LLL, and the stated conditions on DDD are positivity and trace preservation.

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

    Confirmed by the moderator at approval.

  • 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