Running a mapped query tree
ProvedQuantumLTF.Membership.QueryTree_run_mapdecision-treeslearning-theory
Replacing every leaf output of a deterministic membership-query tree by does not alter the queries or branches. Running the mapped tree returns applied to the output of the original tree.
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_boundarySearchTree
Formal statement
namespace QuantumLTF.Membership
/-- Mapping every leaf output commutes with running a query tree. -/
theorem QueryTree_run_map {n : ℕ} {α β : Type} (g : α → β)
(T : QueryTree n α) (f : EuclideanSpace ℝ (Fin n) → ℤ) :
(T.map g).run f = g (T.run f) := by sorry
end QuantumLTF.MembershipSource
Structural property of the QueryTree implementation used for Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, Theorem 3.1.