Optimal Quantum-Classical Separations for Exact Learning

Abstract

We study exact learning with membership queries for concept classes 𝒞⊆{0,1}^N, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted D(𝒞), R(𝒞), and Q(𝒞), respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture R(𝒞)=O(Q(𝒞)²+Q(𝒞)log N). We first refute this conjecture by constructing concept classes 𝒞 and 𝒞' satisfying R(𝒞)=Ω ((Q(𝒞)³log N)/(log Q(𝒞))) and D(𝒞')=Ω(Q(𝒞')³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.

Improved Separations between Quantum and Classical Communication Complexity of Total Functions
François Le Gall
arXiv5 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
Andris Ambainis, Jānis Iraids, Martins Kokainis
arXiv5 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Exponential quantum-classical query separations for cyclic Forrelation
Yuxin Zhang, Changpeng Shao
arXiv30 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Exact diffusion coefficients for quantum--classical hybrid walks
Cook Hyun Kim, Jaesub Park, Namshik Han
arXiv20 Sep 2026PreprintCC BY 4.0Full textQuantum physics & quantum information Statistical & nonlinear physicsarXiv
QRecoupling.jl: numerical and exact computation of classical and quantum recoupling coefficients
Seth K. Asante
arXiv16 Oct 2026PreprintarXiv licenceFull textMathematical physics Computational physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{arunachalam2026optimal,
  title = {{Optimal Quantum-Classical Separations for Exact Learning}},
  author = {Srinivasan Arunachalam and Amin Shiraz Gilani and Nikhil S. Mande},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38073},
  eprint = {2609.38073},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38073},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Optimal Quantum-Classical Separations for Exact Learning
AU  - Srinivasan Arunachalam
AU  - Amin Shiraz Gilani
AU  - Nikhil S. Mande
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.38073
UR  - https://arxiv.org/abs/2609.38073
AB  - We study exact learning with membership queries for concept classes 𝒞⊆{0,1}^N, focusing on the relationships among their deterministic, randomized, and quantum query complexities, denoted D(𝒞), R(𝒞), and Q(𝒞), respectively. The two canonical quantum speedups in this model are witnessed by Grover search and Bernstein-Vazirani, leading to the longstanding conjecture R(𝒞)=O(Q(𝒞)^2+Q(𝒞)log N). We first refute this conjecture by constructing concept classes 𝒞 and 𝒞' satisfying R(𝒞)=Ω ((Q(𝒞)^3log N)/(log Q(𝒞))) and D(𝒞')=Ω(Q(𝒞')^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.
ER  -

Abstract

Related

Cite