Theorem 3.1 — Euclidean distance bounds the distance of observed distributions
ProvedBBBV.RandomPermutation.theorem_3_1p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitytotal-variation
Let and be unit vectors in a finite-dimensional complex Hilbert space with a fixed orthonormal computational basis. If , then the distributions obtained by observing their basis coordinates satisfy
This converts a bound on final quantum states into a bound on measurement outcomes.
Formalization Note Total variation follows the paper's footnote 7: the sum of absolute differences, with no factor .
Preamble
import Mathlib import Definitions.Def_BBBV_RandomPermutation_QueryModel
Formal statement
namespace BBBV.RandomPermutation
theorem theorem_3_1 {ι : Type} [Fintype ι] (u v : EuclideanSpace ℂ ι)
(hu : ‖u‖ = 1) (hv : ‖v‖ = 1) (ε : ℝ) (h : ‖u - v‖ ≤ ε) :
(∑ c : ι, |‖u c‖ ^ 2 - ‖v c‖ ^ 2|) ≤ 4 * ε := by sorry
end BBBV.RandomPermutation
Source
Bennett, Bernstein, Brassard and Vazirani, Strengths and weaknesses of quantum computing, arXiv:quant-ph/9701001v1, p. 7, Theorem 3.1 and footnote 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.