Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The error-register purification dominates the mixed probes

Open
QAlgorithms.Papers.Independent.Intakenext100.P77.purification_dominates

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

prove2quantum

Let n≥1n\ge1n≥1. Fix an unrestricted joint unitary attack on the 2n2n2n ideal two-level signals and a probe initially in a fixed pure basis state. Fix the preparation/measurement bases, a balanced test/information partition, and announced test strings iT,jTi_T,j_TiT​,jT​ whose probability is positive. Symmetrize the attack coherently by Eq. (2), then condition on this test outcome using its actual probability. Write Ei,jE_{i,j}Ei,j​ for the resulting normalized information-register probe coefficients, with Alice's nnn information bits uniform. These coefficients are constructed from the unitary, rather than postulated to have any Fourier or information property. The public classical channel is unjammable and Eve has access only to the quantum channel and the public transcript.

For an information input iii, put ϕi=∑jEi,j⊗∣i⊕j⟩\phi_i=\sum_j E_{i,j}\otimes|i\oplus j\rangleϕi​=∑j​Ei,j​⊗∣i⊕j⟩, ηl=2−n∑i(−1)l⋅iϕi\eta_l=2^{-n}\sum_i(-1)^{l\cdot i}\phi_iηl​=2−n∑i​(−1)l⋅iϕi​, and dl2=∥ηl∥2d_l^2=\|\eta_l\|^2dl2​=∥ηl​∥2. Dot products are modulo two and inner products conjugate the first argument.

Writing ρi=∑j∣Ei,j⟩⟨Ei,j∣\rho_i=\sum_j|E_{i,j}\rangle\langle E_{i,j}|ρi​=∑j​∣Ei,j​⟩⟨Ei,j​∣, we have

Tr⁡error∣ϕi⟩⟨ϕi∣=ρi,Iacc(i:ρi)≤Iacc(i:ϕi).\operatorname{Tr}_{\mathrm{error}}|\phi_i\rangle\langle\phi_i|=\rho_i,\qquad I_{\mathrm{acc}}(i:\rho_i)\le I_{\mathrm{acc}}(i:\phi_i).Trerror​∣ϕi​⟩⟨ϕi​∣=ρi​,Iacc​(i:ρi​)≤Iacc​(i:ϕi​).

The information inequality holds for any normalized prior on iii. Here IaccI_{\mathrm{acc}}Iacc​ optimizes the mutual information over finite POVMs. This supplies an information upper bound by enlarging Eve's hypothetical system, without claiming a physical cloning operation.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P77
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P77

open scoped BigOperators ComplexConjugate ComplexOrder

open QAlgorithms

-- The repair instruction authorizes imports of pinned accepted definitions.
-- These are definitions only; no imported paper theorem is used here.

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

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

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

open QAlgorithms.Papers.Independent.Information100.P39 (pushLaw)

open QAlgorithms.Papers.Independent.Support50.P16 (trivialMeasurement)

attribute [local instance] Classical.propDecidable Classical.decEq

/-- Section 3.2, PDF p.6: the error-labelled purification has exactly Eve's
mixed-state marginal and dominates its accessible information. Priors include
the uniform code/syndrome ensembles used later; no cloning operation is claimed. -/
theorem purification_dominates {n d : ℕ} (hn : 1 ≤ n)
    (U : Matrix.unitaryGroup (Fin d × Qubits (n + n)) ℂ) (e0 : Fin d)
    (iT jT : Qubits n)
    (hpos : 0 < testProbability (coherentBitSymmetrize (attackProbes U e0)) iT jT (fun _ => false)) :
    let E := conditionedSymmetric U e0 iT jT
    (∀ i, traceRight (pureDensity (errorPurification E i)) = probeDensity E i) ∧
    ∀ p : Law (Qubits n),
      ensembleAccessibleInfo p.prob (probeDensity E) id ≤
        ensembleAccessibleInfo p.prob (fun i => pureDensity (errorPurification E i)) id := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P77

end
Source
A Proof of the Security of Quantum Key Distribution, arXiv:quant-ph/9912053v1, PDF p. 6, Section 3.2: error-register purification dominates Eve’s mixed states
Read-back

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

For natural numbers n,dn,dn,d with n≥1n\ge1n≥1, a unitary matrix UUU indexed by {0,…,d−1}×{0,1}2n\{0,\ldots,d-1\}\times\{0,1\}^{2n}{0,…,d−1}×{0,1}2n, an index e0<de_0<de0​<d, and length-nnn strings iT,jTi_T,j_TiT​,jT​, use XOR addition, concatenation ∥\Vert∥, and the sign χ(x,y)=(−1)∑rxryr\chi(x,y)=(-1)^{\sum_rx_ry_r}χ(x,y)=(−1)∑r​xr​yr​ with exponent modulo 222. Let

Su,v(r,q)=2−nχ(u+v,r)U(q,v+r),(e0,u+r),P=∑j∑r,q∣SiT∥0n, jT∥j(r,q)∣2,S_{u,v}(r,q)=2^{-n}\chi(u+v,r)U_{(q,v+r),(e_0,u+r)}, \quad P=\sum_j\sum_{r,q}|S_{i_T\Vert0^n,\ j_T\Vert j}(r,q)|^2,Su,v​(r,q)=2−nχ(u+v,r)U(q,v+r),(e0​,u+r)​,P=j∑​r,q∑​∣SiT​∥0n, jT​∥j​(r,q)∣2,

and assume P>0P>0P>0. On the index set Q0={0,1}2n×{0,…,d−1}Q_0=\{0,1\}^{2n}\times\{0,\ldots,d-1\}Q0​={0,1}2n×{0,…,d−1}, define

Fi,j(a)=P−1/2SiT∥i, jT∥j(a),Gi(a,c)=Fi,i+c(a),Ri(a,b)=∑jFi,j(a)Fi,j(b)‾.F_{i,j}(a)=P^{-1/2}S_{i_T\Vert i,\ j_T\Vert j}(a), \quad G_i(a,c)=F_{i,i+c}(a), \quad R_i(a,b)=\sum_jF_{i,j}(a)\overline{F_{i,j}(b)}.Fi,j​(a)=P−1/2SiT​∥i, jT​∥j​(a),Gi​(a,c)=Fi,i+c​(a),Ri​(a,b)=j∑​Fi,j​(a)Fi,j​(b)​.

For every length-nnn string iii, tracing out the ccc coordinate of the matrix GiGi†G_iG_i^\daggerGi​Gi†​ gives exactly RiR_iRi​, that is,

∑cGi(a,c)Gi(b,c)‾=Ri(a,b).\sum_cG_i(a,c)\overline{G_i(b,c)}=R_i(a,b).c∑​Gi​(a,c)Gi​(b,c)​=Ri​(a,b).

Furthermore, for every probability law ppp on {0,1}n\{0,1\}^n{0,1}n,

A(p,R)≤A(p,GG†).\mathcal A(p,R)\le\mathcal A(p,G G^\dagger).A(p,R)≤A(p,GG†).

Here, for any family of matrices XiX_iXi​ on a finite index set, A(p,X)\mathcal A(p,X)A(p,X) is the real supremum over all positive integers hhh and positive semidefinite matrices M0,…,Mh−1M_0,\ldots,M_{h-1}M0​,…,Mh−1​ with ∑oMo=I\sum_oM_o=I∑o​Mo​=I of H(wI)+H(wO)−H(w)H(w_I)+H(w_O)-H(w)H(wI​)+H(wO​)−H(w), where w(i,o)=p(i)Re⁡tr⁡(MoXi)w(i,o)=p(i)\operatorname{Re}\operatorname{tr}(M_oX_i)w(i,o)=p(i)Retr(Mo​Xi​), wI(i)=∑ow(i,o)w_I(i)=\sum_ow(i,o)wI​(i)=∑o​w(i,o), wO(o)=∑iw(i,o)w_O(o)=\sum_iw(i,o)wO​(o)=∑i​w(i,o), and H(v)=−∑xvxlog⁡2vxH(v)=-\sum_xv_x\log_2v_xH(v)=−∑x​vx​log2​vx​ with log⁡20=0\log_2 0=0log2​0=0. The law ppp may assign zero probability to any inputs.

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