Proof of Theorem 3.6 — consecutive language memberships differ with probability 1/2
ProvedBBBV.RandomPermutation.prob_membership_differsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrandom-permutation
For and , compare the languages associated with and at the string . Exactly one language contains precisely when the first bits of their two inverse images differ. Under the chain's uniform sample law,
This is the membership split used to turn closeness of algorithmic states into a failure bound.
Formalization Note The first bit requires and the preceding permutation requires .
Preamble
import Mathlib import Definitions.Def_BBBV_RandomPermutation_Chain
Formal statement
namespace BBBV.RandomPermutation
theorem prob_membership_differs {n T : ℕ} (hn : 0 < n) (hT : 1 ≤ T) :
((Finset.univ.filter fun ω : Ω n T =>
(firstBit hn ((piChain ω T).symm (BBBV.RandomOracle.ones n)) = 1) ↔
¬ (firstBit hn ((piChain ω (T - 1)).symm (BBBV.RandomOracle.ones n)) = 1)).card : ℝ) /
(Fintype.card (Ω n T) : ℝ) = 1 / 2 := by sorry
end BBBV.RandomPermutation
Source
Bennett, Bernstein, Brassard and Vazirani, Strengths and weaknesses of quantum computing, arXiv:quant-ph/9701001v1, p. 11, proof of Theorem 3.6, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.