Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

IID ensemble uncertainty against collective measurements

Open
QAlgorithms.Papers.Independent.Intakenext100.P63.iid_collective_uncertainty

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

prove2quantum

Let p=(pi)i=1dp=(p_i)_{i=1}^dp=(pi​)i=1d​ be a probability vector with d≥1d\ge1d≥1, and let every ρi\rho_iρi​ be a normalized density on a nonzero finite-dimensional environment EEE. Set ρˉ=∑ipiρi\bar\rho=\sum_ip_i\rho_iρˉ​=∑i​pi​ρi​ and Mi=ρˉ−1/2piρiρˉ−1/2M_i=\bar\rho^{-1/2}p_i\rho_i\bar\rho^{-1/2}Mi​=ρˉ​−1/2pi​ρi​ρˉ​−1/2. View MMM as a POVM on supp⁡ρˉ\operatorname{supp}\bar\rhosuppρˉ​ and let H^(M)\widehat H(M)H(M) be its minimum output Shannon entropy there. Let I1,…,InI_1,\ldots,I_nI1​,…,In​ be IID with law ppp; for any finite collective POVM QQQ on E⊗nE^{\otimes n}E⊗n, define Pr⁡(In=in,J=j)=∏tpitTr⁡[(⨂tρit)Qj]\Pr(I^n=i^n,J=j)=\prod_tp_{i_t}\operatorname{Tr}[(\bigotimes_t\rho_{i_t})Q_j]Pr(In=in,J=j)=∏t​pit​​Tr[(⨂t​ρit​​)Qj​]. For 0<ε,δ<10<\varepsilon,\delta<10<ε,δ<1,

Hmin⁡ε(In∣J)≥n(H^(M)−δ)−16(log⁡2d)2δlog⁡21ε.H_{\min}^{\varepsilon}(I^n|J)\ge n(\widehat H(M)-\delta)-\frac{16(\log_2d)^2}{\delta}\log_2\frac1\varepsilon.Hminε​(In∣J)≥n(H(M)−δ)−δ16(log2​d)2​log2​ε1​.

For sufficiently large nnn, uniformly over QQQ,

Hmin⁡ε(In∣J)≥nH^(M)−8log⁡2dnlog⁡2(1/ε).H_{\min}^{\varepsilon}(I^n|J)\ge n\widehat H(M)-8\log_2d\sqrt{n\log_2(1/\varepsilon)}.Hminε​(In∣J)≥nH(M)−8log2​dnlog2​(1/ε)​.

All entropies are in bits; smoothing is over normalized joint densities at half trace-norm distance. The preparation labels are independent; Eve's measurement need not be a product measurement. Zero prior weights and rank-deficient average states remain allowed.

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 p.9, Corollary 9: IID labels and arbitrary collective environment POVMs.
The associated minimum is on supp(rho-bar); d counts labels, not Eve's outcomes. -/
theorem iid_collective_uncertainty {E : Type} [Fintype E] [DecidableEq E] [Nonempty E]
    (d : ℕ) (hd : 0 < d) (p : Fin d → ℝ) (hp : IsDistribution p)
    (rho : Fin d → Mat E) (hrho : ∀ i, IsDensityMatrix (rho i))
    (eps : ℝ) (he0 : 0 < eps) (he1 : eps < 1) :
    (∀ delta : ℝ, 0 < delta → delta < 1 → ∀ n : ℕ,
      ∀ Q : Measurement (Fin n → E),
      (n : ℝ) * (associatedMinimum p rho - delta) -
        16 * (Real.logb 2 d) ^ 2 / delta * Real.logb 2 (1 / eps) ≤
        traceSmoothConditionalMinBits eps (classicalJoint (iidJoint p rho n Q))) ∧
    (∃ n0 : ℕ, ∀ n ≥ n0, ∀ Q : Measurement (Fin n → E),
      (n : ℝ) * associatedMinimum p rho -
        8 * Real.logb 2 d * Real.sqrt ((n : ℝ) * Real.logb 2 (1 / eps)) ≤
        traceSmoothConditionalMinBits eps (classicalJoint (iidJoint p rho n Q))) := 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. 9, Corollary 9: IID ensemble uncertainty against collective measurements
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>0d>0d>0 be a natural number, let p0,…,pd−1≥0p_0,\ldots,p_{d-1}\ge0p0​,…,pd−1​≥0 sum to 111, and let ρi\rho_iρi​ be positive semidefinite complex matrices on EEE with trace 111. Fix 0<ε<10<\varepsilon<10<ε<1. Set ρˉ=∑ipiρi\bar\rho=\sum_i p_i\rho_iρˉ​=∑i​pi​ρi​, S=f(ρˉ)S=f(\bar\rho)S=f(ρˉ​) for the continuous functional calculus function f(x)=(x)−1f(x)=(\sqrt{x})^{-1}f(x)=(x​)−1, with f(0)=0f(0)=0f(0)=0, and Ai=S(piρi)SA_i=S(p_i\rho_i)SAi​=S(pi​ρi​)S. Define

hassoc=inf⁡ω⪰0, tr⁡ω=1ker⁡ρˉ⊆ker⁡ω[−∑iailog⁡2ai],ai=Re⁡tr⁡(Aiω).h_{\mathrm{assoc}}= \inf_{\substack{\omega\succeq0,\ \operatorname{tr}\omega=1\\ \ker\bar\rho\subseteq\ker\omega}} \left[-\sum_i a_i\log_2a_i\right], \qquad a_i=\operatorname{Re}\operatorname{tr}(A_i\omega).hassoc​=ω⪰0, trω=1kerρˉ​⊆kerω​inf​[−i∑​ai​log2​ai​],ai​=Retr(Ai​ω).

For a measurement QQQ on EnE^nEn, having any positive finite number sss of positive semidefinite effects QjQ_jQj​ summing to the identity, define

PQ(i,j)=(∏t<npit)Re⁡tr⁡ ⁣(Qj⨂t<nρit),P_Q(i,j)=\left(\prod_{t<n}p_{i_t}\right) \operatorname{Re}\operatorname{tr}\!\left(Q_j\bigotimes_{t<n}\rho_{i_t}\right),PQ​(i,j)=(t<n∏​pit​​)Retr(Qj​t<n⨂​ρit​​),

and let XQX_QXQ​ be the diagonal matrix on {0,…,d−1}n×{0,…,s−1}\{0,\ldots,d-1\}^n\times\{0,\ldots,s-1\}{0,…,d−1}n×{0,…,s−1} with diagonal PQP_QPQ​. For a matrix YYY on a product L×JL\times JL×J, define Hmin⁡(Y)H_{\min}(Y)Hmin​(Y) as the real conversion of the extended real supremum of all λ∈R\lambda\in\mathbb Rλ∈R for which some density matrix σ\sigmaσ on JJJ satisfies 2−λIL⊗σ−Y⪰02^{-\lambda}I_L\otimes\sigma-Y\succeq02−λIL​⊗σ−Y⪰0, with either infinity converted to 000, and define

Hmin⁡ε(Y)=sup⁡ω⪰0, tr⁡ω=112Re⁡tr⁡(Y−ω)†(Y−ω)≤εHmin⁡(ω).H_{\min}^{\varepsilon}(Y)= \sup_{\substack{\omega\succeq0,\ \operatorname{tr}\omega=1\\ \frac12\operatorname{Re}\operatorname{tr}\sqrt{(Y-\omega)^\dagger(Y-\omega)} \le\varepsilon}}H_{\min}(\omega).Hminε​(Y)=ω⪰0, trω=121​Retr(Y−ω)†(Y−ω)​≤ε​sup​Hmin​(ω).

For every 0<δ<10<\delta<10<δ<1, every n∈Nn\in\mathbb Nn∈N, and every such QQQ,

n(hassoc−δ)−16(log⁡2d)2δlog⁡2(1/ε)≤Hmin⁡ε(XQ).n(h_{\mathrm{assoc}}-\delta) -\frac{16(\log_2d)^2}{\delta}\log_2(1/\varepsilon) \le H_{\min}^{\varepsilon}(X_Q).n(hassoc​−δ)−δ16(log2​d)2​log2​(1/ε)≤Hminε​(XQ​).

Moreover, there exists n0∈Nn_0\in\mathbb Nn0​∈N such that for all n≥n0n\ge n_0n≥n0​ and all such QQQ,

nhassoc−8log⁡2dnlog⁡2(1/ε)≤Hmin⁡ε(XQ).nh_{\mathrm{assoc}}-8\log_2d\sqrt{n\log_2(1/\varepsilon)} \le H_{\min}^{\varepsilon}(X_Q).nhassoc​−8log2​dnlog2​(1/ε)​≤Hminε​(XQ​).

Zero prior weights are permitted. The first bound includes n=0n=0n=0, using singleton configuration spaces and empty products equal to 111; n0n_0n0​ has no stipulated lower bound.

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