The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)

Abstract

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.

This survey examines when quantum access to classical concepts changes the query, sample, or computational complexity of PAC learning. It organizes results by labeling-oracle model: classical and quantum examples, noisy and agnostic examples, and membership queries. Its scope excludes learning quantum states, channels, and processes, and largely excludes learning frameworks other than PAC. The central sample-complexity result surveyed is that distribution-free classical and quantum learning agree up to constant factors: for VC dimension $d$, realizable learning requires $\Theta((d+\log(1/\delta))/\varepsilon)$ examples, and agnostic learning requires $\Theta((d+\log(1/\delta))/\varepsilon^2)$. The survey describes state-identification, Fourier-analytic, and information-theoretic proofs. It contrasts these bounds with coherent access to example-preparation unitaries and their inverses, where a surveyed realizable-learning upper bound is $\widetilde O((d+\log(1/\delta))/\sqrt{\varepsilon})$. For computational separations, it reviews factoring- and discrete-log-based constructions, learning with errors and noisy parities, and algorithms or hardness results for decision trees, DNFs, juntas, halfspaces, and shallow circuits. Fourier sampling and boosting are recurring techniques. The discussion emphasizes that efficient quantum algorithms for noisy linear problems assume stronger input access than ordinary classical samples. Additional material introduces HSP-induced concept classes and an approximate membership-oracle simulation criterion. A state-distinguishability argument gives exponential example requirements for function pairs differing on an exponentially small domain fraction. The paper lists 23 open problems, including nonuniform marginals, agnostic learning, multiclass labels, generalized example oracles, and access without inverse preparation operations. Most results presented are existing results rather than new learning algorithms.