Exact depth of the boundary-search tree
ProvedQuantumLTF.Membership.boundarySearchTree_depthbinary-searchcomplexitylearning-theory
The explicit boundary-search decision tree first makes two endpoint queries to determine the orientation and then follows exactly bisection levels. Its worst-case membership-query depth is therefore .
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_boundarySearchTree
Formal statement
namespace QuantumLTF.Membership
/-- The boundary-search tree uses two orientation queries followed by exactly `q` bisection queries. -/
theorem boundarySearchTree_depth {n : ℕ} (p : EuclideanSpace ℝ (Fin n))
(L : ℝ) (q : ℕ) :
(boundarySearchTree p L q).depth = q + 2 := by sorry
end QuantumLTF.MembershipSource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Theorem 3.1, pp. 21–22 (PDF pp. 22–23).