Proof of Theorem 3.6 — expected distance between consecutive oracle runs
ProvedBBBV.RandomPermutation.expected_dist_lelower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexityrandom-permutation
Let and . Run the same -query algorithm with the fixed permutation oracle and with , respectively. Averaged over the paper's random transposition chain, the final states satisfy
This quantitative state bound is the immediate input to the final bounded-error argument.
Formalization Note makes a genuine preceding oracle. No lower bound on is needed for this statement; when the query bound forces , its hypotheses cannot hold. The constant remains valid with the corrected factor in Theorem 3.3.
Preamble
import Mathlib import Definitions.Def_BBBV_RandomPermutation_Chain
Formal statement
namespace BBBV.RandomPermutation
theorem expected_dist_le {n T : ℕ} {W : Type} [Fintype W]
(M : QueryAlg (BBBV.RandomOracle.Str n) (BBBV.RandomOracle.Str n) W T) (hT1 : 1 ≤ T)
(hT : (T : ℝ) ≤ (2 : ℝ) ^ ((n : ℝ) / 3) / 100) :
avg (fun ω : Ω n T =>
‖final M (fun _ => ⇑(piChain ω T)) -
final M (fun _ => ⇑(piChain ω (T - 1)))‖) ≤ 1 / 50 := 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, expected-distance claim and final inequality
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.