Depth of the strict boundary-search tree
ProvedQuantumLTF.Membership.boundarySearchTreeStrict_depthlearning-theoryquantum-computing
The corrected boundary-search tree uses exactly two orientation queries followed by bisection queries, so every root-to-leaf path has depth .
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_boundarySearchTreeStrict
Formal statement
theorem QuantumLTF.Membership.boundarySearchTreeStrict_depth {n : ℕ}
(p : EuclideanSpace ℝ (Fin n)) (L : ℝ) (q : ℕ) :
(boundarySearchTreeStrict p L q).depth = q + 2 := by sorrySource
Supporting lemma for Theorem 3.1 of Fast Quantum Algorithms for Learning Linear Threshold Functions