Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5: finite probabilistic exact protocol Pi

Open
QAlgorithms.Papers.Independent.Intakenext100.P54.finite_probabilistic_exact_pi

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

prove2quantum

Let D≥1D\ge1D≥1 and 0<ε≤10<\varepsilon\le10<ε≤1. Put B=(10/ε)2Dlog⁡2(20D/ε)B=(10/\varepsilon)^2D\log_2(20D/\varepsilon)B=(10/ε)2Dlog2​(20D/ε). There are 1≤K≤B1\le K\le B1≤K≤B randomising unitaries for which the following protocol uses one shared maximally entangled state of rank DDD. On a normalized target ∣ψ⟩|\psi\rangle∣ψ⟩, Alice measures

Ak=DK(1+ε)Ukψ‾Uk∗,Afail=I−∑kAk,A_k=\frac{D}{K(1+\varepsilon)}U_k\overline\psi U_k^*,\qquad A_{\rm fail}=I-\sum_k A_k,Ak​=K(1+ε)D​Uk​ψ​Uk∗​,Afail​=I−k∑​Ak​,

announces the outcome, and Bob applies Uk⊤U_k^\topUk⊤​ on good outcome kkk. The effects form a POVM. The unnormalized corrected good branch equals ψ/[K(1+ε)]\psi/[K(1+\varepsilon)]ψ/[K(1+ε)], so the conditional output is exactly ψ\psiψ, and

Pr⁡{failure}=ε1+ε≤ε,C=log⁡2(K+1)≤log⁡2(B+1),E=log⁡2D.\Pr\{\mathrm{failure}\}=\frac{\varepsilon}{1+\varepsilon}\le\varepsilon,\qquad C=\log_2(K+1)\le\log_2(B+1),\qquad E=\log_2D.Pr{failure}=1+εε​≤ε,C=log2​(K+1)≤log2​(B+1),E=log2​D.

The construction works for every target with the same unitaries. This is a finite probabilistic exact RSP protocol.

Formalization Note The complete message support includes failure. The displayed cbit bound corrects the printed bound that counts only good messages.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P54
Formal statement
noncomputable section

open scoped BigOperators Matrix ComplexConjugate ComplexOrder NNReal ENNReal

open MeasureTheory ProbabilityTheory

namespace QAlgorithms.Papers.Independent.Intakenext100.P54

open QAlgorithms.Papers.Independent.Information100.P03 (PureEnsemble)

open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)

open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)

open QAlgorithms.Papers.Independent.Claimed50.P08 (classicalEntropy)

open QAlgorithms.Papers.Independent.Claimed50.P38 (tensorSuperop)

/-- Theorem 5, PDF pp.3–4: the specified Pi protocol, its exact good branches and exact
failure probability. Correction to printed bookkeeping: the complete support has K+1 outcomes,
so the support communication bound is log2(randomisingBound+1), using log2 D ebits. -/
theorem finite_probabilistic_exact_pi (D : ℕ) (hD : 0 < D)
    (eps : ℝ) (heps : 0 < eps) (hepsOne : eps ≤ 1) :
    ∃ K : ℕ, 0 < K ∧ (K : ℝ) ≤ randomisingBound D eps ∧
      Real.logb 2 (K + 1 : ℝ) ≤ Real.logb 2 (randomisingBound D eps + 1) ∧
      ∃ U : Fin K → Matrix.unitaryGroup (Fin D) ℂ,
        Randomising U eps ∧ ∀ psi : RSPVector (Fin D),
          IsPOVM (piEffect U eps psi) ∧
          (∀ k, piBranch U eps psi (some k) =
            ((1 / ((K : ℝ) * (1 + eps)) : ℝ) : ℂ) • pureDensity psi.val) ∧
          (piBranch U eps psi none).trace.re = eps / (1 + eps) ∧
          eps / (1 + eps) ≤ eps := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P54

end
Source
Remote preparation of quantum states, arXiv:quant-ph/0307100v3, PDF p. 4, Theorem 5: finite probabilistic exact protocol Pi
Read-back

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

For every natural number D>0D>0D>0 and real 0<ε≤10<\varepsilon\le10<ε≤1, there exist a natural number K>0K>0K>0 and unitary complex D×DD\times DD×D matrices U0,…,UK−1U_0,\ldots,U_{K-1}U0​,…,UK−1​ such that, writing

B=(10ε)2Dlog⁡2 ⁣(20Dε),B=\left(\frac{10}{\varepsilon}\right)^2D \log_2\!\left(\frac{20D}{\varepsilon}\right),B=(ε10​)2Dlog2​(ε20D​),

one has K≤BK\le BK≤B and log⁡2(K+1)≤log⁡2(B+1)\log_2(K+1)\le\log_2(B+1)log2​(K+1)≤log2​(B+1), and every positive semidefinite matrix ρ\rhoρ of trace one satisfies

1−εDID⪯1K∑kUkρUk†⪯1+εDID.\frac{1-\varepsilon}{D}I_D \preceq\frac1K\sum_kU_k\rho U_k^\dagger \preceq\frac{1+\varepsilon}{D}I_D.D1−ε​ID​⪯K1​k∑​Uk​ρUk†​⪯D1+ε​ID​.

Furthermore, for every unit vector ψ∈CD\psi\in\mathbb C^Dψ∈CD, define

Gk=DK(1+ε)Ukψψ†‾Uk†,Ek=Gk,Enone=ID−∑kGk,G_k=\frac{D}{K(1+\varepsilon)} U_k\overline{\psi\psi^\dagger}U_k^\dagger,\qquad E_k=G_k,\qquad E_{\mathrm{none}}=I_D-\sum_kG_k,Gk​=K(1+ε)D​Uk​ψψ†​Uk†​,Ek​=Gk​,Enone​=ID​−k∑​Gk​,

and

Bk=UkT(D−1GkT)(UkT)†,Bnone=D−1EnoneT.B_k=U_k^{\mathsf T}(D^{-1}G_k^{\mathsf T})(U_k^{\mathsf T})^\dagger, \qquad B_{\mathrm{none}}=D^{-1}E_{\mathrm{none}}^{\mathsf T}.Bk​=UkT​(D−1GkT​)(UkT​)†,Bnone​=D−1EnoneT​.

Then every EkE_kEk​ and EnoneE_{\mathrm{none}}Enone​ is positive semidefinite, their sum is IDI_DID​, and

Bk=1K(1+ε)ψψ†for every k,Re⁡tr⁡Bnone=ε1+ε,ε1+ε≤ε.B_k=\frac{1}{K(1+\varepsilon)}\psi\psi^\dagger \quad\text{for every }k,\qquad \operatorname{Re}\operatorname{tr}B_{\mathrm{none}} =\frac{\varepsilon}{1+\varepsilon}, \qquad \frac{\varepsilon}{1+\varepsilon}\le\varepsilon.Bk​=K(1+ε)1​ψψ†for every k,RetrBnone​=1+εε​,1+εε​≤ε.

Here (ψψ†)ab=ψaψb‾(\psi\psi^\dagger)_{ab}=\psi_a\overline{\psi_b}(ψψ†)ab​=ψa​ψb​​, the overline is entrywise conjugation, T\mathsf TT is transpose, †\dagger† is conjugate transpose, and ⪯\preceq⪯ is the positive semidefinite order. The same family UkU_kUk​ works for every ρ\rhoρ and every ψ\psiψ; the assertion includes D=1D=1D=1 and ε=1\varepsilon=1ε=1.

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