Uniform accuracy and logarithmic depth of localized affine bisection
ProvedQuantumLTF.Membership.localizedAffineBisect_uniform_accuracylearning-theorylinear-threshold-functionsquantum-algorithmssection-3
There is a universal constant such that localized affine bisection simultaneously approximates the height function at every point of the dyadic grid to additive error , using a depth . The hypotheses are precisely the localization conditions used in Theorem 3.2: , , a unit normal , a reference point satisfying , and an initial height estimate within .
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic import Definitions.Def_QuantumLTF_Membership_affineBoundaryBisect import Definitions.Def_QuantumLTF_Membership_ltf import Definitions.Def_QuantumLTF_Membership_height import Definitions.Def_QuantumLTF_Membership_rho import Definitions.Def_QuantumLTF_Membership_gridVec import Theorems.Thm_QuantumLTF_Membership_localizedAffineBisect_error import Theorems.Thm_QuantumLTF_Membership_local_bisection_parameters
Formal statement
namespace QuantumLTF.Membership
open QAlgorithms
theorem localizedAffineBisect_uniform_accuracy :
∃ C : ℝ, 0 < C ∧ ∀ {n b : ℕ}, 2 ≤ n → ∀ ε η : ℝ,
0 < ε → ε ≤ 1 / 2 → 0 < η → η < 1 / 8 →
∀ (w p : EuclideanSpace ℝ (Fin n)) (θ htil : ℝ),
‖w‖ = 1 → 1 / 10 ≤ |inner ℝ w p| →
|htil - height w θ p 0| ≤ ε / 100 →
∃ q : ℕ, (q : ℝ) ≤ C * Real.log (1 / η) ∧
∀ x : Fin n → Qubits b,
|(affineBoundaryBisect p (rho n • gridVec n b x) (sgn (inner ℝ w p)) q
(htil - 1 / 4) (htil + 1 / 4)).run (ltf w θ) -
height w θ p (rho n • gridVec n b x)| ≤ η := by sorry
end QuantumLTF.MembershipSource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, arXiv:2609.40331, Theorem 3.2, pp. 23–26 (PDF pp. 24–27), localized bisection accuracy and query-depth analysis.