Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5.1 Bound 1: first accessible-information bound

Open
QAlgorithms.Papers.Independent.Support50.P27.accessible_bound1

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

prove2quantum

Fix a finite dimensional Eve register and any fixed-parameter conditional QKD output data. Let pm=Pr⁡(M=m)p_m=\Pr(M=m)pm​=Pr(M=m), with pm≥0p_m\ge0pm​≥0 and ∑mpm=1\sum_mp_m=1∑m​pm​=1, and let L=max⁡{m:pm>0}L=\max\{m:p_m>0\}L=max{m:pm​>0}. At each length, all conditional key-pair probabilities are normalized and all conditional Eve operators are density operators. Choose arbitrary normalized representatives on null events. Define

Fm={2−m,ρE,k,k}k∈{0,1}m,ρˉm=2−m∑kρE,k,k,\mathcal F_m=\{2^{-m},\rho_{E,k,k}\}_{k\in\{0,1\}^m},\qquad \bar\rho_m=2^{-m}\sum_k\rho_{E,k,k},Fm​={2−m,ρE,k,k​}k∈{0,1}m​,ρˉ​m​=2−mk∑​ρE,k,k​,

and define the hybrid states

ρqi1=∑m,kpm2−m∣k,k⟩⟨k,k∣⊗ρE,k,k,ρqi2=∑m,kpm2−m∣k,k⟩⟨k,k∣⊗ρˉm.\rho_{\mathrm{qi1}}=\sum_{m,k}p_m2^{-m}|k,k\rangle\langle k,k|\otimes\rho_{E,k,k},\qquad \rho_{\mathrm{qi2}}=\sum_{m,k}p_m2^{-m}|k,k\rangle\langle k,k|\otimes\bar\rho_m.ρqi1​=m,k∑​pm​2−m∣k,k⟩⟨k,k∣⊗ρE,k,k​,ρqi2​=m,k∑​pm​2−m∣k,k⟩⟨k,k∣⊗ρˉ​m​.

If μ2≥0\mu_2\ge0μ2​≥0 and ∑mpmIacc(Fm)≤μ2\sum_mp_mI_{\mathrm{acc}}(\mathcal F_m)\le\mu_2∑m​pm​Iacc​(Fm​)≤μ2​, where information is in bits, then the full trace norm satisfies

∥ρqi1−ρqi2∥1≤∑mpm(2m+1)22ln⁡2Iacc(Fm)≤(2L+1)22ln⁡2μ2.\lVert\rho_{\mathrm{qi1}}-\rho_{\mathrm{qi2}}\rVert_1 \le\sum_mp_m(2^m+1)^2\sqrt{2\ln2}\sqrt{I_{\mathrm{acc}}(\mathcal F_m)} \le(2^L+1)^2\sqrt{2\ln2}\sqrt{\mu_2}.∥ρqi1​−ρqi2​∥1​≤m∑​pm​(2m+1)22ln2​Iacc​(Fm​)​≤(2L+1)22ln2​μ2​​.

This is the finite quantitative bound in the source's uniform-ensemble interpretation. Its exponential length overhead must be absorbed by a separate key-rate restriction before drawing asymptotic conclusions. It does not convert the actual-prior privacy premise of Eq. (4) into the displayed premise.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P27
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Support50.P27

open scoped BigOperators Matrix ComplexConjugate ComplexOrder

open QAlgorithms.Papers.Independent.Dependency50.P07
  (CQData ensembleMean ensembleInformation accessibleInformation)

open QAlgorithms.Papers.Independent.Dependency50.P24 (Key)

open QAlgorithms.Papers.Independent.Dependency50.P47 (cqMatrix)

attribute [local instance] Classical.decEq Classical.propDecidable

/-- PDF pp.11--12, Section 5.1, Bound 1: full hybrid trace norm bounded by
(2^max(m)+1)^2 sqrt(2 ln 2) sqrt(mu2). The hypothesis concerns the explicitly
uniform F_m of the proof. It supplies NO actual-prior conversion from Eq.(4).
The displayed per-length bound is retained; exponential decay needs a rate
restriction and is not asserted for arbitrary key-length families. -/
theorem accessible_bound1 {L : ℕ} {E : Type} [Fintype E] [Nonempty E]
    (D : KeyData L E) (mu2 : ℝ) (hmu2 : 0 ≤ mu2)
    (hprivacy : diagonalAccessible D ≤ mu2) :
    traceNorm (firstHybrid D - secondHybrid D) ≤
      (∑ m, D.lengthProb m * ((2 : ℝ) ^ m.val + 1) ^ 2 *
        Real.sqrt (2 * Real.log 2) *
          Real.sqrt (accessibleInformation (diagonalEnsemble D m))) ∧
    (∑ m, D.lengthProb m * ((2 : ℝ) ^ m.val + 1) ^ 2 *
        Real.sqrt (2 * Real.log 2) *
          Real.sqrt (accessibleInformation (diagonalEnsemble D m))) ≤
      ((2 : ℝ) ^ maxKeyLength D + 1) ^ 2 *
        Real.sqrt (2 * Real.log 2) * Real.sqrt mu2 := by sorry

end QAlgorithms.Papers.Independent.Support50.P27

end
Source
The Universal Composable Security of Quantum Key Distribution, arXiv:quant-ph/0409078v1, PDF p. 11, §5.1 Bound 1: first accessible-information bound
Read-back

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

For every natural number LLL, finite nonempty type EEE, data DDD comprising nonnegative weights w0,…,wLw_0,\ldots,w_Lw0​,…,wL​ summing to 111, probability laws pmp_mpm​ on {0,…,2m−1}2\{0,\ldots,2^m-1\}^2{0,…,2m−1}2, and positive semidefinite, trace-one matrices ρm,a,b\rho_{m,a,b}ρm,a,b​ on EEE, put dm=2md_m=2^mdm​=2m, ρˉm=dm−1∑aρm,a,a\bar\rho_m=d_m^{-1}\sum_a\rho_{m,a,a}ρˉ​m​=dm−1​∑a​ρm,a,a​, and K=max⁡{m:wm>0}K=\max\{m:w_m>0\}K=max{m:wm​>0}. Let ImI_mIm​ be the real supremum over every finite family Mt⪰0M_t\succeq0Mt​⪰0 with at least one outcome and ∑tMt=I\sum_tM_t=I∑t​Mt​=I, of H(um)+H(q)−H(J)H(u_m)+H(q)-H(J)H(um​)+H(q)−H(J), where um(a)=dm−1u_m(a)=d_m^{-1}um​(a)=dm−1​, J(a,t)=dm−1Re⁡tr⁡(Mtρm,a,a)J(a,t)=d_m^{-1}\operatorname{Re}\operatorname{tr}(M_t\rho_{m,a,a})J(a,t)=dm−1​Retr(Mt​ρm,a,a​), q(t)=∑aJ(a,t)q(t)=\sum_aJ(a,t)q(t)=∑a​J(a,t), and H(v)=−∑iv(i)log⁡2v(i)H(v)=-\sum_i v(i)\log_2v(i)H(v)=−∑i​v(i)log2​v(i) with zero summands interpreted as 000. On the space indexed by ((m,a,b),e)((m,a,b),e)((m,a,b),e), define block diagonal matrices F,GF,GF,G: their blocks at label (m,a,b)(m,a,b)(m,a,b) are respectively wmdm−1ρm,a,aw_md_m^{-1}\rho_{m,a,a}wm​dm−1​ρm,a,a​ and wmdm−1ρˉmw_md_m^{-1}\bar\rho_mwm​dm−1​ρˉ​m​ if a=ba=ba=b, and 000 otherwise; entries between distinct labels are zero. For every real μ2≥0\mu_2\ge0μ2​≥0 satisfying ∑mwmIm≤μ2\sum_mw_mI_m\le\mu_2∑m​wm​Im​≤μ2​, the statement asserts

∥F−G∥1≤∑m=0Lwm(dm+1)22ln⁡2Im≤(2K+1)22ln⁡2μ2,\|F-G\|_1 \le \sum_{m=0}^{L}w_m(d_m+1)^2\sqrt{2\ln2}\sqrt{I_m} \le (2^K+1)^2\sqrt{2\ln2}\sqrt{\mu_2},∥F−G∥1​≤m=0∑L​wm​(dm​+1)22ln2​Im​​≤(2K+1)22ln2​μ2​​,

where ∥X∥1=Re⁡tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^\dagger X}∥X∥1​=RetrX†X​, with the square root applied by continuous functional calculus. Length 000, zero weights, and μ2=0\mu_2=0μ2​=0 are included; the uniform diagonal ensembles do not use the branch probabilities pmp_mpm​.

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