Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

One-shot quantum Feinstein packing bounds

Open
QAlgorithms.Papers.Independent.Intakethird100.P05.one_shot_feinstein

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

prove2quantum

Let x↦ρxx\mapsto\rho_xx↦ρx​ be a density-output channel on a finite alphabet and finite-dimensional complex Hilbert space. For an input law ppp, put σ=∑xp(x)ρx\sigma=\sum_xp(x)\rho_xσ=∑x​p(x)ρx​ and ρˉx=Eσ(ρx)\bar\rho_x=\mathcal E_\sigma(\rho_x)ρˉ​x​=Eσ​(ρx​). Suppose δ≥0\delta\ge0δ≥0, c>0c>0c>0, and

∑xp(x)Tr⁡[ρˉx{ρˉx−cσ>0}]≥1−δ.\sum_xp(x)\operatorname{Tr}[\bar\rho_x\{\bar\rho_x-c\sigma>0\}]\ge1-\delta.x∑​p(x)Tr[ρˉ​x​{ρˉ​x​−cσ>0}]≥1−δ.

For every γ>0\gamma>0γ>0 and η>0\eta>0η>0 there are M≥1M\ge1M≥1 distinct words u1,…,uM∈Xu_1,\ldots,u_M\in\mathcal Xu1​,…,uM​∈X and positive decoder operators XkX_kXk​ with ∑kXk≤I\sum_kX_k\le I∑k​Xk​≤I such that

γγ+δmin⁡{η,1−δ−γ−2η}≤Mc,1M∑k=1M(1−Tr⁡[ρukXk])≤δ+γ+2η.\frac{\gamma}{\gamma+\delta}\min\{\eta,1-\delta-\gamma-2\sqrt\eta\}\le\frac{M}{c},\qquad \frac1M\sum_{k=1}^M(1-\operatorname{Tr}[\rho_{u_k}X_k])\le\delta+\gamma+2\sqrt\eta.γ+δγ​min{η,1−δ−γ−2η​}≤cM​,M1​k=1∑M​(1−Tr[ρuk​​Xk​])≤δ+γ+2η​.

The test in the premise is the strict positive spectral projection. The error uses the original channel states and uniform messages. This one-shot statement gives both size and reliability of a single code; no upper restriction on δ\deltaδ or η\etaη is imposed.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P05
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P05

open scoped Matrix ComplexConjugate ComplexOrder BigOperators

open Filter Topology QAlgorithms

open QAlgorithms.Papers.Independent.Information100.P60 (Mat copies)

open QAlgorithms.Papers.Independent.Information100.P07 (positiveProjection)

open QAlgorithms.Papers.Independent.Dependency50.P28 (tr pinch typeI accept)

open QAlgorithms.Papers.Independent.Claimed50.P45 (pinchedTest)

open QAlgorithms.Papers.Independent.Information100.P58 (Distribution)

open QAlgorithms.Papers.Independent.Information100.P27 (average)

open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)

open QAlgorithms.Papers.Independent.Dependency50.P35 (directSum)

open QAlgorithms.Papers.Independent.Renew46.P44 (wordOutput)

attribute [local instance] Classical.propDecidable Classical.decEq

variable {X I : Type} [Fintype X] [DecidableEq X] [Fintype I] [DecidableEq I]

/-- PDF p.4, Lemma 2, (17)–(19): a one-shot quantum Feinstein code with BOTH
cardinality and average-error bounds. There is no delta < 1 hypothesis.
The hypothesis uses pinched states; the output error uses original states. -/
theorem one_shot_feinstein (W : DensityOutputChannel X I) (p : Distribution X)
    (delta c : ℝ) (hdelta : 0 ≤ delta) (hc : 0 < c)
    (hgood : 1 - delta ≤ goodMass W p c)
    (gamma eta : ℝ) (hgamma : 0 < gamma) (heta : 0 < eta) :
    ∃ C : DistinctWordCode X I,
      gamma / (gamma + delta) * min eta (1 - delta - gamma - 2 * Real.sqrt eta) ≤
        (C.size : ℝ) / c ∧
      uniformMessageError W.state C ≤ delta + gamma + 2 * Real.sqrt eta := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P05

end
Source
A New Proof of the Channel Coding Theorem via Hypothesis Testing in Quantum Information Theory, arXiv:quant-ph/0208139v1, PDF p. 4, Lemma 2, (17)–(19)
Read-back

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

For finite index types X,IX,IX,I with decidable equality, let ρx=W(x)\rho_x=W(x)ρx​=W(x) be positive semidefinite complex matrices of trace 111, and let px≥0p_x\ge0px​≥0 with ∑xpx=1\sum_xp_x=1∑x​px​=1. Put ρˉ=∑xpxρx\bar\rho=\sum_xp_x\rho_xρˉ​=∑x​px​ρx​ and ρ^x=∑ℓPℓρxPℓ\widehat\rho_x=\sum_\ell P_\ell\rho_xP_\ellρ​x​=∑ℓ​Pℓ​ρx​Pℓ​, summing over the distinct eigenvalues of ρˉ\bar\rhoρˉ​, with PℓP_\ellPℓ​ its spectral projections. Let P+(A)P_+(A)P+​(A) denote the orthogonal projection onto the range of the positive part max⁡(A,0)\max(A,0)max(A,0), defined by continuous functional calculus. For real δ,c,γ,η\delta,c,\gamma,\etaδ,c,γ,η, assume δ≥0\delta\ge0δ≥0, c>0c>0c>0, γ>0\gamma>0γ>0, η>0\eta>0η>0, and

1−δ≤∑xpx Re⁡Tr⁡(ρ^xP+(ρ^x−cρˉ)).1-\delta\le \sum_xp_x\,\operatorname{Re}\operatorname{Tr} \bigl(\widehat\rho_xP_+(\widehat\rho_x-c\bar\rho)\bigr).1−δ≤x∑​px​ReTr(ρ​x​P+​(ρ​x​−cρˉ​)).

There exists a code with positive integer size MMM, distinct inputs uj∈Xu_j\in Xuj​∈X, and positive semidefinite decoding matrices DjD_jDj​ on III satisfying 1−∑jDj≥0\mathbf1-\sum_jD_j\ge01−∑j​Dj​≥0, such that

γγ+δmin⁡ ⁣{η, 1−δ−γ−2η}≤Mc,1M∑j=0M−1(1−Re⁡Tr⁡(ρujDj))≤δ+γ+2η.\frac{\gamma}{\gamma+\delta} \min\!\left\{\eta,\,1-\delta-\gamma-2\sqrt\eta\right\} \le\frac{M}{c}, \qquad \frac1M\sum_{j=0}^{M-1} \left(1-\operatorname{Re}\operatorname{Tr}(\rho_{u_j}D_j)\right) \le\delta+\gamma+2\sqrt\eta.γ+δγ​min{η,1−δ−γ−2η​}≤cM​,M1​j=0∑M−1​(1−ReTr(ρuj​​Dj​))≤δ+γ+2η​.

There is no assumption that δ<1\delta<1δ<1 or that the expression inside the minimum is positive, so the size lower bound may be nonpositive.

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