Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

An explicit unbounded separation of weak locking and private capacities

Open
QAlgorithms.Papers.Independent.Intakenext100.P63.twoBasis_capacity_separation

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

prove2quantum

Let d≥1d\ge1d≥1 be an integer. The input and receiver registers of Nd\mathcal N_dNd​ have basis {∣b,i⟩:b∈{0,1}, i∈{0,…,d−1}}\{|b,i\rangle:b\in\{0,1\},\ i\in\{0,\ldots,d-1\}\}{∣b,i⟩:b∈{0,1}, i∈{0,…,d−1}}, and its environment has dimension ddd. Put v0i=∣i⟩v_{0i}=|i\ranglev0i​=∣i⟩ and v1i=d−1/2∑xe2πiix/d∣x⟩v_{1i}=d^{-1/2}\sum_x e^{2\pi\mathrm i ix/d}|x\ranglev1i​=d−1/2∑x​e2πiix/d∣x⟩. Define the normalized Stinespring isometry Vd∣b,i⟩=∣b,i⟩⊗vbiV_d|b,i\rangle=|b,i\rangle\otimes v_{bi}Vd​∣b,i⟩=∣b,i⟩⊗vbi​, with receiver and environment channels obtained by the two partial traces. Then

P(Nd)=1,LW(Nd)=1+12log⁡2d.P(\mathcal N_d)=1,\qquad L_W(\mathcal N_d)=1+\tfrac12\log_2d.P(Nd​)=1,LW​(Nd​)=1+21​log2​d.

The capacities allow an independent uniform preshared secret of o(n)o(n)o(n) bits, averaged out in Eve's signal, with averaged decoding error and the full trace-norm or full classical ℓ1\ell^1ℓ1 security criterion tending to zero. These exact formulas give an unbounded additive separation as ddd grows. At d=1d=1d=1 both capacities are one bit; the actual input and receiver dimension is 2d2d2d.

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.1,11, Example 12, (13)–(14), realizing the abstract's unbounded separation.
At d=1 both capacities equal one bit; input and dilationMap dimension are 2d. -/
theorem twoBasis_capacity_separation (d : ℕ) (hd : 0 < d) :
    keyedCapacity (dilationMap (twoBasisDilation d)) (environment (twoBasisDilation d)) false = 1 ∧
    keyedCapacity (dilationMap (twoBasisDilation d)) (environment (twoBasisDilation d)) true =
      1 + (1 / 2 : ℝ) * Real.logb 2 d := 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. 1, Abstract, realized by Example 12: unbounded gap between weak locking and private capacities
Read-back

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

For every positive natural number ddd, let A=B={false,true}×{0,…,d−1}A=B=\{\mathrm{false},\mathrm{true}\}\times\{0,\ldots,d-1\}A=B={false,true}×{0,…,d−1}, let E={0,…,d−1}E=\{0,\ldots,d-1\}E={0,…,d−1}, and define V:CA→CB×EV:\mathbb C^A\to\mathbb C^{B\times E}V:CA→CB×E by

V((c,j),x),(b,i)=1{(c,j)=(b,i)}{1{x=i},b=false,d−1/2e2πiix/d,b=true.V_{((c,j),x),(b,i)} = \mathbf1_{\{(c,j)=(b,i)\}} \begin{cases} \mathbf1_{\{x=i\}},&b=\mathrm{false},\\ d^{-1/2}e^{2\pi\mathrm{i}ix/d},&b=\mathrm{true}. \end{cases}V((c,j),x),(b,i)​=1{(c,j)=(b,i)}​{1{x=i}​,d−1/2e2πiix/d,​b=false,b=true.​

Set N(X)=tr⁡E(VXV∗)N(X)=\operatorname{tr}_E(VXV^*)N(X)=trE​(VXV∗) and Nc(X)=tr⁡B(VXV∗)N_c(X)=\operatorname{tr}_B(VXV^*)Nc​(X)=trB​(VXV∗). The theorem asserts

Cprivate(N,Nc)=1,Cweak(N,Nc)=1+12log⁡2d.C_{\mathrm{private}}(N,N_c)=1, \qquad C_{\mathrm{weak}}(N,N_c)=1+\tfrac12\log_2d.Cprivate​(N,Nc​)=1,Cweak​(N,Nc​)=1+21​log2​d.

For either criterion, the capacity is the total real supremum of nonnegative rates RRR admitting codes of lengths ℓ=n+1\ell=n+1ℓ=n+1 with positive message and key counts Mn,KnM_n,K_nMn​,Kn​, density matrices ρu,m\rho_{u,m}ρu,m​ for every key u<Knu<K_nu<Kn​ and message m<Mnm<M_nm<Mn​, and decoding measurements (Du,m)m<Mn(D_{u,m})_{m<M_n}(Du,m​)m<Mn​​. Density matrices are positive semidefinite of trace 111, and decoding measurements have positive semidefinite effects summing to identity. The required limits and rate condition are

log⁡2Knℓ→0,1KnMn∑u,m(1−Re⁡tr⁡(Du,mN[ℓ](ρu,m)))→0,∀s>0, eventually log⁡2Mnℓ≥R−s.\frac{\log_2K_n}{\ell}\to0,\qquad \frac1{K_nM_n}\sum_{u,m}\left(1-\operatorname{Re}\operatorname{tr}(D_{u,m}N^{[\ell]}(\rho_{u,m}))\right)\to0, \qquad \forall s>0,\ \text{eventually }\frac{\log_2M_n}{\ell}\ge R-s.ℓlog2​Kn​​→0,Kn​Mn​1​u,m∑​(1−Retr(Du,m​N[ℓ](ρu,m​)))→0,∀s>0, eventually ℓlog2​Mn​​≥R−s.

Writing ρˉm=Kn−1∑uρu,m\bar\rho_m=K_n^{-1}\sum_u\rho_{u,m}ρˉ​m​=Kn−1​∑u​ρu,m​, the private criterion requires, for every ε>0\varepsilon>0ε>0, eventually a density matrix ω\omegaω on EℓE^\ellEℓ such that Mn−1∑m∥Nc[ℓ](ρˉm)−ω∥1≤εM_n^{-1}\sum_m\|N_c^{[\ell]}(\bar\rho_m)-\omega\|_1\le\varepsilonMn−1​∑m​∥Nc[ℓ]​(ρˉ​m​)−ω∥1​≤ε. The weak criterion instead requires, eventually for every finite measurement QQQ with a strictly positive number of outcomes, a probability vector ωj\omega_jωj​ such that Mn−1∑m,j∣Re⁡tr⁡(QjNc[ℓ](ρˉm))−ωj∣≤εM_n^{-1}\sum_{m,j}|\operatorname{Re}\operatorname{tr}(Q_jN_c^{[\ell]}(\bar\rho_m))-\omega_j|\le\varepsilonMn−1​∑m,j​∣Retr(Qj​Nc[ℓ]​(ρˉ​m​))−ωj​∣≤ε. Here ∥X∥1=Re⁡tr⁡X∗X\|X\|_1=\operatorname{Re}\operatorname{tr}\sqrt{X^*X}∥X∥1​=RetrX∗X​; neither security expression includes an additional factor 1/21/21/2. The powers are defined by F[ℓ](X)y,y′=∑x,x′Xx,x′∏t<ℓF(Ext,xt′)yt,yt′F^{[\ell]}(X)_{y,y'}=\sum_{x,x'}X_{x,x'}\prod_{t<\ell}F(E_{x_t,x'_t})_{y_t,y'_t}F[ℓ](X)y,y′​=∑x,x′​Xx,x′​∏t<ℓ​F(Ext​,xt′​​)yt​,yt′​​. The theorem includes d=1d=1d=1, when both asserted capacities equal 111.

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