Advantage of Quantum Machine Learning from General Computational
  Advantages
Hayata Yamasaki Natsuto Isogai Mio Murao
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.