Search papers, labs, and topics across Lattice.
This paper investigates the distinction between quantum and classical examples within the PAC learning framework, focusing on two quantum algorithms鈥攐ne utilizing quantum examples and the other classical examples. The authors establish that there exist specific distributions that a quantum learner can efficiently generate using quantum examples, which cannot be replicated by a quantum learner limited to classical examples. This finding advances the understanding of the capabilities of quantum learning models and highlights the inherent advantages of quantum examples in certain learning scenarios.
Quantum learners can efficiently generate distributions that classical examples cannot touch, revealing a significant oracle separation in PAC learning.
We study the power of quantum examples, as compared to classical examples, in the PAC learning framework. Here, we have two learning algorithms, both with access to quantum computation, but one gets quantum examples, whereas the other gets classical examples. It was previously unknown whether there were learning tasks that can be efficiently performed but not by the latter. Our primary result is to show that relative to an oracle, there are distributions that can be efficiently generated by a quantum learner with access to quantum examples, but not by a quantum learner with access to only classical examples, making progress to answering this question in the affirmative.
