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 $\mathcal{E}$. Our figure of merit is the number of runs of $\mathcal{E}$ 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 $\mathcal{E}$, and quantum ML models that can access $\mathcal{E}$ 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 $\mathcal{D}(x)$, a classical ML model can provide accurate predictions on average by accessing $\mathcal{E}$ 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^{\mathrm{\Omega }(n)}$ copies of $\rho$, but we present a quantum ML model using only $\mathcal{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.

Figure 1

Illustration of classical and quantum machine learning settings. The goal is to learn about an unknown CPTP map $\mathcal{E}$ by performing physical experiments. Left panel: in the learning phase of the classical ML setting, a measurement is performed after each query to $\mathcal{E}$; the classical measurement outcomes collected during the learning phase are consulted during the prediction phase. Right panel: in the learning phase of the quantum ML setting, multiple queries to $\mathcal{E}$ may be included in a single coherent quantum circuit, yielding an output state stored in a quantum memory; this stored quantum state is consulted during the prediction phase.

Figure 2

Sample complexity for predicting expectations of all $4^n$ Pauli observables (worst-case prediction error) in an $n$-qubit quantum state. “Upper bound” is the achievable sample complexity of a specific algorithm. “Lower bound” is the lower bound for any algorithm. The classical ML upper bound can be achieved using classical shadows based on random Clifford measurements [29]. The rest of the bounds are obtained in the Supplemental Material, App. E [39].

Figure 3

Numerical experiments—number of copies of an unknown $n$-qubit state needed for predicting expectation values of all $4^n$ Pauli observables, with a constant worst-case prediction error. Mixed states: quantum states of the form $(I+P)/2^n$, where $P$ is an $n$-qubit Pauli observable. Product states: tensor products of single-qubit stabilizer states.