{"id":"arxiv/2609.38073","url":"https://arxiv.org/abs/2609.38073","tags":["quant-ph","cs.CC","cs.LG"],"score":0,"title":"Optimal Quantum-Classical Separations for Exact Learning","domain":"quant-ph","source":"arxiv","authors":["Srinivasan Arunachalam","Amin Shiraz Gilani","Nikhil S. Mande"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}