Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite-block i.i.d. weighted testing inequality

Open
QAlgorithms.Papers.Independent.Intakethird100.P04.iid_weighted_testing_inequality

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let ρ,σ\rho,\sigmaρ,σ be density operators on an arbitrary complex Hilbert space, and let p,qp,qp,q be the spectral probability weights p(i,j)=λi∣⟨xi,yj⟩∣2p(i,j)=\lambda_i|\langle x_i,y_j\rangle|^2p(i,j)=λi​∣⟨xi​,yj​⟩∣2, q(i,j)=γj∣⟨xi,yj⟩∣2q(i,j)=\gamma_j|\langle x_i,y_j\rangle|^2q(i,j)=γj​∣⟨xi​,yj​⟩∣2 from complete eigenbases of ρ,σ\rho,\sigmaρ,σ. For every positive integer nnn, every bounded effect 0≤Tn≤I0\le T_n\le I0≤Tn​≤I on the completed tensor power H⊗nH^{\otimes n}H⊗n, and every b∈Rb\in\mathbb Rb∈R, define αn=1−Tr⁡(ρ⊗nTn)\alpha_n=1-\operatorname{Tr}(\rho^{\otimes n}T_n)αn​=1−Tr(ρ⊗nTn​), βn=Tr⁡(σ⊗nTn)\beta_n=\operatorname{Tr}(\sigma^{\otimes n}T_n)βn​=Tr(σ⊗nTn​) and the product laws pn(ω1,…,ωn)=∏t=1np(ωt)p^n(\omega_1,\ldots,\omega_n)=\prod_{t=1}^n p(\omega_t)pn(ω1​,…,ωn​)=∏t=1n​p(ωt​) and qnq^nqn analogously. Set

fn(b)=∑ω:pn(ω)≤e−nbqn(ω)pn(ω),gn(b)=∑ω:pn(ω)>e−nbqn(ω)qn(ω).f_n(b)=\sum_{\omega:p^n(\omega)\le e^{-nb}q^n(\omega)}p^n(\omega),\qquad g_n(b)=\sum_{\omega:p^n(\omega)>e^{-nb}q^n(\omega)}q^n(\omega).fn​(b)=ω:pn(ω)≤e−nbqn(ω)∑​pn(ω),gn​(b)=ω:pn(ω)>e−nbqn(ω)∑​qn(ω).

Then

αn+e−nbβn≥12(fn(b)+e−nbgn(b)).\alpha_n+e^{-nb}\beta_n\ge\frac12\bigl(f_n(b)+e^{-nb}g_n(b)\bigr).αn​+e−nbβn​≥21​(fn​(b)+e−nbgn​(b)).

This is the finite-block comparison underlying the paper's large-deviation argument. The multiplicative events remain defined at zero spectral weights.

Formalization Note Lean index kkk represents n=k+1n=k+1n=k+1. The completed tensor power is realized in its complete orthonormal coordinates ℓ2(In)\ell^2(I^n)ℓ2(In) by the actual bounded operator with the tensor-product matrix coefficients.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P04
Formal statement
noncomputable section

open Filter

open scoped ENNReal NNReal BigOperators ComplexOrder

namespace QAlgorithms.Papers.Independent.Intakethird100.P04

attribute [local instance] Classical.propDecidable Classical.decEq

attribute [local instance] IsStarNormal.instContinuousFunctionalCalculus

open QAlgorithms.Papers.Independent.Dependency50.P13
  (State operatorTrace relativeEntropy)

open QAlgorithms.Papers.Independent.Support50.P20
  (Effect traceAcceptance IsHilbertCPTP BlockHilbert blockBasis)

open QAlgorithms.Papers.Independent.Frontier18.P18 (boundedOperator)

variable {H K : Type*}

variable [NormedAddCommGroup H] [InnerProductSpace ℂ H] [CompleteSpace H]

variable [NormedAddCommGroup K] [InnerProductSpace ℂ K] [CompleteSpace K]

/-- PDF p.4, (20)--(22): i.i.d. weighted testing inequality. Index k denotes
n=k+1, and b is any real number. Multiplicative events include zero masses. -/
theorem iid_weighted_testing_inequality {I : Type} {J L : Type*}
    (basis : HilbertBasis I ℂ H) (rho sigma : State basis)
    (x : DensitySpectrum rho J) (y : DensitySpectrum sigma L)
    (k : ℕ) (T : Effect (BlockHilbert I k)) (b : ℝ) :
    let delta := ENNReal.ofReal (Real.exp (-((k + 1 : ℕ) : ℝ) * b))
    (1 / 2 : ℝ≥0∞) *
        (lowerMass (iidLaw (spectralP x y) k) (iidLaw (spectralQ x y) k) delta +
          delta * upperMass (iidLaw (spectralP x y) k) (iidLaw (spectralQ x y) k) delta) ≤
      ENNReal.ofReal (1 - traceAcceptance (blockBasis I k) T.val (iidOperator basis rho.val.val k)) +
        delta * ENNReal.ofReal
          (traceAcceptance (blockBasis I k) T.val (iidOperator basis sigma.val.val k)) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P04

end
Source
The Converse Part of The Theorem for Quantum Hoeffding Bound, arXiv:quant-ph/0611289v1, PDF p. 4, §3, (20)–(22)
Read-back

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

Let HHH be a complete complex inner-product space, let I,J,LI,J,LI,J,L be arbitrary index types, and let b=(bi)i∈Ib=(b_i)_{i\in I}b=(bi​)i∈I​ be a Hilbert basis. Let ρ,σ\rho,\sigmaρ,σ be states with underlying bounded operators R,SR,SR,S, each self-adjoint with nonnegative quadratic forms, each satisfying trace one relative to bbb, and each admitting a representation Av=∑r∈N⟨vr,v⟩urAv=\sum_{r\in\mathbb N}\langle v_r,v\rangle u_rAv=∑r∈N​⟨vr​,v⟩ur​ with ∑r∥ur∥∥vr∥<∞\sum_r\|u_r\|\|v_r\|<\infty∑r​∥ur​∥∥vr​∥<∞. Let xxx supply a Hilbert basis (ej)j∈J(e_j)_{j\in J}(ej​)j∈J​ and finite nonnegative eigenvalues λj\lambda_jλj​ with Rej=λjejRe_j=\lambda_j e_jRej​=λj​ej​, and let yyy supply a Hilbert basis (fℓ)ℓ∈L(f_\ell)_{\ell\in L}(fℓ​)ℓ∈L​ and finite nonnegative eigenvalues μℓ\mu_\ellμℓ​ with Sfℓ=μℓfℓSf_\ell=\mu_\ell f_\ellSfℓ​=μℓ​fℓ​. Fix any k∈Nk\in\mathbb Nk∈N, any real number b0b_0b0​, and any bounded operator TTT on Hk=ℓ2(Ik+1;C)\mathcal H_k=\ell^2(I^{k+1};\mathbb C)Hk​=ℓ2(Ik+1;C) such that TTT and 1−T1-T1−T are self-adjoint with nonnegative quadratic forms. Define P(j,ℓ)=λj∣⟨ej,fℓ⟩∣2P(j,\ell)=\lambda_j|\langle e_j,f_\ell\rangle|^2P(j,ℓ)=λj​∣⟨ej​,fℓ​⟩∣2, Q(j,ℓ)=μℓ∣⟨ej,fℓ⟩∣2Q(j,\ell)=\mu_\ell|\langle e_j,f_\ell\rangle|^2Q(j,ℓ)=μℓ​∣⟨ej​,fℓ​⟩∣2, and, for w:{0,…,k}→J×Lw:\{0,\ldots,k\}\to J\times Lw:{0,…,k}→J×L, define Pk(w)=∏t=0kP(w(t))P_k(w)=\prod_{t=0}^kP(w(t))Pk​(w)=∏t=0k​P(w(t)) and Qk(w)=∏t=0kQ(w(t))Q_k(w)=\prod_{t=0}^kQ(w(t))Qk​(w)=∏t=0k​Q(w(t)). Put δ=exp⁡(−(k+1)b0)\delta=\exp(-(k+1)b_0)δ=exp(−(k+1)b0​), embedded into the extended nonnegative reals. Define RkR_kRk​ by selecting a bounded operator on Hk\mathcal H_kHk​ whose canonical-basis coefficients are (Rkev)(u)=∏t=0k⟨bu(t),Rbv(t)⟩(R_k e_v)(u)=\prod_{t=0}^k\langle b_{u(t)},Rb_{v(t)}\rangle(Rk​ev​)(u)=∏t=0k​⟨bu(t)​,Rbv(t)​⟩, returning zero if no such operator exists, and define SkS_kSk​ in the same way using SSS; here eue_ueu​ denotes the canonical unit vector. Set ak(T,A)=Re⁡∑u∈Ik+1⟨eu,TAeu⟩a_k(T,A)=\operatorname{Re}\sum_{u\in I^{k+1}}\langle e_u,TAe_u\rangleak​(T,A)=Re∑u∈Ik+1​⟨eu​,TAeu​⟩, with the total complex sum returning zero for a nonsummable family. Then

12(∑w∈(J×L)k+1Pk(w)≤δQk(w)Pk(w)+δ∑w∈(J×L)k+1δQk(w)<Pk(w)Qk(w))≤[1−ak(T,Rk)]++δ[ak(T,Sk)]+\frac12\left( \sum_{\substack{w\in(J\times L)^{k+1}\\P_k(w)\le\delta Q_k(w)}}P_k(w) + \delta\sum_{\substack{w\in(J\times L)^{k+1}\\\delta Q_k(w)<P_k(w)}}Q_k(w) \right) \le [1-a_k(T,R_k)]_+ +\delta[a_k(T,S_k)]_+21​​w∈(J×L)k+1Pk​(w)≤δQk​(w)​∑​Pk​(w)+δw∈(J×L)k+1δQk​(w)<Pk​(w)​∑​Qk​(w)​≤[1−ak​(T,Rk​)]+​+δ[ak​(T,Sk​)]+​

in the extended nonnegative reals, where [x]+=max⁡(x,0)[x]_+=\max(x,0)[x]+​=max(x,0) is embedded into that space. The real parameter b0b_0b0​ has no sign restriction, while δ\deltaδ is always finite and strictly positive. Equality is included in the first selection and excluded from the second. The case k=0k=0k=0 uses one factor and a one-coordinate block; zero eigenvalues and zero overlaps are allowed.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 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