Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3: smooth max-entropy of the pass-conditioned key pair

Open
QAlgorithms.Papers.Independent.Intakethird100.P01.smoothMaxEntropyAfterPassing

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

prove2quantum

Let n,kn,kn,k be positive integers and N=n+kN=n+kN=n+k. Give two NNN-bit strings an arbitrary normalized joint law. Independently choose a uniform kkk-subset of positions for testing and retain the complementary nnn positions in their original order. Let Λ\LambdaΛ denote the test relative Hamming distance. For 0≤Qtol≤10\le Q_{\mathrm{tol}}\le10≤Qtol​≤1, condition on pass={Λ≤Qtol}\mathrm{pass}=\{\Lambda\le Q_{\mathrm{tol}}\}pass={Λ≤Qtol​} and assume ppass=Pr⁡[pass]>0p_{\mathrm{pass}}=\Pr[\mathrm{pass}]>0ppass​=Pr[pass]>0. Let ρZZ′\rho_{ZZ'}ρZZ′​ be the resulting normalized marginal of the complementary key strings, without an additional test-statistic register. For 0<ε≤10<\varepsilon\le10<ε≤1, define

ε′=εppass,μ=Nnkk+1kln⁡1ε.\varepsilon'=\frac{\varepsilon}{\sqrt{p_{\mathrm{pass}}}},\qquad \mu=\sqrt{\frac{N}{nk}\frac{k+1}{k}\ln\frac1\varepsilon}.ε′=ppass​​ε​,μ=nkN​kk+1​lnε1​​.

With purified-distance smoothing over subnormalized quantum states,

Hmax⁡ε′(Z∣Z′)ρ≤n h(Qtol+μ).H_{\max}^{\varepsilon'}(Z\mid Z')_\rho \le n\,h(Q_{\mathrm{tol}}+\mu).Hmaxε′​(Z∣Z′)ρ​≤nh(Qtol​+μ).

Here h(t)=−tlog⁡2t−(1−t)log⁡2(1−t)h(t)=-t\log_2t-(1-t)\log_2(1-t)h(t)=−tlog2​t−(1−t)log2​(1−t) on 0≤t≤1/20\le t\le1/20≤t≤1/2, with 0log⁡20=00\log_2 0=00log2​0=0, and h(t)=1h(t)=1h(t)=1 for t>1/2t>1/2t>1/2. If ε′≥1\varepsilon'\ge1ε′≥1, the zero substate is allowed and the extended smooth max-entropy is −∞-\infty−∞.

This bounds the residual uncertainty of the key strings after a successful random-sample test; it makes no independent-bit assumption.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P01
Formal statement
namespace QAlgorithms.Papers.Independent.Intakethird100.P01

open scoped BigOperators ComplexConjugate ComplexOrder

-- Accepted extended entropy: the finite-real smoothing helper excludes radius >= 1.

open QAlgorithms.Papers.Independent.Information100.P67
  (IsSubnormalized purifiedDistance conditionalMaxEntropy smoothConditionalMaxEntropyExtended)

noncomputable section

/-- PDF pp.13--14, Lemma 3, Eq.(S15): smooth max-entropy of the key-pair marginal
conditioned on passing, with epsilon_prime=epsilon/sqrt(p_pass). No Lambda register is
retained. For epsilon_prime>=1 the extended entropy allows the zero substate.
Source correction (printed / changed / why): S15 prints only epsilon>0; the referenced
entropy definition [53, Definition 10] restricts the smoothing radius below one at a
normalized center. We use 0<epsilon<=1 (the real domain of sqrt(log(1/epsilon))) and
explicitly extend the full subnormalized smoothing ball to all radii with EReal values.
This agrees with the referenced entropy below radius one and gives minus infinity at
radius>=1, preserving the printed epsilon_prime without an extra epsilon<sqrt(p_pass)
hypothesis. All constants and the displayed entropy inequality are unchanged. -/
theorem smoothMaxEntropyAfterPassing (n k : ℕ) (hn : 0 < n) (hk : 0 < k)
    (P : StringPair (n + k) → ℝ) (hP : ∀ z, 0 ≤ P z) (hPsum : ∑ z, P z = 1)
    (Q : ℝ) (hQ0 : 0 ≤ Q) (hQ1 : Q ≤ 1) (hpass : 0 < passProbability P Q)
    (epsilon : ℝ) (hepsilon0 : 0 < epsilon) (hepsilon1 : epsilon ≤ 1) :
    smoothConditionalMaxEntropyExtended (classicalDensity (keyLawGivenPass P Q))
        (epsilon / Real.sqrt (passProbability P Q)) ≤
      ((n : ℝ) * truncatedBinaryEntropy (Q + samplingDeviation n k epsilon) : ℝ) := by sorry

end

end QAlgorithms.Papers.Independent.Intakethird100.P01
Source
Tight Finite-Key Analysis for Quantum Cryptography, arXiv:1103.4130v2, PDF p. 13, Lemma 3, Eq. (S15); proof on PDF p.14
Read-back

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

For all positive natural numbers n,kn,kn,k, let P(u,v)≥0P(u,v)\ge0P(u,v)≥0 be a real function on pairs of Boolean strings of length n+kn+kn+k with ∑u,vP(u,v)=1\sum_{u,v}P(u,v)=1∑u,v​P(u,v)=1, and give every triple (u,v,s)(u,v,s)(u,v,s) with ∣s∣=k|s|=k∣s∣=k weight P(u,v)/(n+kk)P(u,v)/\binom{n+k}{k}P(u,v)/(kn+k​). For every Q∈[0,1]Q\in[0,1]Q∈[0,1], let ppass>0p_{\mathrm{pass}}>0ppass​>0 be the total weight of triples for which ∣{i∈s:ui≠vi}∣/k≤Q|\{i\in s:u_i\ne v_i\}|/k\le Q∣{i∈s:ui​=vi​}∣/k≤Q. Restrict both strings to the complement of sss, listing its indices in increasing order, and let K(a,b)K(a,b)K(a,b) be the total weight of passing triples producing the length-nnn strings (a,b)(a,b)(a,b), divided by ppassp_{\mathrm{pass}}ppass​. Let ρ\rhoρ be the diagonal complex matrix with diagonal K(a,b)K(a,b)K(a,b). For every real 0<ϵ≤10<\epsilon\le10<ϵ≤1, put

d=n+knkk+1kln⁡(1/ϵ),r=ϵppass.d=\sqrt{\frac{n+k}{nk}\frac{k+1}{k}\ln(1/\epsilon)}, \qquad r=\frac{\epsilon}{\sqrt{p_{\mathrm{pass}}}}.d=nkn+k​kk+1​ln(1/ϵ)​,r=ppass​​ϵ​.

The assertion is

inf⁡τ⪰0, Re⁡Tr⁡τ≤1Dpur(τ,ρ)≤rHmax⁡(τ)≤n htr(Q+d),\inf_{\substack{\tau\succeq0,\ \operatorname{Re}\operatorname{Tr}\tau\le1\\ D_{\mathrm{pur}}(\tau,\rho)\le r}} H_{\max}(\tau) \le n\,h_{\mathrm{tr}}(Q+d),τ⪰0, ReTrτ≤1Dpur​(τ,ρ)≤r​inf​Hmax​(τ)≤nhtr​(Q+d),

as an inequality of extended real numbers, with the real right-hand side embedded into them. Here

Dpur(τ,ρ)=1−(Re⁡Tr⁡τρτ+(1−Re⁡Tr⁡τ)(1−Re⁡Tr⁡ρ))2,D_{\mathrm{pur}}(\tau,\rho) =\sqrt{1-\left( \operatorname{Re}\operatorname{Tr}\sqrt{\sqrt{\tau}\rho\sqrt{\tau}} +\sqrt{(1-\operatorname{Re}\operatorname{Tr}\tau) (1-\operatorname{Re}\operatorname{Tr}\rho)} \right)^2},Dpur​(τ,ρ)=1−(ReTrτ​ρτ​​+(1−ReTrτ)(1−ReTrρ)​)2​,

and Hmax⁡(0)=−∞H_{\max}(0)=-\inftyHmax​(0)=−∞, while for τ≠0\tau\ne0τ=0,

Hmax⁡(τ)=log⁡2sup⁡σ⪰0Tr⁡σ=1(Re⁡Tr⁡τ(I⊗σ)τ)2.H_{\max}(\tau)= \log_2\sup_{\substack{\sigma\succeq0\\\operatorname{Tr}\sigma=1}} \left(\operatorname{Re}\operatorname{Tr} \sqrt{\sqrt{\tau}(I\otimes\sigma)\sqrt{\tau}}\right)^2.Hmax​(τ)=log2​σ⪰0Trσ=1​sup​(ReTrτ​(I⊗σ)τ​​)2.

The matrix σ\sigmaσ is indexed by the second length-nnn string, and III acts on the first; matrix square roots are defined by continuous functional calculus. The function htr(t)h_{\mathrm{tr}}(t)htr​(t) equals [−tln⁡t−(1−t)ln⁡(1−t)]/ln⁡2[-t\ln t-(1-t)\ln(1-t)]/\ln2[−tlnt−(1−t)ln(1−t)]/ln2 for t≤12t\le\tfrac12t≤21​ and equals 111 for t>12t>\tfrac12t>21​, with ln⁡0=0\ln0=0ln0=0 and ln⁡t=ln⁡∣t∣\ln t=\ln|t|lnt=ln∣t∣ for negative ttt. The smoothing infimum permits τ=0\tau=0τ=0, which contributes −∞-\infty−∞ whenever it satisfies the distance bound; in particular this occurs when ϵ=1\epsilon=1ϵ=1. No assumption that Q+d≤12Q+d\le\tfrac12Q+d≤21​ or that r<1r<1r<1 is imposed.

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