Logarithmic parameters for localized bisection
ProvedQuantumLTF.Membership.local_bisection_parameterslearning-theoryquantum-computingreal-analysis
For every target error below one eighth, a bisection count q can be chosen logarithmically in 1/η so that the localized binary-search error 2^(-q-2) is at most η.
Preamble
import Mathlib
Formal statement
theorem QuantumLTF.Membership.local_bisection_parameters :
∃ C : ℝ, 0 < C ∧ ∀ η : ℝ, 0 < η → η < 1 / 8 →
∃ q : ℕ, ((q : ℕ) : ℝ) ≤ C * Real.log (1 / η) ∧
1 / (2 : ℝ) ^ (q + 2) ≤ η := by sorrySource
Query-count selection in Theorem 3.2 of Fast Quantum Algorithms for Learning Linear Threshold Functions