Theorem 5: finite probabilistic exact protocol Pi
OpenQAlgorithms.Papers.Independent.Intakenext100.P54.finite_probabilistic_exact_piLet and . Put . There are randomising unitaries for which the following protocol uses one shared maximally entangled state of rank . On a normalized target , Alice measures
announces the outcome, and Bob applies on good outcome . The effects form a POVM. The unnormalized corrected good branch equals , so the conditional output is exactly , and
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.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P54
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number and real , there exist a natural number and unitary complex matrices such that, writing
one has and , and every positive semidefinite matrix of trace one satisfies
Furthermore, for every unit vector , define
and
Then every and is positive semidefinite, their sum is , and
Here , the overline is entrywise conjugation, is transpose, is conjugate transpose, and is the positive semidefinite order. The same family works for every and every ; the assertion includes and .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.