Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QKD sufficient-security criterion (4)

Open
QAlgorithms.Papers.Independent.Support50.P22.qkdCriterion

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

prove2quantum

Let H=HA⊗HBH=H_A\otimes H_BH=HA​⊗HB​ have dimension d=abd=abd=ab, where a,b≥1a,b\ge1a,b≥1, and let n≥0n\ge0n≥0. Fix a normalized purification ψHnR\psi_{H^nR}ψHnR​ of the Hilbert–Schmidt de Finetti state. Let EEE be the CPTP map induced by a QKD protocol, with classical outputs consisting of a finite length branch, two keys of that branch's length, and the full public transcript. Length zero is allowed. Define SSS to preserve the length and transcript while replacing both keys by an identical uniform key of that length, and construct F=S∘EF=S\circ EF=S∘E. Suppose every input permutation has a CPTP output relabeling that gives covariance for both EEE and FFF. For ϵ≥0\epsilon\ge0ϵ≥0,

∥((E−F)⊗id⁡R)(∣ψ⟩⟨ψ∣)∥1≤ϵ(n+1)d2−1⟹∥E−F∥⋄≤ϵ.\|((E-F)\otimes\operatorname{id}_R)(|\psi\rangle\langle\psi|)\|_1 \le\frac{\epsilon}{(n+1)^{d^2-1}} \quad\Longrightarrow\quad \|E-F\|_\diamond\le\epsilon.∥((E−F)⊗idR​)(∣ψ⟩⟨ψ∣)∥1​≤(n+1)d2−1ϵ​⟹∥E−F∥⋄​≤ϵ.

This is the source's sufficient criterion for general security, with full norms and no hashing-shortening premise. The independent identical local measurements and classical processing enter through their induced channel EEE.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P22
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder Matrix.Norms.L2Operator

open MeasureTheory

namespace QAlgorithms.Papers.Independent.Support50.P22

attribute [local instance] Classical.decEq Classical.propDecidable

open QAlgorithms.Papers.Independent.Gap48.P20 (Copies)

open QAlgorithms.Papers.Independent.Information100.P69 (diamond)

open QAlgorithms.Papers.Independent.Dependency50.P18 (ClassicalOutput)

attribute [local instance] QAlgorithms.Papers.Independent.Support50.P22.postselectionMatrixMeasurableSpace

attribute [local instance] QAlgorithms.Papers.Independent.Support50.P22.postselectionMatrixBorelSpace

/-- QKD sufficient-security criterion, equation (4), PDF p.3 (not p.2).
H has dimension a*b for the Alice--Bob pair; all norm factors are full norms.
The same output channel witnesses covariance for E and the constructed F. -/
theorem qkdCriterion (n a b : ℕ) (ha : 0 < a) (hb : 0 < b)
    {R L C : Type} [Fintype R] [DecidableEq R] [Nonempty R]
    [Fintype L] [DecidableEq L] [Nonempty L]
    [Fintype C] [DecidableEq C] [Nonempty C]
    (len : L → ℕ)
    (psi : EuclideanSpace ℂ (Copies (Fin (a*b)) n × R))
    (hpsi : FinitePurification psi (deFinettiState n (a*b) (Nat.mul_pos ha hb)))
    (E : Matrix (Copies (Fin (a*b)) n) (Copies (Fin (a*b)) n) ℂ →ₗ[ℂ]
      Matrix (KeyOut L C len) (KeyOut L C len) ℂ)
    (hE : IsChannel E) (hclass : ClassicalOutput E)
    (hcov : ∀ pi : Equiv.Perm (Fin n), ∃ K : Superop (KeyOut L C len) (KeyOut L C len),
      IsChannel K ∧ (∀ X, E (permuteInput pi X) = K (E X)) ∧
      (∀ X, idealProtocol len E (permuteInput pi X) = K (idealProtocol len E X)))
    (epsilon : ℝ) (hepsilon : 0 ≤ epsilon)
    (htest : traceNorm (tensorId (E - idealProtocol len E) (pureDensity psi)) ≤
      epsilon / (n+1 : ℝ) ^ ((a*b)^2-1)) :
    diamond (E - idealProtocol len E) ≤ epsilon := by sorry

end QAlgorithms.Papers.Independent.Support50.P22

end
Source
Post-selection technique for quantum channels with applications to quantum cryptography, arXiv:0809.3019v1, PDF p. 3, Unnumbered QKD sufficient-security criterion, equation (4)
Read-back

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

Let n,a,b∈Nn,a,b\in\mathbb Nn,a,b∈N, with a>0a>0a>0 and b>0b>0b>0, put d=abd=abd=ab and Hn={0,…,d−1}{0,…,n−1}H_n=\{0,\ldots,d-1\}^{\{0,\ldots,n-1\}}Hn​={0,…,d−1}{0,…,n−1}, and let R,L,CR,L,CR,L,C be finite nonempty types with decidable equality. Fix ℓ:L→N\ell:L\to\mathbb Nℓ:L→N, and let ZZZ consist of indices (l,((s,t),c))(l,((s,t),c))(l,((s,t),c)) with s,t∈{0,1}ℓ(l)s,t\in\{0,1\}^{\ell(l)}s,t∈{0,1}ℓ(l). Let ψ∈CHn×R\psi\in\mathbb C^{H_n\times R}ψ∈CHn​×R satisfy ∥ψ∥=1\|\psi\|=1∥ψ∥=1 and

∑r∈Rψ(x,r)ψ(y,r)‾=τn(x,y),τn(x,y)=∫∏i=0n−1ρ(xi,yi) dμd(ρ),\sum_{r\in R}\psi(x,r)\overline{\psi(y,r)}=\tau_n(x,y), \qquad \tau_n(x,y)=\int\prod_{i=0}^{n-1}\rho(x_i,y_i)\,d\mu_d(\rho),r∈R∑​ψ(x,r)ψ(y,r)​=τn​(x,y),τn​(x,y)=∫i=0∏n−1​ρ(xi​,yi​)dμd​(ρ),

where μd\mu_dμd​ is the law obtained by taking Ve0Ve_0Ve0​ for a Haar-distributed unitary VVV on Cd2\mathbb C^{d^2}Cd2, reshaping this vector as ϕ∈Cd⊗Cd\phi\in\mathbb C^d\otimes\mathbb C^dϕ∈Cd⊗Cd using the finite-product indexing, and setting ρj,k=∑tϕ(j,t)ϕ(k,t)‾\rho_{j,k}=\sum_t\phi(j,t)\overline{\phi(k,t)}ρj,k​=∑t​ϕ(j,t)ϕ(k,t)​. Let EEE be a complex linear map from matrices on HnH_nHn​ to matrices on ZZZ, assume it is a channel, and assume E(X)z,z′=0E(X)_{z,z'}=0E(X)z,z′​=0 for every matrix XXX whenever z≠z′z\ne z'z=z′. Here a channel means a map of the form X↦∑jKjXKj†X\mapsto\sum_j K_jXK_j^\daggerX↦∑j​Kj​XKj†​ for finitely many matrices satisfying ∑jKj†Kj=I\sum_jK_j^\dagger K_j=I∑j​Kj†​Kj​=I. Define EidealE_{\mathrm{ideal}}Eideal​ by taking E(X)E(X)E(X), discarding its off-diagonal entries, and replacing the key pair at each fixed l,cl,cl,c by equal uniform keys: its diagonal entry at (l,((s,t),c))(l,((s,t),c))(l,((s,t),c)) is 2−ℓ(l)∑u,vE(X)(l,((u,v),c)),(l,((u,v),c))2^{-\ell(l)}\sum_{u,v}E(X)_{(l,((u,v),c)),(l,((u,v),c))}2−ℓ(l)∑u,v​E(X)(l,((u,v),c)),(l,((u,v),c))​ if s=ts=ts=t, and zero otherwise. For each permutation π\piπ of the nnn positions, write Pπ(X)x,y=Xx∘π,y∘πP_\pi(X)_{x,y}=X_{x\circ\pi,y\circ\pi}Pπ​(X)x,y​=Xx∘π,y∘π​, and suppose there exists a channel KπK_\piKπ​ on ZZZ such that, for every XXX,

E(PπX)=Kπ(E(X)),Eideal(PπX)=Kπ(Eideal(X)).E(P_\pi X)=K_\pi(E(X)), \qquad E_{\mathrm{ideal}}(P_\pi X)=K_\pi(E_{\mathrm{ideal}}(X)).E(Pπ​X)=Kπ​(E(X)),Eideal​(Pπ​X)=Kπ​(Eideal​(X)).

For any real ϵ≥0\epsilon\ge0ϵ≥0, if

∥((E−Eideal)⊗id⁡R)(∣ψ⟩⟨ψ∣)∥1≤ϵ(n+1)d2−1,\left\|((E-E_{\mathrm{ideal}})\otimes\operatorname{id}_R) (|\psi\rangle\langle\psi|)\right\|_1 \le \frac{\epsilon}{(n+1)^{d^2-1}},∥((E−Eideal​)⊗idR​)(∣ψ⟩⟨ψ∣)∥1​≤(n+1)d2−1ϵ​,

then ∥E−Eideal∥⋄≤ϵ\|E-E_{\mathrm{ideal}}\|_\diamond\le\epsilon∥E−Eideal​∥⋄​≤ϵ. In these formulas, (∣ψ⟩⟨ψ∣)p,q=ψ(p)ψ(q)‾(|\psi\rangle\langle\psi|)_{p,q}=\psi(p)\overline{\psi(q)}(∣ψ⟩⟨ψ∣)p,q​=ψ(p)ψ(q)​, ∥X∥1=Re⁡Tr⁡X†X\|X\|_1=\operatorname{Re}\operatorname{Tr}\sqrt{X^\dagger X}∥X∥1​=ReTrX†X​, and a map T⊗id⁡RT\otimes\operatorname{id}_RT⊗idR​ acts by applying TTT to each fixed reference block X(x,r),(y,s)X_{(x,r),(y,s)}X(x,r),(y,s)​. The diamond quantity is exactly

∥T∥⋄=sup⁡X a complex matrix on Hn×Hn∥X∥1≤1∥(id⁡Hn⊗T)(X)∥1,\|T\|_\diamond= \sup_{\substack{X\text{ a complex matrix on }H_n\times H_n\\\|X\|_1\le1}} \|(\operatorname{id}_{H_n}\otimes T)(X)\|_1,∥T∥⋄​=X a complex matrix on Hn​×Hn​∥X∥1​≤1​sup​∥(idHn​​⊗T)(X)∥1​,

with no positivity or Hermiticity restriction on XXX. The statement includes n=0n=0n=0, when HnH_nHn​ is a singleton, and key lengths may be zero.

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