Uniform dyadic sampler gives a well-conditioned reference direction
ProvedQuantumLTF.Membership.uniform_dyadic_reference_directionlearning-theoryprobability
For each dimension at least two, one can choose a signed dyadic coordinate precision using O(log n) bits so that a uniformly random encoded grid vector has inner product magnitude between 1/10 and 3 with every fixed unit direction with probability at least 4/5.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_Basic import Definitions.Def_QuantumLTF_Membership_addrOf open QAlgorithms
Formal statement
theorem QuantumLTF.Membership.uniform_dyadic_reference_direction :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, 2 ≤ n →
∃ ℓ f : ℕ, f ≤ ℓ ∧ (ℓ : ℝ) ≤ C * Real.log 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
Statistical core of Lemma 3.1 in Fast Quantum Algorithms for Learning Linear Threshold Functions