Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors resolve the optimal query complexity separations between classical and quantum exact learning with membership queries, refuting a longstanding conjecture rooted in canonical Grover search and Bernstein-Vazirani speedups. By constructing explicit concept classes, they prove tight lower bounds of $\mathsf{R}(\mathcal C) = \Omega(\frac{\mathsf{Q}(\mathcal C)^3\log N}{\log \mathsf{Q}(\mathcal C)})$ for randomized and $\mathsf{D}(\mathcal C') = \Omega(\mathsf{Q}(\mathcal C')^3\log N)$ for deterministic query complexity, matching known upper bounds up to constant factors. This establishes that randomized learners fundamentally outperform deterministic ones in this setting and proves that quantum learning speedups can strictly surpass standard algorithmic paradigms.
Quantum learning algorithms can achieve cubic separations over classical randomized learners, shattering the longstanding belief that exact learning speedups are constrained by Grover search and Bernstein-Vazirani limits.
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.