Lemma 5.5 — disagreement under a one-coordinate perturbation
OpenQuantumLTF.Example.lemma_5_5gaussian-analysislinear-threshold-functionslower-boundssection-5
For the hard family of homogeneous halfspaces indexed by , flipping one coordinate changes the target on Gaussian measure at most
Preamble
import Mathlib import Definitions.Def_QuantumLTF_Membership_ltf import Definitions.Def_QuantumLTF_Membership_disagree import Definitions.Def_QuantumLTF_Example_LowerModel
Formal statement
namespace QuantumLTF.Example
open QuantumLTF.Membership
theorem lemma_5_5 :
∀ m : ℕ, 1 ≤ m → ∀ ε : ℝ, 0 < ε → ε ≤ 1 / (8 * Real.pi) →
∀ z : SignString m, ∀ i : Fin m,
disagree (ltf (hardWeight m ε z) 0)
(ltf (hardWeight m ε (Function.update z i (!(z i)))) 0) ≤
4 * Real.pi * ε / Real.sqrt m := by sorry
end QuantumLTF.ExampleSource
Krivcenko, Nguyen, de Wolf, Fast Quantum Algorithms for Learning Linear Threshold Functions, STOC 2027 submission #347, Lemma 5.5, p. 76 (PDF p. 77).