Affine-line boundary bisection query tree
DefinitionQuantumLTF_Membership_affineBoundaryBisectlearning-theoryquantum-computing
An orientation-aware binary-search query tree whose midpoint queries lie on the affine line x + t p, designed to estimate the boundary height at x coherently.
Definition code
import Mathlib
import Definitions.Def_QuantumLTF_Membership_QueryTree
namespace QuantumLTF.Membership
/-- Orientation-aware bisection for the boundary height along the affine line `x + t • p`. -/
noncomputable def affineBoundaryBisect {n : ℕ}
(p x : EuclideanSpace ℝ (Fin n)) (s : ℤ) :
ℕ → ℝ → ℝ → QueryTree n ℝ
| 0, lo, hi => .leaf ((lo + hi) / 2)
| k + 1, lo, hi =>
let mid := (lo + hi) / 2
.query (x + mid • p) fun ans =>
if s = 1 then
if ans = 1 then affineBoundaryBisect p x s k lo mid
else affineBoundaryBisect p x s k mid hi
else
if ans = 1 then affineBoundaryBisect p x s k mid hi
else affineBoundaryBisect p x s k lo mid
end QuantumLTF.Membership
Source
Coherent height-oracle construction in Theorem 3.2 of Fast Quantum Algorithms for Learning Linear Threshold Functions