Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BB84 purification trajectories preserve the two Claim 10 inequalities

Open
QAlgorithms.Papers.Independent.Intakenext100.P80.bb84_trajectory_invariants

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

prove2quantum

Let 0≤p<1/40\le p<1/40≤p<1/4 and 0≤a≤p0\le a\le p0≤a≤p. Start with independent Pauli noise (qX,qY,qZ)=(p−a,a,p−a)(q_X,q_Y,q_Z)=(p-a,a,p-a)(qX​,qY​,qZ​)=(p−a,a,p−a). Fix any finite word of B and P steps whose first step is B; its suffix may be empty. For each prefix, compute the conditional Pauli error rates by performing those steps, and write pZ=qX+qYp_Z=q_X+q_YpZ​=qX​+qY​ and Δ=qZ−qY\Delta=q_Z-q_YΔ=qZ​−qY​ for the resulting bit-error probability and error difference. Index prefixes by jjj, with j=0j=0j=0 denoting the initial distribution. Then

Δj≥0(1≤j≤L),1−2pZ,j−2Δj>0(0≤j≤L),\Delta_j\ge0\quad(1\le j\le L),\qquad 1-2p_{Z,j}-2\Delta_j>0\quad(0\le j\le L),Δj​≥0(1≤j≤L),1−2pZ,j​−2Δj​>0(0≤j≤L),

where LLL is the length of the fixed word. Thus the first inequality begins after the initial B step, while the second also holds before purification.

These are invariants of the computed BB84 trajectories used in the worst-channel argument; they impose no invariant hypotheses on arbitrary error triples.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P80
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P80

open scoped ComplexConjugate

/-- Claim 10, PDF p.23, inheriting Theorem 9's setup on p.22.
The strict inequality holds initially and at every prefix. Delta need only
be nonnegative after the mandatory first B. The suffix is any fixed finite
B/P word, including the empty word; trajectories are computed, not supplied
as arbitrary triples satisfying invariant hypotheses. -/
theorem bb84_trajectory_invariants (p a : ℝ)
    (hp : 0 ≤ p) (hpUpper : p < 1 / 4) (ha : 0 ≤ a) (haUpper : a ≤ p)
    (suffix : List PurificationStep) :
    0 < 1 - 2 * bitError (bb84Rates p a) - 2 * pauliErrorDifference (bb84Rates p a) ∧
    ∀ k : ℕ, k ≤ suffix.length →
      let q := runSteps (.B :: suffix.take k) (bb84Rates p a)
      0 ≤ pauliErrorDifference q ∧ 0 < 1 - 2 * bitError q - 2 * pauliErrorDifference q := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P80

end
Source
Proof of security of quantum key distribution with two-way classical communications, arXiv:quant-ph/0105121v2, PDF p. 23, Claim 10, with Theorem 9 assumptions on p.22
Read-back

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

For every pair of real numbers p,ap,ap,a satisfying 0≤p<140\le p<\tfrac140≤p<41​ and 0≤a≤p0\le a\le p0≤a≤p, and every finite list LLL whose entries are BBB or PPP, the assertions below hold for the initial triple q0=(x0,y0,z0)=(p−a,a,p−a)q_0=(x_0,y_0,z_0)=(p-a,a,p-a)q0​=(x0​,y0​,z0​)=(p−a,a,p−a) and the transformations defined as follows. Identify Booleans with {0,1}\{0,1\}{0,1}, write ⊕\oplus⊕ for exclusive-or, and set Hu,v=(−1)uv/2H_{u,v}=(-1)^{uv}/\sqrt2Hu,v​=(−1)uv/2​ and E(u,v)(a,b)=1{b=a⊕u}Hv,aE_{(u,v)}(a,b)=\mathbf1_{\{b=a\oplus u\}}H_{v,a}E(u,v)​(a,b)=1{b=a⊕u}​Hv,a​. For each current real triple r=(x,y,z)r=(x,y,z)r=(x,y,z), put wr(0,0)=1−x−y−zw_r(0,0)=1-x-y-zwr​(0,0)=1−x−y−z, wr(1,0)=xw_r(1,0)=xwr​(1,0)=x, wr(1,1)=yw_r(1,1)=ywr​(1,1)=y, wr(0,1)=zw_r(0,1)=zwr​(0,1)=z, and define

Br(o)=∑e,f∈{0,1}2wr(e)wr(f)∑u∈{0,1}∣∑a,b∈{0,1}Eo(a,b)‾Ee(a,b)Ef(u⊕a,u⊕b)∣2,Sr=∑o∈{0,1}2Br(o),Ae,f,g;u,v(a,b)=(−1)b(u1⊕v1)(u2⊕v2)∑a2,a3,b2,b3∈{0,1}Hu1,a2Hu2,a3Hv1,b2Hv2,b3⋅Ee(a⊕a2⊕a3,b⊕b2⊕b3)Ef(a2,b2)Eg(a3,b3),Pr(o)=∑e,f,g∈{0,1}2wr(e)wr(f)wr(g)∑u,v∈{0,1}2∣∑a,b∈{0,1}Eo(a,b)‾Ae,f,g;u,v(a,b)∣2,TB(r)=(Br(1,0)Sr,Br(1,1)Sr,Br(0,1)Sr),TP(r)=(Pr(1,0),Pr(1,1),Pr(0,1)),\begin{aligned} B_r(o)&= \sum_{e,f\in\{0,1\}^2}w_r(e)w_r(f) \sum_{u\in\{0,1\}} \left| \sum_{a,b\in\{0,1\}} \overline{E_o(a,b)}E_e(a,b)E_f(u\oplus a,u\oplus b) \right|^2,\\ S_r&=\sum_{o\in\{0,1\}^2}B_r(o),\\ A_{e,f,g;u,v}(a,b)&= (-1)^{b(u_1\oplus v_1)(u_2\oplus v_2)} \sum_{a_2,a_3,b_2,b_3\in\{0,1\}} H_{u_1,a_2}H_{u_2,a_3}H_{v_1,b_2}H_{v_2,b_3}\\ &\hspace{2em}\cdot E_e(a\oplus a_2\oplus a_3,b\oplus b_2\oplus b_3) E_f(a_2,b_2)E_g(a_3,b_3),\\ P_r(o)&= \sum_{e,f,g\in\{0,1\}^2}w_r(e)w_r(f)w_r(g) \sum_{u,v\in\{0,1\}^2} \left| \sum_{a,b\in\{0,1\}}\overline{E_o(a,b)}A_{e,f,g;u,v}(a,b) \right|^2,\\ T_B(r)&=\left(\frac{B_r(1,0)}{S_r},\frac{B_r(1,1)}{S_r},\frac{B_r(0,1)}{S_r}\right),\\ T_P(r)&=\bigl(P_r(1,0),P_r(1,1),P_r(0,1)\bigr), \end{aligned}Br​(o)Sr​Ae,f,g;u,v​(a,b)Pr​(o)TB​(r)TP​(r)​=e,f∈{0,1}2∑​wr​(e)wr​(f)u∈{0,1}∑​​a,b∈{0,1}∑​Eo​(a,b)​Ee​(a,b)Ef​(u⊕a,u⊕b)​2,=o∈{0,1}2∑​Br​(o),=(−1)b(u1​⊕v1​)(u2​⊕v2​)a2​,a3​,b2​,b3​∈{0,1}∑​Hu1​,a2​​Hu2​,a3​​Hv1​,b2​​Hv2​,b3​​⋅Ee​(a⊕a2​⊕a3​,b⊕b2​⊕b3​)Ef​(a2​,b2​)Eg​(a3​,b3​),=e,f,g∈{0,1}2∑​wr​(e)wr​(f)wr​(g)u,v∈{0,1}2∑​​a,b∈{0,1}∑​Eo​(a,b)​Ae,f,g;u,v​(a,b)​2,=(Sr​Br​(1,0)​,Sr​Br​(1,1)​,Sr​Br​(0,1)​),=(Pr​(1,0),Pr​(1,1),Pr​(0,1)),​

where division by zero is defined to give zero. The first assertion is

0<1−2(x0+y0)−2(z0−y0).0<1-2(x_0+y_0)-2(z_0-y_0).0<1−2(x0​+y0​)−2(z0​−y0​).

The second assertion is that for every natural number kkk with k≤∣L∣k\le |L|k≤∣L∣, if q(k)=(xk,yk,zk)q^{(k)}=(x_k,y_k,z_k)q(k)=(xk​,yk​,zk​) is obtained from q0q_0q0​ by first applying TBT_BTB​ and then applying, in order, the transformations specified by the first kkk entries of LLL, then

0≤zk−ykand0<1−2(xk+yk)−2(zk−yk).0\le z_k-y_k \quad\text{and}\quad 0<1-2(x_k+y_k)-2(z_k-y_k).0≤zk​−yk​and0<1−2(xk​+yk​)−2(zk​−yk​).

The case k=0k=0k=0 concerns the triple after the initial BBB transformation alone; when LLL is empty, this is the only permitted kkk. The parameter case p=0p=0p=0, which forces a=0a=0a=0, is included.

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