Optimal Quantum-Classical Separations for Exact Learning

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.