Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Subexponentially vanishing weak-locking security error

Open
QAlgorithms.Papers.Independent.Intakenext100.P63.schur_subexponential_security

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

prove2quantum

Let N\mathcal NN be a complement of a cq-channel, defined by a normalized fixed Stinespring isometry on nonzero finite-dimensional spaces with Nc(∣i⟩⟨j∣)=δijρi\mathcal N^c(|i\rangle\langle j|)=\delta_{ij}\rho_iNc(∣i⟩⟨j∣)=δij​ρi​. Choose any input prior ppp, and let h=H^(M)h=\widehat H(M)h=H(M) be the minimum output entropy of its associated POVM restricted to the average state's support. Let (ηn)n≥1(\eta_n)_{n\ge1}(ηn​)n≥1​ be any positive schedule with

ηn⟶0,−log⁡2ηnn⟶0.\eta_n\longrightarrow0,\qquad \frac{-\log_2\eta_n}{n}\longrightarrow0.ηn​⟶0,n−log2​ηn​​⟶0.

There is a sequence of uniform-message codes with independent uniform preshared keys whose key bits per use tend to zero, whose limiting inferior communication rate is at least hhh, whose decoding error is zero, and whose full ℓ1\ell^1ℓ1 weak-locking error is at most ηn\eta_nηn​ for all sufficiently large nnn, uniformly over all finite environment POVMs.

This pins the source's slower-than-exponential error claim without asserting any fixed positive security exponent. The formal sequence index nnn corresponds to block length n+1n+1n+1.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P63
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P63

open QAlgorithms Filter

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

open QAlgorithms.Papers.Independent.Information100.P04 (Measurement)

open QAlgorithms.Papers.Independent.Information100.P27 (shannon labelInformation)

open QAlgorithms.Papers.Independent.Information100.P71 (channelPower dilationMap SupportIncluded)

open QAlgorithms.Papers.Independent.Bridge50.P47 (SymmetricIndex universalSymmetricDilation)

open QAlgorithms.Learning (IsDistribution)

open scoped Matrix ComplexConjugate ComplexOrder

attribute [local instance] Classical.propDecidable Classical.decEq

/-- PDF pp.10–11, Remark 11: any positive schedule tending to zero slower than
exponentially can be met at the same asymptotic rate, with o(n) secret bits. -/
theorem schur_subexponential_security {A B E : Type}
    [Fintype A] [DecidableEq A] [Nonempty A] [Fintype B] [DecidableEq B] [Nonempty B]
    [Fintype E] [DecidableEq E] [Nonempty E]
    (V : Matrix (B × E) A ℂ) (hV : Vᴴ * V = 1) (rho : A → Mat E)
    (hCq : CqComplement (environment V) rho) (p : A → ℝ) (hp : IsDistribution p)
    (etaSchedule : ℕ → ℝ) (heta : ∀ n, 0 < etaSchedule n)
    (hzero : Tendsto etaSchedule atTop (nhds 0))
    (hsub : Tendsto (fun n => -Real.logb 2 (etaSchedule n) / (n + 1)) atTop (nhds 0)) :
    ∃ C : (n : ℕ) → KeyedBlockCode A B (n + 1),
      Tendsto (fun n => keyRate (C n)) atTop (nhds 0) ∧
      KeyedRateAtLeast C (associatedMinimum p rho) ∧
      (∀ n, keyedAverageError (dilationMap V) (C n) = 0) ∧
      (∀ᶠ n in atTop, WeakSecure (environment V) (C n) (etaSchedule n)) := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P63

end
Source
Weak locking capacity of quantum channels can be much larger than private capacity, arXiv:1403.6361v3, PDF p. 11, Remark 11: subexponentially small weak-locking error
Read-back

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

Let A,B,EA,B,EA,B,E be finite nonempty types with decidable equality, and let V:CA→CB×EV:\mathbb C^A\to\mathbb C^{B\times E}V:CA→CB×E satisfy V†V=IV^\dagger V=IV†V=I. Put N(X)=tr⁡E(VXV†)N(X)=\operatorname{tr}_E(VXV^\dagger)N(X)=trE​(VXV†) and Nc(X)=tr⁡B(VXV†)N^c(X)=\operatorname{tr}_B(VXV^\dagger)Nc(X)=trB​(VXV†). Suppose ρa\rho_aρa​ are density matrices on EEE, meaning positive semidefinite matrices of trace 111, and Nc(∣a⟩⟨a′∣)N^c(|a\rangle\langle a'|)Nc(∣a⟩⟨a′∣) equals ρa\rho_aρa​ when a=a′a=a'a=a′ and 000 otherwise. Let p:A→Rp:A\to\mathbb Rp:A→R be nonnegative and sum to 111, and define ρˉ=∑apaρa\bar\rho=\sum_a p_a\rho_aρˉ​=∑a​pa​ρa​, S=f(ρˉ)S=f(\bar\rho)S=f(ρˉ​) with f(x)=(x)−1f(x)=(\sqrt{x})^{-1}f(x)=(x​)−1 under continuous functional calculus and f(0)=0f(0)=0f(0)=0, and

hassoc=inf⁡ω⪰0, tr⁡ω=1ker⁡ρˉ⊆ker⁡ω−∑aualog⁡2ua,ua=Re⁡tr⁡(S(paρa)S ω).h_{\mathrm{assoc}}= \inf_{\substack{\omega\succeq0,\ \operatorname{tr}\omega=1\\ \ker\bar\rho\subseteq\ker\omega}} -\sum_a u_a\log_2u_a, \qquad u_a=\operatorname{Re}\operatorname{tr}(S(p_a\rho_a)S\,\omega).hassoc​=ω⪰0, trω=1kerρˉ​⊆kerω​inf​−a∑​ua​log2​ua​,ua​=Retr(S(pa​ρa​)Sω).

Let η:N→R\eta:\mathbb N\to\mathbb Rη:N→R satisfy ηn>0\eta_n>0ηn​>0 for every nnn, ηn→0\eta_n\to0ηn​→0, and −log⁡2ηn/(n+1)→0-\log_2\eta_n/(n+1)\to0−log2​ηn​/(n+1)→0. There exists a sequence of keyed codes of lengths ℓ=n+1\ell=n+1ℓ=n+1, each having positive numbers mnm_nmn​ of messages and knk_nkn​ of keys, density matrices ωk,m\omega_{k,m}ωk,m​ on AℓA^\ellAℓ, and for every key kkk a measurement (Dk,m)m(D_{k,m})_m(Dk,m​)m​ on BℓB^\ellBℓ, such that log⁡2kn/ℓ→0\log_2k_n/\ell\to0log2​kn​/ℓ→0, for every s>0s>0s>0 eventually log⁡2mn/ℓ≥hassoc−s\log_2m_n/\ell\ge h_{\mathrm{assoc}}-slog2​mn​/ℓ≥hassoc​−s, and for every nnn,

1knmn∑k,m[1−Re⁡tr⁡(Dk,mN⊗ℓ(ωk,m))]=0.\frac1{k_nm_n}\sum_{k,m} \left[1-\operatorname{Re}\operatorname{tr} (D_{k,m}N^{\otimes\ell}(\omega_{k,m}))\right]=0.kn​mn​1​k,m∑​[1−Retr(Dk,m​N⊗ℓ(ωk,m​))]=0.

Furthermore, for all sufficiently large nnn, every measurement QQQ on EℓE^\ellEℓ with a positive finite number of outcomes admits a probability vector www on those outcomes satisfying

1mn∑m∑j∣Re⁡tr⁡(Qj(Nc)⊗ℓ(ωˉm))−wj∣≤ηn,ωˉm=1kn∑kωk,m.\frac1{m_n}\sum_m\sum_j \left|\operatorname{Re}\operatorname{tr} \bigl(Q_j(N^c)^{\otimes\ell}(\bar\omega_m)\bigr)-w_j\right| \le\eta_n, \qquad \bar\omega_m=\frac1{k_n}\sum_k\omega_{k,m}.mn​1​m∑​j∑​​Retr(Qj​(Nc)⊗ℓ(ωˉm​))−wj​​≤ηn​,ωˉm​=kn​1​k∑​ωk,m​.

All measurements here consist of positive semidefinite effects summing to the identity. No upper bound on the individual values ηn\eta_nηn​ is assumed.

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