Advantage of Quantum Machine Learning from General Computational Advantages
This work addresses the problem of establishing quantum supremacy in machine learning for researchers in quantum computing and AI, though it is incremental in extending beyond prior specific algorithmic advantages.
The authors tackled the challenge of demonstrating quantum machine learning (QML) advantages in supervised learning with classical data, constructing a broader family of learning tasks that offer provable QML advantages based on general quantum computational benefits, beyond specific algorithms like Shor's, and proving classical hardness for polynomial-time methods.
An overarching milestone of quantum machine learning (QML) is to demonstrate the advantage of QML over all possible classical learning methods in accelerating a common type of learning task as represented by supervised learning with classical data. However, the provable advantages of QML in supervised learning have been known so far only for the learning tasks designed for using the advantage of specific quantum algorithms, i.e., Shor's algorithms. Here we explicitly construct an unprecedentedly broader family of supervised learning tasks with classical data to offer the provable advantage of QML based on general quantum computational advantages, progressing beyond Shor's algorithms. Our learning task is feasibly achievable by executing a general class of functions that can be computed efficiently in polynomial time for a large fraction of inputs by arbitrary quantum algorithms but not by any classical algorithm. We prove the hardness of achieving this learning task for any possible polynomial-time classical learning method. We also clarify protocols for preparing the classical data to demonstrate this learning task in experiments. These results open routes to exploit a variety of quantum advantages in computing functions for the experimental demonstration of the advantage of QML.