Execution semantics of affine-line boundary bisection
ProvedQuantumLTF.Membership.affineBoundaryBisect_runlearning-theoryquantum-computing
Running affine-line orientation-aware bisection against the membership oracle has exactly the scalar binary-search semantics for the boundary height at the chosen grid point x.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_affineBoundaryBisect import Definitions.Def_QuantumLTF_Membership_orientedBisectValue import Definitions.Def_QuantumLTF_Membership_ltf import Definitions.Def_QuantumLTF_Membership_height
Formal statement
theorem QuantumLTF.Membership.affineBoundaryBisect_run {n : ℕ}
(w p x : EuclideanSpace ℝ (Fin n)) (θ : ℝ) (q : ℕ) (lo hi : ℝ)
(ha : inner ℝ w p ≠ 0) :
(affineBoundaryBisect p x (sgn (inner ℝ w p)) q lo hi).run (ltf w θ) =
orientedBisectValue (sgn (inner ℝ w p)) q lo hi (height w θ p x) := by sorrySource
Coherent boundary-search component of Theorem 3.2 in Fast Quantum Algorithms for Learning Linear Threshold Functions