Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Half-error specialization of the one-shot lower bound

Open
QAlgorithms.Papers.Independent.Support50.P20.oneShotCapacity_halfError

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

prove2quantum

Let W:x↦ρxW:x\mapsto\rho_xW:x↦ρx​ be an arbitrary classical-quantum channel on a nonempty input set, with normalized trace-class output states. Let Cϵ(W)C_\epsilon(W)Cϵ​(W) be the extended supremum of rates log⁡2m\log_2 mlog2​m of finite-message codes with complete decoding POVMs and average error at most ϵ\epsilonϵ. For a discrete input law PPP, define the joint state πPAB=∑xP(x)∣x⟩⟨x∣⊗ρx\pi_P^{AB}=\sum_xP(x)|x\rangle\langle x|\otimes\rho_xπPAB​=∑x​P(x)∣x⟩⟨x∣⊗ρx​ and its marginals πPA,πPB\pi_P^A,\pi_P^BπPA​,πPB​. For 0<ϵ<10<\epsilon<10<ϵ<1,

Cϵ(W)≥sup⁡PDHϵ/2(πPAB∥πPA⊗πPB)−log⁡2(1/ϵ)−4.C_\epsilon(W)\ge\sup_P D_H^{\epsilon/2}(\pi_P^{AB}\|\pi_P^A\otimes\pi_P^B)-\log_2(1/\epsilon)-4.Cϵ​(W)≥Psup​DHϵ/2​(πPAB​∥πPA​⊗πPB​)−log2​(1/ϵ)−4.

This is the specialization of Theorem 1 obtained by taking the auxiliary error parameter equal to half the coding error. All logarithms and rates are in bits.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P20
Formal statement
noncomputable section

open Filter

open scoped ENNReal

namespace QAlgorithms.Papers.Independent.Support50.P20

attribute [local instance] Classical.propDecidable Classical.decEq

open QAlgorithms.Papers.Independent.Dependency50.P13
  (IsTraceClass IsPositive operatorTrace State)

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

variable {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℂ H] [CompleteSpace H]

/-- PDF pp.2–3, Remark 1, (4): the epsilonPrime=epsilon/2 lower bound in bits. -/
theorem oneShotCapacity_halfError {X I : Type*} [Nonempty X]
    (b : HilbertBasis I ℂ H) (W : ClassicalInputChannel X b) (epsilon : ℝ)
    (hZero : 0 < epsilon) (hOne : epsilon < 1) :
    optimizedTestingInformation b W (epsilon / 2) -
      (logTwo (1 / epsilon) : ℝ) - 4 ≤ oneUseCodeCapacity b W epsilon := by sorry

end QAlgorithms.Papers.Independent.Support50.P20

end
Source
One-Shot Classical-Quantum Capacity and Hypothesis Testing, arXiv:1007.5456v3, PDF p. 2, Remark 1, (4): epsilon_prime=epsilon/2 one-shot lower bound
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 XXX be any nonempty type, let III be any type, and let b=(bi)i∈Ib=(b_i)_{i\in I}b=(bi​)i∈I​ be a Hilbert basis. Write tr⁡bT=∑i⟨bi,Tbi⟩\operatorname{tr}_bT=\sum_i\langle b_i,Tb_i\rangletrb​T=∑i​⟨bi​,Tbi​⟩. Let WxW_xWx​, for every x∈Xx\in Xx∈X, be a bounded complex-linear operator that is self-adjoint with nonnegative real quadratic form and trace 111, and admits a representation Wxy=∑r=0∞⟨vr,y⟩urW_xy=\sum_{r=0}^\infty\langle v_r,y\rangle u_rWx​y=∑r=0∞​⟨vr​,y⟩ur​ with ∑r∥ur∥∥vr∥<∞\sum_r\|u_r\|\|v_r\|<\infty∑r​∥ur​∥∥vr​∥<∞. An effect QQQ means that both QQQ and 1−Q1-Q1−Q are bounded self-adjoint operators with nonnegative real quadratic forms; put a(Q,R)=Re⁡tr⁡b(QR)a(Q,R)=\operatorname{Re}\operatorname{tr}_b(QR)a(Q,R)=Retrb​(QR). For a probability mass function PPP on XXX and effects QxQ_xQx​, put J(P,Q)=∑xP(x)a(Qx,Wx)J(P,Q)=\sum_xP(x)a(Q_x,W_x)J(P,Q)=∑x​P(x)a(Qx​,Wx​) and B(P,Q)=∑xP(x)∑yP(y)a(Qx,Wy)B(P,Q)=\sum_xP(x)\sum_yP(y)a(Q_x,W_y)B(P,Q)=∑x​P(x)∑y​P(y)a(Qx​,Wy​), using real probability masses. Define Iη(W)=sup⁡PL(inf⁡{max⁡(B(P,Q),0):J(P,Q)≥1−η, Qx effects})\mathcal I_\eta(W)=\sup_P L(\inf\{\max(B(P,Q),0):J(P,Q)\ge1-\eta,\ Q_x\text{ effects}\})Iη​(W)=supP​L(inf{max(B(P,Q),0):J(P,Q)≥1−η, Qx​ effects}), where the infimum is in [0,∞][0,\infty][0,∞], L(0)=+∞L(0)=+\inftyL(0)=+∞, L(+∞)=−∞L(+\infty)=-\inftyL(+∞)=−∞, and L(z)=−log⁡2zL(z)=-\log_2zL(z)=−log2​z for positive finite zzz. Define Cη(W)C_\eta(W)Cη​(W) as the extended-real supremum of log⁡2m\log_2mlog2​m over positive integers mmm, words xi∈Xx_i\in Xxi​∈X, and effects DiD_iDi​ satisfying ∑i=0m−1Di=1\sum_{i=0}^{m-1}D_i=1∑i=0m−1​Di​=1 and 1−m−1∑ia(Di,Wxi)≤η1-m^{-1}\sum_i a(D_i,W_{x_i})\le\eta1−m−1∑i​a(Di​,Wxi​​)≤η; repeated words are permitted. For every real 0<ϵ<10<\epsilon<10<ϵ<1, the declaration asserts the extended-real inequality

Iϵ/2(W)−log⁡2(1/ϵ)−4≤Cϵ(W).\mathcal I_{\epsilon/2}(W)-\log_2(1/\epsilon)-4\le C_\epsilon(W).Iϵ/2​(W)−log2​(1/ϵ)−4≤Cϵ​(W).

No finiteness or countability assumption is made on XXX or III.

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