Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Conjugate-basis error law

Open
QAlgorithms.Papers.Independent.Intakenext100.P77.conjugate_error_law

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.

Change the information input and output bases to their conjugates, leaving the attack, test bases, and transcript fixed. If Po(c)P^o(c)Po(c) is the resulting error probability, averaged over uniform information inputs, then

Po(c)=dc2.P^o(c)=d_c^2.Po(c)=dc2​.

The conjugate coefficients are computed from EEE by Ek,lo=2−n∑i,j(−1)i⋅k+j⋅lEi,jE^o_{k,l}=2^{-n}\sum_{i,j}(-1)^{i\cdot k+j\cdot l}E_{i,j}Ek,lo​=2−n∑i,j​(−1)i⋅k+j⋅lEi,j​. This connects the Fourier spectrum to the counterfactual disturbance of the same attack.

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

/-- Lemma 3.2, PDF p.7, Eq.(5); Appendix E, pp.16--17: the error law in the
conjugate information bases of the SAME conditional attack equals d_c squared. -/
theorem conjugate_error_law {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))
    (c : Qubits n) :
    probeErrorProbability (conjugateProbes (conditionedSymmetric U e0 iT jT)) c =
      fourierWeight (conditionedSymmetric U e0 iT jT) c := 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. 7, Lemma 3.2: conjugate-basis error law
Read-back

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

Let n,d∈Nn,d\in\mathbb Nn,d∈N, with n≥1n\ge1n≥1, let UUU be a unitary matrix indexed by {0,…,d−1}×{0,1}2n\{0,\ldots,d-1\}\times\{0,1\}^{2n}{0,…,d−1}×{0,1}2n, choose e0<de_0<de0​<d, and choose iT,jT,c∈{0,1}ni_T,j_T,c\in\{0,1\}^niT​,jT​,c∈{0,1}n. Write +++ for bitwise XOR, a∥ba\Vert ba∥b for concatenation, and χr(a,b)=(−1)∑k<rakbk mod 2\chi_r(a,b)=(-1)^{\sum_{k<r}a_kb_k\bmod2}χr​(a,b)=(−1)∑k<r​ak​bk​mod2. For a,b,h∈{0,1}2na,b,h\in\{0,1\}^{2n}a,b,h∈{0,1}2n and q<dq<dq<d, define

Sa,b(h,q)=2−nχ2n(a+b,h) U(q,b+h),(e0,a+h),β=∑j∈{0,1}n∑h,q∣SiT∥0,jT∥j(h,q)∣2.S_{a,b}(h,q)=2^{-n}\chi_{2n}(a+b,h)\, U_{(q,b+h),(e_0,a+h)},\qquad \beta=\sum_{j\in\{0,1\}^n}\sum_{h,q}|S_{i_T\Vert0,j_T\Vert j}(h,q)|^2.Sa,b​(h,q)=2−nχ2n​(a+b,h)U(q,b+h),(e0​,a+h)​,β=j∈{0,1}n∑​h,q∑​∣SiT​∥0,jT​∥j​(h,q)∣2.

Assume β>0\beta>0β>0, and define vectors Ei,j∈C{0,1}2n×{0,…,d−1}E_{i,j}\in\mathbb C^{\{0,1\}^{2n}\times\{0,\ldots,d-1\}}Ei,j​∈C{0,1}2n×{0,…,d−1} by Ei,j(h,q)=β−1/2SiT∥i,jT∥j(h,q)E_{i,j}(h,q)=\beta^{-1/2}S_{i_T\Vert i,j_T\Vert j}(h,q)Ei,j​(h,q)=β−1/2SiT​∥i,jT​∥j​(h,q). Define

E^k,l=2−n∑i,j∈{0,1}nχn(i,k)χn(j,l)Ei,j,Fc(h,q,z)=2−n∑i∈{0,1}nχn(c,i)Ei,i+z(h,q).\widehat E_{k,l}=2^{-n}\sum_{i,j\in\{0,1\}^n}\chi_n(i,k)\chi_n(j,l)E_{i,j}, \qquad F_c(h,q,z)=2^{-n}\sum_{i\in\{0,1\}^n}\chi_n(c,i)E_{i,i+z}(h,q).Ek,l​=2−ni,j∈{0,1}n∑​χn​(i,k)χn​(j,l)Ei,j​,Fc​(h,q,z)=2−ni∈{0,1}n∑​χn​(c,i)Ei,i+z​(h,q).

Then

2−n∑i∈{0,1}n∥E^i,i+c∥22=∑h,q,z∣Fc(h,q,z)∣2.2^{-n}\sum_{i\in\{0,1\}^n}\|\widehat E_{i,i+c}\|_2^2 =\sum_{h,q,z}|F_c(h,q,z)|^2.2−ni∈{0,1}n∑​∥Ei,i+c​∥22​=h,q,z∑​∣Fc​(h,q,z)∣2.

The choice of e0e_0e0​ requires d>0d>0d>0, and the normalization uses the test weight with the information input fixed to the all-zero string.

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