Quantum versus Classical Learnability

Rocco A. Servedio, Steven J. Gortler

We consider quantum versions of two well-studied classical learning models: Angluin's model of exact learning from membership queries and Valiant's Probably Approximately Correct (…