Skip to Content

Predictive Quantum Learning


Abstract:

We give the first unconditional separation of quantum and classical learning.  We demonstrate a relational concept class that is efficiently learnable in a quantum predictive analogue of PAC, while in any reasonable classical model exponential amount of training data would be required.  We show that our separation is the best possible in several ways, in particular there is no analogous result for a functional class, as well as for several weaker versions of quantum learning.