Execution semantics of orientation-aware boundary bisection
ProvedQuantumLTF.Membership.boundaryBisect_runlearning-theoryquantum-computing
Running the orientation-aware bisection query tree against a linear-threshold membership oracle has exactly the scalar recursive semantics of binary search for the boundary height. The orientation is the sign of the nonzero directional inner product.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_boundarySearchTree import Definitions.Def_QuantumLTF_Membership_orientedBisectValue import Definitions.Def_QuantumLTF_Membership_ltf import Definitions.Def_QuantumLTF_Membership_height
Formal statement
theorem QuantumLTF.Membership.boundaryBisect_run {n : ℕ}
(w p : EuclideanSpace ℝ (Fin n)) (θ : ℝ) (q : ℕ) (lo hi : ℝ)
(ha : inner ℝ w p ≠ 0) :
(boundaryBisect p (sgn (inner ℝ w p)) q lo hi).run (ltf w θ) =
orientedBisectValue (sgn (inner ℝ w p)) q lo hi (height w θ p 0) := by sorrySource
Supporting lemma for Theorem 3.1 of Fast Quantum Algorithms for Learning Linear Threshold Functions