Error bound for affine-line boundary bisection
ProvedQuantumLTF.Membership.affineBoundaryBisect_errorlearning-theoryquantum-computing
If the boundary height at x lies in the initial interval, affine-line binary search returns an estimate whose error is at most the interval width divided by 2^(q+1).
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_affineBoundaryBisect import Definitions.Def_QuantumLTF_Membership_ltf import Definitions.Def_QuantumLTF_Membership_height
Formal statement
theorem QuantumLTF.Membership.affineBoundaryBisect_error {n : ℕ}
(w p x : EuclideanSpace ℝ (Fin n)) (θ : ℝ) (q : ℕ) (lo hi : ℝ)
(ha : inner ℝ w p ≠ 0)
(hlo : lo ≤ height w θ p x) (hhi : height w θ p x ≤ hi) :
|(affineBoundaryBisect p x (sgn (inner ℝ w p)) q lo hi).run (ltf w θ) -
height w θ p x| ≤ (hi - lo) / (2 : ℝ) ^ (q + 1) := by sorrySource
Coherent boundary-search accuracy used in Theorem 3.2 of Fast Quantum Algorithms for Learning Linear Threshold Functions