Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

High-order smooth min-entropy uncertainty for a product measurement

Open
QAlgorithms.Papers.Independent.Intakenext100.P63.highOrder_smooth_uncertainty

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

prove2quantum

Let M=(Mi)i=1dM=(M_i)_{i=1}^dM=(Mi​)i=1d​ be a POVM on a nonzero finite-dimensional input space, where d≥1d\ge1d≥1 counts its classical outcomes. Write H^(M)=min⁡σH({Tr⁡σMi}i)\widehat H(M)=\min_\sigma H(\{\operatorname{Tr}\sigma M_i\}_i)H(M)=minσ​H({TrσMi​}i​), optimizing over normalized input densities; this minimum is attained. Smooth min-entropy optimizes over normalized states within half trace-norm distance ε\varepsilonε. For 0<ε,δ<10<\varepsilon,\delta<10<ε,δ<1, any n≥0n\ge0n≥0, and any normalized, possibly entangled input ψ\psiψ on nnn systems,

Hmin⁡ε(M⊗n(ψ))≥n(H^(M)−δ)−16(log⁡2d)2δlog⁡21ε.H_{\min}^{\varepsilon}(M^{\otimes n}(\psi))\ge n(\widehat H(M)-\delta)-\frac{16(\log_2d)^2}{\delta}\log_2\frac1\varepsilon.Hminε​(M⊗n(ψ))≥n(H(M)−δ)−δ16(log2​d)2​log2​ε1​.

Moreover, for fixed MMM and ε\varepsilonε there is a threshold independent of ψ\psiψ such that for every subsequent nnn,

Hmin⁡ε(M⊗n(ψ))≥nH^(M)−8log⁡2dnlog⁡2(1/ε).H_{\min}^{\varepsilon}(M^{\otimes n}(\psi))\ge n\widehat H(M)-8\log_2d\sqrt{n\log_2(1/\varepsilon)}.Hminε​(M⊗n(ψ))≥nH(M)−8log2​dnlog2​(1/ε)​.

For d=1d=1d=1 the smooth output min-entropy is exactly zero for all nnn. The measurement outcome law is represented by its diagonal density. This supplies uncertainty against arbitrary entangled inputs without an independence assumption.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P63
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P63

open QAlgorithms Filter

open QAlgorithms.Papers.Independent.Information100.P63 (Mat)

open QAlgorithms.Papers.Independent.Information100.P04 (Measurement)

open QAlgorithms.Papers.Independent.Information100.P27 (shannon labelInformation)

open QAlgorithms.Papers.Independent.Information100.P71 (channelPower dilationMap SupportIncluded)

open QAlgorithms.Papers.Independent.Bridge50.P47 (SymmetricIndex universalSymmetricDilation)

open QAlgorithms.Learning (IsDistribution)

open scoped Matrix ComplexConjugate ComplexOrder

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF pp.8,16–17, Proposition 6: both smooth min-entropy uncertainty bounds,
for arbitrary entangled inputs. d is the number of OUTPUT outcomes.
The deterministic d=1 case is included explicitly. -/
theorem highOrder_smooth_uncertainty {E : Type} [Fintype E] [DecidableEq E] [Nonempty E]
    (d : ℕ) (hd : 0 < d) (M : Fin d → Mat E) (hM : IsPOVM M)
    (eps : ℝ) (he0 : 0 < eps) (he1 : eps < 1) :
    (∃ psi : Mat E, IsDensityMatrix psi ∧
      shannon (fun i => effectProb (M i) psi) = povmMinimumShannon M) ∧
    (∀ (delta : ℝ), 0 < delta → delta < 1 → ∀ (n : ℕ) (psi : Mat (Fin n → E)),
      IsDensityMatrix psi →
      (n : ℝ) * (povmMinimumShannon M - delta) -
        16 * (Real.logb 2 d) ^ 2 / delta * Real.logb 2 (1 / eps) ≤
        traceSmoothStateMinBits eps (measuredState M n psi)) ∧
    (∃ n0 : ℕ, ∀ n ≥ n0, ∀ psi : Mat (Fin n → E), IsDensityMatrix psi →
      (n : ℝ) * povmMinimumShannon M -
        8 * Real.logb 2 d * Real.sqrt ((n : ℝ) * Real.logb 2 (1 / eps)) ≤
        traceSmoothStateMinBits eps (measuredState M n psi)) ∧
    (d = 1 → ∀ (n : ℕ) (psi : Mat (Fin n → E)), IsDensityMatrix psi →
      traceSmoothStateMinBits eps (measuredState M n psi) = 0) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P63

end
Source
Weak locking capacity of quantum channels can be much larger than private capacity, arXiv:1403.6361v3, PDF p. 8, Proposition 6: high-order smooth min-entropy uncertainty
Read-back

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

Let EEE be a finite nonempty type with decidable equality, let d∈Nd\in\mathbb Nd∈N satisfy d>0d>0d>0, and let M0,…,Md−1M_0,\ldots,M_{d-1}M0​,…,Md−1​ be positive semidefinite complex matrices on EEE whose sum is the identity. Fix 0<ε<10<\varepsilon<10<ε<1. For a probability vector aaa, put H(a)=−∑iailog⁡2aiH(a)=-\sum_i a_i\log_2a_iH(a)=−∑i​ai​log2​ai​, and define

hM=inf⁡ω⪰0tr⁡ω=1H((Re⁡tr⁡(Miω))i<d).h_M=\inf_{\substack{\omega\succeq0\\ \operatorname{tr}\omega=1}} H\bigl((\operatorname{Re}\operatorname{tr}(M_i\omega))_{i<d}\bigr).hM​=ω⪰0trω=1​inf​H((Retr(Mi​ω))i<d​).

For any matrix XXX, write ∥X∥tr=Re⁡tr⁡X†X\|X\|_{\mathrm{tr}}=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}∥X∥tr​=RetrX†X​, let ∥X∥op\|X\|_{\mathrm{op}}∥X∥op​ be its Euclidean operator norm, and define

Hmin⁡ε(X)=sup⁡ω⪰0, tr⁡ω=112∥X−ω∥tr≤ε−log⁡2∥ω∥op.H_{\min}^{\varepsilon}(X)= \sup_{\substack{\omega\succeq0,\ \operatorname{tr}\omega=1\\ \frac12\|X-\omega\|_{\mathrm{tr}}\le\varepsilon}} -\log_2\|\omega\|_{\mathrm{op}}.Hminε​(X)=ω⪰0, trω=121​∥X−ω∥tr​≤ε​sup​−log2​∥ω∥op​.

For n∈Nn\in\mathbb Nn∈N and a density matrix ψ\psiψ on EnE^nEn, let DM,n(ψ)D_{M,n}(\psi)DM,n​(ψ) be the diagonal matrix indexed by i∈{0,…,d−1}ni\in\{0,\ldots,d-1\}^ni∈{0,…,d−1}n, with diagonal entry Re⁡tr⁡((⨂t<nMit)ψ)\operatorname{Re}\operatorname{tr}((\bigotimes_{t<n}M_{i_t})\psi)Retr((⨂t<n​Mit​​)ψ). There exists a density matrix attaining hMh_MhM​; for every 0<δ<10<\delta<10<δ<1, every n∈Nn\in\mathbb Nn∈N, and every density matrix ψ\psiψ on EnE^nEn,

n(hM−δ)−16(log⁡2d)2δlog⁡2(1/ε)≤Hmin⁡ε(DM,n(ψ));n(h_M-\delta)-\frac{16(\log_2d)^2}{\delta}\log_2(1/\varepsilon) \le H_{\min}^{\varepsilon}(D_{M,n}(\psi));n(hM​−δ)−δ16(log2​d)2​log2​(1/ε)≤Hminε​(DM,n​(ψ));

there exists n0∈Nn_0\in\mathbb Nn0​∈N such that for every n≥n0n\ge n_0n≥n0​ and every such ψ\psiψ,

nhM−8log⁡2dnlog⁡2(1/ε)≤Hmin⁡ε(DM,n(ψ));nh_M-8\log_2d\sqrt{n\log_2(1/\varepsilon)} \le H_{\min}^{\varepsilon}(D_{M,n}(\psi));nhM​−8log2​dnlog2​(1/ε)​≤Hminε​(DM,n​(ψ));

and if d=1d=1d=1, then Hmin⁡ε(DM,n(ψ))=0H_{\min}^{\varepsilon}(D_{M,n}(\psi))=0Hminε​(DM,n​(ψ))=0 for every nnn and every such ψ\psiψ. A density matrix means a positive semidefinite matrix with trace 111. The universal quantifiers include n=0n=0n=0, where configuration spaces are singletons and empty tensor products have entry 111; no positivity condition is imposed on n0n_0n0​.

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