Information-Theoretic Bounds on Quantum Advantage in Machine Learning

摘要

We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter x and involve execution of a (possibly unknown) quantum process epsilon. Our figure of merit is the number of runs of epsilon required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of epsilon, and quantum ML models that can access epsilon coherently to acquire quantum data; the classical or quantum data are then used to predict the outcomes of future experiments. We prove that for any input distribution D(x), a classical ML model can provide accurate predictions on average by accessing epsilon a number of times comparable to the optimal quantum ML model. In contrast, for achieving an accurate prediction on all inputs, we prove that the exponential quantum advantage is possible. For example, to predict the expectations of all Pauli observables in an n-qubit system rho, classical ML models require 2(Omega)((n)) copies of rho, but we present a quantum ML model using only O(n) copies. Our results clarify where the quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry.