Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Symmetry after measuring the test

Open
QAlgorithms.Papers.Independent.Intakenext100.P77.posttest_symmetry

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

prove2quantum

Let n≥1n\ge1n≥1 and let UUU be any joint unitary attack on 2n2n2n signals with a fixed initial pure probe. Fix the bases and balanced partition and let EsE^sEs be its coherent symmetrization from Eq. (13), with test positions written first. Then, for every test input iTi_TiT​, test outcome jTj_TjT​, and information inputs iI,kIi_I,k_IiI​,kI​,

p(jT∣iT,iI)=p(jT∣iT,kI).p(j_T\mid i_T,i_I)=p(j_T\mid i_T,k_I).p(jT​∣iT​,iI​)=p(jT​∣iT​,kI​).

For a positive common probability, the conditional probes EiI,jIE_{i_I,j_I}EiI​,jI​​ have ∑jI∥EiI,jI∥2=1\sum_{j_I}\|E_{i_I,j_I}\|^2=1∑jI​​∥EiI​,jI​​∥2=1 and retain Eq. (18):

EiI,jI(mT,mI,q)=2−n/2(−1)(iI⊕jI)⋅mIFiI⊕mI,jI⊕mI(mT,q).E_{i_I,j_I}(m_T,m_I,q)=2^{-n/2}(-1)^{(i_I\oplus j_I)\cdot m_I}F_{i_I\oplus m_I,j_I\oplus m_I}(m_T,q).EiI​,jI​​(mT​,mI​,q)=2−n/2(−1)(iI​⊕jI​)⋅mI​FiI​⊕mI​,jI​⊕mI​​(mT​,q).

Here mT,mIm_T,m_ImT​,mI​ are the retained test and information mask registers, qqq is the original probe coordinate, and FFF is computed by symmetrizing only the test mask and dividing by the square root of the same common test probability. This permits the conditional Fourier analysis; individual rows of FFF need not be normalized.

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

/-- Appendix C, PDF pp.14--15, Eqs.(16)--(18): the probability of a test
outcome is independent of the information input. Positive-probability conditional
probes are normalized and retain the explicitly constructed information symmetry. -/
theorem posttest_symmetry {n d : ℕ} (hn : 1 ≤ n)
    (U : Matrix.unitaryGroup (Fin d × Qubits (n + n)) ℂ) (e0 : Fin d)
    (iT jT : Qubits n) :
    (∀ iI kI, testProbability (coherentBitSymmetrize (attackProbes U e0)) iT jT iI =
      testProbability (coherentBitSymmetrize (attackProbes U e0)) iT jT kI) ∧
    (0 < testProbability (coherentBitSymmetrize (attackProbes U e0)) iT jT (fun _ => false) →
      (∀ iI, ∑ jI, ‖conditionedSymmetric U e0 iT jT iI jI‖ ^ 2 = 1) ∧
      ∀ iI jI mT mI q,
        conditionedSymmetric U e0 iT jT iI jI (Fin.append mT mI, q) =
          ((Real.sqrt ((2 : ℝ) ^ n))⁻¹ : ℂ) * character (iI + jI) mI *
            testOnlyConditioned U e0 iT jT (iI + mI) (jI + mI) (mT, q)) := 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. 14, Appendix C: symmetry survives test measurement
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 binary strings iT,jTi_T,j_TiT​,jT​ of length nnn, use XOR addition, concatenation ∥\Vert∥, and χ(x,y)=(−1)∑rxryr\chi(x,y)=(-1)^{\sum_rx_ry_r}χ(x,y)=(−1)∑r​xr​yr​ with the exponent computed modulo 222. Set

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

where u,v,ru,v,ru,v,r have length 2n2n2n, i,ji,ji,j have length nnn, and q<dq<dq<d. Then P(i)=P(k)P(i)=P(k)P(i)=P(k) for every pair of length-nnn strings i,ki,ki,k. Moreover, if P(0n)>0P(0^n)>0P(0n)>0, define

Fi,j(r,q)=SiT∥i, jT∥j(r,q)P(0n),Ti,j(m,q)=2−n/2χ(iT+jT,m)P(0n) U(q,(jT+m)∥j),(e0,(iT+m)∥i).F_{i,j}(r,q)=\frac{S_{i_T\Vert i,\ j_T\Vert j}(r,q)}{\sqrt{P(0^n)}}, \qquad T_{i,j}(m,q)= \frac{2^{-n/2}\chi(i_T+j_T,m)} {\sqrt{P(0^n)}}\, U_{(q,(j_T+m)\Vert j),(e_0,(i_T+m)\Vert i)}.Fi,j​(r,q)=P(0n)​SiT​∥i, jT​∥j​(r,q)​,Ti,j​(m,q)=P(0n)​2−n/2χ(iT​+jT​,m)​U(q,(jT​+m)∥j),(e0​,(iT​+m)∥i)​.

For every iii, ∑j∥Fi,j∥2=1\sum_j\|F_{i,j}\|^2=1∑j​∥Fi,j​∥2=1, and for all length-nnn strings i,j,mT,mIi,j,m_T,m_Ii,j,mT​,mI​ and every q<dq<dq<d,

Fi,j(mT∥mI,q)=2−n/2χ(i+j,mI) Ti+mI,j+mI(mT,q).F_{i,j}(m_T\Vert m_I,q) = 2^{-n/2}\chi(i+j,m_I)\, T_{i+m_I,j+m_I}(m_T,q).Fi,j​(mT​∥mI​,q)=2−n/2χ(i+j,mI​)Ti+mI​,j+mI​​(mT​,q).

The normalization and coordinate identity are asserted only under the strict positivity condition; if P(0n)=0P(0^n)=0P(0n)=0, only the independence of P(i)P(i)P(i) from iii is asserted.

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