# Exponential quantum advantages in learning quantum observables from
classical data

Riccardo Molteni<EMAIL_ADDRESS>applied Quantum algorithms
(aQa), Leiden University, The Netherlands Casper Gyurik
<EMAIL_ADDRESS>applied Quantum algorithms (aQa), Leiden
University, The Netherlands Vedran Dunjko<EMAIL_ADDRESS>applied
Quantum algorithms (aQa), Leiden University, The Netherlands

###### Abstract

Quantum computers are believed to bring computational advantages in simulating
quantum many body systems. However, recent works have shown that classical
machine learning algorithms are able to predict numerous properties of quantum
systems with classical data. Despite various examples of learning tasks with
provable quantum advantages being proposed, they all involve cryptographic
functions and do not represent any physical scenarios encountered in
laboratory settings. In this paper we prove quantum advantages for the
physically relevant task of learning quantum observables from classical
(measured out) data. We consider two types of observables: first we prove a
learning advantage for linear combinations of Pauli strings, then we extend
the result for the broader case of unitarily parametrized observables. For
each type of observable we delineate the boundaries that separate physically
relevant tasks which classical computers can solve using data from quantum
measurements, from those where a quantum computer is still necessary for data
analysis. Our results shed light on the utility of quantum computers for
machine learning problems in the domain of quantum many body physics, thereby
suggesting new directions where quantum learning improvements may emerge.

##  1 Introduction

The very first proposed application of quantum computers can be traced back to
Feynman’s idea of simulating quantum physics on a quantum device. Together
with factoring, simulation of quantum many body systems stand as the clearest
example of dramatic advantages of quantum computers [Llo96]. Machine learning
is another much newer area where quantum computers are believed to possibly
bring advantages in certain learning problems, and in fact there are provable
speed ups achieved by a quantum algorithm [LAT21, SG04, SSHE21, JGM+21] for
specific machine learning problems. Relating back to the original Feynman’s
idea of simulating quantum physics, machine learning problems in quantum many
body physics seem a natural scenario where learning advantages could arise.
However, perhaps surprisingly, it was recently shown that access to data
exemplifying what the hard-to-compute function does can drastically change the
hardness of the computational task questioning the role of quantum computation
in a machine learning scenarios [HBM+21, HKT+22b]. If every quantum
computation could be replicated classically provided access to data, such
results would confine the practical application of quantum computers solely to
the data acquisition stage. This is however not the case, as was shown already
in the examples considered in [SG04, LAT21]. In such cases the unknown
function was cryptographic in nature, and not related to genuine quantum
simulation problems. Nonetheless in [GD23] it was elucidated that learning
problems with provable speed-ups can be derived from any BQP-complete
functions, facilitating connections to more physical scenarios.
The work in [GD23] demonstrated the existence of learning problems with
provable advantages based on such reasonings, however it does not provide any
natural learning setting of the kind encountered in physics. Another
significant open question, raised by the recent progress on classical
algorithms with provable guarantees, pertains to establishing clear boundaries
between classical and quantum algorithms when dealing with data generated by
quantum processes. In this work we provide substantial strides in both
directions. We specifically consider learning problems where an
experimentalist wants to predict expectation values of an unknown observable
from measurements on input quantum states which can either be ground states of
local Hamiltonians or time evolved states. Our result is a proof of learning
advantages for different types of quantum observables. Firstly, we prove an
exponential quantum advantage in learning observables constructed as an
unknown linear combination of Pauli strings. Then we extend our quantum speed-
up result to the far more general case of unitarily-parametrized observables,
linking our results to the extensive body of literature on learning unknown
unitaries from query access. In connection to this, we examine the Hamiltonian
learning problem where the identification of the target function is
demonstrated to be classically easy. We summarize our main results in Table 1.

Class of observables | Learning Problem |  Existence of a Learning Advantage
---|---|---
Linear combination of Pauli strings | Time Evolution Problem | Yes
Ground State Problem | Yes
Flipped Concepts | No - Classically easy
Unitarily-parametrized Observables | Learning the observable | Yes
Hamiltonian Learning | No - Classically easy
Identifying the concept |  Unknown - Classical hardness unknown
Table 1: Main results of this paper

##  2 Related work

Our main results are built upon the theoretical assumption that there exists a
BQP language and an input distribution such that the language cannot be
decided using $\mathrm{HeurP/poly}$, for more on this see [GD23]. Building on
this, the authors also proved that many learning speed-ups could arise by
looking at BQP complete problems. However, in their separation result, the
concept class is limited to be of polynomial size, and the quantum algorithm
crucially leverages this to find the underlying concept in polynomial time by
brute force. In this work we take a step further from their result by
considering a continuous concept class and using a quantum algorithm which
learns the unknown concept from data through a natural machine learning
method.

In recent works by [HKT+22b, LHT+24], significant progresses have been made
with classical machine learning algorithms with provable guarantees for
learning ground state properties from data, restricting the role of a quantum
computer only to the data acquisition phase. In this study, we establish
rigorous limitations on the capabilities of classical algorithms when learning
quantum observables. A key distinction from their approach is that, in
considering ground state problems, we investigate Hamiltonians with a
polynomially decaying spectral gap, whereas the algorithms in [HKT+22b,
LHT+24] have provable guarantees only for gapped Hamiltonians

In [YIM23] the authors proposed a family of supervised learning tasks which
present a learning speed-up with an exponentially sized concept class. Our
construction, which was developed independently from [YIM23], stems from a
physically-motivated context, resulting in the utilization of different
techniques for the quantum learning algorithm given the necessity to handle
errors in the training samples. The result of Theorem 3 further differentiates
our work, as it deals with unitarily parametrized observables for which the
corresponding learning algorithm cannot be straightforwardly simplified to
solving a linear system of equations, as it is in the case of [YIM23].

##  3 The learning problems

We now take in consideration the first scenario where experimentalists can
time evolve arbitrary input states under a fixed Hamiltonian for constant
time, however they do not have full control over the input state preparation.
We model this by allowing the input states to be sampled randomly from an
unknown distribution of quantum states, subsequently they undergo a time
evolution before being measured by an unknown observable. The experimentalists
collect the corresponding measurement outcomes and the goal is to predict
expectation values of the unknown observable on new input states. This simple
scenario is later significantly generalized to cases where the inputs are
known Hamiltonians, and the problem is not time evolution but rather learning
measurements on their ground states. In both cases we rigorously model the
colloquially described learning tasks using concept classes within the PAC
learning framework

Let $H$ be a Hamiltonian and fix a constant time $\tau$, we model the time
evolution learning problem by the following concept class

$\displaystyle\mathcal{F}_{\mathrm{evolved}}^{H,O}$
$\displaystyle=\\{f^{\bm{{\bm{\alpha}}}}(\bm{x})\in\mathbb{R}\;\;|\;\mathbf{{\bm{\alpha}}}\in[-1,1]^{m}\\}$
(1) $\displaystyle\text{with }\;f^{\bm{\alpha}}(\bm{x}):\;\;$
$\displaystyle\;\bm{x}\in\\{0,1\\}^{n}\rightarrow
f^{\bm{\alpha}}(\bm{x})=\text{Tr}[\rho_{H}(\bm{x})O(\mathbf{{\bm{\alpha}}})]\
\;\;\&\;\;O({\bm{\alpha}})=\sum_{i=1}^{m}{\bm{\alpha}}_{i}P_{i}.$ (2)

In the above, $\bm{x}$ specifies the initial state $\ket{\bm{x}}$,
$\rho_{H}(\bm{x})$ the constant time evolved state
$\rho_{H}(\bm{x})=U\ket{\bm{x}}\bra{\bm{x}}U^{\dagger}$ with $U=e^{iH\tau}$
and each $P_{i}$ is a $k$-local Pauli string where $m$ scales polynomially
with $n$. Notice that although we consider binary inputs
$\bm{x}\in\\{0,1\\}^{n}$, the output of each concept is a real. The goal of
the ML learning algorithm is to learn a model $h(\bm{x})$ which approximates
the unknown concept
$f^{\bm{\alpha}}(\bm{x})=\text{Tr}[\rho_{H}(\bm{x})O(\mathbf{{\bm{\alpha}}})]$,
using as training samples data of the form
$\mathcal{T}^{\mathbf{{\bm{\alpha}}}}_{\epsilon_{3}}=\\{(\bm{x}_{\ell},y_{\ell})\\}_{\ell=1}^{N}$
where $y_{\ell}\approx_{\epsilon_{3}}f^{\bm{\alpha}}(\bm{x}_{\ell})$ is an
additive error $\epsilon_{3}$-approximation of the true expectation value
$\text{Tr}[\rho_{H}(\bm{x}_{\ell})O({\bm{\alpha}})]$. Considering datasets
with approximated values makes the learning problem closer to real world
scenarios. In an idealized setting, the dataset would consist of pairs
${(\bm{x}_{\ell},y_{\ell})}$, where $y_{\ell}$ represents the exact
expectation value. However, in real experiments, measurements are conducted by
counting frequencies from a finite number of state copies, resulting in only
approximate estimations of expectation values due to sampling errors.
Formally, we assume a maximum (sampling) error $\epsilon_{3}$ on the training
labels $y_{\ell}$ of our dataset, i.e.
$\epsilon_{3}=\max_{\ell}|\text{Tr}[\rho_{H}(\bm{x}_{\ell})O({\bm{\alpha}})]-y_{\ell}|$.
It is now possible to formally state our learning condition. Assuming the
$\bm{x}_{\ell}$’s in the training data come from an unknown distribution
$\mathcal{D}$, we require that the ML model learns the concept class
$\mathcal{F}^{H,O}_{\mathrm{evolved}}$ in the following sense.

######  Definition 1 (Efficient learning condition).

A concept class $\mathcal{F}$ is efficiently learnable with respect to the
distribution $\mathcal{D}$ if for every $\epsilon,\epsilon_{3}>0$ and
$0<\delta<1$, there exists a poly$(1/\epsilon,1/\delta,1/\epsilon_{3},n)$-time
algorithm $A$ such that for any $f^{\bm{\alpha}}$ in $\mathcal{F}$ and for any
training set $\mathcal{T}^{\bm{\alpha}}_{\epsilon_{3}}$ of
poly$(1/\epsilon,1/\delta,1/\epsilon_{3},n)$ size,
$h(.)=A(\mathcal{T}_{\epsilon_{3}}^{\bm{\alpha}},.)$ satisfies with
probability $1-\delta$:

$\mathbb{E}_{\bm{x}\sim\mathcal{D}}\big{[}\;|f^{\bm{\alpha}}(\bm{x})-h(\bm{x})|^{2}\;\big{]}\leq\epsilon$
(3)

Notice that the learning algorithm possesses no prior knowledge regarding the
observable $O({\bm{\alpha}})$, except for the fact that it is a $k$-local
operator. Any additional information regarding $O({\bm{\alpha}})$ can
exclusively be derived from the training samples within
$\mathcal{T}^{\bm{\alpha}}_{\epsilon_{3}}$. In particular the vector
${\bm{\alpha}}$, which defines the specific concept in the concept class, is
unknown to the learning algorithm. While the classical hardness of the
learning problem relies on considering a specific ${\bm{\alpha}}$ for which
the evaluation of $f^{\bm{\alpha}}(\bm{x})$ is known to be hard, the quantum
algorithm will use a LASSO regression to infer a parameter $w\in[-1,1]^{m}$
close to the target ${\bm{\alpha}}$ so that condition (3) is satisfied.

We emphasize here that our learning definition demands that the trained
classical model can label new points. This stands in contrast to other
settings, e.g. Hamiltonian learning problems, where the task would be
identifying the vector ${\bm{\alpha}}$. In the prior case, a learning
advantage is more easily established as explained in [GD23] where the hardness
of evaluating versus identifying a concept was discussed. Later, we will
explore this difference further and present an example of an identification
problem closely related to the concept class of Eq. (1), which indeed can be
solved by a classical algorithm.

We can now state the first result of this paper, namely the existence of a
concept class for the time evolution learning problem learnable by a quantum
algorithm but for which no classical algorithm can meet the learning condition
of Eq. (3).

######  Theorem 1 (Learning advantage for the time evolution problem).

Under the assumption that there exists a distribution $\mathcal{D}^{\prime}$
such that
$\mathrm{BQP}\not\subset\mathrm{HeurP}^{\mathcal{D}^{\prime}}/\mathrm{poly}$111We
define the class $\mathrm{HeurP}^{\mathcal{D}}/\mathrm{poly}$ as the class of
languages $\mathcal{L}$ that can be decided in $\mathrm{HeurP}/\mathrm{poly}$
under the distribution $\mathcal{D}$, i.e.
$\mathrm{HeurP}^{\mathcal{D}}/\mathrm{poly}=\\{\mathcal{L}\;\;|\;\;(\mathcal{L},\mathcal{D})\in\mathrm{HeurP}/\mathrm{poly}\\}$
, then for any $\mathrm{BQP}$-complete language there exists an associated
distribution $\mathcal{D}$ over the input values $\bm{x}\in\\{0,1\\}^{n}$, a
Hamiltonian $H_{\mathrm{hard}}$ and a set of observables
$\\{O({\bm{\alpha}})\\}_{\bm{\alpha}}$ such that no classical algorithm can
solve the time evolution learning problem, formalized by the concept class
$\mathcal{F}_{\mathrm{evolved}}^{H_{\mathrm{hard}},O}$, in the sense of Def. 1
given data
$\mathcal{T}^{\mathbf{{\bm{\alpha}}}}_{\epsilon_{3}}=\\{(\bm{x}_{\ell},y_{\ell}\approx_{\epsilon_{3}}f^{\bm{\alpha}}(\bm{x}))\\}_{\ell=1}^{N}$
sampled from $\mathcal{D}$. However, there exists a quantum algorithm which
learns $\mathcal{F}_{\mathrm{evolved}}^{H_{\mathrm{hard}},O}$ under any
distribution $\mathcal{D}$.

In the remainder of this Section we prove Theorem 1 by explicitly constructing
an example of a provable classically hard time evolution problem and providing
a quantum algorithm with learning guarantees. We sketch the proof ideas in the
following paragraphs of the main text, while the full proofs can be found in
the Appendix.

Classical hardness The hardness condition relies on the assumption
$\mathrm{BQP}\not\subset\mathrm{HeurP}^{\mathcal{D}}/\mathrm{poly}$ for some
distribution $\mathcal{D}$. Notice that it is a widely believed assumption as,
for example, the discrete logarithm problem is believed to not be in
$\mathrm{HeurBPP}/\mathrm{poly}$ if the input values are sampled from the
uniform distribution [BM19]. In general, by Lemma 3 in [GD23] if there exists
a single $\mathcal{L}\in\text{BQP}$ that is not in HeurP/poly under some
distribution, then for every BQP-complete problem there exists a distribution
under which the problem is not in HeurP/poly.

######  Lemma 1 (Classical hardness of the time evolution learning problem).

Under the assumption that there exists a distribution $\mathcal{D}^{\prime}$
such that
$\mathrm{BQP}\not\subset\mathrm{HeurP}^{\mathcal{D}^{\prime}}/\mathrm{poly}$,
then for any BQP-complete language there exists an associated input
distribution $\mathcal{D}$ and a Hamiltonian $H_{\mathrm{hard}}$ such that no
randomized polynomial-time classical algorithm $A_{c}$ is such that
$h_{cl}(.)=A_{c}(T^{\bm{\alpha}},.)$ satisfies the learning condition of Def.
1 for the concept class $\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$
with $x$ sampled from $\mathcal{D}$.

We now show an appropriate choice of the Hamiltonian $H_{\mathrm{hard}}$ such
that the time evolution problem lies outside $\mathrm{HeurP}/\mathrm{poly}$
for a specific input distribution $\mathcal{D}$. Let $\mathcal{L}$ be a
$\mathrm{BQP}$-complete language and $\mathcal{D}$ a distribution over input
values such that
$(\mathcal{L},\mathcal{D})\not\subset\mathrm{HeurP}/\mathrm{poly}$. Since
$\mathcal{L}\in\mathrm{BQP}$ there exists a quantum circuit $U_{BQP}$ which
decides input bitstrings $x\in\\{0,1\\}^{n}$ correctly on average with respect
to $\mathcal{D}$. As shown more rigorously in the Appendix, measuring the $Z$
operator on the first qubit of the state $U_{BQP}\ket{\bm{x}}$ will output a
positive or negative value depending if $x\in\mathcal{L}$ or not. Therefore,
considering the observable $O^{\prime}=Z\otimes I\otimes...\otimes I$ the
quantum model
$f^{O^{\prime}}(\bm{x})=\text{Tr}[O^{\prime}\rho_{U_{BQP}}(\bm{x})]$, with
$\rho_{U_{BQP}}(\bm{x})=U_{BQP}\ket{\bm{x}}\bra{\bm{x}}U^{\dagger}_{BQP}$,
correctly decides every input $\bm{x}$. We then show in the Appendix that if a
classical algorithm can learn the function
$g(\bm{x})=\text{Tr}[O^{\prime}\rho_{U_{BQP}}(\bm{x})]$ up to the learning
condition in Def. 1, then it would be able to heuristically decide the
language $\mathcal{L}$ with respect to the distribution $\mathcal{D}$.
Finally, using Feynman’s idea [Fey85, Nag10] it is possible to construct a
local Hamiltonian which time-evolves the initial state $\ket{\bm{x}}$ into
$U_{BQP}\ket{\bm{x}}$ in constant time [Chi04]. Considering as
$H_{\mathrm{hard}}$ such constructed Hamiltonian concludes our proof. In fact,
since there exists at least one concept (namely the one labeled by
${\bm{\alpha}}^{\prime}$ such that $O({\bm{\alpha}}^{\prime})=O^{\prime}$)
which is not learnable by a classical algorithm, then we can conclude that for
such kind of Hamiltonians the time evolution problem is not classically
learnable.

Quantum learnability To establish the quantum learnability of the classically
hard concept class constructed above for the time evolution problem, we
present a quantum algorithm directly. This algorithm accurately predicts any
concept in the associated learning problem with high probability when provided
with a sufficient number of training data samples. Crucially, we prove that
the algorithm meets the learning condition of Definition 1 using only
polynomial training samples and running in polynomial time. The central idea
involves leveraging the capability of the quantum algorithm to efficiently
prepare the time-evolved states $\rho_{H(\bm{x})}$, for any input local
Hamiltonians $H$ and, in particular, for the hard instances of
$H_{\mathrm{hard}}$ considered in our hardness result of Lemma 1.

######  Lemma 2 (Quantum learnability of the time evolution learning problem).

There exist a quantum algorithm $A_{q}$ such that for any concept
$f^{\bm{\alpha}}\in\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$
considered in Lemma 1, $A_{q}$ satisfies the following. Given
$n,\epsilon,\delta\geq 0$, and any training dataset
$T^{{\bm{\alpha}}}_{\epsilon_{3}}$ of size

$N=\mathcal{O}\left(\frac{\log(n/\delta)n}{\epsilon}\right)$ (4)

with probability $1-\delta$ the quantum algorithm $A_{q}$ outputs a model
$h^{*}(.)=A(T^{{\bm{\alpha}}}_{\epsilon_{3}},.)$ which satisfies the learning
condition of Def. 1:

$\mathbb{E}_{\mathbf{x}\sim\mathcal{D}(\mathbf{x})}\big{[}\;|f^{{\bm{\alpha}}}(\mathbf{x})-h^{*}(\bm{x})|^{2}\;\big{]}\leq\epsilon$
(5)

where $\mathcal{D}$ is the distribution the training data is sampled from.

The idea for the quantum algorithm is the following. For every point
$\bm{x}_{\ell}$ we construct a vector $\phi(\bm{x}_{\ell})\in[-1,1]^{m}$ of
expectation values of the single Pauli strings present in $O$ on the time
evolved quantum states. The model $h(\bm{x})=w\cdot\phi(\bm{x})$ is then
trained on the data samples with a LASSO regression to find a $w^{*}$ so that
the trained model is in agreement with the training samples, i.e.
$h^{*}(\bm{x}_{\ell})=w^{*}\cdot\phi(\bm{x}_{\ell})\approx y_{\ell}$ for any
$(\bm{x}_{\ell},y_{\ell})\sim\mathcal{T}^{\bm{\alpha}}_{\epsilon_{3}}$. As the
$\ell_{1}$-norm of the optimal $w_{opt}={\bm{\alpha}}$ scales polynomially in
$n$, imposing the constraint $||w||_{\ell_{1}}\leq B$ with $B=\mathcal{O}(n)$
in the LASSO regression will allow to obtain an error $\epsilon$ in the
generalization performance using a training set of at most polynomial size.
This is because the generalization error for the LASSO regression is bound
linearly by $B$ [MRT18]. We write here the description of the quantum
algorithm, while we leave the precise analysis of its sample and time
complexity in the Appendix.

Algorithm 1 Quantum Algorithm

  1. 1.

For every training point in
$T^{\mathbf{{\bm{\alpha}}}}_{\epsilon_{3}}=\\{(\bm{x}_{\ell},y_{\ell})\\}_{i=1}^{N}$
the quantum algorithm prepares poly($n$) copies of the state
$\rho_{H}(\bm{x}_{\ell})$ and computes the estimates of the expectation values
$\langle
P_{j}\rangle_{\ell}=\text{Tr}[\rho_{H}(\bm{x}_{\ell})P_{j}]\;\;\forall
j=1,...,m$ up to a certain precision $\epsilon_{1}$. Note that $m$ scales at
most polynomially in $n$ as $\\{P_{j}\\}_{j=1}^{m}$ are local observables.

  2. 2.

Define the model $h(\bm{x})=w\cdot\phi(\bm{x})$, where $\phi(\bm{x})$ is the
vector of the Pauli string expectation values
$\phi(\bm{x})=\left[\text{Tr}[\rho_{H}(\bm{x})P_{1}],...,\text{Tr}[\rho_{H}(\bm{x})P_{m}]\right]$
computed at Step 1. Then given as hyperparameter a $B\geq 0$ the LASSO ML
model finds an optimal $w^{*}$ from the following optimization process:

$\min_{\begin{subarray}{c}w\in\mathbb{R}^{m}\\\ ||w||_{1}\leq
B\end{subarray}}\;\;\frac{1}{N}\sum_{l=1}^{N}|w\cdot\phi(\bm{x}_{l})-y_{l}|^{2}$
(6)

with
$\\{(\bm{x}_{l},y_{l}=\text{Tr}[\rho_{H}(\bm{x}_{l})O({\bm{\alpha}})])\\}_{l=1}^{N}$
being the training data.

Importantly, to meet the learning condition the optimization does not need to
be solved exactly, i.e. $w^{*}={\bm{\alpha}}$. As we will make it clear in the
Appendix, it is sufficient to obtain a $w^{*}$ whose training error is
$\epsilon_{2}$ larger than the optimal one.

###  3.1 Generalizations: quantum advantages for fixed inputs and for ground
state problems

We showed that the concept class defined in Eq. (1) leads to a learning
advantage. It is important to note that, unlike many other common learning
scenario settings, the physical problem modeled by such concept class implies
that the experimentalists cannot select the initial input states. However,
they do possess precise control over the Hamiltonian governing the evolution
of these input states. It is natural to ask if we can generalize the result
and provide other cases of exponential learning advantages where the
experimentalist has instead only little control over the Hamiltonian employed.

Fixed inputs, unknown Hamiltonians A first example that naturally arises from
the case discussed above is when the experimentalists prepare a fixed initial
state and time evolves it under a Hamiltonian within a fixed family of
Hamiltonians but over which they do not have control. Specifically the
Hamiltonians in such a family will be labeled by some input bitstring
$\bm{x}$, which for example could parameterize the strength of the coupling
interactions. Each initial state will then be evolved by a different
Hamiltonian in the family accordingly to the input $\bm{x}$, which comes from
an unknown underlying distribution. It is easy to see that the mathematical
description of such a learning problem is again defined by the concept class
in Eq.(1). The only change is in the definition of $\rho_{H}(\bm{x})$, now
being $\rho_{H}(\bm{x})=U(\bm{x})\ket{0}\bra{0}U(\bm{x})^{\dagger}$ with
$H(\bm{x})$ the Hamiltonian associated to the quantum circuit $U(\bm{x})$ by
the Feynmann construction [Fey85]. A learning advantage exists for such
concept class as well, as the general definition of a language $\mathcal{L}$
in BQP implies the existence of a family of circuits $\\{U(\bm{x})\\}_{x}$
which correctly decides every $\bm{x}\in\mathcal{L}$.

Ground state problem As our next example we consider the task of predicting
ground state properties of local Hamiltonians. Here, the states to be measured
are no longer time evolved quantum states but rather ground states of local
Hamiltonians. Specifically, the experimentalist is capable of preparing ground
states of input $k$ local Hamiltonians, which once again belong to a family of
Hamiltonians. However, they lack control over the coupling parameters that,
instead, are random values drawn from an underlying distribution. This
situation occurs, for example, in the context of the random Ising [Nat98] or
random Heisenberg model [OS01]. The mathematical formalization of such a
learning problem is the following. Consider a family of parametrized local
Hamiltonians $\mathcal{H}=\\{H(\bm{x})\;\;|\;\;\bm{x}\in\\{0,1\\}^{n}\\}$. Let
us define the concept class for the ground state learning problem similarly to
the time evolution case of Eq. (1), where now the unknown observable
$O({\bm{\alpha}})$ is measured on the states $\rho_{H}(\bm{x})$, which
correspond to the ground states of the Hamiltonians $H(\bm{x})\in\mathcal{H}$,
then we define:

$\displaystyle\mathcal{F}^{\mathcal{H},O}_{\mathrm{g.s.}}$
$\displaystyle=\\{f^{\bm{\alpha}}(\bm{x})\in\mathbb{R}\;\;|\;\mathbf{{\bm{\alpha}}}\in[-1,1]^{m}\\}$
(7) $\displaystyle\text{with }f^{\bm{\alpha}}(\bm{x}):\;\;$
$\displaystyle\;\bm{x}\in\\{0,1\\}^{n}\rightarrow
f^{\bm{\alpha}}(\bm{x})=\text{Tr}[\rho_{H}(\bm{x})O(\mathbf{{\bm{\alpha}}})]\
\;\;\&\;\;O({\bm{\alpha}})=\sum_{i=1}^{m}{\bm{\alpha}}_{i}P_{i}.$ (8)

Considering the training data
$\mathcal{T}^{\mathbf{{\bm{\alpha}}}}_{\epsilon_{3}}=\\{(\bm{x}_{\ell},y_{\ell}\approx_{\epsilon_{3}}f^{\bm{\alpha}}(\bm{x}_{\ell}))\\}_{\ell=1}^{N}$,
the learning condition remains the same as in Definition 1. From the hardness
result of Lemma 1, we obtain the following Theorem

######  Theorem 2 (Learning advantage for the ground state learning problem).

Under the assumption that there exists a distribution $\mathcal{D}^{\prime}$
such that
$\mathrm{BQP}\not\subset\mathrm{HeurP}^{\mathcal{D}^{\prime}}/\mathrm{poly}$,
then for any BQP-complete language there exists an associated distribution
$\mathcal{D}$ over the input values $x\in\\{0,1\\}^{n}$ and a family of
Hamiltonians $\mathcal{H}_{\mathrm{hard}}$ such that no classical algorithm
can learn the ground state problem, formalized by learning the concept class
$\mathcal{F}^{\mathcal{H}_{\mathrm{hard}},O}_{\mathrm{g.s.}}$ in the sense of
Def.1 given data
$\mathcal{T}^{\mathbf{{\bm{\alpha}}}}_{\epsilon_{3}}=\\{(\bm{x}_{\ell},y_{\ell}\approx
f^{\bm{\alpha}}(\bm{x}))\\}_{\ell=1}^{N}$ sampled from $\mathcal{D}$. However,
there exists a quantum algorithm which learns
$\mathcal{F}^{\mathcal{H}_{\mathrm{hard}},O}_{\mathrm{g.s.}}$ under any
distribution $\mathcal{D}$.

###### Proof.

The existence of a class of Hamiltonian $\mathcal{H}_{\mathrm{hard}}$ for
which the ground state problem is classically hard to learn is guaranteed by
the argument above regarding the hardness of time evolution case. The
structure of the proof is exactly the same of the proof for Theorem 1
rigorously written in the Appendix. The only missing step for the ground state
version is that now the states $\rho_{H}(\bm{x})$ we are considering in Eq.
(7) are ground state of Hamiltonians $H(\bm{x})$ and not time evolved states.
However, using the Kitaev’s construction [KSV02, KR03], it is possible to
create for any $\bm{x}\in\\{0,1\\}^{n}$ and $U$ a local Hamiltonian
$H(\bm{x})$ such that its ground state will have a large overlap with
$U\ket{\bm{x}}$, with $U$ an arbitrary quantum circuit with a polynomial
depth. This completes our proof of classical hardness as we consider the
family of Hamiltonian $\mathcal{H}_{\mathrm{hard}}$ to exactly be the set of
such $\\{H(\bm{x})\\}_{x}$ with $U$ implementing a BQP-complete
computation222More rigorously it means that for every $n$, we consider
$U=U^{n}_{BQP}$ from the family $\\{U^{n}_{BQP}\\}_{n}$ of quantum circuits
which correctly decide a BQP-complete language $\mathcal{L}$. Same as before,
it is still the case that there is at least one concept which can not be
evaluated by polynomially sized classical circuits. Finally, also the quantum
algorithm with learning guarantees for the concept class
$\mathcal{F}^{\mathcal{H}_{\mathrm{hard}},O}_{\mathrm{g.s.}}$ closely follows
Algorithm 1. The only missing point to prove here is that the ground states
$\rho_{\mathcal{H}_{\mathrm{hard}}}(\bm{x})$ are easily preparable on a
quantum computer. Recall that the class of hard Hamiltonian
$\mathcal{H}_{\mathrm{hard}}$ considered in the hardness result of the ground
state problem are the one derived from the Kitaev’s circuit-to-Hamiltonian
construction from a $\mathrm{BQP}$-complete circuit. It is well known that
those Hamiltonians present a $\Omega(1/\text{poly}(n))$ gap (in contrast to
the classically learnable Hamiltonians in [HKT+22b]) and it is possible to
construct the ground state $\rho_{\mathcal{H}_{\mathrm{hard}}}$ from the
description of the corresponding Kitaev’s Hamiltonian, known to the learner
through the description of the concept class and the input $\bm{x}$. This then
concludes our proof for the quantum learnability of
$\mathcal{F}^{\mathcal{H}_{\mathrm{hard}},O}_{\mathrm{g.s.}}$, thus completing
the entire proof of Theorem 2 ∎

Notice that if our interest is only about the classical hardness or the
quantum learnability of the ground state problem we can consider concept
classes associated to more general Hamiltonian families than the Kitaev’s
family $\mathcal{H}_{\mathrm{hard}}$ used in our provable advantage result.
Specifically, classical hardness for the time evolution problem is guaranteed
for a number of physically motivated Hamiltonians, such as the Heisenberg
model whose dynamics can efficiently be simulated on a quantum computer.
Notice that for the ground state version of the learning problem considering
generic local Hamiltonian might make the problem quantum not solvable. It is
in fact known that finding ground states of even two local Hamiltonians, as
for example the Heisenberg model, is QMA-hard. Concept classes for which the
quantum learnability condition is met are the ones associated to any family of
Hamiltonian $\mathcal{H}_{\mathrm{quantum}}$ for which a quantum algorithm can
prepare the corresponding ground state given the Hamiltonian description. In
that regard a learning speed-up can still be achieved if we consider providing
to the algorithm guiding states for any family of local Hamiltonians, this in
fact will make the problem $\mathrm{BQP}$-complete [GHGM22].

We note that the ground state learning problem defined by the class in Eq.(7)
very much resembles the ML problem studied in the works [HKT+22b] and [LHT+24]
where the authors showed that a classical algorithm could solve the task. As
their result holds for any local Hamiltonian with constant gap, this gives a
constraint on the family of local Hamiltonians $\mathcal{H}$ one would like to
consider in order to prove a quantum advantage in learning.

The “flipped case” As a final remark, it is interesting to observe that if we
consider the case of fixed input state, which could be a fixed initial state
$\rho_{0}(\bm{x})=\ket{\bm{x}}\bra{\bm{x}}$ in the time evolution scenario
modeled by the concept class in Eq. (1) or a single ground state
$\rho_{H}(\bm{x})$ of a fixed Hamiltonian $H(\bm{x})$ in the ground state
problem, then the learning problem becomes trivially classically easy. Such
learning scenario is formally equivalent to considering a “flip concept” of
the ones defined above. Let us for example consider the task of learning an
unknown quantum process from many measurements, in this case the learning
problem is still modeled by the concept class
$\mathcal{F}^{H,O}_{\mathrm{evolved}}$ of Eq. (1) with the distinction that
now the role of $x$ and ${\bm{\alpha}}$ are switched. Namely, the concepts are
defined as $f^{\bm{x}}({\bm{\alpha}})$ so that the their expressions remain
the same of $f^{\bm{\alpha}}(\bm{x})$. The difference lies in the labeling,
where $x$ now denotes the concept while ${\bm{\alpha}}$ represents the input
vectors. As $\bm{x}$ is constant for an instance of the learning problem,
specified by the concept that generates the data, the training samples are
measurements of the same quantum state $\rho_{H(\bm{x})}$ with different
observables corresponding to different ${\bm{\alpha}}$. Since
$O({\bm{\alpha}})=\sum_{j}{\bm{\alpha}}_{j}P_{j}$, we can make use of data to
solve the linear system and obtain the expectation values of each local Pauli
string $\text{Tr}[\rho_{H_{\mathrm{hard}}}(\bm{x})P_{i}]$. It then becomes
easy to extrapolate the value of
$\text{Tr}[\rho_{H_{\mathrm{hard}}}(\bm{x})O({\bm{\alpha}})]$ for every new
${\bm{\alpha}}$.

###  3.2 Generalization of the quantum learning mechanism to quantum kernels

In [LAT21], considerable effort was invested to construct a task with provable
learning speed-up where the quantum learning model is somewhat generic
(related to natural QML models studied in literature), while still being
capable of learning a classically unlearnable task. In our construction, it is
possible to view the entire learning process as a quantum kernel setting,
similarly to the approach in [YIM23]. However, in standard kernel approaches,
especially those stemming from support vector machines, the optimization
process is solved in the dual formulation where the hypothesis function is
expressed as a linear combination of kernel functions. In contrast, the LASSO
optimization employed here solves the optimization in the primal form with a
constrain on the $\ell_{1}$ norm. This is an issue making our learner not
technically a quantum kernel. While the LASSO formulation does not
straightforwardly convert into a kernel method, one could attempt to address
the regression problem outlined in Equation (6) using an alternative
optimization approach that supports a kernel solution, such as kernel ridge
regression. In this case the optimization is done for vectors with bounded
$\ell_{2}$ norms, nevertheless there exist bounds on the generalization
performance of such procedures as well [MRT18].

##  4 Generalization to observables parametrized by unitaries

We have demonstrated the existence of a quantum advantage for the learning
problem of predicting $k$-local observables from time evolved states and from
ground states. Critically, we considered observables of the type
$O({\bm{\alpha}})=\sum_{i}{\bm{\alpha}}_{i}P_{i}$ and we exploited the linear
structure of $O({\bm{\alpha}})$ to ensure quantum learnability through LASSO
regression. It is however natural to ask if quantum learnability can be
achieved for other types of observables, while maintaining the classical
hardness. In this section we consider the far more general case where the
unknown observable is parameterized through a unitary matrix, i.e.
$O({\bm{\alpha}})=W({\bm{\alpha}})OW^{\dagger}({\bm{\alpha}})$ where $O$ is an
hermitian matrix. Our findings in this scenario will be of two kinds. First we
show as a general result that for every method which learns a unitary $W$
given query access on a known distribution of input quantum states there
exists a learning problem which exhibits a classical-quantum advantage. Then
we concretize the general result by presenting a constructed example of a
learning problem defined by a class of unitary-parameterized observables,
showcasing a provable speed-up. Before stating our findings, let us properly
introduce the learning problem under consideration. Imagine the scenario where
the experimentalist once more measures observables on evolved quantum states.
However, in this case, they lack control over the entire evolution, with a
portion of it remaining unknown. Specifically, the experimentalist will
receive measurements on input-dependent states
$\ket{\psi(\bm{x})}=W({\bm{\alpha}})U(\bm{x})\ket{0}$ for an unknown fixed
${\bm{\alpha}}$. Their objective remains predicting expectation values on
states $\ket{\psi(\bm{x}^{\prime})}$ for new inputs $\bm{x}^{\prime}$.
Concretely such scenario corresponds to the following concept class:

$\displaystyle\mathcal{M}_{U,W,O}$
$\displaystyle=\\{f^{\bm{\alpha}}(\bm{x})\in\mathbb{R}\;\;|\;\;{\bm{\alpha}}\in[-1,1]\\}$
(9) $\displaystyle\text{with }\;\;f^{\bm{\alpha}}(\bm{x}):\;x$
$\displaystyle\in\mathcal{X}\subseteq\\{0,1\\}^{n}\rightarrow\text{Tr}[\rho_{U}(\bm{x})O({\bm{\alpha}})]\in\mathbb{R}\;\;\&\;\;O({\bm{\alpha}})=W({\bm{\alpha}})OW^{\dagger}({\bm{\alpha}}).$
(10)

where $\rho_{U}(\bm{x})=U(\bm{x})\ket{0}\bra{0}U^{\dagger}(\bm{x})$ and $O$ is
a hermitian matrix. Given as training data
$\mathcal{T}^{\bm{\alpha}}=\\{(\bm{x}_{\ell},y_{\ell})\\}_{\ell=1}^{N}$ with
$\mathbb{E}[y_{\ell}]=\text{Tr}[\rho_{U}(\bm{x}_{\ell})O({\bm{\alpha}})]$, the
goal of the learning algorithm is again to satisfy the learning condition of
Def. 1. We are now ready to state our main general result of this Section:

######  Theorem 3 (Learning advantage for unitarily-parametrized observables).

Every (non-adaptive)333Non-adaptive means that the algorithm probes the
unitary with some input states and measures some observables which are chosen
independently, meaning they do not have any choice which depends on previous
outcomes. learning algorithm $\mathcal{A}_{W}$ for learning a unitary
$W(\bm{\alpha})\in\\{W(\bm{\alpha})\\}_{\bm{\alpha}}$, where the probe states
$\\{\ket{\psi_{l}}\\}_{l}$and observables $\\{Q_{m}\\}_{m}$ come from discrete
sets $S=\\{\ket{\psi_{\ell}}\\}_{\ell}$ and $Q=\\{Q_{m}\\}_{m}$ (or they can
be discretized with controllable error), induces a classical-input-classical-
output learning problem with a quantum-classical learning advantage.

In other words, Theorem 3 guarantees that whenever there is an efficient
method to learn a unitary from query access on a set of arbitrary input states
and observables it is also possible to construct a learning problem of the
kind Eq. (9) which exhibits a learning speed-up. We will more mathematically
formalize the statement of Theorem 3 and provide a rigorous proof in the
Appendix. The nontrivial part of our result lies in the fact that in the
majority of the works present in the literature, which provide efficient
algorithms to learn a unitary, the set of required probe states
$\\{\ket{\psi_{\ell}}\\}_{\ell}$ is restricted to specific quantum states,
often classically describable (e.g. stabilizer states). On such a set of
states, our hardness results from the previous section can not directly be
applied as a classical learning algorithm could simply prepare those states as
the quantum algorithm would do.

The detailed proof of Theorem 3 can be found in the Appendix, here we outline
the main ideas.

###### Proof sketch.

The main idea of the proof is to construct a concept class of the kind of
Eq.(9) which can be learned by a quantum algorithm using the learning
algorithm $\mathcal{A}_{W}$, while maintaining classical harndess. Consider
the circuit in Figure 1. Let $U(\bm{x})$ be a unitary that, depending on the
first bit $x_{1}$ of the input $\bm{x}\in\\{0,1\\}^{n}$, prepares the
$\ket{\psi^{n_{S}}_{U}(\bm{x})}$ on the $n_{S}$ qubit register in two
different ways. If $x_{1}=0$, then $\ket{\psi^{n_{S}}_{U}(\bm{x})}$ is exactly
one of the states $\ket{\psi_{\ell}}\in S$, labeled by the final $n_{S}$ bits
$\bm{x_{S}}\in\\{0,1\\}^{n_{S}}$ of the input bitstring $\bm{x}$, i.e.
$\bm{x_{S}}=x_{n-n_{S}}...x_{n}$. If $x_{1}=1$, then $U(\bm{x})$ prepares the
state $\ket{\psi^{n_{S}}_{U}(\bm{x})}$ as the result of a BQP-complete
computation. Regarding the observable, we define a controlled unitary $V_{A}$,
controlled by the first $1+n_{Q}$ qubits register, such that when $x_{1}=0$
$V_{A}$ acts on the target $n_{S}$ qubit register by rotating the $n_{S}$
qubit measurement operator $O$ into one of the $Q_{m}$ in the set $Q$ required
by the learning algorithm. The description of which $Q_{m}$ the unitary
$V_{A}$ implements is contained in the $n_{Q}$ bitstring
$\bm{x_{Q}}\in\\{0,1\\}^{n_{Q}}$ with $\bm{x_{Q}}=x_{2}x_{3}...x_{n_{Q}+1}$.
When $x_{1}=1$, $V_{A}$ acts as the identity matrix on the $n_{S}$ qubit
register. Suppose now the input bits are sampled from the following
distribution $\mathcal{D}$ on $\bm{x}\in\\{0,1\\}^{n}$:

  * •

The first bit $x_{1}$ of $\bm{x}$ is randomly selected with equal probability
between 0 and 1.

  * •

If $x_{1}=0$ then the other $n-1$ bit $x_{2}x_{3}...x_{n}$ are sampled from
the required distribution444Note that the distribution of probes states and
measurements required by $\mathcal{A}_{W}$ to learn the unitary
$W(\bm{\alpha})$ could be very complicated involving perhaps a joint
distribution on probe states and measurements. Nevertheless every target
distribution can be obtained by post-processing of samples from the uniform
distribution, which can be done coherently by taking uniformly random input
bitstrings. by $\mathcal{A}_{W}$ to learn the unitary $W(\bm{\alpha})$.

  * •

If $x_{1}=1$ then the $n_{S}$ bits in $\bm{x_{S}}$ are sampled according to a
hard distribution which makes the BQP computation of $U(\bm{x})$ classically
hard on average. As discussed before, such distribution always exists for BQP-
complete problems assuming the existence of an input distribution
$\mathrm{BQP}\not\subset\mathrm{HeurP}^{\mathcal{D}^{\prime}}/\mathrm{poly}$.

Taking $W(\bm{0})=I^{\otimes n_{S}}$ for $\bm{\alpha}=\bm{0}$ and $O=I\otimes
I^{\otimes n_{Q}}\otimes Z\otimes I^{n_{S}-1}$, it is clear that the concept
$f^{0}=\text{Tr}[\rho_{U}(\mathbf{x})V_{A}OV^{\dagger}_{A}]$ cannot be learned
by any classical algorithm. In particular, by the result of our Lemma 1 any
classical algorithm can not meet the learning condition of Def.(1) on more
than half of the inputs $\bm{x}$ coming from $\mathcal{D}$, namely it is
guaranteed to fail for the inputs for which $x_{1}=0$. To prove quantum
learnability we notice that for every $\bm{\alpha}$ the dataset
$\mathcal{T}^{{\bm{\alpha}}}$ associated to the concept class
$\mathcal{M}_{U,W,O}$ contains exactly the pairs of state and measurement
outcomes needed by the learning algorithm $\mathcal{A}_{W}$ in order to learn
the unitary $W(\bm{\alpha})$. Namely, half of the training samples,
characterized by $x_{1}=0$ in their input $\bm{x}$, allows the algorithm to
recover the unknown $W(\bm{\alpha})$. Therefore the quantum algorithm is able
to learn the unknown observable $O({\bm{\alpha}})$ and evaluate it on each
quantum state associated to every input $\bm{x}\in\\{0,1\\}^{n}$. ∎

As a corollary of Theorem 3, we construct a concrete example of learning
advantage for observables parametrized by shallow unitaries by exploiting the
recent results on learning shallow unitaries in [HLB+24].

######  Corollary 1 (Learning advantage for shallow unitaries).

There exists a family of parametrized unitaries $\\{U(\bm{x})\\}_{x}$ and
parametrized shallow circuits $\\{W({\bm{\alpha}})\\}_{\bm{\alpha}}$, a
measurement $O$ and a distribution $\mathcal{D}$ over $x\in\\{0,1\\}^{n}$ such
that the concept class $\mathcal{M}_{U,W,O}$ is not classically learnable with
respect to the input distribution $\mathcal{D}$. However, there exists a
quantum algorithm which learns $\mathcal{M}_{U,W,O}$ on the input distribution
$\mathcal{D}$.

The full proof of Corollary 1 can be found in the Appendix.

[row sep=0.1cm] $\ket{x_{1}}$ & [5][1.2cm]U(x) [style=red, label style=pos=1,
anchor=north]$\ket{\psi_{U}(\bm{x})}$ [5][1.2cm]V_A
$\ket{\bm{x_{Q}}}$ n_Q [style=red, label style=pos=1,
anchor=north]$\ket{\psi_{U}(\bm{x})}$
[3]$n_{S}$ $\ket{0}$ [3]W(α) [3, brackets=none]$\langle O\rangle$
⋮
$\ket{0}$

Figure 1: Quantum model which exhibits a learning speed-up for the concept
class $\mathcal{M}_{U,W,O}$. The unitary $U(\bm{x})$ prepares the state
$\ket{\psi_{U}(\bm{x})}=\ket{x_{1}}\otimes\ket{\bm{x_{Q}}}\otimes\ket{\psi^{n_{S}}_{U}(\bm{x_{S}})}$
where the form of $\ket{\psi^{n_{S}}_{U}(\bm{x_{S}})}$ depends on $x_{1}$, the
first bit of each input $\bm{x}\in\\{0,1\\}^{n}$. If $x_{1}=0$, then
$\ket{\psi^{n_{S}}_{U}(\bm{x_{S}})}=\ket{\psi_{\bm{x_{S}}}}\in S$ is the
$n_{S}$ qubit state described by the bitstring
$\bm{x_{S}}=x_{2}x_{3}...x_{n_{S}}$ of the set $S$ of polynomially describable
quantum states needed to learn $W(\bm{\alpha})$. If $x_{1}=1$, then
$\ket{\psi^{n_{S}}_{U}(\bm{x_{S}})}$ is the quantum state which decides the
$n_{S}$ input bits $\bm{x_{S}}$, considered as input of a BQP-complete
language $\mathcal{L}$ over the bitstrings $\bm{x_{S}}\in\\{0,1\\}^{n_{S}}$ .
$W({\bm{\alpha}})$ is an unknown parametrized unitary, in order to prove
classical hardness it is sufficient to consider $W({\bm{\alpha}}=0)=I^{\otimes
n_{S}}$ and the measurement operator to be $O=Z\otimes I\otimes...\otimes I$
on the $n_{S}$ qubits register. The unitary $V_{A}$ rotates the measurement
operator $O$ so that, when $x_{1}=0$, the final measurement is an operator
$Q_{\bm{x_{Q}}}$ described by the bitstring $\bm{x_{Q}}$. This provides the
right training samples to learn $W(\bm{\alpha})$, as explained in the proof of
Theorem 3.

###  4.1 Relationship to Hamiltonian learning

In order to further elucidate the lines between settings with and without
classical/quantum learning advantages, we can establish a connection between
the task of learning Hamiltonians from time-evolved quantum states and
learning unitarily-parametrized observables. The setting of the Hamiltonian
learning problem is the following. Given an unknown local Hamiltonian in the
form of $H(\bm{\lambda})=\sum_{i}\lambda_{i}P_{i}$, the objective of the
Hamiltonian learning procedure is to recover $\bm{\lambda}$. In the version of
the problem we consider, we are given a black box which implements the time
evolution under the unknown Hamiltonian $H(\bm{\lambda})$ on any arbitrary
quantum state. The black box action on arbitrary inputs $\rho$ is given by

$\rho\rightarrow U\rho U^{\dagger}$ (11)

with $U=e^{itH(\bm{\lambda})}$, where the evolution time $t$ is known to us.
In [HKT22a] the authors provide a classical algorithm which learns the unknown
$\bm{\lambda}$ from the expectation values of the Pauli string $P_{i}$ on
polynomially many copies of the evolved state $U\rho U^{\dagger}$, for
particular choices of initial states $\rho$’s. We can rephrase the Hamiltonian
learning task in terms of a learning problem with many similarities to the
ones we considered before. Concretely we define the corresponding concept
class

$\displaystyle\mathcal{F}_{\bm{\lambda}}$
$\displaystyle=\\{f^{\bm{\lambda}}(\bm{x})\in\mathbb{R}\;\;|\;\;\bm{\lambda}\in[-1,1]\\}$
(12) $\displaystyle\text{with }\;f^{\bm{\lambda}}(\bm{x}):$
$\displaystyle\;x\in\mathcal{X}\subseteq\\{0,1\\}^{n}\rightarrow\text{Tr}[\rho(\bm{x})O(\bm{\lambda})]\;\;\&\;\;O(\bm{\lambda})=\sum_{i}^{m}U(\bm{\lambda})^{\dagger}P_{i}U(\bm{\lambda}).$
(13)

where $x$ describes the input state $\rho(\bm{x})$, and
$U=e^{itH(\bm{\lambda})}$. Considering
$\mathcal{T}^{\bm{\lambda}}={(\bm{x}_{\ell},\text{Tr}[\rho(\bm{x}_{\ell})O(\bm{\lambda})])}_{\ell}$
as training data, the connection to the Hamiltonian learning task of [HKT22a]
becomes evident if we demand that the learning algorithm needs only to
identify, rather than evaluate, the correct concept that generated the data.
It is worth noting that the concept class $\mathcal{F}_{\bm{\lambda}}$ closely
resembles the concept class for the time evolution problem described earlier,
for which a learning advantage was demonstrated. The main difference is that
in $\mathcal{F}_{\bm{\lambda}}$ the unknown observable is no longer a linear
combination of Pauli strings, instead each Pauli string in $O(\bm{\lambda})$
is parameterized by a unitary. As we are requiring to only identify the
correct concept and considering that the authors in [HKT22a] provide an
algorithm capable of solving the Hamiltonian Learning problem in polynomial
time (for sufficiently small $t$), one might suppose that the classical
difficulty associated with the learning advantage presented in this work
arises solely from the challenge of evaluating the correct concept rather than
from the task of identifying it. This would answer another question left open
in [GD23], at least in the case of concepts labeled by observables with an
unknown unitary parameterization. However it must be noted that for the
Hamiltonian learning algorithm in [HKT22a] to work, the input states
$\rho(\bm{x})$ in Eq.(12) are of a very particular and simple form and do not
come from a distribution $\mathcal{D}$ of $\mathrm{BQP}$ complete quantum
states $\rho_{H_{\mathrm{hard}}}(\bm{x})$ as we assumed in our classical
hardness result. For general input distributions, the hardness of
identification thus remains elusive. In this regard it is important to note
that the task of identification can take various forms. For instance, here we
are focusing on identifying the concept within the concept class that
generated the data, and in this case, it is generally unclear when this
setting allows a classical-efficient solution. In a more general scenario one
could ask if the learning algorithm is able to identify a model from a
hypothesis class that differs from the concept class but that it is still
capable of achieving the learning condition. Colloquially here the question
becomes: can traditional machine learning determine which quantum circuit
could accurately label the data, even though classical computers lack the
capability to evaluate such quantum circuits. In [GD23] it was proven that in
this broader context provable speed-ups in identification are no longer
possible. This is because the classical algorithm can successfully identify a
sophisticated quantum circuit that carries out the entire quantum machine
learning process as its subroutine, thereby delegating the learning aspect to
the labeling function itself, prior to evaluating a data point. Thus the task
of identification is indeed only interesting when the hypothesis class is
somehow restricted, which is often the case in practically relevant learning
scenarios.

## Acknowledgments

This publication is part of the project Divide & Quantum (with project number
1389.20.241) of the research programme NWA-ORC which is (partly) financed by
the Dutch Research Council (NWO). This work was also supported by the Dutch
National Growth Fund (NGF), as part of the Quantum Delta NL programme. This
work was also supported by the European Union’s Horizon Europe program through
the ERC CoG BeMAIQuantum (Grant No. 101124342)

##  Appendix A Proof of Theorem 1

As anticipated in the main text, the proof of the main theorem of our work
consists of two parts. First, we show that there exists a family of
hamiltonians $H_{\mathrm{hard}}\in\mathcal{H}_{\mathrm{hard}}$ and observables
$O$ such that the concept class
$\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$ is not classically
learnable, unless
$\mathrm{BQP}\subseteq\mathrm{HeurP}^{\mathcal{D}}/\mathrm{poly}$ for every
distribution $\mathcal{D}$. Second, we rigorously prove that Algorithm 1
learns $\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$ in polynomial
time. We formally derive the proofs for the concept class
$\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$ of measurements on
time-evolved states. However, as we discussed in the main text, the same
proofs can be easily extended for the class
$\mathcal{F}^{\mathcal{H},O}_{\mathrm{g.s.}}$ of measurements on ground state
of local Hamiltonians through the Kitaev’s circuit-to-hamiltonian
construction. Before stating the main proof, let prove an useful lemma which
guarantees the BQP-completeness of constant time Hamiltonian evolution
following the idea in present in [Chi04].

######  Lemma 3 (Constant time evolution is BQP-complete).

For any $k-$gate quantum circuit $U=U_{k}...U_{2}U_{1}$ which acts on $n$
qubits there exists a local Hamiltonian $H$ such that for any $n$ qubit inital
state $\ket{\psi}$ :

$e^{iHt}\ket{\psi}\ket{0}=U_{k}...U_{2}U_{1}\ket{\psi}\ket{k}$ (14)

for $t=\pi$.

###### Proof.

Consider the Feymann clock Hamiltonian [Fey85, Nag10]:

$H:=\sum_{j=1}^{k}H_{j}$ (15)

where:

$H_{j}=U_{j}\otimes\ket{j}\bra{j-1}+U^{\dagger}_{j}\otimes\ket{j-1}\bra{j}$
(16)

notice that using the common unary encoding for the clock register, such
Hamiltonian is 4 local [Nag10]. Furthermore, the Hamiltonian $H$ acts on two
different registers: the first register (“work register”) consists of $n$
qubit and it will store the computation of the circuit $U$, the second
register (“clock register”) contains $k+1$ qubit and it acts as a counter
which records the progress of the computation. Now, if we evolve an initial
state $\ket{\psi_{0}}=\ket{\psi}\ket{0}$ under the Hamiltonian $H$ the evolved
state will be in the space spanned by the $k+1$ states
$\\{\ket{\psi_{j}}=U_{j}...U_{2}U_{1}\ket{\psi}\ket{j}\\}_{j=0}^{k}$. After
letting the system evolve for a time $\tau$, if now we measure the clock
register and obtain a value $L$ then the work register will exactly contains
the computation of the quanutm circuit $U$ on the initial state $\ket{\psi}$.
This of course will happen only with a certain probability and while there are
many ways to boost such probabilities of getting the desired final state
$\ket{\psi_{k}}=U_{k}...U_{2}U_{1}\ket{\psi}\ket{k}$ we will show how to
modify the Feynmann’s Hamiltonian in Eq. (15) in order to make the evolution
perfect as in Eq. (14).

Notice first that in the subspace spanned by the vectors
$\\{\ket{\psi_{j}}\\}_{j=0}^{k}$ the non zero entries of the matrix $H$ are

$\bra{\psi_{j}}H\ket{\psi_{j\pm 1}}=1$ (17)

We now follow the idea in [Chi04] and modify the Hamiltonian in (15) in the
following way:

$H^{\prime}:=\sum_{j=1}^{k}\sqrt{j(k+1-j)}\;H_{j}$ (18)

The idea in [Chi04] is to associate each state in
$\\{\ket{\psi_{j}}\\}_{j=0}^{k}$ to a quantum system of total angular momentum
$\frac{k}{2}(\frac{k}{2}-1)$ with $z$ component $j-\frac{k}{2}$. The
association is possible by the fact that a system with total angular momentum
$\frac{k}{2}(\frac{k}{2}-1)$ will allow $k+1$ states with $z$ components of
values $-\frac{k}{2},-\frac{k}{2}+1,...,\frac{k}{2}-1,\frac{k}{2}$. These are
exactly the $k+1$ states in $\\{\ket{\psi_{j}}\\}_{j=0}^{k}$ and it is
possible to move among them defining the corresponding ladder operators :

$\displaystyle L_{-}\ket{\psi_{j}}$
$\displaystyle=\sqrt{j(k+1-j)}\ket{\psi_{j-1}}$ (19) $\displaystyle
L_{+}\ket{\psi_{j}}$ $\displaystyle=\sqrt{(k-j)(j+1)}\ket{\psi_{j+1}}$ (20)

By the algebra of the angular momentum, the $x$ component of the total angular
momentum $J_{x}$ can be expressed as

$J_{x}=\frac{1}{2}(L_{+}+L_{-})$ (21)

Comparing Eq.(17) with Eq. (19) it is clear that $H^{\prime}$ is exactly the
$x$ component of the angular momentum operator defined over the states
$\\{\ket{\psi_{j}}\\}_{j=0}^{k}$. As $J_{x}$ rotates between the states with
$z$ component $\pm\frac{k}{2}$ in time $t=\pi$, this concludes the proof.

∎

###  A.1 Classical hardness

######  Theorem 4 (Lemma 1 in the main text).

Under the assumption that there exists a distribution $\mathcal{D}^{\prime}$
such that
$\mathrm{BQP}\not\subset\mathrm{HeurP}^{\mathcal{D}^{\prime}}/\mathrm{poly}$,
then for any BQP-complete language there exists an associated input
distribution $\mathcal{D}$ and a Hamiltonian $H_{\mathrm{hard}}$ such that no
randomized polynomial-time classical algorithm $A_{c}$ is such that
$h_{cl}(.)=A_{c}(T^{\bm{\alpha}},.)$ satisfies the learning condition of Def.
1 for the concept class $\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$
with $x$ sampled from $\mathcal{D}$.

###### Proof.

The main idea of the proof is to show that if there exists a classical
algorithm which learns by Def. 1 the time evolution problem for any local
Hamiltonian, then such algorithm could decide any BQP language on average
implying $\mathrm{BQP}\subseteq\mathrm{HeurP}^{\mathcal{D}}/\mathrm{poly}$,
for any $\mathcal{D}$. As in Lemma 3 in [GD23] it is proved that, under widely
believed assumptions, for any BQP complete language $\mathcal{L}$ there always
exists a distribution $\mathcal{D}$ such that
$(\mathcal{L},\mathcal{D})\not\subset\mathrm{HeurP}/\mathrm{poly}$, such
classical algorithm cannot exist. Be $\\{U^{n}_{BQP}\\}_{n}$ a family of
quantum circuit which decides the BQP complete language $\mathcal{L}$, one
circuit per size. Precisely, that means that for any $x\in\\{0,1\\}^{n}$
measuring the first qubit in the computational basis on the state
$U^{n}_{BQP}\ket{\bm{x}}$ will output 1 (or 0) with probability greater that
2/3 if $\bm{x}\in\mathcal{L}$ ($\bm{x}\not\in\mathcal{L}$). It is obvious that
the the quantum model $f^{O^{\prime}}=\text{Tr}[\rho(\bm{x})O^{\prime}]$
correctly decides every $\bm{x}\in\mathcal{L}$ if
$\rho(\bm{x})=U^{n}_{BQP}\ket{\bm{x}}\bra{\bm{x}}(U^{n}_{BQP})^{\dagger}$ and
$O^{\prime}=Z\otimes\underbrace{I\otimes...\otimes I}_{n-1}$. In fact
measuring the first qubit of $U^{n}_{BQP}\ket{\bm{x}}$:

  1. 1.

For all $\bm{x}\in\mathcal{L}$, $f^{O^{\prime}}(\bm{x})=$ Pr[the output of
$U^{n}_{BQP}$ applied on the input $\ket{\bm{x}}$ is $1$] - Pr[the output of
$U^{n}_{BQP}$ applied to the input $\ket{\bm{x}}$ is $0$] $\geq 2/3-1/3=1/3$.

  2. 2.

For all $\bm{x}\notin\mathcal{L}$, $f^{O^{\prime}}(\bm{x})=$ Pr[the output of
$U^{n}_{BQP}$ applied on the input $\ket{\bm{x}}$ is $1$] - Pr[the output of
$U^{n}_{BQP}$ applied to the input $\ket{\bm{x}}$ is $0$] $\leq 1/3-2/3=-1/3$.

Therefore, as $f^{O^{\prime}}(\bm{x})>0$ if $\bm{x}\in\mathcal{L}$ and
$f^{O^{\prime}}(\bm{x})<0$ if $\bm{x}\notin\mathcal{L}$ such quantum model
could efficiently decide the language $\mathcal{L}$. By Lemma 3 for every $n$
there exist a 4-local Hamiltonian $H_{\mathrm{\mathrm{hard}}}$ such that
evolving the state $\ket{\bm{x}}$ for a time $t=\pi$ under it will produce the
state $U^{n}_{\mathrm{BQP}}\ket{\bm{x}}$ (on the work register). Since such
constructed $H_{\mathrm{hard}}$ is local, its time evolution can be
efficiently implemented on a quantum computer. Working towards a
contradiction, assume now that there exists an algorithm $A_{c}$ which learns
$\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$ with respect to the
distribution $\mathcal{D}$ by Def.1. Then it means that there exists a
randomized classical algorithm which makes use of data such that
$h_{cl}(.)=A_{c}(H_{\mathrm{hard}},\mathcal{T}^{\bm{\alpha}},.)$ satisfies
$\forall\epsilon\geq 0$ and $\forall
f^{\bm{\alpha}}\in\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$ the
condition:

$\mathbb{E}_{\bm{x}\sim\mathcal{D}}\big{[}\;|f^{{\bm{\alpha}}}(\bm{x})-h_{cl}(\bm{x})|^{2}\;\big{]}\leq\epsilon$
(22)

with high probability over the choice of the training dataset and the internal
randomization of $A_{c}$. We want now to show that the classical model
$h_{cl}$ would be able to decide the language $\mathcal{L}$ on average with
respect to $\mathcal{D}$. Firstly notice that as the algorithm $A_{c}$
succeeds with high probability, there exists a fixed dataset
$\mathcal{T}^{\prime\bm{\alpha}}$ and a fixed bitrsting $r^{\prime}$ for its
internal randomization such that
$h^{\prime}_{cl}(.)=A_{c}(H_{\mathrm{hard}},\mathcal{T}^{\prime\bm{\alpha}},r^{\prime},.)$
satisfies Eq.(22). Throughout the reminder of the proof let us fix such
dataset $\mathcal{T}^{\prime\bm{\alpha}}$ and random bitstring $r^{\prime}$.
Also, since Def. 1 assumes Eq. (22) is satisfied for every concept
${\bm{\alpha}}$, such an $A_{c}$ would be able to evaluate on avarage the
particular concept ${\bm{\alpha}}^{\prime}$ which corresponds to the
observable $O({\bm{\alpha}}^{\prime})=O^{\prime}=Z\otimes I\otimes...\otimes
I$. We now show that such classical algorithm would be able to decide the
language $\mathcal{L}$ in $\mathrm{HeurP}/\text{poly}$ with respect to the
distribution $\mathcal{D}$. Remember that a language $L$ and distribution $D$
is in $\mathrm{HeurP}/\text{poly}$ if there exist a classical algorithm
$\mathcal{A}$ and a polynomial-size advice string $\omega$ such that

$\text{Pr}_{\bm{x}\sim\mathcal{D}}[\mathcal{A}(\omega,\bm{x})\neq
L(\bm{x})]\leq\epsilon$ (23)

where $L(\bm{x})=1$ if $\bm{x}\in L$ and 0 otherwise. Notice that Eq.(23) is
equivalent to

$\sum_{\bm{x}\in\mathcal{X}_{err}}p(\bm{x})\leq\epsilon$ (24)

where $\mathcal{X}_{err}$ is the set of input $\bm{x}$ such that
$[\mathcal{A}(\omega,\bm{x})\neq L(\bm{x})]$, i.e.
$\mathcal{X}_{err}=\\{\bm{x}\in\\{0,1\\}^{n}\;\;|\;\;[\mathcal{A}(\omega,x)\neq
L(\bm{x})\\}$, and $p(\bm{x})$ is the probability associated to the input
$\bm{x}$ with respect to the distribution $\mathcal{D}$.
Consider now the previously introduced language $\mathcal{L}$ and distribution
$\mathcal{D}$ such that
$(\mathcal{L},\mathcal{D})\not\subset\text{HeurP}/\text{poly}$. Consider the
classical algorithm $h^{\prime}_{cl}$ which satisfies the learning condition
in Eq. (22) with an error $\epsilon^{\prime}=0.09\epsilon$ for the concept
defined by ${\bm{\alpha}}^{\prime}$ above. Let define now the set
$\mathcal{X}\subseteq\\{0,1\\}^{n}$ to be the set of inputs such that
$\mathcal{X}=\\{\bm{x}\in\mathcal{X}\text{ s.t.
}|f^{{\bm{\alpha}}^{\prime}}(\bm{x})-h^{\prime}_{cl}(\bm{x})|\geq 0.3\\}$, so
that:

$\displaystyle\epsilon^{\prime}$
$\displaystyle\geq\mathbb{E}_{\bm{x}\sim\mathcal{D}}\big{[}\;|f^{{\bm{\alpha}}}(\bm{x})-h^{\prime}_{cl}(\bm{x})|^{2}\;\big{]}$
(25)
$\displaystyle\geq\sum_{\bm{x}}|f^{{\bm{\alpha}}}(\bm{x})-h^{\prime}_{cl}(\bm{x})|^{2}p(\bm{x})$
(26)
$\displaystyle\geq\sum_{\bm{x}\in\mathcal{X}}|f^{{\bm{\alpha}}}(\bm{x})-h^{\prime}_{cl}(\bm{x})|^{2}p(\bm{x})+\sum_{\bm{x}\not\in\mathcal{X}}|f^{{\bm{\alpha}}}(\bm{x})-h^{\prime}_{cl}(\bm{x})|^{2}p(\bm{x})$
(27) $\displaystyle\geq 0.09\sum_{x\in\mathcal{X}}p(\bm{x})$ (28)

From last equation we obtain that
$\sum_{\bm{x}\in\mathcal{X}}p(\bm{x})\leq\epsilon$. Notice that the classical
algorithm $h^{\prime}_{cl}$ is such that $h^{\prime}_{cl}(\bm{x})>0$ if
$x\in\mathcal{L}$ and $h^{\prime}_{cl}(\bm{x})<0$ if $\bm{x}\in\mathcal{L}$
for every $\bm{x}\in\\{0,1\\}^{n}/\mathcal{X}$. Then, the condition
$\sum_{\bm{x}\in\mathcal{X}}p(\bm{x})\leq\epsilon$ is exactly the defining
condition of $\mathrm{HeurP}/\mathrm{poly}$ in Eq.(24). This implies that the
classical algorithm $A_{cl}$ using as advice $\mathcal{T}^{\prime\bm{\alpha}}$
and $r^{\prime}$ is able to decide the language $\mathcal{L}$ in
$\mathrm{HeurP}/\mathrm{poly}$ with respect to the distribution $\mathcal{D}$.
This concludes the proof. ∎

###  A.2 Quantum Learnability

In this Section we prove that Algorithm 1 satisfies the learning condition in
Def. 1 using only polynomial resources in both time and samples. As a first
step, notice that the quanutm states $\rho_{H_{\mathrm{hard}}}(\bm{x})$ in Eq.
(1) of $\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$ are easily
preparable on a quantum computer.

Since the quantum algorithm can efficiently prepare time evolved states of
local Hamiltonians, the quantum states
$\rho_{H_{\mathrm{hard}}}(\bm{x})=U\ket{\bm{x}}\bra{\bm{x}}U^{\dagger}$ with
$U=e^{iH_{\mathrm{\mathrm{hard}}}\pi}$ can efficiently be prepared on a
quantum computer. In order to demonstrate the quantum learnability of
$\mathcal{F}^{H_{\mathrm{hard}},O}_{\mathrm{evolved}}$, all that remains is to
rigorously bound the sample and time complexity of Algorithm 1 in the
following Theorem 6. As the bound obtained on the sample complexity derives
from the generalization bound of the LASSO algorithm [MRT18, LHT+24], we first
repeat this result.

######  Theorem 5 (Theorem 11.16 in [MRT18]).

Let $\mathcal{X}\subseteq\mathbb{R}^{A}$ and
$\mathcal{C}=\\{\bm{x}\in\mathcal{X}\mapsto\vec{w}\cdot\bm{x}:\|\vec{w}\|_{1}\leq
B\\}$. Let
$\mathcal{S}=((\bm{x}_{1},y_{1}),\dots,(\bm{x}_{N},y_{N}))\in(\mathcal{X}\times\mathcal{Y})^{N}$.
Let $\mathcal{D}$ denote a distribution over $\mathcal{X}\times\mathcal{Y}$
according to which the training data $\mathcal{S}$ is drawn. Assume that there
exists $r_{\infty}>0$ such that for all $\bm{x}\in\mathcal{X}$,
$\|x\|_{\infty}\leq r_{\infty}$ and $M>0$ such that $|h(\bm{x})-y|\leq M$ for
all $(\bm{x},y)\in\mathcal{X}\times\mathcal{Y}$. Then, for any $\delta>0$,
with probability at least $1-\delta$, each of the following inequalities holds
for all $h\in\mathcal{C}$:

$\mathbb{E}_{(\bm{x},y)\sim\mathcal{D}}[|h(\bm{x})-y|^{2}]:=R(h)\leq\hat{R}_{\mathcal{S}}(h)+2r_{\infty}BM\sqrt{2\log(2|A|)N}+M\sqrt{2\log(1/\delta)}/{2N}$

where $R(h)$ is the prediction error for the hypothesis $h$ and
$\hat{R}_{\mathcal{S}}(h)$ is the training error of $h$ on the training set
$\mathcal{S}$.

We are now ready to state Theorem 6 which provides a rigorous guarantee on the
number of samples and the time complexity required by Algorithm 1.

######  Theorem 6 (Lemma 2 in the main text).

Given $n$, $\delta,\epsilon\geq 0$ and a training data set
$\mathcal{T}^{\bm{\alpha}}_{N}=\\{(\bm{x}_{\ell},y_{\ell})\\}_{\ell=1}^{N}$ of
size

$N=\mathcal{O}\left(\frac{\log(n/\delta)n}{\epsilon}\right)$ (29)

where $x_{\ell}$ is sampled from an unknown distribution $\mathcal{D}$ over
$x\in\\{0,1\\}^{n}$ and
$|y_{\ell}-\text{Tr}(O({\bm{\alpha}})\rho(\bm{x}_{\ell}))|\leq\epsilon$ for
any geometrically local observable
$O({\bm{\alpha}})=\sum_{i}^{m}{\bm{\alpha}}_{i}P_{i}$ with
$P_{i}\in\\{I,X,Y,Z\\}^{\otimes n}$ and ${\bm{\alpha}}\in[-1,1]^{m}$, and
$\rho(\bm{x})=U(\bm{x})\ket{0}\bra{0}U^{\dagger}(\bm{x})$. Then there exists a
quantum algorithm $\mathcal{A}_{q}(\mathcal{T}_{N},x)=h(\bm{x})$ such that:

$\mathbb{E}_{x\sim\mathcal{D}}|h(\bm{x}_{l})-\text{Tr}[O({\bm{\alpha}})\rho(\bm{x})]|^{2}\leq\epsilon$
(30)

with probability at least $1-\delta$. The computational time of the quantum
algorithm is bounded in $\mathcal{O}(nN)$

###### Proof.

The proof of the theorem is based on the well known bound on the prediction
error of the LASSO algorithm of Theorem 5. Consider the algorithm described in
Algorithm 1. First, we demonstrate now that Algorithm 1 satisfies the
condition of Theorem 6. In our setting, the input space of the learned model
$h$ is $\mathcal{X}=[-1,1]^{m}\subset\mathbb{R}^{m}$ as we consider $h$ a
function of the $m-$dimensional feature vector $\phi(\bm{x})$. Clearly,
$||\phi(\bm{x})||_{\infty}\leq 1$ for all $x\in\mathcal{X}$. The hypothesis
class $\mathcal{C}$ of our algorithm is given by the set of function of the
same form of the learned $h$, i.e.
$\mathcal{C}=\\{\phi(\bm{x})\in\mathcal{X}\rightarrow
w\cdot\phi(\bm{x}):||w||_{1}\leq B\\}$ with $B=poly(n)$. With respect to
Theorem 6, we can also choose $M=poly(n)$ so that $|h(\bm{x}_{l})-y_{l}|<M$
for all $l=1,...,N$:

$|h(\bm{x}_{l})-y_{l}|\leq|w\cdot\phi(\bm{x}_{l})|+|y_{l}|\leq||w||_{1}||\phi(\bm{x}_{l})||_{\infty}+2\leq
poly(n)$ (31)

Where the second inequalitiy follows by Hölder’s inequality. By Theorem 6
then, the bound on the prediction error $R(h)$ of the learned model
$h(\bm{x})=w^{*}\phi(\bm{x})$ is

$R(h)\leq\hat{R}(h)+2BM\sqrt{\frac{2\log(2m)}{N}}+M^{2}\sqrt{\frac{\log\delta^{-1}}{2N}}$
(32)

where $\hat{R}(h)$ is the training error on the dataset $T^{\bm{\alpha}}_{N}$.

We now bound the training error $\hat{R}(h)$. Let $\epsilon_{1}$ be the
maximum sampling error associated to the measurement of a Pauli observable on
$\rho(\bm{x}_{\ell})$, i.e.

$\epsilon_{1}=\max_{\begin{subarray}{c}i\in[1,...,m]\\\
\bm{x}\in\\{0,1\\}^{n}\end{subarray}}\;\;|[\rho(\bm{x})P_{i}]-\phi(\bm{x}_{i})|$
(33)

Let also $\epsilon_{2}$ the maximum sampling error associated to $y_{\ell}$,
such that:

$|y_{\ell}-\text{Tr}[O({\bm{\alpha}})\rho(\bm{x}_{l})]|\leq\epsilon_{2}\;\;\;\;\;\forall(\bm{x}_{\ell},y_{\ell})\in
T^{\bm{\alpha}}_{N}$ (34)

We can now derive a bound on the training error for the optimal value of
$w_{opt}={\bm{\alpha}}$ of the model
$h_{opt}(\bm{x})={\bm{\alpha}}\cdot\phi(\bm{x})$:

$\displaystyle\hat{R}(h_{opt})=\frac{1}{N}\sum_{\ell=1}^{N}|h_{opt}(\bm{x}_{\ell})-y_{\ell}|^{2}$
$\displaystyle\leq\max_{\ell}|h(\bm{x}_{\ell})-y_{\ell}|$ (35)
$\displaystyle\leq(|\text{Tr}[\rho(\bm{x}_{\ell^{*}})O({\bm{\alpha}})]-h(\bm{x}_{\ell^{*}})|+|\text{Tr}[\rho(\bm{x}_{\ell^{*}})O({\bm{\alpha}})]-y_{\ell}|)^{2}$
(36)
$\displaystyle\leq\left(\left(\sum_{i}|{\bm{\alpha}}_{i}|\right)\epsilon_{1}+\epsilon_{2}\right)^{2}$
(37) $\displaystyle\leq(B\epsilon_{1}+\epsilon_{2})^{2}$ (38)

In practice, we can require to the LASSO algorithm to obtain a $w^{*}$ which
achieves a training error at most $\epsilon_{3}/2$ larger than the optimal
one. We can obtain such precision by setting $B=poly(n)$. Formally, we have

$\hat{R}(h)\leq\frac{\epsilon_{3}}{2}+\min_{\begin{subarray}{c}w\in\mathbb{R}^{m}\\\
||w||_{1}\leq
B\end{subarray}}\frac{1}{N}\sum_{\ell=1}^{N}|w\cdot\phi(\bm{x}_{\ell})-\text{Tr}[\rho(\bm{x}_{\ell})O({\bm{\alpha}})]|^{2}$
(39)

Because we have set $B=poly(n)$, we have that the second term must be at most
$\hat{R}(h_{opt})$ and therefore we have

$\hat{R}(h)\leq(B\epsilon_{1}+\epsilon_{2})^{2}+\frac{\epsilon_{3}}{2}$ (40)

We note that as $B\leq\mathcal{O}(poly(n))$ we can bound the error
$\epsilon^{\prime}_{1}=B\epsilon_{1}$ to scale polynomially to zero by just
reducing the sampling error $\epsilon_{1}$ using polynomially many more copies
of each $\rho(\bm{x}_{l})$. Thus we can rewrite equation (32) as

$R(h)\leq(\epsilon^{\prime}_{1}+\epsilon_{2})^{2}+\frac{\epsilon_{3}}{2}+2BM\sqrt{\frac{2\log(2m)}{N}}+M^{2}\sqrt{\frac{\log(\delta)^{-1}}{2N}}$
(41)

Then, in order to bound the prediction error above by
$\epsilon=(\epsilon^{\prime}_{1}+\epsilon_{2})^{2}+\epsilon_{3}$ we need to
choose an N such that

$2BM\sqrt{\frac{2\log(2m)}{N}}+M^{2}\sqrt{\frac{\log(\delta)^{-1}}{2N}}\leq\frac{\epsilon_{3}}{2}$
(42)

By substituting $M=B$ we obtain that:

$2BM\sqrt{\frac{2\log(2m)}{N}}+M^{2}\sqrt{\frac{\log(\delta)^{-1}}{2N}}\leq\left(\frac{B^{2}}{\sqrt{N}}(\sqrt{2\log(2\mathcal{O}(n))}+\sqrt{\log(\delta^{-1})}\right)$
(43)

so that it is upper bounded by $\epsilon_{3}/2$ choosing $N$ as

$\displaystyle N$
$\displaystyle=2\frac{B^{4}\sqrt{2\log(\mathcal{O}(n)/\delta)}}{\epsilon_{3}}$
(44) $\displaystyle\sim\frac{\log(n/\delta)poly(n)}{\epsilon_{3}}$ (45)

By setting $\epsilon^{\prime}_{1}=0.2\epsilon$, $\epsilon_{2}=\epsilon$, and
$\epsilon_{3}=0.4$ we have
$(\epsilon^{\prime}_{1}+\epsilon_{2})^{2}+\epsilon_{3}\leq\epsilon$ and
recover the claim of the Theorem.

Finally we bound the efficiency of our algorithm. The training time is
dominated by the creation of the feature map $\phi(\bm{x}_{\ell})$ for each
training point and by the LASSO regression over the corresponding feature
space. To create the vector $\phi(\bm{x})$ the quantum algorithm needs to
prepare multiple copies of $\rho(\bm{x}_{\ell})$ $\forall\bm{x}_{\ell}\in
T_{N}^{\bm{\alpha}}$. As seen before, only a polynomial number of copies are
sufficient to achieve a desired error $\epsilon^{\prime}_{1}$, so that the
whole process takes time $\mathcal{O}(nN)$. For the LASSO regression, it is
known that to obtain a training error at most $\epsilon_{3}/2$ larger than the
optimal function value, the LASSO algorithm on the feature space of
$\phi(\bm{x})$ can be executed in time $\mathcal{O}\left(\frac{m_{\phi}\log
m_{\phi}}{\epsilon^{2}_{3}}\right)$ [HK12], where in our case $m_{\phi}=m$. It
is easy to show that even this time is bounded by $\mathcal{O}(nN)$. The
prediction time corresponds to the time for the evaluation of the learned
model $h(\bm{x})=w^{*}\cdot\phi(\bm{x})$ which takes time
$\mathcal{O}(m)\sim\mathcal{O}(n)$. In conclusion, the overall time of the
quantum algorithm is bounded by $\mathcal{O}(nN)$

∎

##  Appendix B Proof of Theorem 3 and Corollary 1

We rewrite here Theorem 3 form the main text, formalizing the result and
providing a detailed proof.

######  Theorem 7 (Theorem 3 in the main text).

Given a discrete set of polynomially describle quantum states
$S=\\{\ket{\psi_{\ell}}\\}_{\ell}$ and measurements operators
$Q=\\{Q_{m}\\}_{m}$. Then for every efficient (non-adaptive) algorithm
$\mathcal{A}_{W}$ which learns an arbitrary unitary $W$ from query access to
it on states from $S$ and measured by operators in $Q$ there exists a
distribution $\mathcal{D}$ over $\\{0,1\\}^{n}$, a family of unitaries
$\\{U(\bm{x})\\}_{\bm{x}}$ and a measurement $O$ for which the concept class
$\mathcal{M}_{U,W,O}$ exhibits a learning advantage.

###### Proof.

We can think at the algorithm $\mathcal{A}_{W}$ as an algorithm which receives
in input pairs of $\\{(\ket{\psi_{\ell}},y^{m_{\ell}}_{\ell})_{\ell}\\}$,
where $\ket{\psi_{\ell}}\in S$ and $y^{m_{\ell}}_{\ell}\in\mathbb{R}$ is the
measurement outcome of a randomly selected operator $Q_{m_{l}}\in Q$ on
$\ket{\psi_{\ell}}$, and for any $\epsilon\geq 0$ outputs a matrix $\tilde{W}$
such that $||\tilde{W}-W||\leq\epsilon$ in some norm distance. The idea to
construct a $\mathcal{M}_{U,W,O}$ which exhibits a separation is the
following, illustrated also in Figure 1. Consider the family of quantum states
$\\{\ket{\psi_{U}(\bm{x})}\\}_{\bm{x}}$ constructed by parameterized unitaries
$\\{U(\bm{x})\\}_{\bm{x}}$ in the following way, depending on the input
$\bm{x}\in\\{0,1\\}^{n}$:

  * •

The first $1+n_{Q}$ qubit of $\ket{\psi_{U}(\bm{x})}$ are initializated in the
state $\ket{x_{1}}\otimes\ket{x_{2}x_{3}...x_{n_{Q}+1}}$, the remaining
$n_{S}=n-(1+n_{Q})$ qubit $\bm{x_{S}}=x_{n-n_{S}}x_{n-(n_{S}-1)}...x_{n}$ are
in the state $\ket{0^{\otimes n_{S}}}$.

  * •

If the first bit $x_{1}$ is 0, then $U(\bm{x})$ prepares on the $n_{S}$ qubits
register the state $\ket{\psi_{\bm{x_{S}}}}$ from the set $S$ described by the
bitstring $\bm{x_{S}}\in\\{0,1\\}^{n_{S}}$. As we assumed that every state in
$S$ allows a polynomial classical description, we only need an input
$\bm{x}\in\\{0,1\\}^{n}$ of polyinomial size. We thus have:

$U(\bm{x})\left(\ket{0}\otimes\ket{\bm{x_{Q}}}\otimes\ket{0^{\otimes
n_{S}}}\right)=\ket{0}\otimes\ket{\bm{x_{Q}}}\otimes\ket{\psi_{stab}(\bm{x_{S}})}$
(46)

  * •

If the first bit $x_{1}$ is 1, then on the $n_{S}$ qubit register $U(\bm{x})$
prepares the state $\ket{\psi_{BQP}(\bm{x_{S}})}$ such that
$\bra{\psi_{BQP}(\bm{x_{S}})}Z\otimes I\otimes...\otimes
I\ket{\psi_{BQP}(\bm{x_{S}})}$ outputs $+1/3$ if the $n_{S}$ bitstring
$\bm{x_{S}}$ belongs to an arbitrary (previously fixed) BQP complete language
$\mathcal{L}$ defined over input $\bm{x_{S}}\in\\{0,1\\}^{n_{S}}$, while it
outputs $-1/3$ otherwise. Following the same arguments used in the proof of
Lemma 1, for any $\mathcal{L}\in\mathrm{BQP}$ it always exists such
$U(\bm{x})$. We thus have:

$U(\bm{x})\left(\ket{1}\otimes\ket{\bm{x_{Q}}}\otimes\ket{0^{\otimes
n_{S}}}\right)=\ket{1}\otimes\ket{\bm{x_{Q}}}\otimes\ket{\psi_{BQP}(\bm{x_{S}})}$
(47)

Regarding the unknown observable $O({\bm{\alpha}})$, we will consider a
measurement operator of the kind Eq.(9). Specifically we define a controlled
operator $V_{A}$, controlled by the $1+n_{Q}$ qubit register
$\ket{x_{1}x_{2}x_{3}...x_{n_{Q}+1}}$, such that
$V_{A}=\sum_{0\bm{x_{Q}}}\ket{0\bm{x_{Q}}}\bra{0\bm{x_{Q}}}\otimes
V(\bm{x_{Q}})$ with $\bm{x_{Q}}=x_{2}x_{3}...x_{n_{Q}+1}$ if $x_{1}=0$ and
$V_{A}=\sum_{1\bm{x_{Q}}}\ket{1\bm{x_{Q}}}\bra{1\bm{x_{Q}}}\otimes I^{\otimes
n_{S}}$ if $x_{1}=1$. The unitary matrices $V(\bm{x_{Q}})$ are defined such
that they rotate the measurement $O$ into the observable $Q_{\bm{x_{Q}}}\in Q$
described by the bitstring $\bm{x_{Q}}=x_{2}x_{3}...x_{n_{Q}+1}$, i.e.
$Q_{\bm{x_{Q}}}=V(\bm{x_{Q}})OV^{\dagger}(\bm{x_{Q}})$ where $O$ could be
taken as the local observable $Z_{1}=Z\otimes I^{\otimes n_{S}-1}$ on the
$n_{S}$ qubit register. The final observable $O(\bm{\alpha})$ will then be
$O(\bm{\alpha})=(I^{\otimes(1+n_{Q})}\otimes
W(\bm{\alpha})\;V_{A})O(V_{A}\;I^{\otimes(1+n_{Q})}\otimes
W(\bm{\alpha}))^{\dagger}$, with $W({\bm{\alpha}})$ an arbitrary unitary
parameterized by ${\bm{\alpha}}$. Furthermore, we define
$W({\bm{\alpha}}=\vec{0})=I\otimes...\otimes I$. We can now construct a
distribution $\mathcal{D}$ such that the concept class $\mathcal{M}_{U,W,O}$
exhibits a learning separation. For Lemma 1, there exists a distribution
$\mathcal{D}_{\mathrm{hard}}$ for which the concept
$f^{0}=\text{Tr}[\rho_{U}(\mathbf{x})V_{A}OV^{\dagger}_{A}]$ cannot be
efficiently learned by a classical algorithm when $U(\bm{x})$ is the circuit
which decides the BQP-complete language $\mathcal{L}$ over the $n_{S}$-sized
bitstrings $\bm{x_{S}}$. We now define the following distribution
$\mathcal{D}$ on the input bitsrings $\bm{x}\in\\{0,1\\}^{n}$:

  * •

The first bit $x_{1}$ of $\bm{x}$ is extracted randomly with equal probability
between 0 or 1.

  * •

If $x_{1}=0$ then the other $n-1$ bit $x_{2}x_{3}...x_{n}$ are extracted from
the required distribution by $\mathcal{A}_{W}$ to learn the unitary
$W(\bm{\alpha})$.

  * •

If $x_{1}=1$ then the following $n_{Q}$ bit $\bm{x_{Q}}$ are extracted
uniformly at random while the $n_{S}$ bit $\bm{x_{S}}$ are sampled with
respect to the distribution $\mathcal{D}_{\mathrm{hard}}$.

Classical hardness The classical hardness of the learning task comes directly
from the proof of Lemma 1. Consider the concept $f^{0}\in\mathcal{M}_{U,W,M}$
defined by $W(\bm{0})=I^{\otimes n_{S}}$. For the same reasoning of the proof
of Lemma 1 there cannot exists a polynomial sized classical circuit which
evaluates $f^{0}(\bm{x})$ correctly on average with respect to the
distribution $\mathcal{D}$ for the cases where $x_{1}=1$. As $x_{1}$ is
equally sampled between 0 and 1, no classical algorithm can meet the learning
condition of Eq. 1 on half of the input bitstrings, thus it can not learn the
concept $f^{0}\in\mathcal{M}_{U,W,O}$ in polynomial time for every $\epsilon$.
As the learning algorithm must suceed for every $\bm{\alpha}$, this suffices
to prove the classical hardness of the learning task.

Quantum learnability Recall that the data the learning algorithm receives for
a concept $f^{\bm{\alpha}}\in\mathcal{M}_{U,W,M}$ are
$\mathcal{T}^{\bm{\alpha}}=\\{\bm{x}_{\ell},y_{\ell}\\}_{\ell}$ with
$\mathbb{E}[y_{\ell}]=\text{Tr}[\rho_{U}(\bm{x}_{\ell})O({\bm{\alpha}})]$ and
$\rho_{U}(\bm{x}_{\ell})=\ket{\psi_{U}(\bm{x})}\bra{\psi_{U}(\bm{x})}$. Now,
in the case the first bit of $\bm{x}_{\ell}$ is 0, $\mathcal{T}^{\bm{\alpha}}$
are exaclty the pairs $\\{(\ket{\psi_{\ell}},y^{m}_{\ell})\\}_{\ell}$ required
by the algorithm $\mathcal{A}_{W}$ to learn $W(\bm{\alpha})$ and thus
$O(\bm{\alpha})$. As $x_{1}=0$ for half of the training samples in
$\mathcal{T}^{\bm{\alpha}}$, the quantum algorithm is able to learn
$O(\bm{\alpha})$ and evaluate it on any input state.

∎

We provide here the the rigorous proof of Corollary 1. The proof follows the
same steps of the one for Theorem 3 above while concretizing the result for
shallows $W$.

First, let us repeat the result in [HLB+24] for learning shallow unitaries. Be
stab1 the family of single qubit stabilizer states
$\mathrm{stab1}=\\{\ket{0},\ket{1},\ket{+},\ket{-},\ket{y+},\ket{y-}\\}$,
then:

######  Lemma 4 (Lemma 10 in [HLB+24], Learning a few-body observable with an
unknown support).

Given an error $\epsilon$, failure probability $\delta$, an unknown $n$-qubit
observable $O$ with $\|O\|_{\infty}\leq 1$ that acts on an unknown set of $k$
qubits, and a dataset
$\mathcal{T}_{O}(N)=\\{|\psi_{\ell}\rangle=\bigotimes_{i=1}^{n}|\psi_{\ell,i}\rangle,v_{\ell}\\}_{\ell=1}^{N}$,
where $|\psi_{\ell,i}\rangle$ is sampled uniformly from stab1 and $v_{\ell}$
is a random variable with
$\text{E}[v_{\ell}]=\langle\psi_{\ell}|O|\psi_{\ell}\rangle$,
$|v_{\ell}|=\mathcal{O}(1)$. Given a dataset size of

$N=\frac{2^{\mathcal{O}(k)}\log(n/\delta)}{\epsilon^{2}},$ (48)

with probability at least $1-\delta$, we can learn an observable $O^{\prime}$
such that $\|O^{\prime}-O\|_{\infty}\leq\epsilon$ and
$\textup{supp}(O^{\prime})\subseteq\textup{supp}(O)$. The computational
complexity is $\mathcal{O}(n^{k}\log(n/\delta)/\epsilon^{2})$.

The proof of Lemma 1 then goes by explicitly constructing a family of
parametrized circuit $\\{U(\bm{x})\\}_{\bm{x}}$ and an input distribution
$\mathcal{D}$ such that the concept class $\mathcal{M}_{U,W,M}$ is quantum
learnable using Lemma 4 while still being classically hard. Let rewrite here
Corollary 1

######  Corollary 2 (Corollary 1 in the main text).

There exists a family of parametrized unitaries $\\{U(\bm{x})\\}_{\bm{x}}$ and
parametrized shallow circuits $\\{W({\bm{\alpha}})\\}_{\bm{\alpha}}$, a
measurement $O$ and a distribution $\mathcal{D}$ over $\bm{x}\in\\{0,1\\}^{n}$
such that the concept class $\mathcal{M}_{U,W,O}$ is not classically learnable
with respect to the input distribution $\mathcal{D}$. However, there exists a
quantum algorithm which learns $\mathcal{M}_{U,W,O}$ on the input distribution
$\mathcal{D}$.

###### Proof.

Let first define the set of unitaries $\\{U(\bm{x})\\}_{\bm{x}}$,
$\\{W(\bm{\alpha})\\}_{\bm{\alpha}}$, measurement operator $O$ and input
distribution $\mathcal{D}$ on which the separation result holds. We provided a
graphical representation of it in Figure 2. Be
$n_{S}=\left\lfloor{\frac{n}{3}}\right\rfloor$, we define the set
$\\{U(\bm{x})\\}_{\bm{x}}$ as the set of unitaries which act on a $n_{S}+1$
qubit system in the following way, depending on the first bit $x_{1}$ of the
input $\bm{x}$.

If $x_{1}=0$ then each $U(\bm{x})$ is defined such that

$U(\bm{x})\left(\ket{x_{1}}\otimes\ket{0^{n_{S}}}\right)=\ket{x_{1}}\otimes\ket{\psi_{stab}(\bm{x})}$
(49)

where
$\ket{\psi_{stab}(\bm{x})}=\bigotimes_{i=1}^{n_{S}}\ket{\psi^{i}_{stab1}(\bm{x})}$
is a $n_{S}$ qubit tensor product of single qubit stabilizer states
$\ket{\psi^{i}_{stab1}(\bm{x})}\in\\{\ket{0},\ket{1},\ket{+},\ket{-},\ket{y+},\ket{y-}\\}$.
Since $n_{S}=\left\lfloor{\frac{n}{3}}\right\rfloor$, the output state
$\ket{\psi_{stab}(\bm{x})}$ is completely described by the remaining $n-1$
input bits $x_{2}x_{3}...x_{n}$.

Let consider now the case when $x_{1}=1$. Be $\mathcal{L}$ a BQP-complete
language defined over the input $\tilde{\bm{x}}\in\\{0,1\\}^{n_{S}}$. Then we
define the set of $\\{U(\bm{x})\\}_{\bm{x}}$ in the following way:

$U(\bm{x})\left(\ket{x_{1}}\otimes\ket{0^{n_{S}}}\right)=\ket{x_{1}}\otimes\ket{\psi_{BQP}(\bm{x})}$
(50)

where $\ket{\psi_{BQP}(\bm{x})}$ is such that
$\bra{\psi_{BQP}(\bm{x})}Z\otimes I\otimes...\otimes
I\ket{\psi_{BQP}(\bm{x})}=1/3$ if $\tilde{\bm{x}}\in\mathcal{L}$ and $-1/3$ if
$\tilde{\bm{x}}\not\in\mathcal{L}$. As we described in the Proof of Lemma 1,
such a circuit $U_{BQP}(\bm{x})$ always exists for any BQP language.

As a set of unitaries $\\{W(\bm{\alpha})\\}_{\bm{\alpha}}$ we consider any set
of parametrized unitaries acting on the $n_{S}$ qubit register such that for
each $\bm{\alpha}$ parameter $W(\bm{\alpha})$ is shallow and such that
$W(\bm{0})=I^{\otimes n_{S}}$. The $n_{S}$ qubit register is then measured by
the observable $M=Z\otimes I\otimes...\otimes I$. Finally we define the
distribution $\mathcal{D}$ on the input bitstrings $\bm{x}\in\\{0,1\\}^{n}$ to
be the following:

  * •

The first bit $x_{1}\in\\{0,1\\}$ of $\bm{x}$ is extracted randomly with equal
probability.

  * •

If $x_{1}=0$ then the other $n-1$ bit $x_{2}x_{3}...x_{n}$ are extracted
following the uniform distribution over $\\{0,1\\}^{n-1}$.

  * •

If $x_{1}=1$ then the following $n_{S}$ bits $x_{2}x_{3}...x_{n_{S}+1}$ are
extracted following the distribution $\mathcal{D}_{\mathrm{hard}}$ such that
$(\mathcal{L},\mathcal{D}_{\mathrm{hard}})\not\subset\mathrm{HeurP}/\mathrm{poly}$.
As we assumed $\mathcal{L}\in\mathrm{BQP}$-complete such a distribution always
exists by Lemma 3 in[GD23]. The other $n-(n_{S}+1)$ input bits are sampled
uniformly at random.

We now show that the concept class $\mathcal{M}_{U,W,M}$ defined in Eq. 9 with
$\\{U(\bm{x})\\}_{\bm{x}}$, $\\{W(\bm{\alpha})\\}_{\bm{\alpha}}$ and $M$
considered above exhibits a learning separation with respect the input
distribution $\mathcal{D}$.

Classical hardness The argument is exactly the same as the one presented
before in the proof of Theorem 3.

Quantum learnability The quantum learnability is guaranteed by Lemma 4 in
[HLB+24]. Recall that the training data the learning algorithm receives for a
concept $f^{\bm{\alpha}}\in\mathcal{M}_{U,W,M}$ are
$\mathcal{T}^{\bm{\alpha}}=\\{\bm{x}_{\ell},y_{\ell}\\}_{\ell}$ with
$\mathbb{E}[y_{\ell}]=\text{Tr}[\rho_{U}(\bm{x}_{\ell})O({\bm{\alpha}})]$.
Now, in the case the first bit of $\bm{x}_{\ell}$ is 0,
$\mathcal{T}^{\bm{\alpha}}$ is exactly the training set
$\mathcal{T}_{\bm{\alpha}}$ required by the algorithm in Lemma 4 to learn
$O(\bm{\alpha})$. Since for every $\bm{\alpha}$ the unitary $W(\bm{\alpha})$
is of shallow depth, the locality of $O(\bm{\alpha})$ scales logarithmic with
the number of qubit $n_{S}$. Then Lemma 4 guarantees that the learning
algorithm runs in polynomial time requiring a polynomial-sized dataset, a
condition met as half of the training samples in $\mathcal{T}^{\bm{\alpha}}$
will suffice.

∎

[row sep=0.1cm] $\ket{x_{1}}$ & [4][1.2cm]U(x) [style=red, label style=pos=1,
anchor=north]$\ket{\psi_{U}(\bm{x})}$
[3]$n_{S}$ $\ket{0}$ [3]W(α)
⋮
$\ket{0}$

Figure 2: Quantum model which exhibits a learning separation for the concept
class $\mathcal{M}_{U,W,O}$ when $W$ is a shallow circuit. The unitary
$U(\bm{x})$ prepares the state
$\ket{\psi_{U}(\bm{x})}=\ket{x_{1}}\otimes\ket{\psi^{n_{S}}_{U}(\bm{x_{S}})}$
where the form of $\ket{\psi^{n_{S}}_{U}(\bm{x_{S}})}$ depends on $x_{1}$, the
first bit of each input $\bm{x}\in\\{0,1\\}^{n}$. If $x_{1}=0$, then
$\ket{\psi^{n_{S}}_{U}(\bm{x_{S}})}=\ket{\psi_{stab}(\bm{x_{S}})}=\bigotimes_{i=1}^{n_{S}}\ket{\psi^{i}_{stab1}(\bm{x_{S}})}$
is the $n_{S}=\left\lfloor{\frac{n}{3}}\right\rfloor$ qubit tensor product of
single-qubit stabilizers described by the classical bitstring
$x_{2}x_{3}...x_{n}$. If $x_{1}=1$, then $\ket{\psi^{n_{S}}_{U}(\bm{x_{S}})}$
is the quantum state which decides the $n_{S}$ input bits
$\bm{x_{S}}=x_{2}x_{3}...x_{n_{S}+1}$, considered as input of a BQP-complete
language $\mathcal{L}$ over the bitstrings $\bm{x_{S}}\in\\{0,1\\}^{n_{S}}$ .
$W({\bm{\alpha}})$ is a parametrized shallow unitary, to prove classical
hardness it is sufficient to consider $W({\bm{\alpha}}=0)=I^{\otimes n_{S}}$
and the measurement operator to be $O=Z\otimes I\otimes...\otimes I$ on the
$n_{S}$ qubits register.

## References

  * [BM19] Manuel Blum and Silvio Micali.  How to generate cryptographically strong sequences of pseudo random bits.  In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pages 227–240. 2019.
  * [Chi04] Andrew MacGregor Childs.  Quantum information processing in continuous time.  PhD thesis, Massachusetts Institute of Technology, 2004.
  * [Fey85] Richard Feynman.  Quantum mechanical computers.  Optics news, 11(2):11–20, 1985.
  * [GD23] Casper Gyurik and Vedran Dunjko.  Exponential separations between classical and quantum learners.  arXiv preprint arXiv:2306.16028, 2023.
  * [GHGM22] Sevag Gharibian, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae.  Improved hardness results for the guided local hamiltonian problem.  arXiv preprint arXiv:2207.10250, 2022.
  * [HBM+21] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean.  Power of data in quantum machine learning.  Nature communications, 12(1):2631, 2021.
  * [HK12] Elad Hazan and Tomer Koren.  Linear regression with limited observation.  arXiv preprint arXiv:1206.4678, 2012.
  * [HKT22a] Jeongwan Haah, Robin Kothari, and Ewin Tang.  Optimal learning of quantum hamiltonians from high-temperature gibbs states.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 135–146. IEEE, 2022.
  * [HKT+22b] Hsin-Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V Albert, and John Preskill.  Provably efficient machine learning for quantum many-body problems.  Science, 377(6613):eabk3333, 2022.
  * [HLB+24] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R McClean.  Learning shallow quantum circuits.  arXiv preprint arXiv:2401.10095, 2024.
  * [JGM+21] Sofiene Jerbi, Casper Gyurik, Simon Marshall, Hans Briegel, and Vedran Dunjko.  Parametrized quantum policies for reinforcement learning.  Advances in Neural Information Processing Systems, 34:28362–28375, 2021.
  * [KR03] Julia Kempe and Oded Regev.  3-local hamiltonian is qma-complete.  arXiv preprint quant-ph/0302079, 2003.
  * [KSV02] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi.  Classical and quantum computation.  Number 47. American Mathematical Soc., 2002.
  * [LAT21] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme.  A rigorous and robust quantum speed-up in supervised machine learning.  Nature Physics, 17(9):1013–1017, 2021.
  * [LHT+24] Laura Lewis, Hsin-Yuan Huang, Viet T Tran, Sebastian Lehner, Richard Kueng, and John Preskill.  Improved machine learning algorithm for predicting ground state properties.  nature communications, 15(1):895, 2024.
  * [Llo96] Seth Lloyd.  Universal quantum simulators.  Science, 273(5278):1073–1078, 1996.
  * [MRT18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of machine learning.  MIT press, 2018.
  * [Nag10] Daniel Nagaj.  Fast universal quantum computation with railroad-switch local hamiltonians.  Journal of Mathematical Physics, 51(6), 2010.
  * [Nat98] Thomas Nattermann.  Theory of the random field ising model.  In Spin glasses and random fields, pages 277–298. World Scientific, 1998.
  * [OS01] J Oitmaa and OP Sushkov.  Two-dimensional randomly frustrated spin-1/2 heisenberg model.  Physical Review Letters, 87(16):167206, 2001.
  * [SG04] Rocco A Servedio and Steven J Gortler.  Equivalences and separations between quantum and classical learnability.  SIAM Journal on Computing, 33(5):1067–1092, 2004.
  * [SSHE21] Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Eisert.  On the quantum versus classical learnability of discrete distributions.  Quantum, 5:417, 2021.
  * [YIM23] Hayata Yamasaki, Natsuto Isogai, and Mio Murao.  Advantage of quantum machine learning from general computational advantages.  arXiv preprint arXiv:2312.03057, 2023.