Quantum Predictive Learning and Communication Complexity with Single Input

Understand

We define a new model of quantum learning that we call Predictive Quantum (PQ).

• This is a quantum analogue of PAC, where during the testing phase the student is only required to answer a polynomial number of testing queries.
• We demonstrate a relational concept class that is efficiently learnable in PQ, while in any "reasonable" classical model exponential amount of training data would be required.
• This is the first unconditional separation between quantum and classical learning.