Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Actual private-code errors imply smooth entropy bounds and a code converse

Open
QAlgorithms.Papers.Independent.Intakenext100.P30.private_code_entropy_converse

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

prove2quantum

Let a stochastic code on MMM have decoding error at most ε\varepsilonε for every message and eavesdropper trace distance at most ε\varepsilonε for every message to one fixed normalized reference. Assume ε≥0\varepsilon\ge0ε≥0 and put r=2εr=\sqrt{2\varepsilon}r=2ε​ and b=log⁡2∣M∣b=\log_2|M|b=log2​∣M∣. Let M′M'M′ be the actual decoder output. Then

Hmax⁡r(M∣M′)≤0for every message law,Hmin⁡r(M∣Z)≥bfor uniform M.H_{\max}^{r}(M|M')\le0\quad\text{for every message law},\qquad H_{\min}^{r}(M|Z)\ge b\quad\text{for uniform }M.Hmaxr​(M∣M′)≤0for every message law,Hminr​(M∣Z)≥bfor uniform M.

For the uniform message law, the ensuing data-processing step also gives

b≤Hmin⁡r(M∣Z)−Hmax⁡r(M∣Y).b\le H_{\min}^{r}(M|Z)-H_{\max}^{r}(M|Y).b≤Hminr​(M∣Z)−Hmaxr​(M∣Y).

Both entropy inequalities and the code-level converse follow from the actual operational error conditions; none is a hypothesis. This supplies the source's common trace-error-to-purified-radius interface, rather than an assertion for two independent purified-distance error parameters.

All alphabets are finite and nonempty, and output Hilbert spaces are finite dimensional and nonzero. A classical–quantum channel assigns a positive semidefinite, trace-one matrix to each input. Encoders may use private randomness; decoders are normalized POVMs. Codes are fixed independently of the message, with no supplied shared key or entanglement. Logarithms and entropies are in bits.

For a normalized cq state, smoothing ranges over positive subnormalized matrices at purified distance at most the indicated radius. Smooth min-entropy is an extended supremum and smooth max-entropy an extended infimum; at the zero operator their unsmoothed values are respectively +∞+\infty+∞ and −∞-\infty−∞.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P30
Formal statement
noncomputable section

open scoped BigOperators ComplexConjugate Matrix ComplexOrder

open Filter

namespace QAlgorithms.Papers.Independent.Intakenext100.P30

variable {X Y Z M U V A B C : Type*}

variable [Fintype X] [DecidableEq X] [Fintype Y] [DecidableEq Y]

variable [Fintype Z] [DecidableEq Z] [Fintype M] [DecidableEq M]

variable [Fintype U] [DecidableEq U] [Fintype V] [DecidableEq V]

variable [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]

variable [Fintype C] [DecidableEq C]

attribute [local instance] Classical.propDecidable

/-- Section III, PDF p.5: both entropy inequalities are DERIVED from the actual
code's messagewise reliability and trace-distance secrecy. The max-entropy claim
holds for every message law, the min-entropy claim for the uniform law. The ensuing data-processing argument gives the
uniform-message code bound as well. This is the source's common sqrt(2 epsilon) interface, not an independent-(delta,epsilon)
purified-error statement. All nonnegative errors are included: radius >= 1
puts zero in the smoothing ball, giving Hmin=+infinity and Hmax=-infinity. -/
theorem private_code_entropy_converse [Nonempty X] [Nonempty Y] [Nonempty Z] [Nonempty M]
    (thetaY : X → Matrix Y Y ℂ) (thetaZ : X → Matrix Z Z ℂ)
    (hY : RRIsCq thetaY) (hZ : RRIsCq thetaZ) (code : RRCode M X Y)
    (epsilon : ℝ) (he0 : 0 ≤ epsilon)
    (hgood : RRPrivateGood thetaY thetaZ code epsilon) :
    (∀ p : RRDistribution M,
      rrSmoothMax (rrCqState p.prob (fun m => Matrix.diagonal
        (fun guess => ((effectProb (code.decoder guess)
          (rrEncoded thetaY code.encoder m)) : ℂ)))) (Real.sqrt (2 * epsilon)) ≤ 0) ∧
    (Real.logb 2 (Fintype.card M : ℝ) : EReal) ≤
      rrSmoothMin (rrCqState (rrUniform M) (rrEncoded thetaZ code.encoder))
        (Real.sqrt (2 * epsilon)) ∧
    (Real.logb 2 (Fintype.card M : ℝ) : EReal) ≤
      rrSmoothMin (rrCqState (rrUniform M) (rrEncoded thetaZ code.encoder))
          (Real.sqrt (2 * epsilon)) -
        rrSmoothMax (rrCqState (rrUniform M) (rrEncoded thetaY code.encoder))
          (Real.sqrt (2 * epsilon)) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P30

end
Source
Noisy channel coding via privacy amplification and information reconciliation, arXiv:1012.4814v2, PDF p. 5, §III: private converse from actual code errors
Read-back

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

Let X,Y,Z,MX,Y,Z,MX,Y,Z,M be nonempty finite types with decidable equality, and let θxY\theta^Y_xθxY​ and θxZ\theta^Z_xθxZ​, for x∈Xx\in Xx∈X, be positive semidefinite matrices of trace 111 on YYY and ZZZ, respectively. A code consists of a probability distribution eme_mem​ on XXX for each m∈Mm\in Mm∈M, and positive semidefinite matrices DmD_mDm​ on YYY satisfying ∑mDm=IY\sum_mD_m=I_Y∑m​Dm​=IY​. Put Ym=∑xem(x)θxYY_m=\sum_xe_m(x)\theta^Y_xYm​=∑x​em​(x)θxY​, Zm=∑xem(x)θxZZ_m=\sum_xe_m(x)\theta^Z_xZm​=∑x​em​(x)θxZ​, T(A)=Re⁡tr⁡A†AT(A)=\operatorname{Re}\operatorname{tr}\sqrt{A^\dagger A}T(A)=RetrA†A​, and suppose ϵ≥0\epsilon\ge0ϵ≥0, 1−Re⁡tr⁡(DmYm)≤ϵ1-\operatorname{Re}\operatorname{tr}(D_mY_m)\le\epsilon1−Retr(Dm​Ym​)≤ϵ for every mmm, and there exists a single positive semidefinite matrix σ\sigmaσ on ZZZ of trace 111 such that T(Zm−σ)/2≤ϵT(Z_m-\sigma)/2\le\epsilonT(Zm​−σ)/2≤ϵ for every mmm. The entropy expressions in the conclusion have the following literal meanings: for a matrix ρ\rhoρ indexed by A×BA\times BA×B, define

Hmin⁡(ρ)=sup⁡{a∈R:∃ ω≥0, tr⁡ω=1, 2−aIA⊗ω−ρ≥0},H_{\min}(\rho)= \sup\left\{a\in\mathbb R:\exists\,\omega\ge0,\ \operatorname{tr}\omega=1,\ 2^{-a}I_A\otimes\omega-\rho\ge0\right\},Hmin​(ρ)=sup{a∈R:∃ω≥0, trω=1, 2−aIA​⊗ω−ρ≥0},

where real numbers are embedded in the extended real line, and define Hmax⁡(0)=−∞H_{\max}(0)=-\inftyHmax​(0)=−∞, while for ρ≠0\rho\ne0ρ=0,

Hmax⁡(ρ)=log⁡2sup⁡ω≥0tr⁡ω=1F(ρ,IA⊗ω)2,F(τ,ρ)=Re⁡tr⁡τ ρ τ.H_{\max}(\rho)= \log_2\sup_{\substack{\omega\ge0\\\operatorname{tr}\omega=1}} F(\rho,I_A\otimes\omega)^2,\qquad F(\tau,\rho)=\operatorname{Re}\operatorname{tr} \sqrt{\sqrt{\tau}\,\rho\,\sqrt{\tau}}.Hmax​(ρ)=log2​ω≥0trω=1​sup​F(ρ,IA​⊗ω)2,F(τ,ρ)=Retrτ​ρτ​​.

All matrix square roots here use continuous functional calculus. For r∈Rr\in\mathbb Rr∈R, let

Br(ρ)={τ≥0:Re⁡tr⁡τ≤1, 1−F(τ,ρ)2≤r},Hmin⁡r(ρ)=sup⁡τ∈Br(ρ)Hmin⁡(τ),Hmax⁡r(ρ)=inf⁡τ∈Br(ρ)Hmax⁡(τ),\mathcal B_r(\rho)= \left\{\tau\ge0:\operatorname{Re}\operatorname{tr}\tau\le1,\ \sqrt{1-F(\tau,\rho)^2}\le r\right\},\quad H_{\min}^{r}(\rho)=\sup_{\tau\in\mathcal B_r(\rho)}H_{\min}(\tau),\quad H_{\max}^{r}(\rho)=\inf_{\tau\in\mathcal B_r(\rho)}H_{\max}(\tau),Br​(ρ)={τ≥0:Retrτ≤1, 1−F(τ,ρ)2​≤r},Hminr​(ρ)=τ∈Br​(ρ)sup​Hmin​(τ),Hmaxr​(ρ)=τ∈Br​(ρ)inf​Hmax​(τ),

with suprema and infima in the extended real line. In particular, the smoothing condition is exactly the displayed square-root condition; the real square root is 000 on negative inputs. For weights ppp on MMM and matrices AmA_mAm​, write C(p,A)(m,b),(m′,b′)=1m=m′p(m)(Am)b,b′C(p,A)_{(m,b),(m',b')}=\mathbf1_{m=m'}p(m)(A_m)_{b,b'}C(p,A)(m,b),(m′,b′)​=1m=m′​p(m)(Am​)b,b′​. Set r=2ϵr=\sqrt{2\epsilon}r=2ϵ​, uM(m)=1/∣M∣u_M(m)=1/|M|uM​(m)=1/∣M∣, and let GmG_mGm​ be the diagonal matrix on MMM whose diagonal entry at ggg is Re⁡tr⁡(DgYm)\operatorname{Re}\operatorname{tr}(D_gY_m)Retr(Dg​Ym​). Then all three assertions hold:

for every probability distribution p on M,Hmax⁡r ⁣(C(p,G))≤0,log⁡2∣M∣≤Hmin⁡r ⁣(C(uM,Z)),log⁡2∣M∣≤Hmin⁡r ⁣(C(uM,Z))−Hmax⁡r ⁣(C(uM,Y)).\begin{aligned} &\text{for every probability distribution }p\text{ on }M, &&H_{\max}^{r}\!\left(C(p,G)\right)\le0,\\ &\log_2|M| &&\le H_{\min}^{r}\!\left(C(u_M,Z)\right),\\ &\log_2|M| &&\le H_{\min}^{r}\!\left(C(u_M,Z)\right) -H_{\max}^{r}\!\left(C(u_M,Y)\right). \end{aligned}​for every probability distribution p on M,log2​∣M∣log2​∣M∣​​Hmaxr​(C(p,G))≤0,≤Hminr​(C(uM​,Z)),≤Hminr​(C(uM​,Z))−Hmaxr​(C(uM​,Y)).​

Singleton types are included, ϵ\epsilonϵ has no upper bound, and the entropy inequalities and subtraction are interpreted in the extended real line.

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