arXiv:2609.38073
Optimal Quantum-Classical Separations for Exact Learning
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.
AI Summary
The paper asks how much quantum membership queries can reduce the cost of exactly identifying an unknown concept in $\mathcal C\subseteq\{0,1\}^N$. It constructs families attaining the known general classical-simulation bounds, refuting the conjecture $\mathsf R(\mathcal C)=O(\mathsf Q(\mathcal C)^2+\mathsf Q(\mathcal C)\log N)$. The randomized separation has $\mathsf Q=\Theta(t)$, $\mathsf R=\Omega(t^3)$, and $N=\Theta(t^{14})$, attaining $\mathsf R=\Omega(\mathsf Q^3\log N/\log\mathsf Q)$. Its Boolean oracle hides truncated polynomial values at unique marked addresses, with values constant along lines of an unknown slope. Coherent Grover search and Fourier sampling recover the slope; a slope-indexed auxiliary “cheat sheet” then allows recovery of the polynomial coefficients. The classical lower bound uses Yao’s principle and hybrids replacing polynomial values by random-function values and then independent block labels. A supporting lemma bounds how well adaptive equality queries distinguish limited independence from full randomness. A separate construction hides a bilinear form in one of $q^2$ blocks, giving $\mathsf Q=\Theta(q)$, $\mathsf D=\Omega(q^4)$, and $\log N=\Theta(q)$, attaining $\mathsf D=\Omega(\mathsf Q^3\log N)$. Grover search and Bernstein–Vazirani give the quantum algorithm; linear constraints give the deterministic lower bound. This construction does not yield the randomized separation: randomness reduces its classical cost to $O(q^2)$. Additional results show that every concept class has a Boolean decision matching its quantum identification complexity up to constants, and relate fractional teaching and splitting parameters to query complexity. The tight randomized example occupies the regime $\log N=\Theta(\log\mathsf Q)$; the bounds concern query complexity.
We used GPT-5.6 in the process of discovering most of our results, but notably the construction underlying our separation
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.