Scaled-grid heights stay near the estimated offset
ProvedQuantumLTF.Membership.height_grid_localizationlearning-theoryquantum-computing
Under the reference-direction event and an ε/100 estimate of the offset, every boundary height on the scaled centered grid lies within one quarter of that estimate.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic import Definitions.Def_QuantumLTF_Membership_height import Definitions.Def_QuantumLTF_Membership_rho import Definitions.Def_QuantumLTF_Membership_gridVec open QAlgorithms
Formal statement
theorem QuantumLTF.Membership.height_grid_localization {n b : ℕ}
(hn : 2 ≤ n) (ε : ℝ) (hε : 0 < ε) (hε2 : ε ≤ 1 / 2)
(w p : EuclideanSpace ℝ (Fin n)) (θ htil : ℝ)
(hw : ‖w‖ = 1) (ha : 1 / 10 ≤ |inner ℝ w p|)
(hhtil : |htil - height w θ p 0| ≤ ε / 100)
(x : Fin n → Qubits b) :
|height w θ p (rho n • gridVec n b x) - htil| ≤ 1 / 4 := by sorrySource
Search-interval localization in the proof of Theorem 3.2 of Fast Quantum Algorithms for Learning Linear Threshold Functions