Theorem 3.1, p. 7 — unit vectors within Euclidean distance ε give measurement distributions within total variation 4ε
ProvedBBBV.RandomOracle.theorem_3_1measurementp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationtotal-variation
Let be a finite set and let be unit vectors, , with Euclidean distance . Measuring in the computational basis gives the outcome with probability , and likewise for . Then the total variation distance between the two outcome distributions satisfies
The theorem converts a bound on the distance between two superpositions into a bound on the difference of any observable probability, in particular of acceptance probabilities; it is the step from the hybrid argument (Theorem 3.3) to a statement about what an algorithm outputs.
Formalization Note The total variation distance is the paper's footnote 7, , without the factor . The constant is the paper's; it is not sharp.
Preamble
import Mathlib
Formal statement
namespace BBBV.RandomOracle
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.RandomOracle
Source
Bennett, Bernstein, Brassard and Vazirani, Strengths and weaknesses of quantum computing, arXiv:quant-ph/9701001v1, p. 7, Theorem 3.1 and footnotes 6–7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.