Quantum learning can outperform classical methods by more than expected
Optimal Quantum-Classical Separations for Exact Learning
Computational ComplexityMachine Learning
Summary
This paper looks at how well computers can learn exactly with questions, comparing classical and quantum methods. The authors show that quantum approaches can be much faster than previously thought, breaking an old assumption about how their speeds relate. They build specific examples where quantum learning beats classical learning by a larger margin than the known methods based on famous quantum algorithms. This means quantum learning can be more powerful and diverse than just simple search or pattern-finding tasks.
What this means in practice
- •For quantum algorithm developers: Design quantum learning algorithms by exploring beyond traditional Grover and Bernstein-Vazirani approaches for better performance.
- •For machine learning engineers: Assess limits of classical versus quantum query strategies to inform when quantum methods might offer significant learning speed advantages.
A theory result. No direct application yet.
Authors
Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande
Abstract
We study exact learning with membership queries for concept classes $\mathcal C\subseteq\{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)=Ω\!\left(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)}\right) \qquad\text{and}\qquad \mathsf{D}(\mathcal C')=Ω(\mathsf{Q}(\mathcal C')^3\log 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.