Theorem 1.4 (companion theorem) — with
OpenExactLearningSeparation678.Randomized.Supplement.theorem_1_4machine-learningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexity
Let () be the bilinear hidden-block classes of Definition 2.1 on the domain , of size . Then , and there are an absolute and a threshold such that
Here is the deterministic and the bounded-error quantum membership-query complexity of exactly learning the class. Divergence means that for every bound all sufficiently large have .
This family witnesses the existence statement of Theorem 1.4, and it matches the Servedio–Gortler simulation , so that simulation is optimal.
Formalization Note The true coordinate count appears inside the logarithm (natural). The constant and the threshold precede .
Differences from the source:
- encoding: there exists C ⊆ {0,1}^N with Q(C) = ω(1) and D(C) = Ω(Q(C)³ log N) → the explicit Definition 2.1 family C_q (q ≥ 2) with its true domain cardinality q²·2^(2q), Q(C_q) → ∞, and one c > 0 and one threshold for all later q; reason: the proof supplies this witness family; the explicit quantifiers retain the entire existential asymptotic conclusion
- encoding: [q²], F₂^q, and Boolean values xᵀAy → Fin (q^2), Fin q → ZMod 2, and decide (b′ = b ∧ x ⬝ᵥ A y = 1); reason: a relabeling of the same domain and concepts
- encoding: logarithms of unspecified base → natural logarithm Real.log; reason: a change of base is absorbed into the absolute constant
- encoding: D(C): deterministic learner identifying the target with certainty → least worst-case depth of a DecisionTree whose output equals c for every c ∈ C; reason: the published deterministic decision-tree model
Preamble
import Definitions.Def_ExactLearningSeparation678_Randomized_Supplement_Models open Classical set_option autoImplicit false
Formal statement
namespace ExactLearningSeparation678.Randomized.Supplement
open QAlgorithms.Learning
/-- Theorem 1.4, p.3 (repeated p.14), for the witness family `C_q` of Definition 2.1, `q ≥ 2`:
the true domain size is `N_q = q²·2^{2q}`, `Q(C_q) → ∞`, and one absolute `c > 0` and one
threshold give `D(C_q) ≥ c · Q(C_q)³ · log N_q` for every later `q`. Natural logarithm. -/
theorem theorem_1_4 :
(∀ q : ℕ, 2 ≤ q → Fintype.card (BilinDomain q) = q ^ 2 * 2 ^ (2 * q)) ∧
(∀ B : ℕ, ∃ M : ℕ, ∀ q : ℕ, 2 ≤ q → M ≤ q →
B ≤ quantumExactComplexity (bilinClass q)) ∧
(∃ c : ℝ, 0 < c ∧ ∃ q₀ : ℕ, ∀ q : ℕ, 2 ≤ q → q₀ ≤ q →
c * (quantumExactComplexity (bilinClass q) : ℝ) ^ 3 *
Real.log (Fintype.card (BilinDomain q) : ℝ) ≤
(detExactComplexity (bilinClass q) : ℝ)) := by sorry
end ExactLearningSeparation678.Randomized.Supplement
Source
Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande, STOC 2027 submission #678 (October 2026), Theorem 1.4, p.3; Definition 2.1, p.13; §§2.2–2.4, pp.13–14; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/678.pdf