A Quantum/Classical Example Oracle Separation for Making Things Up

Within computational learning theory, a central question is understanding the relative power of quantum computers compared to classical computers. While prior research established that quantum computers can achieve algorithmic speedups in learning, it remained unclear whether having access to quantum examples (superposition samples) provides a strict advantage over having only classical examples (computational basis samples) when both algorithms possess quantum computing capabilities. This paper investigates whether quantum examples are strictly more powerful than classical examples for PAC learning and distribution generation.

To study this separation, the author examines the PAC learning and PAC generation frameworks relative to oracles. First, the paper investigates the relationship between function hardness and distributional hardness, showing that under cryptographic assumptions, a concept class can be hard to PAC learn while its induced distribution class is efficiently PAC generated. Second, to prove the core separation between quantum and classical examples, the paper leverages Simon's hidden period finding algorithm and the probabilistic method over a random function oracle. The author constructs a distribution class where a quantum learner with quantum examples can efficiently recover a hidden period and generate the distribution, whereas a quantum learner restricted to classical examples requires an exponential number of samples and fails.

First, the paper demonstrates that relative to a one-way permutation oracle, there exists a function class that cannot be efficiently learned, yet its induced distribution class can be efficiently generated. This indicates that function hardness does not automatically imply distributional hardness in this setting. Second, and most importantly, the paper proves that relative to an auxiliary random function oracle, a distribution class can be efficiently PAC generated by a quantum learner with quantum examples, but cannot be efficiently generated by any quantum learner restricted to classical examples. This establishes the first explicit separation showing that quantum examples are strictly more powerful than classical examples in the learning setting.