Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

B and P steps: conditional Pauli error transformations

Open
QAlgorithms.Papers.Independent.Intakenext100.P80.bp_error_updates

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

prove2quantum

Let independent input EPR pairs have Bell-diagonal Pauli noise with probabilities qX,qY,qZ≥0q_X,q_Y,q_Z\ge0qX​,qY​,qZ​≥0, where qX+qY+qZ≤1q_X+q_Y+q_Z\le1qX​+qY​+qZ​≤1, and put qI=1−qX−qY−qZq_I=1-q_X-q_Y-q_ZqI​=1−qX​−qY​−qZ​. A B step applies the bilateral controlled-NOT to two pairs, measures the target pair in the ZZZ basis, and retains the control pair exactly when the two measurement outcomes agree. Let pSp_SpS​ be its acceptance probability per two-pair block, and let qXB,qYB,qZBq^B_X,q^B_Y,q^B_ZqXB​,qYB​,qZB​ be the conditional error probabilities of the retained pair. A P step applies the three-pair phase repetition-code procedure, corrects the surviving pair by ZZZ precisely when both relative phase syndromes disagree, and retains it for every syndrome. Write qXP,qYP,qZPq^P_X,q^P_Y,q^P_ZqXP​,qYP​,qZP​ for its output error probabilities. Then

pS=1−2(qX+qY)(1−qX−qY),qXB=qX2+qY2pS,qYB=2qXqYpS,qZB=2qIqZpS,qXP=3qI2(qX+qY)+6qIqXqZ+3qX2qY+qX3,qYP=6qIqYqZ+3qX(qY2+qZ2)+3qYqZ2+qY3,qZP=3qI(qY2+qZ2)+6qXqYqZ+3qY2qZ+qZ3.\begin{aligned} p_S&=1-2(q_X+q_Y)(1-q_X-q_Y),\\ q^B_X&=\frac{q_X^2+q_Y^2}{p_S},& q^B_Y&=\frac{2q_Xq_Y}{p_S},& q^B_Z&=\frac{2q_Iq_Z}{p_S},\\ q^P_X&=3q_I^2(q_X+q_Y)+6q_Iq_Xq_Z+3q_X^2q_Y+q_X^3,\\ q^P_Y&=6q_Iq_Yq_Z+3q_X(q_Y^2+q_Z^2)+3q_Yq_Z^2+q_Y^3,\\ q^P_Z&=3q_I(q_Y^2+q_Z^2)+6q_Xq_Yq_Z+3q_Y^2q_Z+q_Z^3. \end{aligned}pS​qXB​qXP​qYP​qZP​​=1−2(qX​+qY​)(1−qX​−qY​),=pS​qX2​+qY2​​,=3qI2​(qX​+qY​)+6qI​qX​qZ​+3qX2​qY​+qX3​,=6qI​qY​qZ​+3qX​(qY2​+qZ2​)+3qY​qZ2​+qY3​,=3qI​(qY2​+qZ2​)+6qX​qY​qZ​+3qY2​qZ​+qZ3​.​qYB​=pS​2qX​qY​​,qZB​=pS​2qI​qZ​​,

These transformations describe the effective noise after a purification round. Independence is an assumption of this calculation, rather than a restriction on the adversaries in the paper's separate QKD security results.

Formalization Note Both step maps are computed from branch amplitudes of the specified circuits and Born probabilities. They are not defined by the displayed polynomials.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P80
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P80

open scoped ComplexConjugate

/-- Appendix C, PDF p.22, Eqs.(15)--(22); physical steps are defined on
PDF pp.16,18. For independent Bell-diagonal noise, the circuit-derived B
and P outputs have exactly these Pauli rates. B survival is per two-pair
block, rather than the retained/input population fraction. -/
theorem bp_error_updates (q : PauliRates) (hq : IsPauliRates q) :
    bSurvival q = 1 - 2 * (q.qX + q.qY) * (1 - q.qX - q.qY) ∧
    (bStep q).qX = (q.qX ^ 2 + q.qY ^ 2) / bSurvival q ∧
    (bStep q).qY = 2 * q.qX * q.qY / bSurvival q ∧
    (bStep q).qZ = 2 * identityRate q * q.qZ / bSurvival q ∧
    (pStep q).qX = 3 * identityRate q ^ 2 * (q.qX + q.qY) +
      6 * identityRate q * q.qX * q.qZ + 3 * q.qX ^ 2 * q.qY + q.qX ^ 3 ∧
    (pStep q).qY = 6 * identityRate q * q.qY * q.qZ +
      3 * q.qX * (q.qY ^ 2 + q.qZ ^ 2) + 3 * q.qY * q.qZ ^ 2 + q.qY ^ 3 ∧
    (pStep q).qZ = 3 * identityRate q * (q.qY ^ 2 + q.qZ ^ 2) +
      6 * q.qX * q.qY * q.qZ + 3 * q.qY ^ 2 * q.qZ + q.qZ ^ 3 := 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. 22, Appendix C, equations (15)–(22)
Read-back

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

For every real triple q=(x,y,z)q=(x,y,z)q=(x,y,z) satisfying x≥0x\ge0x≥0, y≥0y\ge0y≥0, z≥0z\ge0z≥0, and x+y+z≤1x+y+z\le1x+y+z≤1, the following seven equalities hold simultaneously. To specify all quantities, put r=1−x−y−zr=1-x-y-zr=1−x−y−z; identify Booleans with {0,1}\{0,1\}{0,1}, write ⊕\oplus⊕ for exclusive-or, and set w(0,0)=rw(0,0)=rw(0,0)=r, w(1,0)=xw(1,0)=xw(1,0)=x, w(1,1)=yw(1,1)=yw(1,1)=y, w(0,1)=zw(0,1)=zw(0,1)=z, 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​. Define

B(o)=∑e,f∈{0,1}2w(e)w(f)∑s∈{0,1}∣∑a,b∈{0,1}Eo(a,b)‾Ee(a,b)Ef(s⊕a,s⊕b)∣2,S=∑o∈{0,1}2B(o),Ae,f,g;s,t(a,b)=(−1)b(s1⊕t1)(s2⊕t2)∑a2,a3,b2,b3∈{0,1}Hs1,a2Hs2,a3Ht1,b2Ht2,b3⋅Ee(a⊕a2⊕a3,b⊕b2⊕b3)Ef(a2,b2)Eg(a3,b3),P(o)=∑e,f,g∈{0,1}2w(e)w(f)w(g)∑s,t∈{0,1}2∣∑a,b∈{0,1}Eo(a,b)‾Ae,f,g;s,t(a,b)∣2.\begin{aligned} B(o)&= \sum_{e,f\in\{0,1\}^2}w(e)w(f) \sum_{s\in\{0,1\}} \left| \sum_{a,b\in\{0,1\}} \overline{E_o(a,b)}E_e(a,b)E_f(s\oplus a,s\oplus b) \right|^2,\\ S&=\sum_{o\in\{0,1\}^2}B(o),\\ A_{e,f,g;s,t}(a,b)&= (-1)^{b(s_1\oplus t_1)(s_2\oplus t_2)} \sum_{a_2,a_3,b_2,b_3\in\{0,1\}} H_{s_1,a_2}H_{s_2,a_3}H_{t_1,b_2}H_{t_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(o)&= \sum_{e,f,g\in\{0,1\}^2}w(e)w(f)w(g) \sum_{s,t\in\{0,1\}^2} \left| \sum_{a,b\in\{0,1\}}\overline{E_o(a,b)}A_{e,f,g;s,t}(a,b) \right|^2. \end{aligned}B(o)SAe,f,g;s,t​(a,b)P(o)​=e,f∈{0,1}2∑​w(e)w(f)s∈{0,1}∑​​a,b∈{0,1}∑​Eo​(a,b)​Ee​(a,b)Ef​(s⊕a,s⊕b)​2,=o∈{0,1}2∑​B(o),=(−1)b(s1​⊕t1​)(s2​⊕t2​)a2​,a3​,b2​,b3​∈{0,1}∑​Hs1​,a2​​Hs2​,a3​​Ht1​,b2​​Ht2​,b3​​⋅Ee​(a⊕a2​⊕a3​,b⊕b2​⊕b3​)Ef​(a2​,b2​)Eg​(a3​,b3​),=e,f,g∈{0,1}2∑​w(e)w(f)w(g)s,t∈{0,1}2∑​​a,b∈{0,1}∑​Eo​(a,b)​Ae,f,g;s,t​(a,b)​2.​

Thus the BBB output coordinates are B(1,0)/S,B(1,1)/S,B(0,1)/SB(1,0)/S,B(1,1)/S,B(0,1)/SB(1,0)/S,B(1,1)/S,B(0,1)/S, and the PPP output coordinates are P(1,0),P(1,1),P(0,1)P(1,0),P(1,1),P(0,1)P(1,0),P(1,1),P(0,1). The asserted equalities are

S=1−2(x+y)(1−x−y),B(1,0)S=x2+y2S,B(1,1)S=2xyS,B(0,1)S=2rzS,P(1,0)=3r2(x+y)+6rxz+3x2y+x3,P(1,1)=6ryz+3x(y2+z2)+3yz2+y3,P(0,1)=3r(y2+z2)+6xyz+3y2z+z3.\begin{aligned} S&=1-2(x+y)(1-x-y),\\ \frac{B(1,0)}{S}&=\frac{x^2+y^2}{S},\\ \frac{B(1,1)}{S}&=\frac{2xy}{S},\\ \frac{B(0,1)}{S}&=\frac{2rz}{S},\\ P(1,0)&=3r^2(x+y)+6rxz+3x^2y+x^3,\\ P(1,1)&=6ryz+3x(y^2+z^2)+3yz^2+y^3,\\ P(0,1)&=3r(y^2+z^2)+6xyz+3y^2z+z^3. \end{aligned}SSB(1,0)​SB(1,1)​SB(0,1)​P(1,0)P(1,1)P(0,1)​=1−2(x+y)(1−x−y),=Sx2+y2​,=S2xy​,=S2rz​,=3r2(x+y)+6rxz+3x2y+x3,=6ryz+3x(y2+z2)+3yz2+y3,=3r(y2+z2)+6xyz+3y2z+z3.​
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