Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1: label-versus-mean Shannon distinguishability

Proved
QAlgorithms.Papers.Independent.Support50.P27.label_mean_shannon

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

prove2quantum

Let m≥0m\ge0m≥0, and let {qx,ρx}x=12m\{q_x,\rho_x\}_{x=1}^{2^m}{qx​,ρx​}x=12m​ be an ensemble of density operators on a finite dimensional nonzero Hilbert space. Thus qx≥0q_x\ge0qx​≥0, ∑xqx=1\sum_xq_x=1∑x​qx​=1, and every ρx\rho_xρx​ is positive semidefinite with trace one, including at zero-weight labels. Write ρˉ=∑xqxρx\bar\rho=\sum_xq_x\rho_xρˉ​=∑x​qx​ρx​. Let IaccI_{\mathrm{acc}}Iacc​ be the supremum, over finite POVMs, of the mutual information in bits between the ensemble label and the measurement outcome. Let SD⁡(ρ,σ)\operatorname{SD}(\rho,\sigma)SD(ρ,σ) denote accessible information of the equiprobable binary ensemble consisting of ρ\rhoρ and σ\sigmaσ. Then

∀x,qxSD⁡(ρx,ρˉ)≤Iacc({qx,ρx}).\forall x,\qquad q_x\operatorname{SD}(\rho_x,\bar\rho)\le I_{\mathrm{acc}}(\{q_x,\rho_x\}).∀x,qx​SD(ρx​,ρˉ​)≤Iacc​({qx​,ρx​}).

The estimate relates a single label's distinguishability from the ensemble mean to the information available from the whole ensemble. No strictly positive weight assumption is imposed.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P27
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Support50.P27

open scoped BigOperators Matrix ComplexConjugate ComplexOrder

open QAlgorithms.Papers.Independent.Dependency50.P07
  (CQData ensembleMean ensembleInformation accessibleInformation)

open QAlgorithms.Papers.Independent.Dependency50.P24 (Key)

open QAlgorithms.Papers.Independent.Dependency50.P47 (cqMatrix)

attribute [local instance] Classical.decEq Classical.propDecidable

/-- PDF p.12, Lemma 1: any label's weighted Shannon distinguishability from
the ensemble mean is at most accessible information. Zero label weights and
m=0 are allowed; all conditional states are normalized density matrices. -/
theorem label_mean_shannon {m : ℕ} {E : Type} [Fintype E] [Nonempty E]
    (A : CQData (Fin (2 ^ m)) E) (hA : A.Valid) :
    ∀ x, A.prob x * shannonDistinguishability (A.state x) (ensembleMean A) ≤
      accessibleInformation A := by sorry

end QAlgorithms.Papers.Independent.Support50.P27

end
Source
The Universal Composable Security of Quantum Key Distribution, arXiv:quant-ph/0409078v1, PDF p. 12, Lemma 1: label-versus-mean Shannon distinguishability
Read-back

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

For every natural number mmm, finite nonempty type EEE, and ensemble AAA consisting of numbers px≥0p_x\ge0px​≥0 summing to 111 over x∈{0,…,2m−1}x\in\{0,\ldots,2^m-1\}x∈{0,…,2m−1} and positive semidefinite, trace-one matrices ρx\rho_xρx​ on EEE, let ρˉ=∑xpxρx\bar\rho=\sum_xp_x\rho_xρˉ​=∑x​px​ρx​. For any finite ensemble (qi,σi)(q_i,\sigma_i)(qi​,σi​) on EEE, define A(q,σ)\mathcal A(q,\sigma)A(q,σ) as the real supremum over all finite families Mt⪰0M_t\succeq0Mt​⪰0 with at least one outcome and ∑tMt=I\sum_tM_t=I∑t​Mt​=I, of H(q)+H(v)−H(J)H(q)+H(v)-H(J)H(q)+H(v)−H(J), where J(i,t)=qiRe⁡tr⁡(Mtσi)J(i,t)=q_i\operatorname{Re}\operatorname{tr}(M_t\sigma_i)J(i,t)=qi​Retr(Mt​σi​), v(t)=∑iJ(i,t)v(t)=\sum_iJ(i,t)v(t)=∑i​J(i,t), and H(a)=−∑iailog⁡2aiH(a)=-\sum_i a_i\log_2a_iH(a)=−∑i​ai​log2​ai​ with zero summands interpreted as 000. The statement is that every label xxx satisfies

px A((12,12),(ρx,ρˉ))≤A(p,ρ).p_x\,\mathcal A\bigl((\tfrac12,\tfrac12),(\rho_x,\bar\rho)\bigr) \le \mathcal A(p,\rho).px​A((21​,21​),(ρx​,ρˉ​))≤A(p,ρ).

Labels with px=0p_x=0px​=0 are included; m=0m=0m=0, giving a single label, is also included.

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).

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