Theorem 3.5, p. 8 — a quantum algorithm with T ≤ c·2^{n/2} queries fails on ≥ 1/8 of the oracles to decide whether 1ⁿ has a preimage
ProvedBBBV.RandomOracle.theorem_3_5There are a constant and a threshold such that the following holds for every . Let be any quantum algorithm (with any finite workspace) that makes queries to an oracle . Choose uniformly at random among all such functions. Then
where "decide" means: accept with probability at least if has a preimage, and at most if it does not.
This is the finite core of the paper's Theorem 3.5, "for any which is , relative to a random oracle, with probability , does not contain ": the language is in , and the theorem shows that no bounded-error quantum algorithm recognises it on input with queries. Grover's algorithm shows that queries suffice, so the bound is tight up to the constant.
Formalization Note The statement is in the query model (see the definitions file): every oracle QTM running steps is a -query algorithm, oracle answers on lengths other than are fixed and absorbed into the unitaries (the page proves the bound "for every way of fixing the oracle answers on inputs of length not equal to "), and the input is absorbed into the initial state. Queries return the full value ; since one Boolean query is simulated by two full-value queries, the statement implies the bound for the paper's Boolean oracle with halved. The constant is existential: the page picks , but with the paper's own count ( strings from Corollary 3.4 at ) that choice gives and the step fails; with the corrected Corollary 3.4 ( strings) the argument works for . The hypothesis of the theorem is exactly "below for some eventually". The closing step of the paper — a probability- statement over countably many machines and all — is not formalized. The constant and the threshold do not depend on the workspace or on the algorithm.
import Mathlib import Definitions.Def_BBBV_RandomOracle_QueryModel
namespace BBBV.RandomOracle
open Classical in
theorem theorem_3_5 :
∃ c : ℝ, 0 < c ∧ ∃ N : ℕ, ∀ n : ℕ, N ≤ n →
∀ (W : Type) [Fintype W] [DecidableEq W] (T : ℕ), (T : ℝ) ≤ c * Real.sqrt (2 ^ n) →
∀ M : QueryAlg (Str n) (Str n) W T,
(1 / 8 : ℝ) ≤
((Finset.univ.filter fun A : Str n → Str n =>
¬ Decides M (fun _ => A) (∃ x, A x = ones n)).card : ℝ) /
(Fintype.card (Str n → Str n) : ℝ) := by sorry
end BBBV.RandomOracle
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.