# Optimal Quantum-Classical Separations for Exact Learning

arXiv: https://arxiv.org/abs/2609.38073 · HTML: https://mlsanity.com/paper/2609.38073/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 31 references that are in the map.
- First posted on arXiv 29 Sep 2026.

## Builds on (most cited first, 7 of 7)

- [Point Location and Active Learning: Learning Halfspaces Almost Optimally](https://mlsanity.com/paper/2004.11380/) (2020)
- [Two new results about quantum exact learning](https://mlsanity.com/paper/1810.00481/) (2018)
- [Bounds in Query Learning](https://mlsanity.com/paper/1904.10122/) (2019)
- [Exact Learning from an Honest Teacher That Answers Membership Queries](https://mlsanity.com/paper/1706.03935/) (2017)
- [Adaptive Exact Learning of Decision Trees from Membership Queries](https://mlsanity.com/paper/1901.07750/) (2019)
- [On Polynomial time Constructions of Minimum Height Decision Tree](https://mlsanity.com/paper/1802.00233/) (2018)
- [On Exact Learning of d-Monotone Functions](https://mlsanity.com/paper/2502.01265/) (2025)

## Abstract (arXiv)

We study exact learning with membership queries for concept classes mathcal Csubseteq0,1N, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted mathsfD(mathcal C), mathsfR(mathcal C), and mathsfQ(mathcal C), respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture  mathsfR(mathcal C)=O(mathsfQ(mathcal C)2+mathsfQ(mathcal C)log N).  We first refute this conjecture by constructing concept classes mathcal C and mathcal C' satisfying [ mathsfR(mathcal C)=Omega!left(fracmathsfQ(mathcal C)3log Nlog mathsfQ(mathcal C)right) qquadandqquad mathsfD(mathcal C')=Omega(mathsfQ(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.