Theorem 3.6 — random permutation query lower bound for the first inverse bit
ProvedBBBV.RandomPermutation.theorem_3_6Let , and let be any finite-dimensional quantum query algorithm making queries to a permutation of the length- binary strings. For a permutation , ask whether the first bit of is . If , then
The probability is over all permutations; the algorithm and its finite workspace are fixed before the permutation is sampled. This is the finite-length lower bound in the proof of the paper's almost-sure oracle separation.
Formalization Note The statement uses the query model rather than a full oracle quantum Turing machine. Answers at lengths other than are fixed and absorbed into the inter-query unitaries. The hypothesis makes the first bit defined. The paper's constants and are kept. The almost-sure statement over countably many machines is outside this mission's Lean goal. One full-value oracle query can be simulated by Boolean queries, while one Boolean query can be simulated by two full-value queries, so the lower bound transfers to the paper's Boolean oracle with a constant adjustment.
import Mathlib import Definitions.Def_BBBV_RandomPermutation_Chain
namespace BBBV.RandomPermutation
open Classical
theorem theorem_3_6 (n : ℕ) (hn : 0 < n) (W : Type) [Fintype W] (T : ℕ)
(hT : (T : ℝ) ≤ (2 : ℝ) ^ ((n : ℝ) / 3) / 100)
(M : QueryAlg (BBBV.RandomOracle.Str n) (BBBV.RandomOracle.Str n) W T) :
(1 / 8 : ℝ) ≤
((Finset.univ.filter fun A : Equiv.Perm (BBBV.RandomOracle.Str n) =>
¬ Decides M (fun _ => ⇑A) (firstBit hn (A.symm (BBBV.RandomOracle.ones n)) = 1)).card : ℝ) /
(Fintype.card (Equiv.Perm (BBBV.RandomOracle.Str n)) : ℝ) := by sorry
end BBBV.RandomPermutation
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.