Proof of Theorem 3.5, p. 9 — the oracles of ℬ on which M fails are at least half the oracles of 𝒜 on which M succeeds
ProvedBBBV.RandomOracle.double_countingcountingdouble-countinglower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be any property of oracles (in the application: " correctly decides whether "). For an oracle and write for with its answer at changed to . Suppose that for every (no preimage of ) with , at least strings have . Then
where is the set of oracles under which has exactly one preimage.
This is the counting step of the proof of Theorem 3.5: each successful oracle of maps to at least failing oracles of , and each oracle of is the image of at most oracles of .
Formalization Note The statement is for an arbitrary property , which is all the counting uses; the hypothesis is the conclusion of the preceding step of the proof (Corollary 3.4 with and the step).
Preamble
import Mathlib import Definitions.Def_BBBV_RandomOracle_QueryModel
Formal statement
namespace BBBV.RandomOracle
open Classical in
theorem double_counting {n : ℕ} (hn : 1 ≤ n) (Good : (Str n → Str n) → Prop)
(h : ∀ A, NoInverse A → Good A →
2 ^ (n - 1) ≤ (Finset.univ.filter fun y => ¬ Good (Function.update A y (ones n))).card) :
(Finset.univ.filter fun A => NoInverse A ∧ Good A).card ≤
2 * (Finset.univ.filter fun B => UniqueInverse B ∧ ¬ Good B).card := by sorry
end BBBV.RandomOracle
Source
Bennett, Bernstein, Brassard and Vazirani, Strengths and weaknesses of quantum computing, arXiv:quant-ph/9701001v1, p. 9, proof of Theorem 3.5, sixth paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.