Optimal Quantum-Classical Separations for Exact Learning

Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande

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…