Information-theoretic bounds on quantum advantage in machine learning

Hsin-Yuan Huang
Institute for Quantum Information and Matter, Caltech, Pasadena, CA, USA
Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA, USA
Richard Kueng
Institute for Integrated Circuits, Johannes Kepler University Linz, Austria
John Preskill
Institute for Quantum Information and Matter, Caltech, Pasadena, CA, USA
Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA, USA
Walter Burke Institute for Theoretical Physics, Caltech, Pasadena, CA, USA
AWS Center for Quantum Computing, Pasadena, CA, USA

We study the complexity of training classical and quantum machine learning (ML) models for predicting outcomes of physical experiments. The experiments depend on an input parameter $x$ and involve execution of a (possibly unknown) quantum process $\cE$. Our figure of merit is the number of runs of $\cE$ during training, disregarding other measures of runtime. A classical ML model performs a measurement and records the classical outcome after each run of $\cE$, while a quantum ML model can access $\cE$ coherently to acquire quantum data; the classical or quantum data is then used to predict outcomes of future experiments.
We prove that, for any input distribution $\cD(x)$, a classical ML model can provide accurate predictions on average by accessing $\cE$ a number of times comparable to the optimal quantum ML model.
In contrast, for achieving accurate prediction on all inputs, we show that exponential quantum advantage is possible for certain tasks. For example, to predict expectation values of all Pauli observables in an $n$-qubit system $\rho$, we present a quantum ML model using only $\mathcal{O}(n)$ copies of $\rho$ and prove that classical ML models require $2^{\Omega(n)}$ copies.

§ INTRODUCTION

The widespread applications of machine learning (ML) to problems of practical interest have fueled interest in machine learning using quantum platforms [16, 71, 43].  Though many potential applications of quantum ML have been proposed, so far the prospect for quantum advantage in solving purely classical problems remains unclear [76, 75, 36, 7]. On the other hand, it seems plausible that quantum ML can be fruitfully applied to problems faced by quantum scientists, such as characterizing the properties of quantum systems and predicting the outcomes of quantum experiments [24, 78, 25, 35, 62, 73].

Here we focus on an important class of learning problems motivated by quantum mechanics. Namely, we are interested in predicting functions of the form

\begin{equation}
f(x) = \Tr(O \cE(\lvert x \rangle \! \langle x \rvert)),
\label{eq:target-function}
\end{equation}

where $x$ is a classical input, $\cE$ is an arbitrary (possibly unknown) completely positive and trace preserving (CPTP) map, and $O$ is a known observable.
We emphasize that model (<ref>) encompasses any physical process that takes a classical input and produces a real number as output. Therefore, this general setup also includes learning classical functions, such as functions generated by neural networks [37]. It also encompasses many classical ML tasks, such as classification and regression [63].

A particularly important special case of setup (<ref>) is training an ML model to predict what would happen in (quantum) physical experiments [62].
Such experiments might explore, for instance, the outcome of a reaction in quantum chemistry [86], ground state properties of a novel molecule or material [67, 23, 13, 82, 68, 55, 35], or the behavior of neutral atoms in an analog quantum simulator [21, 58, 15]. In these cases, the input $x$ subsumes parameters that characterize the process, e.g., chemicals involved in the reaction, a description of the molecule, or the intensity of lasers that control the neutral atoms. The map $\cE$ characterizes a (potentially very complicated) quantum evolution happening in the lab. Depending on the parameter $x$, it produces the quantum state $\cE(\lvert x \rangle \! \langle x \rvert)$.
Finally, the experimentalist measures a certain observable $O$ at the end of the experiment.
The goal is to predict the measurement outcome for new physical experiments, with different values of $x$ than those encountered during training.

Illustration of classical and quantum machine learning models: In both classical and quantum machine learning models, the goal is to learn about an unknown CPTP map $\cE$ by performing physical experiments. (Left) In the learning phase of the classical model, a measurement is performed after each query to $\cE$; the classical measurement outcomes collected during the learning phase is consulted during the prediction phase. (Right) In the learning phase of the quantum model, multiple queries to $\cE$ 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.

Motivated by these concrete applications, we want to understand the power of classical and quantum ML for learning functions of the form given in Equation (<ref>).
On the one hand, we consider classical ML models that can gather classical measurement data $\{(x_i, o_i)\}_{i=1}^{N_{\mathrm{C}}}$, where $o_i$ is the outcome when we perform a POVM measurement on the state $\cE(\ketbra{x_i}{x_i})$.
We denote by $N_{\mathrm{C}}$ the number of such quantum experiments performed during training in the classical ML setting.
On the other hand, we consider quantum ML models in which multiple runs of the CPTP map $\cE$ can be composed coherently to prepare a quantum state stored in a quantum memory, and predictions are produced by a quantum computer with access to that quantum memory. We denote by $N_{\mathrm{Q}}$ the number of times $\cE$ is being used during training in the quantum ML setting.
The classical and quantum ML settings are illustrated in Figure <ref>.
The goal of each ML model is to learn a function $h(x)$ that accurately approximates $ f(x)$ while accessing the quantum process $\cE$ as few times as possible.

We focus on the question whether quantum ML can have a large advantage over classical ML: to achieve a small prediction error, can the optimal $N_{\mathrm{Q}}$ in the quantum ML setting be much less than the optimal $N_{\mathrm{C}}$ in the classical ML setting? For the purpose of this comparison we disregard the runtime of the classical or quantum computer that generates the predictions; we are only interested in how many times the process $\cE$ must run during the learning phase in the quantum and classical settings.

Our first main result addresses small average prediction error, i.e. the prediction error $|h(x)-f(x)|^2$ averaged over some specified input distribution $\mathcal{D}(x)$.
We rigorously show that, for any $\cE$, $O$, and $\mathcal{D}$, and for any quantum ML model, one can always design a restricted classical ML model achieving similar average prediction error such that $N_{\mathrm{C}}$ is larger than $N_{\mathrm{Q}}$ by only a small polynomial factor.
We say that the classical ML model is restricted if the POVM after each execution of $\cE$ is a measurement of the observable $O$ whose expectation value we wish to predict; in this special case, $o_i \in \mathbb{R}$ and $\E[o_i] = \Tr(O\cE(\ketbra{x_i}{x_i}))$.
Hence, there is no exponential advantage of quantum ML over classical ML if the goal is to achieve a small average prediction error, and the efficiency is quantified by the number of times $\cE$ is used in the classical or quantum model.

However, the situation changes if the goal is to achieve a small worst-case prediction error rather than a small average prediction error — an exponential separation between $N_{\mathrm{C}}$ and $N_{\mathrm{Q}}$ becomes possible if we insist on predicting $f(x)=\Tr(O \cE(\lvert x \rangle \! \langle x \rvert))$ accurately for every input $x$.
We illustrate this point with an example: accurately predicting expectation values of Pauli observables in an unknown $n$-qubit quantum state $\rho$. This is a crucial subroutine in many quantum computing applications; see e.g. [68, 56, 48, 29, 50, 53, 54, 52].
We present a quantum ML model that uses $N_{\mathrm{Q}}=\mathcal{O}(n)$ copies of $\rho$ to predict expectation values of all $n$-qubit Pauli observables. In contrast we prove that any classical ML model requires $N_{\mathrm{C}}=2^{\Omega(n)}$ copies of $\rho$ to achieve the same task even if the classical ML can perform arbitrary adaptive single-copy POVM measurements.

§ MACHINE LEARNING SETTINGS

We assume that the observable $O$ is known and the physical experiment $\cE$ is an unknown CPTP map that belongs to a (known) function class $\cF$. Apart from $\cE \in \cF$, the process can be arbitrary — a common assumption in statistical learning theory [77, 17, 11, 79, 9].
For the sake of concreteness, we assume that $\cE$ is a CPTP map from a Hilbert space of $n$ qubits to a Hilbert space of $m$ qubits.
Regarding inputs, we consider bit-strings of size $n$: $x \in \left\{0,1\right\}^n$. This is not a severe restriction, since floating-point representations of continuous parameters can always be truncated to a finite number of digits.
We now give precise definitions for classical and quantum ML; see Fig. <ref> for an illustration.

Classical (C) ML models: A classical ML model consists of two phases: learning and prediction. During the learning phase, a randomized classical algorithm selects classical inputs $x_i$ and we perform a (quantum) experiment that results in an outcome $o_i$ from performing a POVM measurement on $\cE(\ketbra{x_i}{x_i})$.

A total of  $N_{\mathrm{C}}$ experiments
give rise to (classical) training data
$\{(x_i, o_i)\}_{i=1}^{N_{\mathrm{C}}}$.
After obtaining training data, the classical ML model will execute a randomized algorithm $\mathcal{A}$ to learn a prediction model

\begin{equation}
s_{\mathrm{C}} = \mathcal{A}\left(\{(x_1, o_1), \ldots (x_{N_{\mathrm{C}}},o_{N_{\mathrm{C}}})\}\right),
\end{equation}

where $s_{\mathrm{C}}$ is stored in the classical memory.
In the prediction phase, a sequence of new inputs $\tilde{x}_1, \tilde{x}_2, \ldots \in \{0, 1\}^n$ is provided. The classical ML model will use $s_{\mathrm{C}}$ to evaluate predictions $h_{\mathrm{C}}(\tilde{x}_1), h_{\mathrm{C}}(\tilde{x}_2), \ldots$ that approximate $f(\tilde{x}_1), f(\tilde{x}_2), \ldots$ up to small errors.

Restricted classical ML models: We will also consider a restricted version of classical ML. Rather than performing arbitrary POVM measurements, we restrict the ML model to measure the target observable $O$ on the output state $\cE{\ketbra{x_i}{x_i}}$ to obtain the measurement outcome $o_i$. In this case, we always have $o_i \in \mathbb{R}$ and $\E[o_i] = \Tr(O \cE(\ketbra{x_i}{x_i}))$.

Quantum (Q) ML models: A quantum ML model also consists of two phases.
During the learning phase, the model starts with an initial state $\rho_0$ in a Hilbert space of arbitrarily high dimension.
Subsequently, the quantum ML model accesses the unknown CPTP map $\cE$ a total of $N_{\mathrm{Q}}$ times. These queries are interleaved with quantum data processing steps:

\begin{equation} \label{eq:outputQSQML-main}
\rho_{\mathrm{Q}} = \mathcal{C}_{N_{\mathrm{Q}}} (\cE \otimes \mathcal{I}) \mathcal{C}_{N_{\mathrm{Q}}-1} \ldots \mathcal{C}_1 (\cE \otimes \mathcal{I}) (\rho_0),
\end{equation}

where each $\mathcal{C}_{i}$ is an arbitrary but known CPTP map, and we write $\cE \otimes \mathcal{I}$ to emphasize that $\cE$ acts on an $n$-qubit subsystem of a larger quantum system.
The final state $\rho_{\mathrm{Q}}$, encoding the prediction model learned from the queries to the unknown CPTP map $\cE$, is stored in a quantum memory.
In the prediction phase, a sequence of new inputs $\tilde{x}_1, \tilde{x}_2, \ldots \in \{0, 1\}^n$ is provided. A quantum computer with access to the stored quantum state $\rho_Q$ executes a computation
to produce prediction values $h_{\mathrm{Q}}(\tilde{x}_1), h_{\mathrm{Q}}(\tilde{x}_2), \ldots$ that approximate $f(\tilde{x}_1), f(\tilde{x}_2), \ldots$ up to small errors[Due to non-commutativity of quantum measurements, the ordering of new inputs matters. For instance, the two lists $\tilde{x}_1, \tilde{x}_2$ and $\tilde{x}_2, \tilde{x}_1$ can lead to different outcome predictions $h_{\mathrm{Q}}(\tilde{x}_i)$. Our main results do not depend on this subtletey — they are valid, irrespective of prediction input ordering.].

The quantum ML setting is strictly more powerful than the classical ML setting.
During the prediction phase, the classical ML model is restricted to processing classical data, albeit data obtained by measuring a quantum system during the learning phase.
In contrast, quantum ML can work directly in the quantum realm. The quantum ML has an exponential advantage relative to the classical ML model for some tasks, as we demonstrate in Sec. <ref>.

§ AVERAGE-CASE PREDICTION ERROR

For a prediction model $h(x)$, we consider the average-case prediction error

\begin{equation}
\sum_{x \in \{0, 1\}^n} \mathcal{D}(x) |h(x) - \Tr(O \cE(\ketbra{x}{x}))|^2,
\end{equation}

with respect to a fixed distribution $\mathcal{D}$ over inputs. This could, for instance, be the uniform distribution.

Although quantum ML is strictly more powerful than classical ML, there are fundamental limitations.
The following rigorous statement limits the potential for quantum advantage.

Fix an $n$-bit probability distribution $\mathcal{D}$, an $m$-qubit observable $O$ $(\norm{O}\leq 1)$ and a family $\cF$ of CPTP maps with $n$ input qubits and $m$ output qubits.
Suppose there is a quantum ML model which accesses the map $\cE\in \cF$ $N_{\mathrm{Q}}$ times, producing with high probability a function $h_{\mathrm{Q}}(x)$ that achieves

\begin{equation}
\sum_{x \in \{0, 1\}^n} \mathcal{D}(x) \left| h_{\mathrm{Q}}(x) - \Tr(O \mathcal{E}(\ketbra{x}{x})) \right|^2 \leq \epsilon.
\end{equation}

Then there is a restricted classical ML model using $N_{\mathrm{C}} =\mathcal{O}(m N_{\mathrm{Q}} / \epsilon)$ experiments, producing with high probability a function $h_C$ that achieves

\begin{equation} \label{eq:aveprederr}
\sum_{x \in \{0, 1\}^n} \mathcal{D}(x) \left| h_{\mathrm{C}}(x) - \Tr(O \mathcal{E}(\ketbra{x}{x})) \right|^2 =\mathcal{O}(\epsilon).
\end{equation}

The proof consists of two parts.
First, we cover the entire family of maps $\cF$ with a maximal packing net, i.e. the largest subset $\mathcal{S} = \{\cE_a\}_{a=1}^{|\mathcal{S}|} \subset \cF$ such that the functions $f_{\cE_a}(x) = \Tr(O \cE_a(\ketbra{x}{x}))$ obey
$\sum_{x \in \left\{0,1\right\}^n} \mathcal{D}(x) \left| f_{\mathcal{E}_a}(x) - f_{\mathcal{E}_b} (x)\right|^2 >4 \epsilon$ whenever $a \neq b$.
We then set up a communication protocol as follows. Alice chooses an element $a$ of the packing net uniformly at random, records her choice $a$ in the register $C$, and then applies $\cE_a$ $N_Q$ times to prepare a quantum state $\rho_{\cE_a}$ in the register $B$. Alice's ensemble of quantum states, indexed by $a$, is thus described by the density operator

\begin{equation}
\rho_A= \frac{1}{|\mathcal{S}|}\sum_{a=1}^{|\mathcal{S}|}\left(|a\rangle\!\langle a|\right)_C\otimes \left(\rho_{\cE_a}\right)_B.
\end{equation}

Alice then sends the register $B$ to Bob, hoping that Bob can decode the state $\rho_{\cE_a}$ to recover her chosen message $a$. Using the quantum ML model, Bob performs a measurement that outputs the function $h_{Q,a}(x)$. Because by assumption the function $h_{Q,a}(x)$ achieves a small average-case prediction error with high probability, and because the packing net has been constructed so that the functions $\{f_{\cE_a}\}$ are sufficiently distinguishable, Bob can decode successfully with high probability. Because Alice chose from among $|\mathcal{S}|$ possible messages, the mutual information of Alice's register $C$ and Bob's measurement outcome must be at least of order $\log |\mathcal{S}|$ bits. According to Holevo's theorem, this means that the Holevo $\chi$ quantity of Alice's ensemble, the mutual information of the $C$ and $B$ registers in the state $\rho_A$, must also be $\chi=\Omega(\log |\mathcal{S})|$. Furthermore, we can analyze how $\chi$ depends on $N_Q$, finding that each additional application of $\cE_a$ to the $B$ register can increase $\chi$ by at most $\mathcal{O}(m)$. We conclude that $\chi =\mathcal{O}(m N_{\mathrm{Q}})$, yielding the lower bound $N_{\mathrm{Q}} = \Omega(\log(|\mathcal{S}|) / m)$. The lower bound applies to any quantum ML, where the size $|\mathcal{S}|$ of the packing net depends on the average-case prediction error $\epsilon$. This completes the first part of the proof.

In the second part, we explicitly construct a restricted classical ML model that achieves a small average-case prediction error using a modest number of experiments.
In the restricted classical ML model, an input $x_i$ is selected by sampling from the probability distribution $\mathcal{D}$, and an experiment is performed in which the observable $O$ is measured in the output quantum state $\cE(\ketbra{x_i}{x_i})$, obtaining measurement outcome $o_i$ which has expectation value $\Tr(O \cE(\ketbra{x_i}{x_i}))$.
A total of $N_{\mathrm{C}}$ such experiments are conducted.
Then, the classical ML model minimizes the least-squares error to find the best fit within the aforementioned packing net $\mathcal{S}$:

\begin{equation}
h_{\mathrm{C}} = \argmin_{f \in \mathcal{S}} \frac{1}{N_{\mathrm{C}}} \sum_{i=1}^{N_{\mathrm{C}}} |f(x_i) - o_i|^2.
\end{equation}

Because the measurement outcome $o_i$ fluctuates about the expectation value of $O$, it may be impossible to achieve zero training error.
Yet it is still possible for $h_{\mathrm{C}}$ to achieve a small average-case prediction error, potentially even smaller than the training error.
We use properties of maximal packing nets
and of quantum fluctuations of measurement outcomes to perform a tight statistical analysis of the average-case prediction error, finding that with high probability $\sum_{x \in \{0, 1\}^n} \mathcal{D}(x) \left| h_{\mathrm{C}}(x) - \Tr(O \mathcal{E}(\ketbra{x}{x})) \right|^2 = \mathcal{O}(\epsilon)$, provided that $N_{\mathrm{C}}$ is of order $\log(|\mathcal{S}|) / \epsilon$.

Finally, we combine the two parts to conclude $N_{\mathrm{C}} = \mathcal{O}(m N_{\mathrm{Q}} / \epsilon)$.
The full proof is in Appendix <ref>.

Theorem <ref> shows that all problems that are approximately learnable by a quantum ML model are also approximately learnable by some restricted classical ML model which executes the quantum process $\cE$ a comparable number of times. This
applies in particular, to predicting outputs of quantum-mechanical processes.
The relation $N_{\mathrm{C}} = \mathcal{O}(m N_{\mathrm{Q}} / \epsilon)$ is tight. We give an example in Appendix <ref> with $N_{\mathrm{C}} = \Omega(m N_{\mathrm{Q}} / \epsilon)$.

§ WORST-CASE PREDICTION ERROR

Model     Upp. bd.     Low. bd.

Quantum ML     $\mathcal{O}(n)$     $\Omega(n)$

Classical ML     $\mathcal{O}(n 2^n)$     $ 2^{\Omega(n)}$

Restricted CML     $\mathcal{O}(2^{2n})$     $\Omega(2^{2n})$

Sample complexity for predicting expectations of all $4^n$ Pauli observables (worst-case prediction error) in an $n$-qubit quantum state. Upp. bd. is the achievable sample complexity of a specific algorithm. Low. bd. is the lower bound for any algorithm. The classical ML upper bound can be achieved using classical shadows based on random Clifford measurements [50]. The rest of the bounds are obtained in Appendix <ref>.

Numerical experiments – number of copies of an unknown $n$-qubit state needed for predicting expectation values of all $4^n$ Pauli observables, with 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.

Rather than achieving a small average prediction error, one may be interested in obtaining a prediction model that is accurate for all inputs $x \in \{0, 1\}^n$.
For a prediction model $h(x)$, we consider the worst-case prediction error to be

\begin{equation}
\max_{x \in \{0, 1\}^n} |h(x) - \Tr(O \cE(\ketbra{x}{x}))|^2.
\end{equation}

Under such a stricter performance requirement, exponential quantum advantage becomes possible.

We highlight this potential by means of an illustrative and practically relevant example: predicting expectation values of Pauli operators in an unknown $n$-qubit quantum state $\rho$.
This is a central task for many quantum computing applications [68, 48, 29, 50, 56, 53, 54, 52].
To formulate this problem in our framework, suppose the $2n$-bit input $x$ specifies one of the $4^n$ $n$-qubit Pauli operators $P_x \in \{I, X, Y, Z\}^{\otimes n}$, and suppose that $\cE_{\rho}(|x\rangle\!\langle x|)$ prepares the unknown state $\rho$ and maps $P_x$ to the fixed observable $O$, which is then measured; hence

\begin{equation}
f(x) = \Tr(O \cE_\rho(\ketbra{x}{x})) =
\Tr(P_x \rho).
\end{equation}

In this setting, according to Theorem <ref>, there is no large quantum advantage if our goal is to estimate the Pauli operator expectation values with a small average prediction error.
However, an exponential quantum advantage is possible if we insist on accurately predicting every one of the $4^n$ Pauli observables.

Let us first present an efficient quantum ML model.
The procedure for predicting $\Tr(P_x \rho)$ has two stages, the first requiring only a classical memory, and the second requiring a quantum memory. The goal of the first stage is to predict the absolute value $|\Tr(P_x \rho)|$ for each $x$. For this purpose, $N_1$ copies of the quantum state $\rho$ are grouped into pairs; then, for each pair and for each of the $n$ qubits, a complete Bell basis measurement is performed and the outcomes are deposited in the classical memory. Analysis of this classical data yields predictions of $|\Tr(P_x \rho)|$ for $M$ different values of $x$, where with high probability each prediction has an error less than $\epsilon$. To achieve this accuracy, $N_1=\mathcal{O}(\log(M) / \epsilon^4)$ copies of $\rho$ suffice.

Once the absolute value is determined, the goal of the second stage is to determine the sign of $\Tr(P_x \rho)$. Importantly, to achieve our desired prediction error, there is no needed to find the sign for any value of $x$ for which the absolute value was found to be very small in the first stage. With $N_2$ copies of $\rho$ stored in the quantum memory, an entangled measurement can be performed acting on all the copies, whose sole purpose is to determine the sign of $\Tr(P_x \rho)$, without collecting any further information about $\rho$. If both $N_2$ and $|\Tr(P_x \rho)|$ are sufficiently large, this measurement is very likely to return the correct value of the sign. Because the measurement is strongly biased in favor of one of the two possible outcomes, it introduces only a very “gentle” disturbance of the pre-measurement state; therefore, by performing many such measurements in succession acting on the  quantum memory register, the sign of $P_x$ can be measured reliably for many possible values of $x$.
We find that $N_2=\mathcal{O}(\log(M)/\epsilon^2)$ copies of $\rho$ suffice to determine the sign of $\Tr(P_x \rho)$ for $M$ different Pauli operators, if $|\Tr(P_x \rho)|> \epsilon$ for each $P_x$.
The second stage can also be more amenable to near-term implementation using a heuristic that groups commuting observables [53, 52]; see Appendix <ref> for further discussion.
Together, we obtain an upper bound on the total number of queries $N_Q=N_1 +N_2$ to the map $\cE_\rho$ using our quantum ML protocol.

The quantum ML model only needs $N_{\mathrm{Q}}
= \mathcal{O}(\log(M)/\epsilon^4)$
copies of $\rho$ to predict expectation values of any $M$ Pauli observables to error $\epsilon$.

More details regarding the estimation protocol, as well as a rigorous proof, are provided in Appendix <ref>.
Theorem <ref> improves upon existing shadow tomography protocols [3, 4, 50, 22] for the special case of predicting Pauli observables.
Because each access to $\cE_\rho$ allows us to obtain one copy of $\rho$, we only need $N_{\mathrm{Q}} = \mathcal{O}(n)$ to predict expectation values of all $4^n$ Pauli observables up to a constant error.

For classical ML models, we prove the following fundamental lower bound; see Appendix <ref>.

Any classical ML must use $N_{\mathrm{C}} \geq 2^{\Omega(n)}$ copies of $\rho$ to predict expectation values of all Pauli observables with a small error.

This theorem holds even when the POVM measurements performed by the classical ML model could depend on the previous POVM measurement outcomes adaptively.
This establishes an exponential gap separating classical ML models from fully quantum ML models.
Table <ref> provides a summary of the upper and lower bounds on the sample complexity for predicting expectation values of Pauli observables.

§ NUMERICAL EXPERIMENTS

We support our theoretical findings with numerical experiments,
focusing on the task of predicting the expectation values of all $4^n$ Pauli observables in an unknown $n$-qubit quantum state $\rho$, with a small worst-case prediction error.
In this case, the function is $f(x) = \Tr(O \cE_{\rho}(\ketbra{x}{x})) = \Tr(P_x \rho)$, where $x \in \{I, X, Y, Z\}^n$ indexes the Pauli observables, and $\cE_{\rho}$ prepares the unknown state $\rho$ then maps $P_x$ to the fixed observable $O$.
This is the task we considered in Section <ref>.
Note that average-case prediction of Pauli observables is a much easier task, because most of the $4^n$ expectation values are exponentially small in $n$.

We consider two classes of underlying states $\rho$:
(i) Mixed states:  $\rho =(I + P) / 2^n$, where $P$ is a tensor product of $n$ Pauli operators. States in this class have rank $2^{n-1}$.
(ii) Product states: $\rho = \bigotimes_{i=1}^n |s_i \rangle \! \langle s_i|$,
where each $|s_i \rangle$ is one the six possible single-qubit stabilizer states.
We consider stabilizer states to ensure that classical simulation of the quantum ML model is tractable for reasonably large system size.

The numerical experiment in Figure <ref> implements the best-known ML procedures.
We can clearly see that there is an exponential separation between the number of copies of the state $\rho$ required for classical and quantum ML to predict expectation values when $\rho$ is in the class of mixed states.
However, for the class of product states, the separation is much less pronounced. Restricted classical ML can only obtain outcomes $o_i \in \{\pm 1\}$ with $\E[o_i] = \Tr(P_{x_i} \rho)$. Hence each copy of $\rho$ provides at most one bit of information, and therefore $\mathcal{O}(n)$ copies are needed to predict expectation values of all $4^n$ Pauli observables. In contrast, standard classical ML can perform arbitrary POVM measurements on the state $\rho$, so each copy can provide up to $n$ bits of information. The separation between classical ML and quantum ML is marginal for product states.

§ CONCLUSION AND OUTLOOK

Our main result Theorem <ref> limits the potential advantage of quantum ML over classical ML for predicting outcomes of quantum experiments with a specified average-case prediction error. Our figure of merit is the number of times the quantum process $\cE$ must be accessed in the quantum and classical settings, disregarding other measures of runtime of the model. This information-theoretic analysis complements recent studies of the computational complexity of classical ML models trained with data from quantum experiments [49].
Together, these rigorous results indicate that classical ML trained using quantum measurement data can be surprisingly powerful, boosting our hopes that near-term experimental platforms [69], assisted by classical ML, may fruitfully address challenging quantum problems in physics, chemistry, and materials science.

On the other hand, Theorem <ref> and <ref> rigorously establish the fact that quantum ML can have an exponential advantage over classical ML for certain problems where the objective is achieving a specified worst-case prediction error.
An important future direction will be identifying further learning problems which allow substantial quantum advantage, pointing toward potential practical applications of quantum technology.

§.§ Acknowledgments:

The authors want to thank Victor Albert, Sitan Chen, Jerry Li, Spiros Michalakis, Yuan Su, and Thomas Vidick for valuable input and inspiring discussions. HH is supported by the J. Yang & Family Foundation.

JP acknowledges funding from  ARO-LPS, NSF, and DOE. The Institute for Quantum Information and Matter is an NSF Physics Frontiers Center.

[1]
S. Aaronson.
Qma/qpoly/spl sube/pspace/poly: de-merlinizing quantum protocols.
In CCC, pages 13–pp, 2006.

[2]
S. Aaronson.
Read the fine print.
Nat. Phys., 11(4):291–293, 2015.

[3]
S. Aaronson.
Shadow tomography of quantum states.
In STOC, pages 325–338, 2018.

[4]
S. Aaronson and G. N. Rothblum.
Gentle measurement of quantum states and differential privacy.
In STOC, pages 322–333, 2019.

[5]
A. Ambainis and J. Emerson.
Quantum t-designs: t-wise independence in the quantum world.
In CCC, pages 129–140, 2007.

[6]
H. Araki and E. H. Lieb.
Entropy inequalities.
In Inequalities, pages 47–57. Springer, 2002.

[7]
J. M. Arrazola, A. Delgado, B. R. Bardhan, and S. Lloyd.
Quantum-inspired algorithms in practice.
arXiv preprint arXiv:1905.10415, 2019.

[8]
S. Arunachalam and R. de Wolf.
Optimal quantum sample complexity of learning algorithms.
arXiv preprint arXiv:1607.00932, 2016.

[9]
S. Arunachalam and R. de Wolf.
Guest column: A survey of quantum learning theory.
ACM SIGACT News, 48(2):41–67, 2017.

[10]
S. Arunachalam, A. B. Grilo, and H. Yuen.
Quantum statistical query learning.
arXiv preprint arXiv:2002.08240, 2020.

[11]
P. L. Bartlett and S. Mendelson.
Rademacher and gaussian complexities: Risk bounds and structural
J Mach Learn Res, 3(Nov):463–482, 2002.

[12]
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. De Wolf.
Quantum lower bounds by polynomials.
J. ACM, 48(4):778–797, 2001.

[13]
A. D. Becke.
A new mixing of hartree–fock and local density-functional theories.
J. Chem. Phys., 98(2):1372–1377, 1993.

[14]
I. Bengtsson and K. Życzkowski.
Geometry of quantum states: an introduction to quantum
Cambridge university press, 2017.

[15]
H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi,
A. S. Zibrov, M. Endres, M. Greiner, et al.
Probing many-body dynamics on a 51-atom quantum simulator.
Nature, 551(7682):579–584, 2017.

[16]
J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd.
Quantum machine learning.
Nature, 549(7671):195–202, 2017.

[17]
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth.
Learnability and the vapnik-chervonenkis dimension.
J. ACM, 36(4):929–965, 1989.

[18]
X. Bonet-Monroig, R. Babbush, and T. E. O’Brien.
Nearly optimal measurement scheduling for partial tomography of
quantum states.
Phys. Rev. X, 10(3):031064, 2020.

[19]
F. G. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu.
Quantum SDP solvers: Large speed-ups, optimality, and applications
to quantum learning.
In ICALP, 2019.

[20]
S. Bubeck, S. Chen, and J. Li.
Entanglement is necessary for optimal quantum property testing.
arXiv preprint arXiv:2004.07869, 2020.

[21]
I. Buluta and F. Nori.
Quantum simulators.
Science, 326(5949):108–111, 2009.

[22]
C. Bădescu and R. O'Donnell.
Improved quantum data analysis.
arXiv preprint arXiv:2011.10908, 2020.

[23]
R. Car and M. Parrinello.
Unified approach for molecular dynamics and density-functional
Phys. Rev. Lett., 55(22):2471, 1985.

[24]
G. Carleo and M. Troyer.
Solving the quantum many-body problem with artificial neural
Science, 355(6325):602–606, 2017.

[25]
J. Carrasquilla and R. G. Melko.
Machine learning phases of matter.
Nat. Phys., 13(5):431–434, 2017.

[26]
K.-M. Chung and H.-H. Lin.
Sample efficient algorithms for learning quantum channels in pac
model and the approximate state discrimination problem.
arXiv preprint arXiv:1810.10938, 2018.

[27]
I. Cong, S. Choi, and M. D. Lukin.
Quantum convolutional neural networks.
Nat. Phys., 15(12):1273–1278, 2019.

[28]
J. Cotler, S. Choi, A. Lukin, H. Gharibyan, T. Grover, M. E. Tai, M. Rispoli,
R. Schittko, P. M. Preiss, A. M. Kaufman, et al.
Quantum virtual cooling.
Phys. Rev. X, 9(3):031013, 2019.

[29]
O. Crawford, B. van Straaten, D. Wang, T. Parks, E. Campbell, and S. Brierley.
Efficient quantum measurement of pauli operators in the presence of
finite sampling error.
arXiv preprint arXiv:1908.06942, 2020.

[30]
V. Dunjko and H. J. Briegel.
Machine learning & artificial intelligence in the quantum domain: a
review of recent progress.
Rep. Prog. Phys., 81(7):074001, 2018.

[31]
A. Elben, R. Kueng, H.-Y. R. Huang, R. van Bijnen, C. Kokail, M. Dalmonte,
P. Calabrese, B. Kraus, J. Preskill, P. Zoller, and B. Vermersch.
Mixed-state entanglement from local randomized measurements.
Phys. Rev. Lett., 125:200501, Nov 2020.

[32]
T. J. Evans, R. Harper, and S. T. Flammia.
Scalable bayesian hamiltonian learning.
arXiv preprint arXiv:1912.07636, 2019.

[33]
E. Farhi and H. Neven.
Classification with quantum neural networks on near term processors.
arXiv preprint arXiv:1802.06002, 2018.

[34]
S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert.
Quantum tomography via compressed sensing: error bounds, sample
complexity and efficient estimators.
New J. Phys., 14(9):095022, 2012.

[35]
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl.
Neural message passing for quantum chemistry.
arXiv preprint arXiv:1704.01212, 2017.

[36]
A. Gilyén, S. Lloyd, and E. Tang.
Quantum-inspired low-rank stochastic regression with logarithmic
dependence on the dimension.
arXiv preprint arXiv:1811.04909, 2018.

[37]
I. Goodfellow, Y. Bengio, and A. Courville.
Deep Learning.
The MIT Press, 2016.

[38]
D. Gross, S. Nezami, and M. Walter.
Schur-Weyl duality for the Clifford group with applications:
Property testing, a robust Hudson theorem, and de Finetti representations.
arXiv preprint arXiv:1712.08628, 2017.

[39]
J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu.
Sample-optimal tomography of quantum states.
IEEE Trans. Inf. Theory, 63(9):5628–5641, 2017.

[40]
I. Hamamura and T. Imamichi.
Efficient evaluation of quantum observables using entangled
npj Quantum Inf., 6(1):1–8, 2020.

[41]
R. Harper, W. Yu, and S. T. Flammia.
Fast estimation of sparse quantum noise.
arXiv preprint arXiv:2007.07901, 2020.

[42]
A. W. Harrow, A. Hassidim, and S. Lloyd.
Quantum algorithm for linear systems of equations.
Phys. Rev. Lett., 103(15):150502, 2009.

[43]
V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala,
J. M. Chow, and J. M. Gambetta.
Supervised learning with quantum-enhanced feature spaces.
Nature, 567(7747):209–212, 2019.

[44]
C. W. Helstrom.
Quantum detection and estimation theory.
J. Statist. Phys., 1:231–252, 1969.

[45]
A. S. Holevo.
Bounds for the quantity of information transmitted by a quantum
communication channel.
Problemy Peredachi Informatsii, 9(3):3–11, 1973.

[46]
A. S. Holevo.
Statistical decision theory for quantum systems.
J. Multivariate Anal., 3:337–394, 1973.

[47]
R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki.
Quantum entanglement.
Rev. Mod. Phys., 81(2):865, 2009.

[48]
H.-Y. Huang, K. Bharti, and P. Rebentrost.
Near-term quantum algorithms for linear systems of equations.
arXiv preprint arXiv:1909.07344, 2019.

[49]
H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven, and
J. R. McClean.
Power of data in quantum machine learning.
arXiv preprint arXiv:2011.01938, 2020.

[50]
H.-Y. Huang, R. Kueng, and J. Preskill.
Predicting many properties of a quantum system from very few
Nat. Phys., 16:1050––1057, 2020.

[51]
W. J. Huggins, S. McArdle, T. E. O'Brien, J. Lee, N. C. Rubin, S. Boixo, K. B.
Whaley, R. Babbush, and J. R. McClean.
Virtual distillation for quantum error mitigation.
arXiv preprint arXiv:2011.07064, 2020.

[52]
W. J. Huggins, J. McClean, N. Rubin, Z. Jiang, N. Wiebe, K. B. Whaley, and
R. Babbush.
Efficient and noise resilient measurements for quantum chemistry on
near-term quantum computers.
arXiv preprint arXiv:1907.13117, 2019.

[53]
A. F. Izmaylov, T.-C. Yen, R. A. Lang, and V. Verteletskyi.
Unitary partitioning approach to the measurement problem in the
variational quantum eigensolver method.
J. Chem. Theory Comput., 16(1):190–195, 2019.

[54]
Z. Jiang, A. Kalev, W. Mruczkiewicz, and H. Neven.
Optimal fermion-to-qubit mapping via ternary trees with applications
to reduced quantum states learning.
Quantum, 4:276, 2020.

[55]
A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M.
Hardware-efficient variational quantum eigensolver for small
molecules and quantum magnets.
Nature, 549(7671):242–246, 2017.

[56]
C. Kokail, C. Maier, R. van Bijnen, T. Brydges, M. K. Joshi, P. Jurcevic, C. A.
Muschik, P. Silvi, R. Blatt, C. F. Roos, et al.
Self-verifying variational quantum simulation of lattice models.
Nature, 569(7756):355–360, 2019.

[57]
R. Kueng.
Quantum and classical information processing with tensors (lecture
notes), Spring 2019.
Caltech course notes: <https://iqim.caltech.edu/classes>.

[58]
H. Levine, A. Keesling, A. Omran, H. Bernien, S. Schwartz, A. S. Zibrov,
M. Endres, M. Greiner, V. Vuletić, and M. D. Lukin.
High-fidelity control and entanglement of rydberg-atom qubits.
Phys. Rev. Lett., 121(12):123603, 2018.

[59]
S. Lloyd, M. Mohseni, and P. Rebentrost.
Quantum algorithms for supervised and unsupervised machine learning.
arXiv preprint arXiv:1307.0411, 2013.

[60]
S. Lloyd, M. Mohseni, and P. Rebentrost.
Quantum principal component analysis.
Nat. Phys., 10(9):631–633, 2014.

[61]
W. Matthews, S. Wehner, and A. Winter.
Distinguishability of quantum states under restricted families of
measurements with an application to quantum data hiding.
Comm. Math. Phys., 291(3):813–843, 2009.

[62]
A. A. Melnikov, H. P. Nautrup, M. Krenn, V. Dunjko, M. Tiersch, A. Zeilinger,
and H. J. Briegel.
Active learning machine learns to create new quantum experiments.
Proc. Natl. Acad. Sci. U.S.A., 115(6):1221–1226, 2018.

[63]
M. Mohri, A. Rostamizadeh, and A. Talwalkar.
Foundations of machine learning.
The MIT Press, 2018.

[64]
A. Montanaro.
Learning stabilizer states by bell sampling.
arXiv preprint arXiv:1707.04012, 2017.

[65]
A. Montanaro and R. de Wolf.
A survey of quantum property testing.
Theory Comput., pages 1–81, 2016.

[66]
M. Paini and A. Kalev.
An approximate description of quantum states.
arXiv preprint arXiv:1910.10543, 2019.

[67]
R. G. Parr.
Density functional theory of atoms and molecules.
In Horizons of quantum chemistry, pages 5–15. Springer, 1980.

[68]
A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love,
A. Aspuru-Guzik, and J. L. O’brien.
A variational eigenvalue solver on a photonic quantum processor.
Nat. Commun., 5:4213, 2014.

[69]
J. Preskill.
Quantum computing in the NISQ era and beyond.
Quantum, 2:79, 2018.

[70]
P. Rebentrost, M. Mohseni, and S. Lloyd.
Quantum support vector machine for big data classification.
Phys. Rev. Lett., 113(13):130503, 2014.

[71]
M. Schuld and N. Killoran.
Quantum machine learning in feature hilbert spaces.
Phys. Rev. Lett., 122(4):040504, 2019.

[72]
R. A. Servedio and S. J. Gortler.
Equivalences and separations between quantum and classical
SIAM J. Comput., 33(5):1067–1092, 2004.

[73]
O. Sharir, Y. Levine, N. Wies, G. Carleo, and A. Shashua.
Deep autoregressive models for the efficient variational simulation
of many-body quantum systems.
Phys. Rev. Lett., 124(2):020503, 2020.

[74]
G. Struchalin, Y. A. Zagorovskii, E. Kovlakov, S. Straupe, and S. Kulik.
Experimental estimation of quantum state properties from classical
arXiv preprint arXiv:2008.05234, 2020.

[75]
E. Tang.
Quantum-inspired classical algorithms for principal component
analysis and supervised clustering.
arXiv preprint arXiv:1811.00414, 2018.

[76]
E. Tang.
A quantum-inspired classical algorithm for recommendation systems.
In STOC, pages 217–228, 2019.

[77]
L. G. Valiant.
A theory of the learnable.
Commun. ACM, 27(11):1134–1142, 1984.

[78]
E. P. Van Nieuwenburg, Y.-H. Liu, and S. D. Huber.
Learning phase transitions by confusion.
Nat. Phys., 13(5):435–439, 2017.

[79]
V. Vapnik.
The nature of statistical learning theory.
Springer science & business media, 2013.

[80]
R. Vershynin.
High-dimensional probability: An introduction with applications
in data science, volume 47.
Cambridge university press, 2018.

[81]
V. Verteletskyi, T.-C. Yen, and A. F. Izmaylov.
Measurement optimization in the variational quantum eigensolver using
a minimum clique cover.
J. Chem. Phys., 152(12):124114, 2020.

[82]
S. R. White.
Density-matrix algorithms for quantum renormalization groups.
Phys. Rev. B, 48(14):10345, 1993.

[83]
N. Wiebe, D. Braun, and S. Lloyd.
Quantum algorithm for data fitting.
Phys. Rev. Lett., 109(5):050505, 2012.

[84]
C. Zhang.
An improved lower bound on query complexity for quantum pac learning.
Inf. Process. Lett., 111(1):40–45, 2010.

[85]
L. Zhao, C. A. Pérez-Delgado, and J. F. Fitzsimons.
Fast graph operations in quantum computation.
Phys. Rev. A, 93(3):032314, 2016.

[86]
Z. Zhou, X. Li, and R. N. Zare.
Optimizing chemical reactions with deep reinforcement learning.
ACS Cent. Sci., 3(12):1337–1344, 2017.

§ APPENDIX

Appendix <ref> provides additional context and discusses relevant existing work. Details regarding the numerical experiments can be found in Section <ref>. The remaining portions are devoted to theory and mathematical proofs. Appendix <ref> provides a thorough treatment of average prediction errors  culminating in a proof of Theorem <ref> (bounds between query complexity – number of access to quantum process $\cE$ – in classical and quantum ML). Appendix <ref> provides a stylized example that highlights that the bound is tight.
Finally, Appendix <ref> provides sample complexity upper and lower bounds for predicting many Pauli expectation values with small worst-case error (leading to exponential separation in query complexity).

§ RELATED WORK

Quantum PAC learning

It is instructive to relate the main result on achieving average-case prediction error (Theorem <ref>) to quantum probably approximately correct (PAC) learning [72, 84, 8, 9, 26, 10]. The latter rigorously established the absence of information-theoretic quantum advantage for learning classical Boolean functions $h: \{0, 1\}^n \rightarrow \{0, 1\}$.
This is a special case of predicting functions of the form $f(x)=\Tr \left( O \cE(\ketbra{x}{x})\right)$.
To see this, we reversibly encode every $n$-bit Boolean function $h$ in a (unitary) CPTP map that acts on $(n+1)$ qubits:

\begin{equation}
\cE_h(\rho) = U_h \rho U_h^\dagger, \quad \text{where} \quad  U_h\ket{x, a} = \ket{x, h(x) \oplus a} \quad \text{for all} \quad  x \in \{0, 1\}^n, a \in \{0, 1\},
\end{equation}

where $\oplus$ is addition in $\mathbb{Z}_2$.
This is the quantum oracle for implementing the Boolean function $h$.
Fix $O=\mathbb{I}^{\otimes n} \otimes Z=Z_{n+1}$ – a Pauli-$Z$ operator acting on the final qubit – to conclude
$\Tr(O \cE_h(\ketbra{x}{x})) = h(x)$.
In quantum PAC learning, the quantum ML models (or quantum learners) are restricted to quantum samples of the form $\sum_x \sqrt{\mathcal{D}(x)} \ket{x} \ket{h(x)}$, where $\mathcal{D}(x)$ is the probability for sampling $x$ in the input distribution $\mathcal{D}$ and $h(x)$ is the Boolean function in question.
Furthermore, quantum PAC learning forcuses on the worst-case input distribution $\mathcal{D}_\star$.
This leaves open the potential for large quantum advantages in more general settings. For instance, the quantum ML could be allowed to access the CPTP map $\cE_h$ or we may want to consider an input distribution with the largest classical-quantum separation.
Theorem <ref> closes these open questions showing that no large quantum advantage in sample complexity (or query complexity) is possible even in the much more general setting of learning $f(x) = \Tr(O \cE(\ketbra{x}{x}))$.
Note that direct access to $\cE_h$ would also enable the construction of quantum PAC samples  (if we assume the quantum ML model depends on the fixed input distribution $\cD$). The quantum ML model simply inputs the pure state $\sum_x \sqrt{\mathcal{D}(x)} \ket{x} \ket{0}$ to $\cE_h$ to obtain

\begin{equation}
U_h \sum_x \sqrt{\mathcal{D}(x)} \ket{x} \ket{0} = \sum_x \sqrt{\mathcal{D}(x)} \ket{x} \ket{h(x)},
\end{equation}

which is the quantum sample considered in quantum PAC learning.

Quantum machine learning:

Quantum computers have the potential to improve existing machine learning models based on classical computers.
A series of works require that an exponential amount of data stored in quantum random access memory [16, 42, 70, 60, 59, 83, 30, 48].
Due to the quantum data structure, one can obtain exponential speed-up for certain machine learning tasks.
However, the act of storing the exponential amount of data will take exponential time. Furthermore, if we assume a similar data structure for classical machines, then the exponential advantage may not be available [2, 76, 75, 36, 7].
Another recent line of works focuses on using quantum computers to represent a family of classically intractable functions [33, 43, 71, 27].  However, computational power provided by data in a machine learning task can also make a classical ML model stronger [49] and may challenge some of these proposals in practice.

Shadow tomography:

Shadow tomography is the task of simultaneously estimating the outcome probabilities associated with $M$ 2-outcome measurements up to accuracy $\epsilon$: $p_i (\rho) = \mathrm{tr}(E_i \rho)$, where each $E_i$ is a positive semi-definite matrix with operator norm at most one [3, 19, 4, 22].
The best existing result is given by [22]. They showed that
N= \mathcal{O} \left(\log (M)^2 \log (d) /\epsilon^4 \right)
$ copies of the unknown state suffice to achieve this task.
Their protocol is based on an improved quantum threshold search: finding an observable $E_i$ with the expectation value $\Tr(E_i \rho)$ exceeding a certain threshold. Then, they combine this with online learning of quantum states similar Aaronson's original protocol. [3].
A more experimentally friendly shadow tomography protocol has been proposed in [50]. It only yields competitive scaling complexities for a restricted set of observables, but can
implemented on state-of-the-art quantum platforms [74, 31].

Measuring expectation values of Pauli observables:

Due to the importance of measuring Pauli observables in near-term applications of quantum computers,
a series of methods [29, 53, 81, 40, 54, 52, 18] have been proposed to reduce the number of measurements needed to estimate
Pauli expectation values.
All of them are based on one basic, yet powerful, observation: Commuting observables can be measured simultaneously.
For example, quantum chemistry applications are often contingent on measuring
$\mathcal{O}(n^4)$ Pauli observables [68].
The aforementioned Pauli estimation protocols group these observables into $\mathcal{O}(n^3)$ or even only $\mathcal{O}(n)$ commuting groups.
In turn,  $\mathcal{O}(n^3)$ or $\mathcal{O}(n)$ copies of the underlying state suffice to  obtain expectation values for all  $\mathcal{O}(n^4)$ relevant Pauli observables by exploiting commutation relations.
On the other hand, the novel technique proposed in Appendix <ref>
gets by with even fewer state preparations. A total of $\mathcal{O}(\log(n^4)) = \mathcal{O}(\log(n))$ copies suffice.
Restriction to few-body Pauli observables can yield additional improvements. Several protocols are known for this special case, see e.g. [66, 28, 18, 54, 32, 50].

§ DETAILS OF NUMERICAL EXPERIMENTS

§.§ Mixed states

For the case of mixed states given by $\rho = (I + P_{x^*}) / 2^n$, we have $f(x) = \Tr(P_x \rho)= \delta_{x,x^*}$ for all $x \in \{I, X, Y, Z\}^n$. That is, $f (x)$ is a point function, i.e. $f(x^*) =1$ for exactly one $x^*$, all other Pauli strings evaluate to zero.

Restricted classical ML:

We consider a restricted classical ML model that implements an exhaustive search over all Pauli observables $P_x$ with $x \in \left\{I,X,Y,Z\right\}^n$.
For each $x$, we repeatedly measure the observable $P_x$ and check whether the outcome $-1$  ever occurs. If this is the case, we know $f(x)=0$ with certainty (recall, that $f(x) \in \left\{0,1\right\}$ is a point function). After looping through all observables, we will be left with a single input $x^*$ that obeys $f(x^*)=1$. There are a total of $4^n$ inputs and whenever $x \neq x^*$, the expected number of measurements required to obtain the outcome $-1$ is $1/(\mathrm{Pr}_x[-1])=2$. In contrast, for $x=x^*$, outcome $-1$ can never occur. This results in a sample complexity of $\mathcal{O}(4^n)$ – a scaling that is confirmed by our numerical experiments and matches the lower bound $\Omega(4^n)$.

Classical ML:

For classical ML, we implement property prediction with classical shadows based on random Clifford measurements

[50]. The sample complexity to
predict $M$ Pauli observables up to small constant accuracy is known to be $\mathcal{O}(\max_{x} \Tr(P_x^2) \log(M))$. Using $\Tr (P_x^2)=\Tr (I^{\otimes n})=2^n$ and $M=4^n$, this upper bound simplifies to $\mathcal{O}(n 2^n)$. The numerical experiments confirm this theoretical prediction.

Quantum ML:

For quantum ML, we use the procedure introduced in Appendix <ref>.
We first perform several repetitions of two-copy Bell basis measurements to estimate absolute values $|\Tr(P_x \rho)|^2$ for all $4^n$ possible inputs $x$.
This allows us to immediately identify $x^*$.
One could solve for $x^*$ by performing Gaussian elimination in $GF(2)$. A similar strategy has also been used for learning quantum channels [41].
The required sample complexity is $\mathcal{O}(\log(4^n)) = \mathcal{O}(n)$ and the numerical experiments confirm this linear scaling.

§.§ Product states

We consider the unknown $n$-qubit state to be a tensor product of $n$ single-qubit stabilizer states (there are only six choices $\ket{0}, \ket{1}, \ket{+}, \ket{-}, \ket{y, +}, \ket{y, -}$).
We only need to obtain measurement outcomes for single-qubit Pauli observables to completely determine such product states.

Restricted classical ML:
Recall that the goal of this task is to predict $f(x) = \Tr(P_x \rho)$ for an unknown quantum state $\rho$.
The restricted classical ML can collect measurement data of the form $\{(x_i, o_i)\}$, where $x_i \in \{I, X, Y, Z\}^n$ and $o_i \in \pm 1$ is the measurement outcome when we measure $P_x$ on $\rho$.
We simply collect measurement outcomes for the $3n$ single-qubit Pauli observables by choosing the appropriate $x_i$. For each qubit, we
sample $\pm 1$-outcomes in the $X$-, $Y$- and $Z$-basis. Once we find that two of the three Pauli observables result in both the outcome $\pm 1$, we can determine the single-qubit state for the particular qubit. For two of the three bases, the underlying distribution is uniform, while deterministic outcomes are produced in the third basis.
In turn, we expect to require $6n$ Pauli measurements to unambiguously characterize the underlying stabilizer state. This scaling is confirmed by the numerical experiments.

Classical ML:
We associate classical ML models with reconstruction procedures that can perform arbitrary POVM measurements on individual copies of the unknown state $\rho$.
Here, we consider a sequence of POVMs where we measure first in the all-$X$ basis, second in the all-$Y$ basis, and then in the all-$Z$ basis (and repeat).
Similar to the restricted classical ML, we also check if two of the three possible single-qubit observables $X, Y, Z$ have resulted in both outcomes $\pm 1$.
Once two of the three single-qubit observables have produce both outcomes $\pm 1$, we can perfectly identify the corresponding single-qubit stabilizer state.
But, to complete the assignment, we need to be able to do so for all $n$ qubits. This incurs an additional logarithmic factor in the expected number of measurements. We expect to require $\mathcal{O}(\log(n))$ measurement repetitions to unambiguously determine the underlying product state.
Numerical experiments confirm this scaling behavior.

Quantum ML:
Quantum ML models can perform quantum data processing on multiple copies of quantum states. For product states, we only perform the following procedure.
For each repetition, we perform two-copy Bell basis measurements on $\rho \otimes \rho$ to simultaneously measure $X\otimes X, Y \otimes Y, Z \otimes Z$ on each of the $n$ qubits in $\rho$.
We can determine the eigenbasis (X-basis, Y-basis, or Z-basis) of each qubit when we found that two of the observables $X\otimes X, Y \otimes Y, Z \otimes Z$ result in both $\pm 1$ outcomes.
For two of the three observables, the underlying distribution is uniform in $\pm 1$, while deterministic outcomes are produced in the third observable.
Since we know the stabilizer bases for each qubit after a few two-copy measurements, we simply measure the $n$ qubits in the corresponding stabilizer basis on the final copy to recover the full state.
We refer to [38, 64, 85, 65] for results on efficient procedures for testing and learning stabilizer states in general.

§ PROOF OF THEOREM <REF>

This section contains a thorough treatment of average prediction errors. We consider related setups for classical ML and quantum ML.

The learning problem is defined by a (known) family of CPTP maps $\cF$, an input distribution $\mathcal{D}$, and an observable $O$ with $\norm{O} \leq 1$.
Each CPTP map $\cE \in \cF$ maps a $n$-qubit quantum state to $m$-qubit state. This collection defines a function

\begin{equation}
f_{\cE}(x) = \Tr(O \cE(\lvert x \rangle \! \langle x \rvert)): \{0, 1\}^n \rightarrow \mathbb{R}
\end{equation}

The goal is to learn a function $f: \{0, 1\}^n \rightarrow \mathbb{R}$
such that with high probability

\begin{equation}
\mathbb{E}_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \quad \text{is small}.
\end{equation}

A bit of additional context is appropriate here:
we are studying the existence of learning algorithms under a fixed learning problem defined by input distribution $\cD$, observable $O,$ and family of CPTP maps $\cF$.
In turn, the actual learning algorithms may and, in general, will depend on these potentially intricate mathematical objects.

One of our main technical contributions – Theorem <ref> – highlights that a substantial quantum advantage is impossible for this setting (small average-case prediction error). This is in stark contrast to the setting of achieving small worst-case prediction error.
The proof consists of two parts.
Section <ref> establishes a lower bound for the query complexity of any quantum ML model.
Subsequently, Section <ref> provides an upper bound for the query complexity achieved by certain classical ML models.
Finally, a combination of these two results establishes Theorem <ref>, see  Section <ref>.

§.§ Information-theoretic lower bound for quantum machine learning models

The quantum machine learning model consists of learning phase and prediction phase. In the learning phase, the quantum ML model accesses the quantum experiment characterized by the CPTP map $\cE$ for $N_{\mathrm{Q}}$ times to learn a model.
We consider the quantum ML model to be a mixed state quantum computation algorithm (a generalization of unitary quantum computation). Starting point is an initial state $\rho_0$ on any number of qubits. Subsequently, arbitrary quantum operations $\mathcal{C}_t$ (CPTP maps) are interleaved with in total $N_{\mathrm{Q}}$ invocations $\mathcal{E} \otimes \mathcal{I}$ of the unknown (black box) CPTP map and produce a final state

\begin{equation} \label{eq:outputQSQML}
\rho_{\cE} = \mathcal{C}_{N_{\mathrm{Q}}} (\cE \otimes \mathcal{I}) \mathcal{C}_{N_{\mathrm{Q}}-1} \ldots \mathcal{C}_2 (\cE \otimes \mathcal{I}) \mathcal{C}_1 (\cE \otimes \mathcal{I}) \mathcal{C}_0(\rho_0).
\end{equation}

In this model, we assume that $\mathcal{E}$ always acts on the first $n$ qubits. This, however, is no real restriction, because the quantum operations $\mathcal{C}_t$ are unrestricted. In particular, they could cointain certain SWAP operations that permute the qubits around.
The final state $\rho_{\cE}$ is the quantum memory that stores the prediction model learned from the CPTP map $\cE$ using the quantum ML algorithm. This concludes the quantum learning phase.

In the prediction phase,
we assume that new inputs are provided as part of a sequence

\begin{equation}
x_1, x_2, x_3, \ldots \in \{0, 1\}^n.
\end{equation}

For each sequence member $x_i$, the quantum ML model accesses the input $x_i$, as well as the current quantum memory.
It produces an outcome by performing a POVM measurement on the quantum memory $\rho_{\cE}$. We emphasize that this can, and in general will, affect the quantum memory nontrivially. The quantum ML outputs $h_{\mathrm{Q}}(x_i)$ depend on the entire sequence $x_1,\ldots,x_i$. And different sequence orderings will produce different predictions.

For example, when $n=2$, the following ordering may result in the prediction

\begin{equation}
x_1 = 00, x_2 = 01, x_3 = 10, x_4 = 11 \,\, \rightarrow \,\, h_{\mathrm{Q}}(00) = -0.3, h_{\mathrm{Q}}(01) = 0.5, h_{\mathrm{Q}}(10) = 0.2, h_{\mathrm{Q}}(11) = -0.7,
\end{equation}

but a different ordering may result in a slightly different prediction, such as

\begin{equation}
x_1 = 11, x_2 = 01, x_3 = 10, x_4 = 00 \,\, \rightarrow  \,\, h_{\mathrm{Q}}(00) = -0.2, h_{\mathrm{Q}}(01) = 0.5, h_{\mathrm{Q}}(10) = 0.2, h_{\mathrm{Q}}(11) = -0.6.
\end{equation}

Also, note that $h_{\mathrm{Q}}(x_i)$ can be randomized because a quantum measurement is performed to produce the prediction outcome.
The ordering does not affect the theorem we want to prove. In the following, we will fix the input ordering to be an arbitrary ordering. For example, we can use the input ordering such that the quantum ML model has the smallest prediction error.

After fixing an input ordering, we can treat the entire prediction phase (taking a sequence of inputs $x_1, x_2, \ldots$ and producing $h_{\mathrm{Q}}(x_1), h_{\mathrm{Q}}(x_2), \ldots$) as an enormous POVM measurement on the output state $\rho_{\cE}$ obtained from the learning phase.
Each outcome $a$ from the enormous POVM measurement on the output state $\rho_{\cE}$ corresponds to a function $h_{\mathrm{Q}, a}(x): \{0, 1\}^n \rightarrow \mathbb{R}$.
Using Naimark's dilation theorem, every POVM measurement is a projective measurements on a larger Hilbert space. Since the quantum memory that the quantum ML model can operate on contains an arbitrary amount of qubits, we can use Naimark's dilation theorem to restrict the enormous POVM measurement to a projective measurement $\{P_a\}_a$.
Hence, for any CPTP map $\cE \in \cF$, when we asks the quantum ML model to produce the prediction for an ordering of inputs $x_1, x_2, \ldots$, the output values $h_{\mathrm{Q}}(x_1), h_{\mathrm{Q}}(x_2), \ldots$ will be given by

\begin{equation} \label{eq:h-QaofQML}
h_{\mathrm{Q}, a}(x) \quad \text{with probability} \quad \Tr(P_a \rho_{\cE}) = \Tr(P_a \mathcal{C}_{N_{\mathrm{Q}}} (\cE \otimes\, \mathcal{I}) \mathcal{C}_{N_{\mathrm{Q}}-1} \ldots \mathcal{C}_2 (\cE \otimes\, \mathcal{I}) \mathcal{C}_1 (\cE \otimes\, \mathcal{I}) \mathcal{C}_0(\rho_0)),
\end{equation}

for a projective measurement $\{P_a\}_a$ with $\sum_a P_a = I$.

Finally, we will assume that the produced function $h_{\mathrm{Q}}(x)$ achieves small prediction error

\begin{equation} \label{eq:QMLassumption}
\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}}(x) - \Tr(O \mathcal{E}(\lvert x \rangle \! \langle x \rvert)) \right|^2 \leq \epsilon \quad \text{with probability at least $2/3$.}
\end{equation}

for any CPTP map $\mathcal{E} \in \cF$.
This assumption asserts that

\begin{equation} \label{eq:prob2/3}
\sum_{a=1}^A \Tr(P_a \rho_{\cE}) \mathbbm{1}\left[\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a}(x) - \Tr(O \mathcal{E}(\lvert x \rangle \! \langle x \rvert)) \right|^2 \leq \epsilon\right] \geq 2/3,
\end{equation}

where $\mathbbm{1}[z]$ denotes the indicator function of event $z$. That is, $\mathbbm{1}[z]=1$ if $z$ is true and $\mathbbm{1}[z]=0$ otherwise.

§.§.§ Maximal packing net

We emphasize that Rel. (<ref>) must be valid for any $\mathcal{E} \in \mathcal{F}$.
Because we only need to output a function $h_{\mathrm{Q}}(x)$ that approximates $f(x) = \Tr(O \cE(\ketbra{x}{x}))$ in average, the task will not be hard when there are only a few qualitatively different CPTP maps in $\mathcal{F}$.
However, the problem could become harder when $\mathcal{F}$ contains a large amount of very different CPTP maps.
The task is now to transform this requirement into a stringent lower bound on $N_{\mathrm{Q}}$ – the number of black-box uses of the unknown CPTP map $\mathcal{E} \otimes \mathcal{I}$ within the quantum computation (<ref>). As a starting point, we equip the set of target functions $\cF_f = \{f_{\cE}(x) = \Tr(O \mathcal{E}(\lvert x \rangle \! \langle x \rvert)) | \cE \in \cF\}$ with a packing  net. Packing nets are discrete subsets whose elements are guaranteed to have a certain minimal pairwise distance (think of spheres that must not overlap with each other). We choose points (functions) $f_{\mathcal{E}_i} \in \mathcal{F}_f$ and demand

\begin{equation} \label{eq:epspackingnetdistance}
\E_{x \sim \mathcal{D}} |f_{\cE_i}(x) - f_{\cE_j}(x)|^2 > 4\epsilon \quad \text{whenever} \quad i \neq j.
\end{equation}

We denote the resulting packing net of $\mathcal{F}_f$ by $M^p_{4\epsilon}(\cF_f)$ and note that every such set has finitely many elements ($\mathcal{F}_f$ is a compact set).
We also assume that $M^p_{4\epsilon}(\cF_f)$ is maximal in the sense that no other $4\epsilon$-packing net can contain more points (functions). This assumption is standard and often implicit in the definition of a (finite) packing net.

We will now present two different proof strategies that utilize packing nets to derive a query complexity lower bound for the quantum machine learning model.
The first proof analyzes mutual information in a synthetic communication protocol [34, 39, 50].
The second proof analyzes polynomials [12] and only works when $n \geq m$.

§.§.§ Proof strategy I: mutual information analysis

Let us define a communication protocol between two parties, say Alice and Bob.
They use the packing net $M^p_{4 \epsilon}(\cF_f)$ as a dictionary to communicate randomly selected classical messages. More precisely,
Alice samples an integer $X$ uniformly at random from  $1,2, \ldots, |M^p_{4\epsilon}(\cF_f)|$ and chooses the corresponding CPTP map $\cE_X \in  M^p_{4\epsilon}(\cF_f)$.
When Bob wants to access the unknown CPTP map $\cE_X$, he will ask Alice to apply the CPTP map $\cE_X$.
Bob will then execute the quantum machine learning model (<ref>) to obtain a prediction model $h_{\mathrm{Q}, a}(x)$, where $a$ parameterizes the prediction model.
Subsequently, Bob solves the following optimization problem

\begin{equation}
\tilde{X} = \argmin_{X' = 1, \ldots, |M^p_{4\epsilon}(\cF_f)|} \E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a}(x) - \Tr(O \mathcal{E}_{X'}(\lvert x \rangle \! \langle x \rvert)) \right|^2
\label{eq:bob-decoding}
\end{equation}

to obtain an integer $\tilde{X}$.
This decoding procedure seems adequate, provided that the prediction model $h_{\mathrm{Q}}$ approximately reproduces the true underlying function.

More precisely, assumption (<ref>) asserts

\begin{equation}
\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a}(x) - \Tr(O \mathcal{E}_X(\lvert x \rangle \! \langle x \rvert)) \right|^2 \leq \epsilon \quad \text{with probability at least $2/3$.}
\end{equation}

Here is where the choice of dictionary matters: $M^p_{4\epsilon}(\cF_f)$ is a packing net, see Equation (<ref>).
For $X' \neq X$ this necessarily implies

\begin{align}
\E_{X \sim \mathcal{D}} \left| h_{\mathrm{Q}, a}(x) - f_{\cE_{X'}}(x) \right|^2 &\geq \left( \Big(\E_{X \sim \mathcal{D}} \left| f_{\cE_{X}}(x) - f_{\cE_{X'}}(x) \right|^2\Big)^{1/2} - \Big(\E_{X \sim \mathcal{D}} \left| h_{\mathrm{Q}, a}(x) - f_{\cE_{X}}(x) \right|^2\Big)^{1/2}\right)^2 \\
&> \left( 2 \sqrt{\epsilon} - \sqrt{\epsilon} \right)^2 = \epsilon.
\end{align}

This allows us to conclude that Bob's decoding strategy (<ref>)
succeeds perfectly if

\begin{equation}
\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a}(x) - \Tr(O \mathcal{E}_X(\lvert x \rangle \! \langle x \rvert)) \right|^2 \leq \epsilon.
\end{equation}

In turn, Assumption <ref> ensures $\tilde{X}=X$ (perfect decoding) with probability at least $2/3$.

Now, we use the fact that Alice samples her message $X$ uniformly at random from a total of $|M^p_{4\epsilon}(\cF_f)|$ integers.
Hence, Fano's inequaltiy provides a lower bound on the mutual information between sent and decoded message, namely

\begin{equation} \label{eq:MutualInfo-Mp}
I(X : \tilde{X}) \geq \Omega\left(\log(|M^p_{4\epsilon}(\cF_f)|)\right).
\end{equation}

Next, note that $\tilde{X}$ is obtained by classically processing a measurement outcome $a$ of the quantum state $\rho_{\mathcal{E}_X}$ The data processing inequality and Holevo's theorem [45, 47, 14, 6] then imply

\begin{equation} \label{eq:MutualInfo-DP}
I(X : \tilde{X}) \leq I(X : a) \leq \chi(X : \rho_{\cE_X}).
\end{equation}

The Holevo $\chi$ quantity between the classical random variable $X$ and the quantum state $\rho_{\cE_X}$ is

\begin{equation}
\chi(X : \rho_{\cE_X}) = S\left( \E_X \rho_{\cE_X} \right) - \E_X S\left(\rho_{\cE_X}\right),
\end{equation}

where $S(\rho) = \Tr(-\rho \log \rho)$ is the von Neumann entropy. Throughout this work, we refer to $\log$ with base $\mathrm{e}$. Recall that Bob produces $\rho_{\cE_X}$ by utilizing a total of $N_{\mathrm{Q}}$ channel copies obtained from Alice.
We can use the specific layout (<ref>) of Bob's quantum computation to produce an upper bound on the Holevo-$\chi$:

\begin{equation}
\chi(X : \rho_{\cE_X}) \leq \mathcal{O}(m N_{\mathrm{Q}})
\label{eq:holevo-upper-bound}
\end{equation}

This bound follows from induction over a sample-resolved variant of Bob's quantum computation. For $t =0,1,\ldots,N_{\mathrm{Q}}$, we will show that

\begin{equation}
\rho^t_{\cE} = \mathcal{C}_{t} (\cE \otimes\, \mathcal{I}) \mathcal{C}_{t-1} \ldots \mathcal{C}_1 (\cE \otimes\, \mathcal{I}) \mathcal{C}_0(\rho_0)
\quad \text{obeys} \quad \chi(X : \rho^t_{\cE_X}) \leq (2\log 2) m t.
\end{equation}

Bound (<ref>) then follows from recognizing that setting $t=N_{\mathrm{Q}}$ reproduces Bob's complete computation, see Equation (<ref>).

The base case ($t=0$) is simple, because $\rho^0_{\cE_X} = \mathcal{C}_0(\rho_0)$ does not depend on $X$ at all. This ensures

\begin{equation}
\chi \left(X: \rho_{\cE_X}^0 \right) = S\left( \E_X \rho_{\cE_X}^0 \right) - \E_X S\left(\rho_{\cE_X}^0\right)= S \left( \rho_{\cE_X}^0 \right) - S\left(\rho_{\cE_X}^0\right) = 0
\leq (2 \log 2) m t \quad (t=0).
\end{equation}

Now, let us move to the induction step ($t>0$). The induction hypothesis provides us with

\begin{equation} \label{eq:induchypoIX}
\chi(X : \rho^{t-1}_{\cE_X}) \leq (2\log 2)m (t-1)
\end{equation}

and we must  relate $\chi(X : \rho^{t}_{\cE_X})$ to $\chi(X : \rho^{t-1}_{\cE_X})$.
To achieve this goal, we use the fact that the Holevo-$\chi$ is closely related to the quantum relative entropy $D(\rho || \sigma) = \Tr\left( \rho (\log \rho - \log \sigma) \right)$ [47, 14, 6]. Indeed,

\begin{equation}
\chi(X : \rho^t_{\cE_X})
%= S\left( \E_X \rho^t_{\cE_X} \right) - \E_X S\left(\rho^t_{\cE_X}\right)
= \E_X\left[ \Tr\left( \rho^t_{\cE_X} \log \rho^t_{cE_X} - \rho^t_{\cE_X} \log \left(\E_{X'}\rho^t_{cE_{X'}} \right) \right) \right]
=  \E_{X} D\left(\rho^t_{\cE_X} || \E_{X'}\rho^t_{cE_{X'}}\right),
\end{equation}

and monotonicity of the quantum relative entropy asserts

\begin{align*}
\E_{X} D\left(\rho^t_{\cE_X} || \E_{X'}\rho^t_{cE_{X'}}\right)
=&  \E_{X} D\left( \mathcal{C}_{t}\left( \left(\cE_{X} \otimes\, \mathcal{I}\right) \left( \rho^{t-1}_{\cE_X} \right) \right) \,\, || \,\, \mathcal{C}_{t}\left( \E_{X'} \left(\cE_{X'} \otimes\, \mathcal{I}\right)\left( \rho^{t-1}_{\cE_{X'}} \right)\right)\right)\\
\leq & \E_{X} D\left( \left(\cE_{X} \otimes\, \mathcal{I}\right) \left( \rho^{t-1}_{\cE_X} \right) \,\, || \,\, \E_{X'} \left(\cE_{X'} \otimes\, \mathcal{I}\right)\left( \rho^{t-1}_{\cE_{X'}} \right)\right)\\
=& S\left( \E_X \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right) - \E_X S\left( \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X})\right).
\end{align*}

This effectively allows us to ignore the $t$-th quantum operation $\mathcal{C}_t$ and instead exposes the $t$-th invocation of $\mathcal{E} \otimes \mathcal{I}$.

We analyze the two remaining terms separately.
Let use define the notation $\Tr_{\leq m}$ as the partial trace over the first $m$ qubits, and $\Tr_{> m}$ as the partial trace over the rest of the qubits.
Subadditivity of the von Neumann entropy $S(\rho)$ [47, 14, 6] implies

\begin{align}
S\left( \E_X \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right) &\leq S\left( \Tr_{\leq m} \E_X \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right) + S\left( \Tr_{> m} \E_X \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right),\\
&\leq S\left( \Tr_{\leq m} \E_X \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right) + m \log 2\\
&= S\left( \Tr_{\leq n} \E_X \rho^{t-1}_{\cE_X} \right) + m \log 2.
\end{align}

The second inequality uses the fact that the maximum entropy for an $m$-qubit system is at most $m \log 2$. The last equality is due to the following technical observation (the action of a CPTP map can be traced out).

Fix a CPTP map $\mathcal{E}$ from $n$ qubits to $m$ qubits and let $\mathcal{I}$ denote the identity map on $n' \geq 0$ qubits. Then, $\Tr_{\leq m}[(\cE \otimes \mathcal{I}) \rho] = \Tr_{\leq n}[\rho]$ for any $(n+n')$-qubit state $\rho$.

Let $\mathcal{E}(\rho) = \sum_i K_i \rho K_i^\dagger$ be a Kraus representation of the CP map $\mathcal{E}$. TP moreover implies $\sum_i K_i^\dagger K_i = I$. For any input state $\rho$,
Linearity and (partial) cyclicity of the partial trace then ensure

\begin{align*}
\Tr_{\leq m}\left((\cE \otimes \mathcal{I}) \rho\right) =&
\sum_i \Tr_{\leq m} \left( K_i \otimes I\rho K_i^\dagger \otimes I\right)
= \sum_i \Tr_{\leq m} \left( \rho (K_i^\dagger K_i) \otimes I \right)
= \Tr_{\leq m} \left(\rho I \otimes I \right)
= \Tr_{\leq m} \left( \rho \right).
\end{align*}

This concludes the proof of the lemma.

Similarly, the second term can be lower bounded by

\begin{align}
\E_X S\left( \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right) &\geq \E_X S\left( \Tr_{\leq m} \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right) - \E_X S\left( \Tr_{> m} \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right),\\
&\geq \E_X  S\left( \Tr_{\leq m} \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right) - m \log 2,\\
&= \E_X S\left( \Tr_{\leq n} \rho^{t-1}_{\cE_X} \right) - m \log 2.
\end{align}

We can combine these two bounds with the monotonicity of the quantum relative entropy to obtain

\begin{align}
\chi(X : \rho^t_{\cE_X}) &\leq S\left( \E_X \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X}) \right) - \E_X S\left( \left(\cE_{X} \otimes\, \mathcal{I}\right)(\rho^{t-1}_{\cE_X})\right)\\
&\leq S\left( \Tr_{\leq n} \E_X \rho^{t-1}_{\cE_X} \right) - \E_X S\left( \Tr_{\leq n} \rho^{t-1}_{\cE_X} \right) + (2\log 2)m \\
&= \E_X D\left( \Tr_{\leq n} \rho^{t-1}_{\cE_X} ||  \Tr_{\leq n} \E_{X'} \rho^{t-1}_{\cE_{X'}}\right) + (2\log 2)m\\
&\leq \E_X D\left( \rho^{t-1}_{\cE_X} || \E_{X'} \rho^{t-1}_{\cE_{X'}} \right) + (2 \log 2) m\\
& = \chi(X : \rho^{t-1}_{\cE_X}) + (2 \log 2) m.
\end{align}

Plug in the induction hypothesis (<ref>) to complete the argument:

\begin{equation}
\chi(X : \rho^t_{\cE_X})
\leq \chi(X : \rho^{t-1}_{\cE_X}) + (2 \log 2) m \leq (2 \log 2 ) m(t-1) + (2 \log 2) m  = (2 \log 2) mt. \label{eq:holevo-upper-bound2}
\end{equation}

It is worthwhile to pause and recapitulate the main insights from this section: i.) a lower bound on the mutual information in terms of packing net cardinality, see Equation eqrefeq:MutualInfo-Mp, (<ref>);  ii.) Holevo's theorem, see Equation (<ref>) ; and, (iii) an upper bound on the Holevo-$\chi$ in terms of query complexity, see Equation (<ref>) for $t=N_{\mathrm{Q}}$.
Combining all of them yields

\begin{equation*}
\Omega\left(\log(|M^p_{4\epsilon}(\cF_f)|)\right) \leq I \left( X: \tilde{X}\right)
\leq \chi \left( X: \rho_{\cE_X} \right) \leq (2 \log 2) mN_{\mathrm{Q}}.
\end{equation*}

Rearranging this display yields a lower bound on the minimal query complexity in terms of packing net size:https://www.overleaf.com/project/5ee11fe492c6f40001a34112

\begin{equation} \label{eq:NQlowerbound}
N_{\mathrm{Q}} \geq \Omega\left(\frac{\log(|M^p_{4\epsilon}(\cF_f)|)}{m}\right).
\end{equation}

§.§.§ Proof strategy II: polynomial method

Here, we provide an alternative proof for a quantum lower bound that is based on the so-called polynomial method [12]. The result will be slightly less general – it requires $n \leq m$ as an extra assumption. But the argument is instructive, as it has a very different flavor.
Because the two proofs have very different flavor, we provide both of them. But we emphasize once more that the mutual information proof works in a somewhat more general setting.

Let us start by recalling that we may embed a $4\epsilon$-packing net $M^p_{4\epsilon}(\cF_f)$ within the set of target functions $\cF_f$. Geometrically, this means that each $\cE \in M^p_{4\epsilon}(\cF_f)$ describes the center of a $2\epsilon$-ball (this radius is defined with respect to average prediction error squared). And, according to the defining property Equation (<ref>), these balls do not overlap. We can use these disjoint balls to cluster different quantum machine learning solutions. Define

\begin{equation} \label{eq:smallballFQ}
\mathcal{F}^{\mathrm{Q}}_{\cE} = \left\{ a \in A \,\, : \,\, \E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a}(x) - f_{\cE}(x) \right|^2 \leq \epsilon \right\},
\end{equation}

where $A$ is a placeholder for all possible answers the quantum machine learning model can provide.
See the definition given in Equation (<ref>).
The packing net condition (<ref>) ensures that different clusters are completely disjoint. For distinct $\cE_1,\cE_2 \in \cF$ and $a_1 \in \cF^{\mathrm{Q}}_{\cE_1}$, $a_2 \in \cF^{\mathrm{Q}}_{\cE_2}$, two triangle inequalities and Equation (<ref>) yield

\begin{align}
\sqrt{\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a_1}(x) - h_{\mathrm{Q}, a_2}(x) \right|^2}
&\geq \sqrt{\E_{x \sim \mathcal{D}} \left| f_{\cE_1}(x) - h_{\mathrm{Q}, a_2}(x) \right|^2} - \sqrt{\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a_1}(x) - f_{\cE_1}(x) \right|^2} \\
&\geq \sqrt{\E_{x \sim \mathcal{D}} \left| f_{\cE_1}(x) - f_{\cE_2}(x) \right|^2} - \sqrt{\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a_2}(x) - f_{\cE_2}(x) \right|^2} \\
&- \sqrt{\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, {a_1}}(x) - f_{\cE_1}(x) \right|^2} \\
&> 2 \sqrt{\epsilon} - \sqrt{\epsilon} - \sqrt{\epsilon} = 0.
\end{align}

This implies $f_{a_1}^Q \neq f_{a_2}^Q$ and, more importantly, $\mathcal{F}^Q_{\cE_1} \cap \mathcal{F}^Q_{\cE_2} = \varnothing$ whenever $ f_{\cE_1} \neq f_{\cE_2}$.

We will use this insight to reason about an auxiliar matrix $P$ of size
$|M^p_{4\epsilon}(\cF_f)| \times |M^p_{4\epsilon}(\cF_f)|$.
We label rows and columns by packing net elements $f_{\cE_i}$ with $i=1$ (rows) or $i=2$ (columns). For each pair $f_{\cE_1},f_{\cE_2}$, let $P_{\cE_1,\cE_2}$ denote the probability of a mix-up between $\cE_1$ and $\cE_2$. Such mix-ups occur if the underlying CPTP map is $\cE_2$, but the quantum ML model outputs an answer $a \in \cF^{\mathrm{Q}}_{\cE_1}$ that belongs to the cluster associated with $\cE_1$:

\begin{align}
P_{\cE_1, \cE_2} &= \sum_{a=1}^A \Tr(P_a \rho_{\cE_2}) \mathbbm{1}\left[\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}, a}(x) - f_{\cE_1}(x) \right|^2 \leq \epsilon\right]
= \sum_{a: h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_1}} \Tr(P_a \rho_{\cE_2}).% & \forall f_{\cE_1}, f_{\cE_2} \in M^p_{4\epsilon}(\cF_f).
\label{eq:polynomial-method-P}
\end{align}

Here, $\rho_{\epsilon_2}$ is the outcome state of the quantum ML model (trained on CPTP map $\cE_2$) and $P_a$ is the POVM element associated with predicting $a_1$.
Recall that the main assumption on the quantum ML model is that it predicts accurately with probability at least $2/3$.
This implies

\begin{equation}
P_{\cE_1, \cE_1} \geq 2 / 3
\quad \text{for each}  \quad \cE_1 \in M^p_{4\epsilon}(\cF_f),
\end{equation}

while each row sum over off-diagonal matrix elements is strictly smaller. For $f_{\cE_2} \in M^p_{4\epsilon}(\cF_f)$,

\begin{align}
\sum_{\substack{f_{\cE_1} \in M^p_{4\epsilon}(\cF_f) \\ f_{\cE_1} \neq f_{\cE_2}}} P_{\cE_1, \cE_2}
&= \sum_{\substack{f_{\cE_1} \in M^p_{4\epsilon}(\cF_f) \\ f_{\cE_1} \neq f_{\cE_2}}} \sum_{a: h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_1}} \Tr(P_a \rho_{\cE_2}) \\
&= \sum_{\substack{f_{\cE_1} \in M^p_{4\epsilon}(\cF_f)}} \sum_{a: h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_1}} \Tr(P_a \rho_{\cE_2}) - \sum_{a: h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_2}} \Tr(P_a \rho_{\cE_2}) \\
&= \sum_{\substack{a: \exists f_{\cE_1} \in M^p_{4\epsilon}(\cF_f) \\ h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_1}}} \Tr(P_a \rho_{\cE_2}) - \sum_{a: h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_2}} \Tr(P_a \rho_{\cE_2}) \\
&\leq \sum_{a=1}^A \Tr(P_a \rho_{\cE_2}) - \sum_{a: h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_2}} \Tr(P_a \rho_{\cE_2}) \\
&= 1 - P_{\cE_2, \cE_2} \leq 1/3.
\end{align}

The first equality uses the definition of matrix $P$. The third equality follows from the observation that distinct clusters are also disjoint ($\mathcal{F}^Q_{\cE_1} \cap \mathcal{F}^Q_{\cE_2} = \varnothing$).
We conclude that the $|M^p_{4\epsilon}(\cF_f)| \times |M^p_{4\epsilon}(\cF_f)|$-matrix $P$
is diagonally dominant. Such matrices are guaranteed to be non-singular, i.e. they have full rank.

This is a suitable starting point for analyzing the probability $\Tr(P_a \rho_{\cE})$ via a polynomial method [12].
$\{K^{\cE}_i\}_{i=1}^{2^n 2^m}$,

\begin{equation}
{\cE}(\rho) = \sum_{i} K^{\cE}_i \rho (K^{\cE}_i)^\dagger,
\end{equation}

with $K^{\cE}_i \in \mathbb{C}^{2^m \times 2^n}$ be the Kraus representation of a fixed CPTP map $\cE \in \cF$.
This representation is parametrized by (at most) $2^n 2^m \times 2^m  2^n=2^{2(n+m)}$ complex parameters:

\begin{equation*}
(K^{\cE}_{i})_{jk} = z^{\cE}_{i \times 2^{n+m} + j \times 2^{n} + k}
\quad \text{defines} \quad z^{\cE} \in \mathbb{C}^{2^{2(n+m)}}.
\end{equation*}

On a high level, we parametrize inputs to the quantum ML model by vectors.
After training, the probability of obtaining answer $a \in A$ corresponds to a homogeneous polynomial of degree $N_{\mathrm{Q}}$ in $z^{\cE}$ and of degree $N_{\mathrm{Q}}$ in $\bar{z}^{\cE}$:

\begin{align}
\Tr(P_a \rho_{\cE}) &= \Tr(P_a \mathcal{C}_{N_{\mathrm{Q}}} (\cE \otimes\, \mathcal{I}) \mathcal{C}_{N_{\mathrm{Q}}-1} \ldots \mathcal{C}_2 (\cE \otimes\, \mathcal{I}) \mathcal{C}_1 (\cE \otimes\, \mathcal{I}) \mathcal{C}_0(\rho_0))\\
&= w_a^\dagger  \underset{N_{\mathrm{Q}}\text{ times}}{\underbrace{(z^{\cE} \otimes \bar{z}^{\cE}) \otimes \cdots \otimes (z^{\cE} \otimes \bar{z}^{\cE}})},
\end{align}

where $w_a^\dagger$ is a dual tensor product vector with compatible dimension $N=2^{2(n+m)2N_{\mathrm{Q}}}=2^{4(n+m)N_{\mathrm{Q}}}$. Every matrix element $P_{\mathcal{E}_1,\mathcal{E}_2}$ of $P$ defined in Equation (<ref>) can be expressed as a sum of homogeneous polynoials in $(z^{\mathcal{E}_2} \otimes \bar{z}^{\mathcal{E}_2}) \otimes \cdots \otimes (z^{\mathcal{E}_2} \otimes \bar{z}^{\mathcal{E}_2})$.
Collecting all $M=|M^p_{4\epsilon}(\cF_f)|$ possible tensor products as rows of the matrix

\begin{equation}
Z = \begin{bmatrix}
(z^{\mathcal{E}_1} \otimes \bar{z}^{\mathcal{E}_1}) \otimes \cdots \otimes (z^{\mathcal{E}_1} \otimes \bar{z}^{\mathcal{E}_1})
& \cdots &
(z^{\mathcal{E}_M} \otimes \bar{z}^{\mathcal{E}_M}) \otimes \cdots \otimes (z^{\mathcal{E}_M} \otimes \bar{z}^{\mathcal{E}_M})
\end{bmatrix}
\in \mathbb{C}^{N \times M}
\end{equation}

allows us to present the multilinear characterization of all entries of $P$ in a single display:

\begin{align*}
P= W Z \quad \text{with} \quad  W
= \begin{bmatrix}
\sum_{h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_1}} w_a^\dagger \\
\vdots \\
\sum_{h_{\mathrm{Q}, a} \in \mathcal{F}^Q_{\cE_M}} w_a^\dagger \\
\end{bmatrix}
\in \mathbb{C}^{M \times 2^N}
\end{align*}

Above, we have shown that the $M \times M$-matrix $P$ must have full column rank. This is only possible if

\begin{equation}
|M^p_{4\epsilon}(\cF_f)| = M \leq N = 2^{2(n+m)2N_{\mathrm{Q}}}=2^{4(n+m)N_{\mathrm{Q}}}.
\end{equation}

Rearranging these terms and assuming $n \leq m$ implies the following lower bound on quantum query complexity $N_{\mathrm{Q}}$:

\begin{equation}
N_{\mathrm{Q}} \geq \frac{\log(|M^p_{4\epsilon}(\cF_f)|)}{4(n + m)} \geq \frac{\log(|M^p_{4\epsilon}(\cF_f)|)}{8m}.
\end{equation}

§.§ Information-theoretic upper bound for restricted classical machine learning models

We will focus on restricted classical ML models that can select inputs $x_i \in \{0, 1\}^n$ and obtain the corresponding outcome $o_i \in \mathbb{R}$. This outcome is obtained by performing a single-shot measurement (the projective measurement given by the eigenbasis of $O$)
of observable $O$ on the output quantum state
$\mathcal{E}(\lvert x_i \rangle \! \langle x_i \rvert)$.
This ensures

\begin{equation}
\E[o_i] = \Tr(O \mathcal{E}(\lvert x_i \rangle \! \langle x_i \rvert) =f_{\cE}(x_i) \quad \text{and, moreover,} \quad \left|o_i \right| \leq 1 \text{ with probability one}, \label{eq:target-fct-thm1}
\end{equation}

because observables are bounded in spectral norm ($\norm{O} \leq 1$).
By using the obtained training data $\{(x_i, o_i)\}_{i}$, the restricted classical ML model will produce a prediction model $h_{\mathrm{C}}(x)$ that allows accurate prediction of $f_{\cE}(x) = \Tr(O \cE(\ketbra{x}{x}))$.
The restricted classical ML model should provide accurate prediction model for any CPTP map $\cE \in \cF$.

§.§.§ Classical machine learning model for a given learning problem

We consider the following classical machine learning model. First, we sample $N$ classical inputs $x_1, \ldots, x_{N}$ according to the distribution $\mathcal{D}$.
Then, we obtain an associated quantum measurement outcome $o_i$ for each input $x_i$.That is, $o_i$ is a random variable that reproduces the target function in expectation only, see Equation (<ref>). We denote the underlying distribution by $\mathcal{D}_o (O,\cE(\ketbra{x_i}{x_i}))$ to delineate dependence on input $x_i$ and CPTP map $\cE$.
After obtaining the training data $\{(x_i, o_i)\}_{i=1}^N$, the model performs the following optimization to minimize the empirical training error

\begin{equation}
f_* = \argmin_{f \in M^p_{4 \epsilon}(\cF_f)} \frac{1}{N} \sum_{i=1}^N |f(x_i) - o_i|^2. \label{eq:training-step}
\end{equation}

Here, $M^p_{4 \epsilon}(\cF_f)$ is the maximal packing net defined in Section <ref>.
The packing net is a subset of the function class $\cF_f$ that contains functions that are sufficiently different from one another.
By “empirical training error” we mean the deviation of the function $f(x_i)$ from the actual measurement outcome $o_i$, averaged over $N$ data points:
$\frac{1}{N} \sum_{i=1}^N |f(x_i) - o_i|^2.$
In the later discussion, we will also refer to the ideal training error, meaning the average deviation of the function $f(x_i)$ from the expectation value $f_{\cE}(x_i) = \Tr(O \cE(\ketbra{x_i}{x_i}))$:
$\frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2.$
This distinction is important; the ideal training error could be close to zero as long as the maximal packing net $M^p_{4 \epsilon}(\cF_f)$ is closely packed, but because of the statistical fluctuation in the quantum measurements, the outcomes $\{o_i\}$ can deviate substantially from the expectation value $f_{\cE}(x_i)$. Therefore we might not be able to achieve small empirical training error even if $f = f_{\cE}$.

In the following, we will provide a tight statistical analysis for bounding the prediction error

\begin{equation}
\E_{x \sim \mathcal{D}} |f_*(x) - f_{\cE}(x)|^2.
\end{equation}

The statistical analysis relies crucially on the distance measure used to define the packing net $M^p_{4 \epsilon}(\cF_f)$.
Recall that this is the average squared distance over the input distribution $\mathcal{D}$, and the statistical fluctuation in performing quantum measurements to obtain $o_i$, see Equation (<ref>).
In particular, we will show that a data size of $N = \Theta(\log(|M^p_{4 \epsilon}(\cF_f)|) / \epsilon)$ suffices to achieve prediction errors of order $\mathcal{O}(\epsilon)$ only.

We find it worthwhile to point out that this scaling is better than one might expect.
Standard results in statistical learning theory [11, 63] usually yield a data size of order $\log(|M^p_{4 \epsilon}(\cF_f)|) / \epsilon^2$, which is worse than our result by an additional $1/\epsilon$ factor.

§.§.§ Concentration results I: Ideal training error

We begin by considering the concentration of the ideal training error for an arbitrary function $f$ from the maximal packing net $M^p_{4 \epsilon}(\cF_f)$:

\begin{equation}
\frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2,
\end{equation}

which only depends on the inputs $x_1, \ldots, x_N$ and is independent of the observable measurement outcome $o_i$.
We use the quantifier ideal because we compare directly with the expectation value $f_{\cE}(x_i)$ rather than the measurement outcome $o_i$.

As a first step, view $\left|f(x) - f_{\cE}(x) \right|^2$ with $x \overset{\mathcal{D}}{\sim} \left\{0,1\right\}^n$ as a random variable. It is easy to check that this random variable is bounded: $\left|f(x)-f_{\cE} (x)\right|^2 \leq (|f(x)| + |f_{\cE} (x)|)^2 \leq 4$ for all $x \in \left\{0,1\right\}^n$. This implies the following bound on the variance:

\begin{align}
\Var[|f(x) - f_{\cE}(x)|^2]
\leq \E_{x \sim \mathcal{D}}|f(x) - f_{\cE}(x)|^4
%\leq \max_{x \in \left\{0,1\right\}^n}|f(x) - f_{\cE}(x)|^2 \E_{x \sim \mathcal{D}}|f(x) - f_{\cE}(x)|^2
\leq 4 \E_{x \sim \mathcal{D}}|f(x) - f_{\cE}(x)|^2.
\end{align}

Bernstein's inequality is a powerful concentration bound that controls sums of independent random variables that have small variance and are also bounded. According to the above argument, $\left|f(x)-f_{\cE}(x)\right|^2$ has both properties. For $t>0$, Bernstein's inequality implies

\begin{align}
\mathrm{Pr} \left[
\left| \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2
- \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right| \geq t \right]
\leq 2 \exp\left( - \frac{1}{2} \frac{N t^2}{ 4 \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 + \frac{8}{3} t} \right). %\quad \text{for $t >0$}.
\end{align}

Assigning $t = \frac{1}{4} \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2$ allows us to conclude

\begin{align}
&\mathrm{Pr} \left[
\left| \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2
- \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right| \geq \frac{1}{4} \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right]\\
\leq & 2 \exp\left( - \frac{3}{448} N \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right)
\end{align}

On the other hand, if
$\E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \leq 4 \epsilon$, we instead assign $t = \epsilon$ to obtain

\begin{align}
&\mathrm{Pr} \left[
\left| \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2
- \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right| \geq \epsilon \right]
\leq 2 \exp\left( - \frac{3}{112} N \epsilon \right).
\end{align}

These two tail bounds (that cover different regimes) and a union bound then imply

\begin{align}
&\mathrm{Pr} \left[ \forall f \in M^p_{4 \epsilon}(\cF_f),
\left| \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2
- \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right| \geq \frac{1}{4} \max\left(4 \epsilon, \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right) \right] \nonumber\\
\leq & 2 \sum_{f \in M^p_{4 \epsilon}(\cF_f)} \exp\left( - \frac{3}{448} N \max\left(4 \epsilon, \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right) \right)
\leq  2 \left|M^p_{4 \epsilon}(\cF_f)\right| \exp\left( - \frac{3}{112} N \epsilon \right).
\end{align}

Intuitively, this can be understood as follows.
The functions $f$ close to $f_{\cE}$ will be distorted by at most $\epsilon$, while the functions $f$ that are further away from $f_{\cE}$ will be distorted by a value proportional to the distance $\E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2$.
For $\delta \in (0,1)$ (confidence), we set

\begin{equation} \label{eq:cmlNbound}
N \geq \frac{38 \log(2 \left|M^p_{4 \epsilon}(\cF_f)\right|/ \delta)}{\epsilon}.
\end{equation}

(Throughout this paper, $\log$ has base $\mathrm{e}$ unless otherwise indicated.)
Then, with probability at least $1 - \delta$, we have

\begin{equation} \label{eq:fluc-f-fcE}
\forall f \in M^p_{4 \epsilon}(\cF_f),
\left| \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2
- \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right| < \frac{1}{4} \max\left(4 \epsilon, \E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \right).
\end{equation}

We note that the training data size $N$ in Equation (<ref>) scales as $1 / \epsilon$ rather than $1 / \epsilon^2$, an improvement over the standard scaling typically encountered in
statistical learning theory [11, 63].
The $1 / \epsilon^2$ comes naturally when we sample over the different inputs $x_i$ and apply a concentration inequality on the ideal training error $\frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2$ to guarantee an  $\mathcal{O}(\epsilon)$ statistical fluctuation around the prediction error $\E_{x \sim \cD} |f(x) - f_{\cE}(x)|^2$.
The main reason for the improved scaling is that any function $f$ with a small prediction error $\E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 \leq 4 \epsilon$ also has a small variance (e.g., a highly biased coin that almost always come out heads has a variance close to zero, which is much smaller than for an unbiased coin), so we need only $N=\mathcal{O}(1/\epsilon)$ to achieve $\mathcal{O}(\epsilon)$ statistical fluctuations. Furthermore, by examining Equation (<ref>), we see that if function $f$  has a large prediction error then the statistical fluctuations in the training data may also be large.
This is a price we pay to avoid a training set with size $N$ scaling as $1/\epsilon^2$.
The increased statistical fluctuations for a function $f$ with a large prediction error are not problematic, because the statistical fluctuation are still smaller than the prediction error in that case.
We find that functions with small prediction error have small ideal training error, while functions with large prediction error have large ideal training error, which is adequate for our purposes.

We condition on the event that the display Equation (<ref>) holds true and proceed to the second step.

§.§.§ Concentration results II: Shifted empirical training error

In the second step, we will condition on a set of inputs $x_1, \ldots, x_N$ and study the concentration of statistical fluctuations in the observable measurement outcome $o_i$.
Let us define a new quantity, which we call the shifted empirical training error:

\begin{equation}
\frac{1}{N} \sum_{i=1}^N \left[ |f(x_i) - o_i|^2 - |f_{\cE}(x_i) - o_i|^2 \right],
\end{equation}

where $f$ can be any function in the packing net $M^p_{4 \epsilon}(\cF_f)$.

The expectation value of the shifted empirical training error can be computed by means of direct expansion.
Recall that $\E_{o \sim \mathcal{D}_o(O, \mathcal{E}(\lvert x_i \rangle \! \langle x_i \rvert))} [o] = f_{\cE}(x_i)$.
This yields

\begin{equation}
\E_{\substack{o \sim \mathcal{D}_o(O, \mathcal{E}(\lvert x_i \rangle \! \langle x_i \rvert))}} |f(x_i) - o|^2 - |f_{\cE}(x_i) - o|^2 = |f(x_i) - f_{\cE}(x_i)|^2,
\end{equation}

and for fixed input $x_i$, we can also bound the variance:

\begin{align}
\Var_{o \sim \mathcal{D}_o(O, \mathcal{E}(\lvert x_i \rangle \! \langle x_i \rvert))} |f(x_i) - o|^2 - |f_{\cE}(x_i) - o|^2 &= \E_{\substack{o \sim \mathcal{D}_o(O, \mathcal{E}(\lvert x_i \rangle \! \langle x_i \rvert))}} 4 (f(x_i) - f_{\cE}(x_i))^2 (o - f_{\cE}(x_i))^2\\
&=  4 (f(x_i) - f_{\cE}(x_i))^2 \Var_{o \sim \mathcal{D}_o(O, \mathcal{E}(\lvert x_i \rangle \! \langle x_i \rvert))}[o] \\
&\leq  4 |f(x_i) - f_{\cE}(x_i)|^2.
\end{align}

The last inequality uses $o\sim \mathcal{D}_o(O, \mathcal{E}(\lvert x_i \rangle \! \langle x_i \rvert))$ which lies within $[-1, 1]$ with probability one. This is due to the assumption that $\norm{O} \leq 1$.
Now, we can capitalize on the fact that $o_1, \ldots, o_N$ are independent and bounded random variables whose variance is also small. Bernstein's inequality implies

\begin{align}
&\mathrm{Pr} \left[
\left| \frac{1}{N} \sum_{i=1}^N \left[ |f(x_i) - o_i|^2 - |f_{\cE}(x_i) - o_i|^2 \right]
- \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 \right| \geq t \right]\\
\leq &2 \exp\left( - \frac{1}{2} \frac{N t^2}{\frac{4}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 + \frac{8}{3} t} \right) \quad \text{for $t >0$}.
\end{align}

Assigning $t = \frac{1}{4N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2$ ensures

\begin{align}
&\mathrm{Pr} \left[
\left| \frac{1}{N} \sum_{i=1}^N \left[ |f(x_i) - o_i|^2 - |f_{\cE}(x_i) - o_i|^2 \right]
- \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 ] \right| \geq \frac{1}{4N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 \right]\\
\leq & 2 \exp\left( - \frac{3}{448} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 \right). \label{eq:foconc-large}
\end{align}

If $\frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 \leq 4 \epsilon$, we instead assign $t = \epsilon$ to obtain

\begin{align}
\mathrm{Pr} \left[
\left| \frac{1}{N} \sum_{i=1}^N \left[ |f(x_i) - o_i|^2 - |f_{\cE}(x_i) - o_i|^2 \right]
- \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 ] \right| \geq \epsilon \right]
\leq 2 \exp\left( - \frac{3}{112} N \epsilon \right). \label{eq:foconc-small}
\end{align}

These results are conditioned on $x_1, \ldots, x_N$ already being sampled (the result of first step) where the event given in Equation (<ref>) holds.

§.§.§ Prediction error for functions in the maximal packing net

Before bounding the prediction error of $f_\star$ obtained by the restricted classical ML model, we need to show that the following events happen simultaneously with high probability.

* There exists a function $\tilde{f} \in M^p_{4 \epsilon}(\cF_f)$ with small prediction error that results in an empirical training error that is upper bounded by a certain threshold.
In particular, we will set out to show that

\begin{equation}
\frac{1}{N} \sum_{i=1}^N |\tilde{f}(x_i) - o_i|^2 \leq \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{25}{4} \epsilon.
\label{eq:classical-ML-aux2}
\end{equation}

We refer to this as Event $1$.

* All functions $f \in M^p_{4 \epsilon}(\cF_f)$ that have a large prediction error will result in an empirical training error lower bounded by a certain threshold.
In particular, we define the event to be: for all models $f \in M^p_{4 \epsilon}(\cF_f)$ such that $\E_{x \sim D} |f(x) - f_{\cE}(x)|^2 \geq 12 \epsilon$ will have:

\begin{equation}
\frac{1}{N} \sum_{i=1}^N |f(x_i) - o_i|^2  \geq \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{27}{4} \epsilon.
\label{eq:classical-ML-aux1}
\end{equation}

We refer to this as Event $2$.

Then, we can combine these statements to obtain a bound on the prediction error of $f_\star$. Let us first relate the packing net to another useful concept.

For all $f_{\cE} \in \cF_f$, there exists $\tilde{f} \in M^p_{4 \epsilon}(\cF_f)$, such that

\begin{equation}
\E_{x \sim D} |f(x) - f_{\cE}(x)|^2 \leq 4 \epsilon.
\end{equation}

The proof is standard, see e.g. [80], and based on contradicting the assumption that $M^p_{4\epsilon}(\cF_f)$ is a maximal packing net. Since it is short and insightful, we include the full proof for completeness.

If there exists $f_{\cE} \in \cF$, such that for all $\tilde{f} \in M^p_{4 \epsilon}(\cF_f)$, we have

\begin{equation}
\E_{x \sim \mathcal{D}} |f(x) - f_{\cE}(x)|^2 > 4 \epsilon,
\end{equation}

then we can add $f_{\cE}$ into the packing net $M^p_{4 \epsilon}(\cF_f)$. Hence $M^p_{4 \epsilon}(\cF_f)$ is not the maximal packing net.

For Event 1 in Equation (<ref>), we want to show the existence of a function $\tilde{f}$ that has a small prediction error as well as an empirical training error upper bounded by a threshold.
Because $M^p_{4 \epsilon}(\cF_f)$ is a maximal packing net, using Lemma <ref>, there exists a function $\tilde{f}$ such that the prediction error

\begin{equation}
\E_{x \sim D} |\tilde{f}(x) - f_{\cE}(x)|^2 \leq 4 \epsilon.
\end{equation}

We now condition on Equation (<ref>) being true, which happens with probability at least $1-\delta$.
Therefore, we have the following bound on the ideal training error

\begin{equation} \label{eq:emppredicerr-5/4}
\frac{1}{N} \sum_{i=1}^N |\tilde{f}(x_i) - f_{\cE}(x_i)|^2 \leq 5 \epsilon.
\end{equation}

We can now use this insight to control the shifted empirical training error. Use a combination of Eqs. (<ref>) and (<ref>) to conclude

\begin{align}
&\mathrm{Pr} \left[
\left| \frac{1}{N} \sum_{i=1}^N \left[ |\tilde{f}(x_i) - o_i|^2 - |f_{\cE}(x_i) - o_i|^2 \right]
- \frac{1}{N} \sum_{i=1}^N |\tilde{f}(x_i) - f_{\cE}(x_i)|^2 ] \right| \geq \frac{5}{4} \epsilon \right] \\
\leq & 2 \exp\left( - \frac{3}{112} N \epsilon \right) \leq \frac{\delta}{|M^p_{4 \epsilon}(\cF_f)|}.
\end{align}

The first inequality comes from separately analyzing the two cases: $\frac{1}{N} \sum_{i=1}^N |\tilde{f}(x_i) - f_{\cE}(x_i)|^2 \leq 4 \epsilon$ or $4 \epsilon < \frac{1}{N} \sum_{i=1}^N |\tilde{f}(x_i) - f_{\cE}(x_i)|^2 \leq 5 \epsilon$, then take the looser statement.
The second inequality arises from inserting the (lower bound) on training data size $N$ from Equation (<ref>).
Therefore, if the display from Equation (<ref>) is true (which happens with probability at least $1-\delta$), then

\begin{align}
\frac{1}{N} \sum_{i=1}^N |\tilde{f}(x_i) - o_i|^2 &\leq \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{1}{N} \sum_{i=1}^N |\tilde{f}(x_i) - f_{\cE}(x_i)|^2 + \frac{5}{4} \epsilon\\
&\leq \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{25}{4} \epsilon \quad \text{with probability at least $1 - \delta / |M^p_{4 \epsilon}(\cF_f)|$}.
\end{align}

The second inequality is contingent on using Equation (<ref>).
This is Event $1$ that we have set out to establish. And it is guaranteed to happen with high probability.

We now move on to Event $2$ given in Equation (<ref>). For any $f \in M^p_{4 \epsilon}(\cF_f)$ with a large prediction error

\begin{equation}
\E_{x \sim D} |f(x) - f_{\cE}(x)|^2 \geq 12 \epsilon,
\end{equation}

we want to show that the training error $\frac{1}{N} \sum_{i=1}^N |f(x_i) - o_i|^2$ will also be large.
We again condition on the event displayed by Equation (<ref>) (which happens with probability at least $1-\delta$).
This relation implies the following bound on the ideal training error

\begin{equation}
\frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 \geq \frac{3}{4} \E_{x \sim D} |f(x) - f_{\cE}(x)|^2 \geq 9 \epsilon.
\end{equation}

Using the concentration result from Equation (<ref>), we have

\begin{align}
&\mathrm{Pr} \left[
\left| \frac{1}{N} \sum_{i=1}^N \left[ |f(x_i) - o_i|^2 - |f_{\cE}(x_i) - o_i|^2 \right]
- \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 ] \right| \geq \frac{1}{4N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 \right]\\
&\leq 2 \exp\left( - \frac{3}{448} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2 \right) \leq 2 \exp\left( - \frac{3}{448} N \left(9 \epsilon\right) \right) \leq \frac{\delta}{|M^p_{4 \epsilon}(\cF_f)|}.
\end{align}

The last inequality uses the training data size bound from Equation (<ref>).
This ensures

\begin{align}
\frac{1}{N} \sum_{i=1}^N |f(x_i) - o_i|^2 &\geq \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{3}{4} \frac{1}{N} \sum_{i=1}^N |f(x_i) - f_{\cE}(x_i)|^2\\
&\geq \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{9}{16} \E_{x \sim D} |f(x) - f_{\cE}(x)|^2\\
&\geq \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{27}{4} \epsilon \quad \text{with probability at least $1 - \delta / |M^p_{4 \epsilon}(\cF_f)|$}.
\end{align}

We can combine these insights by applying union bound to obtain that all the desired events given in Equation (<ref>) and (<ref>) happen simultaneously with probability at least $1 - \delta$ if we condition on Equation (<ref>) to be true.
Furthermore, because the event in display (<ref>) happens with probability $1 - \delta$, we can guarantee that the the desired events given in Equation (<ref>) and (<ref>) happen simultaneously with a probability at least $(1 - \delta)^2 \geq 1 - 2 \delta$. This statement uses the following basic fact from elementary probability theory:
Let $p({A|B})$ be the probability of event $A$ when we condition on event $B$. And let $p(B)$ be the probability of event $B$. Then the probability of event $A$, $p(A)$, is larger or equal to the probability that $A, B$ both happens, $p(A, B) = p(A|B) p(B)$.

To conclude, we have shown that using a training data of size $N\geq 38 \log(2 \left|M^p_{4 \epsilon}(\cF_f)\right|/ \delta) / \epsilon$ guarantees that the relations given in Equation (<ref>) and (<ref>) happen with probability at least $1 - 2 \delta$.

§.§.§ Prediction error for functions produced by restricted classical ML

Let us choose a data of size $N \geq 38 \log(4 \left|M^p_{4 \epsilon}(\cF_f)\right|/ \delta) / \epsilon$ such that the two relations in Equation (<ref>) and (<ref>) are both true with probability $1-\delta$. We now combine these with two other concepts from the previous subsections.
Let $f_{\cE}(x)$ be the actual target function and recall that (at least) one packing net element $\tilde{f} \in M^p_{4 \epsilon}(\cF_f)$ is guaranteed to be close ($\E_{x \sim \mathcal{D}} | \tilde{f}(x) - f_{\cE} (x) |^2 \leq 4 \epsilon$ according to Lemma <ref>).
The restricted classical ML model tries to identify such a packing net element by minimizing the empirical training error: $f_* = \argmin_{f \in M^p_{4 \epsilon}(\cF_f)} \frac{1}{N} \sum_{i=1}^N |f(x_i) - o_i|^2$ according to Equation (<ref>).
This setup ensures

\begin{align}
\frac{1}{N} \sum_{i=1}^N |f_*(x_i) - o_i|^2
= \min_{f \in M^{p}_{4\epsilon} (\cF_f)} \frac{1}{N} \sum_{i=1}^N |f(x_i) - o_i|^2
\leq \frac{1}{N} \sum_{i=1}^n \left|\tilde{f} (x_i) - o_i \right|^2.
\end{align}

The first relation in Equation (<ref>) allows us to take it from there. Indeed,

\begin{align*}
\frac{1}{N} \sum_{i=1}^n \left|\tilde{f} (x_i) - o_i \right|^2
\leq \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{25}{4} \epsilon
< \frac{1}{N} \sum_{i=1}^N |f_{\cE}(x_i) - o_i|^2 + \frac{27}{4} \epsilon
\end{align*}

where the strict inequality is completely trivial. Apply the second relation in Equation (<ref>) to complete the chain of arguments:

\begin{align}
\frac{1}{N} \sum_{i=1}^N |f_*(x_i) - o_i|^2 <
\min_{f \in M_{4\epsilon}^p (\cF_f):\; \E_{x \sim \mathcal{D}}|f(x)-f_{\cE}(x)|^2 \geq 12 \epsilon}
\frac{1}{N} \sum_{i=1}^N \left| f(x_i) - o_i \right|^2.
\end{align}

In words, this display implies that the empirical training error achieved by $f_*$ – the output of the restricted classical ML model – is strictly smaller than any empirical training error that could be achieved by any packing net function that has a comparatively large prediction error (at least $12 \epsilon$).
Therefore if $f_*$ has a prediction error of at least $12 \epsilon$, then this leads to a contradiction that $\frac{1}{N} \sum_{i=1}^N |f_*(x_i) - o_i|^2 < \frac{1}{N} \sum_{i=1}^N |f_*(x_i) - o_i|^2$.
By contradiction, this claim implies that the prediction error achieved by $f_*$ cannot be too bad. We obtain:

Let $f_*: \left\{0,1\right\}^n \to \mathbb{R}$ be the packing net element that minimizes the empirical training error in Equation (<ref>). Then, for $\delta \in (0,1)$, training data of size $N \geq 38 \log(4 \left|M^p_{4 \epsilon}(\cF_f)\right|/ \delta) / \epsilon$ implies:

\begin{equation}
\E_{x \sim \mathcal{D}} |f^*(x) - f_{\cE}(x)|^2
< 12 \epsilon \quad \text{with probability at least $1-\delta$.}
\end{equation}

§.§ Combining the upper and lower bound

If a quantum ML model produces a prediction $h_{\mathrm{Q}}$ achieving average prediction error

\begin{equation}
\E_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}}(x) - \Tr(O \mathcal{E}(\lvert x \rangle \! \langle x \rvert)) \right|^2 \leq \epsilon,
\end{equation}

with probability at least $2/3$ for any CPTP map $\mathcal{E} \in \cF$, then,
as proven in Equation (<ref>), the quantum ML must access the map $\cE$ at least $N_{\mathrm{Q}}$ times, where

\begin{equation}
N_{\mathrm{Q}} =\Omega\left(\frac{\log(|M^p_{4\epsilon}(\cF_f)|)}{m}\right).
\end{equation}

On the other hand, from Proposition <ref>, we know there is a restricted classical ML model producing prediction $h_{\mathrm{C}}$ achieving average prediction error

\begin{equation}
\E_{x \sim \mathcal{D}} \left| h_{\mathrm{C}}(x) - \Tr(O \mathcal{E}(\lvert x \rangle \! \langle x \rvert)) \right|^2 \leq 12 \epsilon = \mathcal{O}(\epsilon),
\end{equation}

with high probability for any CPTP map $\cE \in \cF$, such that the restricted classical ML accesses the map $N_{\mathrm{C}}$ times, where

\begin{equation}
% N_{\mathrm{C}} = \mathcal{O}\left( \frac{\log(|M_{4\epsilon}(\cF_f)|)}{\epsilon}\right) \leq \mathcal{O}\left( \frac{\log(|M^p_{4\epsilon}(\cF_f)|)}{\epsilon}\right) \leq \mathcal{O}\left( \frac{m N_{\mathrm{Q}}}{\epsilon} \right)
N_{\mathrm{C}} = \mathcal{O}\left( \frac{\log(|M^p_{4\epsilon}(\cF_f)|)}{\epsilon}\right) = \mathcal{O}\left( \frac{m N_{\mathrm{Q}}}{\epsilon} \right)
\end{equation}

This concludes the proof of Theorem <ref>.

§ EXAMPLES SATURATING THE MAXIMUM INFORMATION-THEORETIC ADVANTAGE

For any $\epsilon \in (0,1/3)$, and positive integer $m$, there exists a learning problem (<ref>)
– specified by an $m$-qubit observable $O$, a family $\mathcal{F}$ of CPTP maps and a distribution $\mathcal{D}$ on $n$-bit inputs, where $n=m{-}1$, – with the following property:

Any restricted classical ML model that can learn a function $h_{\mathrm{C}}(x)$ that achieves

\begin{equation}
\E_{x \sim \mathcal{D}} \left| h_{\mathrm{C}}(x) - \Tr(O \mathcal{E}(\ketbra{x}{x})) \right|^2 \leq \epsilon,
\end{equation}

must use classical training data of size $N_{\mathrm{C}} = \Omega(m N_{\mathrm{Q}} / \epsilon)$, where $N_{\mathrm{Q}}$ is the number of queries in the best quantum ML model.

This statement follows from constructing a stylized learning problem that admits the largest possible separation (albeit only a small polynomial factor). We first introduce the problem and discuss quantum and classical strategies (and their limitations) afterwards. We will focus on restricted classical ML models because Theorem <ref> also considers restricted classical ML models.
We leave open the question of whether the separation between unrestricted classical ML and quantum ML is tight or not.

Learning problem formulation
Fix $\epsilon \in (0,1/3)$ and an integer $n$, where $m=n{+}1$ is the integer in the statement of Proposition <ref>.

We consider a family of CPTP maps $\mathcal{F}=\left\{ \mathcal{E}_{a}:\; a \in \left\{0,1\right\}^{n}\right\}$ containing $2^{n}$ elements, where each map in the family takes an $n$-qubit input to an $(n{+}1)$-qubit output.
The map $\mathcal{E}_a$, labeled by bit string $a \in \left\{0,1\right\}^{n}$, is comprised of $2 \times 2^{n}$ Kraus operators:

\begin{equation}
\mathcal{E}_{a}(\rho)
= \sum_{z \in \left\{0,1\right\}^{n}}
\sum_{i=1}^2 K^{z,i}_{a}\rho (K^{z,i}_{a})^\dagger
\quad \text{with} \quad
\begin{cases}
K_{a}^{z,1} =& \sqrt{\tfrac{1+\sqrt{3 \epsilon}}{2}} (I \otimes I^{\otimes n})|a \odot z,a \rangle \! \langle z|, \\
K_{a}^{z,2} =& \sqrt{\tfrac{1-\sqrt{3 \epsilon}}{2}} (X \otimes I^{\otimes n})|a \odot z,a \rangle \! \langle z|.
\end{cases}
\label{eq:function-class}
\end{equation}

Here, $X$ is a single-qubit bit flip and
$a \odot z \in \left\{0,1\right\}$ denotes the inner product of bit-strings in $\mathbb{Z}_2$.
We also choose the $(n{+}1)$-qubit observable
$O= Z \otimes I^{\otimes n}$, i.e. we measure the first qubit in the $Z$-basis and trace out the rest of the system. By construction, the resulting function
admits a closed-form expression:

\begin{equation}
f_a (x) = \Tr \left( O \cE_{a} (\ketbra{x}{x}) \right)
\sqrt{3 \epsilon}\left( 1- 2 a \odot x \right).
\label{eq:closed-form-expression}
\end{equation}

We consider $\cD$ to be the uniform distribution over the $n$-bit inputs.

Upper bound on the quantum query complexity

The above learning problem is exceedingly easy to solve in the quantum realm. Since the function class $\mathcal{F} = \left\{ \mathcal{E}_a:\; a \in \left\{0,1\right\}^{n}\right\}$
is known, it suffices to extract the label $a \in \left\{0,1\right\}^{n}$ of the underlying CPTP map. Once $a$ is known, the closed-form expression (<ref>) allows to predict future function values $f_a (x)$ efficiently with perfect accuracy – regardless of the input $x \in \left\{0,1\right\}^n$.

Quantum computers are very well equipped to extract the label $a$. In fact, a single query of the unknown CPTP map $\mathcal{E}_a$ suffices to extract the label by executing the following simple procedure:

* prepare the all-zero state on $n$ qubits: $\rho_0 = |0,\ldots,0 \rangle \! \langle 0,\ldots,0|$;

* query $\mathcal{E}$ and apply it to $\rho_0$: $\rho_1 = \tfrac{1}{2} (I + \sqrt{3 \epsilon} Z ) \otimes |a \rangle \! \langle a|$, according to Equation (<ref>);

* throw away (trace out) the first qubit to obtain the $n$ remaining ones: $\rho_2 = |a \rangle \! \langle a|$;

* perform a computational basis measurement to extact $a \in \left\{0,1\right\}^{n}$ with probability one.

We see that a single quantum
query ($N_{\mathrm{Q}}=1$) suffices to extract the label $a$ with certainty. Subsequently, we can make efficient and perfect predictions via the closed-form expression (<ref>):

\begin{equation}
\mathbb{E}_{x \sim \mathcal{D}} \left| h_{\mathrm{Q}}(x)-\Tr \left( O \cE_a (\ketbra{x}{x}) \right) \right|^2 =0 \leq \epsilon \quad \Leftarrow \quad N_{\mathrm{Q}} =1. \label{eq:explicit-quantum-bound}
\end{equation}

In words, $N_{\mathrm{Q}}=1$ allows for training a quantum ML model $h_{\mathrm{Q}}(x)$ that achieves zero prediction error
for all input distributions (perfect prediction).
This concrete ML model is also optimal, because $N_{\mathrm{Q}}=1$ is the smallest number of queries conceivable ($N_{\mathrm{Q}}=0$ would not reveal any information about the underlying CPTP map).

Lower bound on the classical query complexity

Let us now turn to potential classical strategies for solving the above learning problem. In contrast to the previous paragraph, we will not construct an explicit strategy. Instead, we will use ideas similar to Appendix <ref> to establish a fundamental lower bound.

Recall that the input distribution $\cD$ is taken to be the uniform distribution.
Also, for each $\cE_a \in \cF$, the underlying function $f_a (x) = \Tr \left(O\mathcal{E}_a (\ketbra{x}{x})\right)$ admits a closed form expression, see Equation (<ref>).
For $a,b \in \left\{0,1\right\}^{n}$,

\begin{align}
\E_{x \sim \mathcal{D}} \left|f_a (x) - f_b (x) \right|^2
\frac{1}{2^{n}}\sum_{x \in \left\{0,1\right\}^{n}}  \left| \sqrt{3 \epsilon} 2 (a - b) \odot x \right|^2 %\\
= \begin{cases}
0 & \text{if $a=b$}, \\
6 \epsilon& \text{else},
\end{cases}
\end{align}

because $2^{-n}\sum_{x \in \left\{0,1\right\}^{n}} \left|c \odot x \right|^2 = 1/2$ for all $n$-bit strings $c \neq (0,\ldots,0)$.
Now, suppose that a restricted classical ML model can utilize training data $\mathcal{T}=\left\{(x_i,o_i)\right\}_{i=1}^{N_{\mathrm{C}}}$ to learn a function $h_{\mathrm{C}}(x)$ that obeys $\E_{x \sim \mathcal{D}} \left|h_{\mathrm{C}} (x) - \Tr \left(O \cE_a (\ketbra{x}{x})\right) \right|^2 \leq \epsilon$ with high probability for any label $a \in \left\{0,1\right\}^{n}$.
Then, this model would also allow us to identify the underlying label.
Indeed $\E_{x \sim \mathcal{D}} \left|h_{\mathrm{C}} (x) - f_b  \right|^2 \leq \epsilon$ if $b=a$, while for $b \neq a$, by the triangle inequality,

\begin{equation}\label{eq:triangle-distinguish}
\E_{x \sim \mathcal{D}} \left|h_{\mathrm{C}} (x) - f_b(x)  \right|^2
\geq \Big(\sqrt{\E_{x \sim \mathcal{D}} \left|f_a (x) - f_b (x) \right|^2}
- \sqrt{\E_{x \sim \mathcal{D}} \left|h_{\mathrm{C}} (x) - f_a (x) \right|^2} \Big)^2
\geq \left(\sqrt{6 \epsilon} - \sqrt{\epsilon}\right)^2 %= (\sqrt{6}-1)^2 \epsilon
> \epsilon.
\end{equation}

By checking $\E_{x \sim D} \left|h_{\mathrm{C}}(x)-f_b (x)\right|^2 \leq \epsilon$ for every possible value $b \in \left\{0,1\right\}^n$, the restricted classical ML model allows us to recover the underlying bit-string label $a \in \left\{0,1\right\}^{n}$
with high probability. For this part of the argument, what's essential is that the right-hand-side of the inequality Equation (<ref>) is greater than $\epsilon$. If we replace $3\epsilon$ in Equation (<ref>) by $\alpha \epsilon$, where $\alpha$ is a constant, we require $\sqrt{2\alpha} - 1> 1$, or $\alpha > 2$. We chose $\alpha = 3$ merely for convenience.

For any random hidden bitstring $a \in \{0, 1\}^n$, we can use the restricted classical ML to obtain the training data $\{(x_i, o_i)\}_{i=1}^{N_{\mathrm{C}}}$ and determine the underlying bitstring $a$.
We assume that the restricted classical ML first query $x_1$ obtains $o_1$, then query $x_2$ obtains $o_2$, and so on.
We also have

\begin{equation}
o_i =
\begin{cases}
+ 1& \text{with probability } p_+=\frac{1}{2} \left( 1 + \sqrt{3 \epsilon} \left(1- 2 a \odot x_i \right) \right), \\
-1 &  \text{with probability } p_-=\frac{1}{2} \left( 1- \sqrt{3 \epsilon} \left(1- 2 a \odot x_i \right) \right),
\end{cases}
\label{eq:measurement-outcome}
\end{equation}

which is a single-shot outcome for measuring the observable $O$ on the state $\cE_a (\ketbra{x_i}{x_i})$ in the eigenbasis of $O=Z \otimes I^{\otimes n}$.
Because we can use the training data $\{(x_i, o_i)\}_{i=1}^{N_{\mathrm{C}}}$ to determine $a$ with high probability (by the assumption of the restricted classical ML model), Fano's inequality and the data processing inequality then imply a bound on the mutual information between the training data and the CPTP map label $a$:

\begin{equation}
I \big( a: \left\{ (x_i,o_i) \right\}_{i=1}^{N_{\mathrm{C}}} \big) = \Omega(n).
\label{eq:classical-aux1}
\end{equation}

Next, using chain rule of mutual information based on conditional mutual information, we have

\begin{equation}
I \big( a: \left\{ (x_i,o_i) \right\}_{i=1}^{N_{\mathrm{C}}} \big)
= \sum_{i=1}^{N_{\mathrm{C}}} I (a: (x_i,o_i) | \{(x_j, o_j)\}_{j=1}^{i-1}) = \sum_{i=1}^{N_{\mathrm{C}}} I (a: o_i | \{(x_j, o_j)\}_{j=1}^{i-1}, x_i).
\label{eq:classical-aux2}
\end{equation}

The second equality follows from the fact that $x_i$ is chosen by the restricted classical ML using only the information of $\{(x_j, o_j)\}_{j=1}^{i-1}$, hence the input $x_i$ does not provide any additional information about $a$, i.e., $I(a : x_i | \{(x_j, o_j)\}_{j=1}^{i-1}) = 0$. We now upper bound each term:

\begin{equation}
I (a: o_i | \{(x_j, o_j)\}_{j=1}^{i-1}, x_i) = H(o_i | \{(x_j, o_j)\}_{j=1}^{i-1}, x_i) - H(o_i | \{(x_j, o_j)\}_{j=1}^{i-1}, x_i, a)
\end{equation}

Because $o_i$ is a two-outcome random variable, $H(o_i | \{(x_j, o_j)\}_{j=1}^{i-1}, x_i) \leq H(o_i) \leq \log_2(2)$.
We now consider the distribution of $o_i$ when we condition on
$\{(x_j, o_j)\}_{j=1}^{i-1}, x_i, a$.
A closer inspection of Equation (<ref>) reveals that the probability of one outcome is $p=\tfrac{1}{2} \left( 1 + \sqrt{3 \epsilon} \right)$ and the other is $1-p$ (the value $a \odot x_i \in \left\{0,1\right\}$ only ever permutes the outcome sign). This ensures

\begin{equation}
H(o_i | \{(x_j, o_j)\}_{j=1}^{i-1}, x_i, a) = -p \log_2 (p) - (1-p) \log_2 (1-p) \geq \log_2 (2) - (2p-1)^2,
\end{equation}

and we conclude

\begin{equation}
I (a: o_i | \{(x_j, o_j)\}_{j=1}^{i-1}, x_i) \leq (2p-1)^2 = 3 \epsilon.
\label{eq:classical-aux3}
\end{equation}

Finally, we
combine Eqs. (<ref>), (<ref>) and (<ref>) to conclude

\begin{align*}
%\Omega (m) =
\Omega (n) \leq  I \big( a: \left\{ (x_i,o_i) \right\}_{i=1}^{N_{\mathrm{C}}} \big)
\leq \sum_{i=1}^{N_{\mathrm{C}}} I (a: o_i | \{(x_j, o_j)\}_{j=1}^{i-1}, x_i) \leq 3 \epsilon N_{\mathrm{C}}.
\end{align*}

Therefore, recalling that the output size of our family of maps is $m=n{+}1$, we have for a restricted classical ML model with small average prediction error:

\begin{equation}
\E_{x \sim \mathcal{D}} \left| h_{\mathrm{C}}(x) - \Tr \left( O \cE_a (\ketbra{x}{x}) \right) \right|^2 \leq \epsilon \quad \text{with high probability} \quad \Rightarrow \quad N_{\mathrm{C}} = \Omega \left( m/\epsilon \right).
\end{equation}

Proposition <ref> follows from combining this assertion with the fact that the underlying learning problem does admit a perfect quantum solution with $N_{\mathrm{Q}}=1$, see Equation (<ref>).

§ EXPONENTIAL SEPARATION FOR PREDICTING EXPECTATION VALUES OF PAULI OPERATORS

In this section, we consider an example to demonstrate the existence of exponential information-theoretic quantum advantage when we want to achieve small worst-case prediction error.

§.§ Task description

The learning task is to train an ML model that allows accurate prediction of

\begin{equation}
x \in \{I, X, Y, Z\}^{n} \rightarrow \Tr(P_x \rho),
\end{equation}

where $\rho$ is an unknown $n$-qubit state, $X, Y, Z$ are the single-qubit Pauli operators, and $P_x$ is the tensor product of Pauli operators given by $x$.
This easily fits into the framework described in the main text.
Every unknown quantum state $\rho$ defines an unknown quantum channel $\cE_\rho$.
The unknown quantum channel $\cE_\rho$ takes a classical input $x \in \{I, X, Y, Z\}^n$, prepares the unknown quantum state $\rho$, and rotates the quantum state $\rho$ according to the input $x$ such that a Pauli-Z measurement on the first qubit is equivalent to measuring $P_x$ on $\rho$.
More precisely, we define

\begin{equation}
\cE_\rho(\ketbra{x}{y}) = \delta_{x, y} C_x^\dagger \rho C_x,
\end{equation}

where $\ket{x}$ is an encoding of the classical input $x$ (e.g., as a $2n$-qubit computational basis state), $C_x$ is a Clifford unitary that satisfies

\begin{equation}
C_x Z_1 C_x^\dagger = P_x,
\end{equation}

and we extend the above definition linearly over the entire space of quantum state space.
The goal of the machine learning model is to produce $f(x)$ such that

\begin{equation}
\max_{x \in \{I, X, Y, Z\}^n} \left| f(x) - \Tr(Z_1 \cE_\rho(\ketbra{x}{x})) \right| \leq \epsilon.
\end{equation}

We consider restricted classical ML models that can only obtain $\{(x_i, o_i)\}$, where $x_i$ are inputs denoting the Pauli operators, and $o_i$ are measurement outcome when measuring $\cE_\rho(\ketbra{x_i}{x_i})$ with $Z_1$, which is equivalent to the measurement outcome of measuring $\rho$ with $P_{x_i}$.
Classical ML models can obtain $\{(x_i, o_i)\}$, where $o_i$ is now the measurement outcome of an arbitrary POVM on the output state $\cE_\rho(\ketbra{x_i}{x_i})$.
Note that for restricted classical ML, $o_i \in \mathbb{R}$, but for classical ML, $o_i$ is in the set indexing the POVM elements $\{F_o\}_o$ with $\sum_o F_o = I$.
Quantum ML models can access the unknown quantum channel $\cE_{\rho}$ at will.
Recall that, according to Theorem <ref>, for achieving a small average prediction error according to any input distribution, no large quantum advantage in sample complexity can be found.

In the following, we will show that to achieve a small worst-case prediction error, an exponential quantum advantage in sample complexity is possible.
In Section <ref>, we give a simple quantum ML algorithm that can accurately predict the expectation values of all $4^n$ Pauli observables using only $\mathcal{O}(n)$ samples.
In Section <ref> and <ref>, we will show that any classical ML algorithm requires at least an exponential number of samples to accurately predict the expectation values of all $4^n$ Pauli observables.
In Section <ref>, we will give a matching lower bound $\Omega(n)$ for quantum ML.

§.§ Sample complexity of a quantum ML algorithm

The quantum ML algorithm accesses the quantum channel $\cE_\rho$ multiple times to obtain multiple copies of the underlying quantum state $\rho$.
Each access to $\cE_\rho$ allows us to obtain one copy of $\rho$.
Then, the quantum ML algorithm performs a sequence of measurements on the copies of $\rho$ to accurately predict $\Tr(P_x \rho)$ for all $x \in \{I, X, Y, Z\}^n$.
To this end, we will give a detailed proof for Theorem <ref> given below.
From Theorem <ref>, we only need $\mathcal{O}(\log(100 \times 4^n) / \epsilon^4) = \mathcal{O}(n / \epsilon^4)$ copies to accurately predict all $4^n$ Pauli operators with probability at least $0.99$.
Hence we only need to access the quantum channel $\cE_\rho$ for $\mathcal{O}(n / \epsilon^4)$ times.

For any $M$ Pauli operators $P_1, \ldots, P_M$, there is a procedure that produces $\hat{p}_1, \ldots, \hat{p}_M$ with

\begin{equation}
\left|\hat{p}_i - \Tr(P_i \rho)\right| \leq \epsilon,\,\, \forall i = 1, \ldots, M,
\end{equation}

under probability at least $1-\delta$ by performing POVM measurements on

\begin{equation}
N = \mathcal{O}\left( \frac{\log(M / \delta)}{\epsilon^4} \right)
\end{equation}

copies of the unknown quantum state $\rho$.

The procedure takes in the Pauli operators one by one and produces the estimate $\hat{p}_i$ sequentially.
Throughout the prediction process, the procedure maintains two blocks of memory:

* Classical memory: We perform $N_1$ repetitions of Bell measurements on two copies of the quantum state $\rho \otimes \rho$. For repetition $t$, we go through every qubit, and measure the $k$-th qubit from the first and second copies in the Bell basis to obtain:

\begin{equation}\label{eq:Bell-basis-meas}
S^{(t)}_k \in \Big\{ \ketbra{\Psi^+}{\Psi^+}, \ketbra{\Psi^-}{\Psi^-}, \ketbra{\Phi^+}{\Phi^+}, \ketbra{\Phi^-}{\Phi^-} \Big\},
\end{equation}

where the Bell basis encompasses four maximally entangled 2-qubit states. Set $\ket{\Omega} = \tfrac{1}{\sqrt{2}} \left( \ket{00}+\ket{11} \right)$ (Bell state) and define

\begin{align*}
\ket{\Psi^+} &= I \otimes I \ket{\Omega}
=\frac{1}{\sqrt{2}} \left( \ket{00} + \ket{11} \right),\\
\ket{\Psi^-} &=   I \otimes Z \ket{\Omega}
= \frac{1}{\sqrt{2}} \left( \ket{00} - \ket{11} \right),\\
\ket{\Phi^+} &= I \otimes X \ket{\Omega}
= \frac{1}{\sqrt{2}} \left( \ket{01} + \ket{10} \right),\\
\ket{\Phi^-} &= \mathrm{i} I \otimes Y \ket{\Omega}
=\frac{1}{\sqrt{2}} \left( \ket{01} - \ket{10} \right).
\end{align*}

We then efficiently store the measurement data $S^{(t)}_k, \forall k = 1, \ldots, n, \forall t = 1, \ldots, N_1$ in a classical memory with $2 nN_1$ bits.
We use this block of memory to estimate $|\Tr(P \rho)|^2$ for any Pauli operator $P$.

* Quantum memory: We store $N_2$ copies of the unknown quantum state $\rho$. We use this block of memory to estimate $\sign(\Tr(P \rho))$ for any Pauli operator $P$.

Consider any tensor product of Pauli operators $P = \sigma_{1} \otimes \ldots \otimes \sigma_{n}$, where $\sigma_k \in \{I, X, Y, Z\}, \forall k = 1, \ldots, n$. The classical memory is used to predict the absolute value of $\Tr(P \rho)$, while the quantum memory is used to predict the sign of $\Tr(P \rho)$. This allows us to obtain an accurate estimate for $\Tr(P \rho)$. The following remark is central to the procedure.

If we find that the absolute value of $\Tr(P \rho)$ is close to zero, then we need not and should not use the quantum memory to predict the sign of $\Tr(P \rho)$. By measuring the sign only for the Pauli observables such that the absolute value of the expectation value is appreciable, we can find the sign for may Pauli observables without badly disturbing the copies of $\rho$ stored in the quantum memory.

We proceed to give a detailed procedure for estimating the absolute value and the sign of $\Tr(P_i \rho)$.

§.§.§ Measuring absolute values

To understand how the absolute value of the expectation of a Pauli operator is estimated, first consider the case where $\rho$ is the density operator of a single qubit, and suppose that $\rho\otimes \rho$ is measured in the Bell basis. The outcome $S$ is the projector onto one of the four Bell states, as in Equation (<ref>). If $\sigma\in \{I,X,Y,Z\}$ is any Pauli matrix, then each Bell state is an eigenstate of $\sigma\otimes\sigma$ with eigenvalue $\pm 1$. In the state $S$, the $+1$ eigenvalue of $\sigma\otimes\sigma$ occurs with probability $\mathrm{Prob}(+) = \frac{1}{2}\Tr\left((I\otimes I+\sigma\otimes\sigma)(\rho\otimes\rho)\right)$, and the $-1$ eigenvalue  occurs with probability $\mathrm{Prob}(-) = \frac{1}{2}\Tr\left((I\otimes I-\sigma\otimes\sigma)(\rho\otimes\rho)\right)$. Therefore,

\begin{equation}
\E\left[\Tr\left((\sigma \otimes \sigma) S\right)\right]
= \mathrm{Prob}(+) - \mathrm{Prob}(-) = \Tr \left((\sigma\otimes\sigma)(\rho\otimes\rho)\right) = |\Tr (\sigma\rho)|^2,
\end{equation}

This observation can be generalized to the case where $\rho$ is an $n$-qubit state, and each pair of qubits in $\rho\otimes \rho$ is measured in the Bell basis, yielding the outcomes $\{S_k, k = 1,2, \dots, n\}$. If $P = \sigma_{1} \otimes \ldots \otimes \sigma_{n}$ is a Pauli observable, then $S_k$ is an eigenstate of $\sigma_k\otimes \sigma_k$ with eigenvalue $\pm 1$ for each $k$, just as in the $n=1$ case; in particular,

\begin{equation}
\prod_{k=1}^n \Tr\left((\sigma_{k} \otimes \sigma_{k}) S_k\right)
=\pm 1.
\end{equation}

This product is $+1$ when  $\otimes_{k=1}^n S_k$ is an eigenstate of $P\otimes P$ with eigenvalue $+1$, and it is $-1$ when  $\otimes_{k=1}^n S_k$ is an eigenstate of $P\otimes P$ with eigenvalue $-1$.

\begin{align}\label{eq:bell-expected}
& \E\left[\prod_{k=1}^n \Tr\left((\sigma_{k} \otimes \sigma_{k}) S_k\right)\right]
=\E\left[ \Tr\left( (P \otimes P) \bigotimes_{k=1}^n S_k \right) \right]\nonumber\\
& = \mathrm{Prob}(P\otimes P =+1) - \mathrm{Prob}(P\otimes P=-1)
=\Tr\left( (P \otimes P) (\rho \otimes \rho) \right)
= |\Tr(P \rho)|^2.
\end{align}

Because Equation (<ref>) relates the distribution of Bell measurement outcomes to $|\Tr(P \rho)|$, we can estimate $|\Tr(P \rho)|$ accurately by repeating Bell measurement on $\rho\otimes\rho$ sufficiently many times. Suppose we have altogether $2N_1$ copies of $\rho$, and perform the Bell measurement on $N_1$ pairs of copies. We collect the measurement data $\{S_k^{(t)}\}$ in the classical memory, where $k=1,2,\dots n$ labels the qubit pairs, and $t=1,2, \dots N_1$ labels the repeated measurements.

For each Pauli observable $P = \sigma_{1} \otimes \ldots \otimes \sigma_{n}$, we define the corresponding expression

\begin{equation}
\hat{a}(P) = \frac{1}{N_1} \sum_{t = 1}^{N_1} \prod_{k=1}^n \Tr\left((\sigma_{k} \otimes \sigma_{k}) S^{(t)}_k\right),
\end{equation}

which can be computed efficiently in time  $\mathcal{O}(nN_1)$.

Using the statistical property given in
Equation (<ref>), we can apply Hoeffding's inequality to
show that, with high probability, the estimate $\hat{a}(P)$ is close to the expectation value $|\Tr(P \rho)|^2$:

Given $N_1 = \Theta(\log(1 / \delta) / \epsilon^2)$. For any Pauli operator $P$, we have

\begin{equation}