Proof of Theorem 3.6 — expected query magnitude of a later sampled string
ProvedBBBV.RandomPermutation.expected_queryMag_lep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexityquery-magnituderandom-permutation
In the hybrid computation, let be the state before query step . If , then the string sampled by the chain has expected query magnitude at most the reciprocal of the number of length- binary strings:
This bound applies to the random string , including , and is the independence estimate needed for the hybrid comparison.
Formalization Note Expectation is a finite average over the explicit chain sample space. At , the initial state is fixed and is uniform.
Preamble
import Mathlib import Definitions.Def_BBBV_RandomPermutation_Chain
Formal statement
namespace BBBV.RandomPermutation
theorem expected_queryMag_le {n T : ℕ} {W : Type} [Fintype W]
(M : QueryAlg (BBBV.RandomOracle.Str n) (BBBV.RandomOracle.Str n) W T) (i : Fin T) (j : ℕ)
(hij : (i : ℕ) ≤ j) (hj : j ≤ T + 1) :
avg (fun ω : Ω n T => queryMag (x ω j) (state M (hybrid ω) i)) ≤
1 / (2 : ℝ) ^ n := 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, paragraph beginning 'We claim'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.