Theorem 3.3 (corrected) — hybrid bound for modified oracle answers
ProvedBBBV.RandomPermutation.theorem_3_3Run a -query unitary algorithm with a baseline oracle answer function at each step . Let be a finite set of step-string pairs and let agree with outside . If and the sum of the baseline query magnitudes obeys
then the two final states differ in norm by at most . Here is the baseline state before step .
This hybrid estimate controls the effect of changing a small collection of query answers.
Formalization Note The baseline may vary by step because the proof of Theorem 3.6 uses a hybrid run. The paper prints as the final bound; the correct bound is . Already for one query with all magnitude on the modified string, changing an XOR answer can move the final state by while . At the sum is empty, the two runs coincide, and Lean's convention causes no change in meaning.
import Mathlib import Definitions.Def_BBBV_RandomPermutation_QueryModel
namespace BBBV.RandomPermutation
theorem theorem_3_3 {X R W : Type} [Fintype X] [Fintype R] [Fintype W]
[AddCommGroup R] {T : ℕ} (M : QueryAlg X R W T)
(g₀ g₁ : Fin T → X → R) (F : Finset (Fin T × X))
(hF₀ : ∀ i y, (i, y) ∉ F → g₁ i y = g₀ i y)
(ε : ℝ) (hε : 0 < ε)
(hF : (∑ p ∈ F, queryMag p.2 (state M g₀ p.1)) ≤ ε ^ 2 / (T : ℝ)) :
‖final M g₀ - final M g₁‖ ≤ 2 * ε := by sorry
end BBBV.RandomPermutation
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.