The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)
It provides a comprehensive overview for researchers in quantum machine learning, identifying gaps and challenges in the field, but is incremental as it synthesizes existing work rather than introducing new methods.
This survey consolidates known results in quantum learning theory for classical concepts under the PAC framework, highlighting separations in query, sample, and time complexity between classical and quantum learning, and presents 23 open problems to outline current limitations.
This paper surveys various results in the field of Quantum Learning theory, specifically focusing on learning quantum-encoded classical concepts in the Probably Approximately Correct (PAC) framework. The cornerstone of this work is the emphasis on query, sample, and time complexity separations between classical and quantum learning that emerge under learning with query access to different labeling oracles. This paper aims to consolidate all known results in the area under the above umbrella and underscore the limits of our understanding by leaving the reader with 23 open problems.