Research
Optimal Quantum-Classical Separations for Exact Learning
arXiv:2609.38073v1 Announce Type: cross Abstract: We study exact learning with membership queries for concept classes mathcal Csubseteq{0,1}^N, focusing on the relationships among their deterministic,
arXiv:2609.38073v1 Announce Type: cross Abstract: We study exact learning with membership queries for concept classes mathcal Csubseteq{0,1}^N, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted mathsf{D}(mathcal C), mathsf{R}(mathcal C), and mathsf{Q}(mathcal C), respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture $ mathsf{R}(mathcal C)=O(mathsf{Q}(mathcal C)^2+mathsf{Q}(mathcal C)log N). We first refute this conjecture by constructing concept classes mathcal C and mathcal C'$ satisfying [ mathsf{R}(mathcal C)=Omega!left(frac{mathsf{Q}(mathcal C)^3log N}{log mathsf{Q}(mathcal C)}right) qquadext{and}qquad mathsf{D}(mathcal C')=Omega(mathsf{Q}(mathcal C')^3log N). ] The first bound matches the upper bound of Arunachalam et al.[Quantum'21] up to constant factors, while the second matches the upper bound of Servedio and Gortler[SICOMP'04]. In particular, this shows that the saving in the randomized upper bound of Arunachalam et al. fundamentally relies on randomness. Apart from characterizing the optimal relationship between classical and quantum query complexity, our results are the first to show that quantum speedups for learning can go beyond the Grover and Bernstein-Vazirani paradigms.
Related
Source: arXiv cs.LG | 2026-09-30