Uniform dyadic grid window probability
ProvedQuantumLTF.Membership.uniform_dyadic_windowlearning-theoryprobability
In every dimension at least two, a uniform signed dyadic grid with at most four plus the base-two logarithmic ceiling bits per coordinate has inner-product magnitude between 1/10 and 3 with probability at least 4/5 in every fixed unit direction.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic import Definitions.Def_QuantumLTF_Membership_addrOf open QAlgorithms
Formal statement
theorem QuantumLTF.Membership.uniform_dyadic_window (n : ℕ) (hn : 2 ≤ n) :
∃ ℓ f : ℕ, f ≤ ℓ ∧ ℓ ≤ 4 + ⌈Real.logb 2 n⌉₊ ∧
∀ w : EuclideanSpace ℝ (Fin n), ‖w‖ = 1 →
((PMF.uniformOfFintype (Qubits (n * ℓ))).toOuterMeasure
{z | 1 / 10 ≤ |inner ℝ w (addrOf n ℓ f z)| ∧
|inner ℝ w (addrOf n ℓ f z)| ≤ 3}).toReal ≥ 4 / 5 := by sorrySource
Small-ball and tail estimate underlying Lemma 3.1 of Fast Quantum Algorithms for Learning Linear Threshold Functions