††thanks: The first three authors contributed equally to this work.††thanks:
The first three authors contributed equally to this work.††thanks: The first
three authors contributed equally to this work.

# On fundamental aspects of quantum extreme learning machines

Weijie Xiong  Institute of Physics, Ecole Polytechnique Fédérale de Lausanne
(EPFL), Switzerland  Giorgio Facelli  Institute of Physics, Ecole
Polytechnique Fédérale de Lausanne (EPFL), Switzerland  Mehrad Sahebi
Institute of Electrical and Micro Engineering, Ecole Polytechnique Fédérale de
Lausanne (EPFL), Switzerland  Owen Agnel  Department of Computer Science,
University of Oxford, Oxford, UK  Thiparat Chotibut  Department of Physics,
Chulalongkorn University, Bangkok, Thailand  Supanut Thanasilp  Institute of
Physics, Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland  Zoë
Holmes  Institute of Physics, Ecole Polytechnique Fédérale de Lausanne (EPFL),
Switzerland

(August 28, 2024)

###### Abstract

Quantum Extreme Learning Machines (QELMs) have emerged as a promising
framework for quantum machine learning. Their appeal lies in the rich feature
map induced by the dynamics of a quantum substrate – the quantum reservoir –
and the efficient post-measurement training via linear regression. Here we
study the expressivity of QELMs by decomposing the prediction of QELMs into a
Fourier series. We show that the achievable Fourier frequencies are determined
by the data encoding scheme, while Fourier coefficients depend on both the
reservoir and the measurement. Notably, the expressivity of QELMs is
fundamentally limited by the number of Fourier frequencies and the number of
observables, while the complexity of the prediction hinges on the reservoir.
As a cautionary note on scalability, we identify four sources that can lead to
the exponential concentration of the observables as the system size grows
(randomness, hardware noise, entanglement, and global measurements) and show
how this can turn QELMs into useless input-agnostic oracles. Our analysis
elucidates the potential and fundamental limitations of QELMs, and lays the
groundwork for systematically exploring quantum reservoir systems for other
machine learning tasks.

##  I Introduction

Extreme learning machines (ELMs) [1, 2, 3, 4] are a class of feed-forward
neural networks designed to address the challenges of conventional neural
networks training. While gradient-based training methods such as
backpropagation have propelled the rapid development of neural network models,
their efficiency can diminish with increasing data and model size due to
issues like vanishing gradients and increasing computational resources [5].
ELMs leverage a single hidden layer with numerous randomly initialized hidden
neurons, whose parameters are subsequently fixed to create a rich
representation of the input data. Training ELMs reduces to a one-step linear
regression on the output layer weights, which is simply a convex optimization
problem. This approach can significantly reduce training time and even improve
generalization performance [6, 7, 4].

Figure 1: Framework of a QELM and results of this work. A QELM encodes
classical data onto accessible qubits (red arrows in panel (a) or the encoding
unitary $U(\bm{x})$ in panel (b)). The accessible and hidden qubits then
undergo a unitary (reservoir) evolution $U_{R}$, and a set of observables is
measured. The estimates of the observables are classically post-processed to
predict the output via linear regression. The reservoir unitary is fixed and
only the linear regression weights $\bm{\eta}$ are classically optimized. The
encoding strategy determines the achievable Fourier frequencies of the
prediction. Pauli re-uploading and the exponential encoding lead to
polynomially and exponentially many frequencies in (c) and (d) respectively.
Hence, the prediction of a QELM using Pauli encoding has a more concentrated
Fourier spectrum, which is more efficiently simulated classically. The
exponential encoding, which corresponds to the partial control regime
$M<|\Omega|$, allows for a wider range of target functions compared to the
Pauli re-uploading, where $M>|\Omega|$ and might offer a quantum advantage.
(e) We discuss four sources of exponential concentration for the measurement
outcomes as the system size grows, which result in a QELM with input-agnostic
predictions.

With the advent of near-term quantum devices, Quantum Extreme Learning
Machines (QELMs) have emerged as a compelling alternative to traditional ELMs
[8, 9]. This growing interest stems not only from the capability of QELMs to
directly process quantum data [9, 10, 11, 12], but also from the fact that
QELMs can leverage the complex dynamics of a quantum system evolving in an
exponentially large Hilbert space – a quantum reservoir – to construct an
intricate feature map of classical data inputs. Employing a quantum reservoir
enables QELMs and more generally quantum reservoir computing to achieve
predictive power with significantly lower resource requirements, compared to
extensive hidden layers required in the classical counterparts [8, 13, 14].
Notably, despite involving measurement outcomes from the quantum reservoir,
training QELMs remains a convex optimization problem based on linear
regression. This guarantees trainability even on noisy quantum hardware,
unlike gradient-based VQAs which can suffer from noise-induced barren plateaus
[15]. These advantages suggest that QELMs hold promise for harnessing the
potential of near-term quantum devices in various quantum machine learning
tasks.

However, for any Quantum Machine Learning (QML) model learning on classical
data, it is important to consider the expressivity limitations arising from
the data encoding strategy [16]. In many cases, the predictions of a typical
QML model can be expressed in terms of a Fourier series [16]. Hence, the
richness of achievable Fourier frequencies and the controllability of the
Fourier coefficients become natural measures of a QML model’s expressivity and
predictive power. As a rule of thumb, the less expressive a QML model is, the
more efficiently it can be classically simulated. Hence, the Fourier
decomposition provides a way to assess its classical simulability, in
particular whether it is possible to construct a classical surrogate of the
quantum model, and hence the lack of (or potential for) quantum advantage [17,
18, 19].

In parallel, there is growing awareness of the dangers posed by exponential
concentration, where quantum expectation values (e.g. of a loss or a kernel)
exponentially concentrate around a fixed value with growing problem size [20,
21, 22, 23, 15, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]. The main
sources of exponential concentration are ansatz Haar-expressivity [20], noise
[15], entanglement [26] and global measurements [22]. Originally identified as
a problem for quantum neural networks (QNNs) [20], it has recently been shown
that exponential concentration, analogously, acts as a barrier to the
scalability of quantum kernel methods [30, 36]. While for QNNs exponential
concentration inhibits the training of the model, for quantum kernel methods
the trainability is guaranteed but it is the generalization capabilities of
the model that suffer.

This work aims to explore the potential and limitations of QELM through the
lenses of Fourier-expressivity, exponential concentration, and classical
simulability. We focus on the framework of a general QELM that learns from
classical data and performs regression or classification tasks from the
measurement outcomes of a quantum reservoir. Under this framework, we first
show that the prediction of a QELM can be expressed as a Fourier series.
Similar to a QNN [16], the achievable Fourier frequencies of a QELM are also
fully determined by the encoding scheme, i.e. the eigenvalues of the Hermitian
generators of encoding unitary. The Fourier coefficients are input-independent
and controlled by the dynamics of the QELM, as well as the measurement. Based
on that, we investigate the classical simulability for typical encoding
strategies. In particular, the encoding using Pauli generators leads to a
prediction composed of linearly many Fourier modes in the system size, which
can be efficiently surrogated by a classical computer [17, 18, 19]. Hence, the
use of an exponential encoding, which results in exponentially many Fourier
frequencies, is a prerequisite for quantum advantage. We further link the
Fourier-expressivity of QELM to the independence of the Fourier coefficients,
which is upper bounded by three factors: the number of Fourier frequencies
determined by the encoding strategy, the number of observables, and the
measurement locality.

Then, we further study the effect of exponential concentration on QELM. In
particular, QELM implements a set of observables, whose outcomes are then used
to train the final linear regression. We show that the Haar-expressivity of
both the encoding and reservoir unitaries, entanglement, global measurement,
and noise can independently induce the exponential concentration of the
observables’ expectation values about the means. This, in turn, necessitates
exponentially many shots to accurately estimate the observable’s outcomes and
reliably reconstruct the input-dependent prediction. Crucially, these four
sources of concentration limit the scalability of a QELM, since the model’s
predictions will become more agnostic to the input data as the system size
grows. Our results on both the Fourier-expressivity and the cautionary
scenarios that lead to input-independent predictions of QELM are summarized in
Fig. 1. Our key contributions and related analytical work are tabulated in
Table 1.

| Expressivity | Controllability | Exponential concentration
---|---|---|---
Classical data | Sec. III, Ref. [37, 38] | Sec. III |  | Sec. IV (induced by data-embedding,
---
reservoir dynamics, or measurement)
Quantum data | Ref. [9] | Ref. [9] | Sec. IV (induced by reservoir dynamics, or measurement)

Table 1: Summary of our main analytical results and related analytical work:
The controllability generally refers to the scope of QELM’s predictive
capabilities that can be adjusted by controlling the trainable weights. For
classical data, we show that the output prediction is a linear combination of
Fourier series; hence, the controllability of trainable weights here means the
controllability of Fourier coefficients.

##  II Background

Quantum extreme learning machines (QELMs) can be used to solve both regression
and classification tasks. Their success can be attributed to the ability of
QELMs to encode input data in exponentially large many-body quantum states
induced by the dynamics of a quantum reservoir. This high-dimensional input
feature map facilitates efficient classification and linear regression,
similar to the concept underlying kernel methods.

Recent studies have demonstrated the potential of QELMs across diverse quantum
machine learning tasks, encompassing binary classification [39], supervised
learning on benchmark datasets [40, 41, 42], input recognition and parity
check [43], and quantum state reconstruction [9, 12]. Notably, QELMs can
process both quantum [9, 12, 11, 10] and classical data [37, 38, 39, 40, 41,
43, 42]. However, theoretical investigation on their potential and limitations
when processing classical data remains relatively unexplored. This motivates
our current study concerning the consequences of the interplay between
classical data encoding and exponential concentration phenomena in QELMs.

We consider the following framework of QELMs. Given a training set
$\\{(\bm{x}^{(l)},\bm{y}^{(l)})\\}_{l=1}^{N_{\rm
tr}}\subset\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}$ consisting of $N_{\rm
tr}$ input-output classical vector pairs, the objective of a QELM is to learn
a function $\bm{f}$ such that $\bm{f}(\bm{x})\approx\bm{y}$. For brevity, we
focus our analysis on a scalar output ($d_{y}=1$), as the generalization to
the vector output case is more cumbersome and existing proposals are mostly
based on a scalar output case.

As mentioned earlier, at its core, a QELM harnesses a quantum reservoir, e.g.
quantum spins [9], crystal model [42], photonic [12] and NMR [43] platform, as
a means of implementing a rich feature map to the input data. These reservoir
states that encode the inputs are then read out via measurements, yielding
classical vectors of observables that are subsequently used to train the model
classically via linear regression to match the outputs (labels). More
concretely, as shown in Fig. 1, a QELM consists of the following components:

  1. 1.

Encoding of classical data: An input vector
$\bm{x}\in\mathcal{X}=\\{\bm{x}^{(l)}\\}_{l=1}^{N_{tr}}$ is encoded into a
quantum state via a parametrized unitary $U(\bm{x})$ applied on the space of
$n_{A}$ accessible qubits. Let $\rho_{0}$ denote the initial state of all
accessible qubits, then the state after encoding is

$\rho(\bm{x})=U(\bm{x})\rho_{0}U^{\dagger}(\bm{x})\,.$ (1)

  2. 2.

Reservoir evolution: As well as the accessible qubits, a QELM is equipped with
a reservoir composed of $n_{H}$ hidden qubits. We suppose the hidden qubits
are initialized in the $\ket{0}$ state. The second step of a QELM is to apply
the reservoir dynamics to the composite system of accessible and hidden
qubits. Without loss of generality, we consider the reservoir evolution
described by some unitary $U_{R}$. The state of the reservoir after the
evolution is

$\widetilde{\rho}(\bm{x})=U_{R}\big{(}\rho(\bm{x})\otimes|0\rangle\langle
0|\big{)}U_{R}^{\dagger}\,.$ (2)

Indeed, by virtue of Stinespring’s dilation theorem, supposing that the
reservoir undergoes a CPTP channel evolution would only correspond to some
unitary evolution on a larger hidden space. Thus, we will restrict ourselves
only to unitary dynamics.

  3. 3.

Readout: Next, the reservoir state after the evolution is read out by
measurements on a set of observables $\\{O_{1},O_{2},\dots,O_{M}\\}$, whose
theoretical expectation value is

$\expectationvalue{O_{k}}_{\bm{x}}=\operatorname{Tr}[O_{k}\widetilde{\rho}(\bm{x})]\,.$
(3)

These theoretical expectation values yield the measurement readout (classical)
vector.

  4. 4.

Linear regression: Finally, the resulting measurement readout vectors are
classically trained via linear regression to match the corresponding
prediction labels. That is, given a set of trainable weights
$\bm{\eta}=[\eta_{1},\eta_{2},...,\eta_{M}]^{T}$, a QELM makes the following
prediction

$f_{\bm{\eta}}(\bm{x})=\sum_{k=1}^{M}\eta_{k}\expectationvalue{O_{k}}_{\bm{x}}\,.$
(4)

The weight vector $\bm{\eta}$ is typically trained by minimizing the empirical
loss

$\mathcal{L}(\bm{\eta})=\sum_{k=1}^{N_{\rm
tr}}\left(f_{\bm{\eta}}\big{(}\bm{x}^{(l)}\big{)}-y^{(l)}\right)^{2}\,.$ (5)

The success of a QELM model will depend on a number of factors including the
expressivity of the encoding strategy, the inductive bias induced by the
reservoir (which acts as a feature map), as well as both the number and type
of measurements used for readout. We will start by analysing the role of these
factors through the lens of expressivity.

##  III Fourier decomposition analysis

###  III.1 General analysis

To analyse the expressivity of a quantum model it is helpful to consider its
Fourier decomposition. For simplicity we will here assume that the inputs are
scalars, i.e., $\bm{x}\rightarrow x$, but in Appendix A.1 we discuss the
generalization to vector inputs.

Ref. [16] showed that the output of a general variational quantum circuit that
encodes classical data via parameterized unitaries can be expressed as a
Fourier series of the form

$f_{\bm{\theta}}(x)=\sum_{\omega\in\Omega}c_{\omega}e^{i\omega x}\,.$ (6)

The set of frequencies $\Omega$ is determined by the encoding strategy and the
coefficients $c_{\omega}$ are determined by the corresponding VQC parameters.
Here we show that the output of a QELM with scalar input can also be expressed
as a Fourier series.

Let us suppose that the accessible qubits are initialized in the state

$\rho_{0}=\sum_{i,j}\alpha_{ij}|i\rangle\langle j|\,.$ (7)

Here we use $\ket{i}$ to denote the state of the effective qudit corresponding
to the accessible qubits, i.e. we denote the basis $\\{\ket{00\cdots
00},\ket{00\cdots 01},\dots,\ket{11\cdots 11}\\}$ as
$\\{\ket{0},\ket{1},\dots,\ket{2^{n_{A}}-1}\\}$. Let us further consider a
scalar input $x\in\mathbb{R}$ and assume that the encoding unitary has the
form

$U(x)=e^{iHx}\,,$ (8)

where the generator $H$ is a Hermitian observable. We further assume an
appropriate computational basis, such that the generator $H$ is a diagonal
Hamiltonian with eigenvalues
$\\{\lambda_{1},\lambda_{2},\dots,\lambda_{2^{n_{A}}}\\}$.

It follows that the state of accessible qubits after the encoding is

$\displaystyle\rho(x)$ $\displaystyle=U(x)\rho_{0}U(x)^{\dagger}$ (9)
$\displaystyle=\sum_{i,j=0}^{2^{n_{A}}-1}e^{(\lambda_{j}-\lambda_{i})x}\alpha_{ij}|i\rangle\langle
j|\,.$ (10)

By Eq. (3) and (2) the expectation value of a readout observable $O$ takes the
form

$\displaystyle\expectationvalue{O}_{x}$
$\displaystyle=\operatorname{Tr}[OU_{R}\left(\rho(x)\otimes|0\rangle\langle
0|\right)U_{R}^{\dagger}]$ (11)
$\displaystyle=\sum_{\omega\in\Omega}a_{\omega}e^{i\omega{x}}\,,$ (12)

where the Fourier frequencies are given by the differences of the eigenvalues
of $H$

$\Omega=\\{\lambda_{j}-\lambda_{i}:i,j=1,2,\dots,2^{n_{A}}\\}\,,$ (13)

and the corresponding Fourier coefficients are

$a_{\omega}=\sum_{i,j\mathrm{\,s.t.\,}\lambda_{j}-\lambda_{i}=\omega}\alpha_{ij}\bra{j,0}U_{R}^{\dagger}{}OU_{R}\ket{i,0}\,.$
(14)

Thus we already see that only the eigenvalues of the Hamiltonian determine the
accessible frequencies $\Omega$. Instead, the weighting $a_{\omega}$ of each
frequency is determined by the initial state, reservoir dynamics and choice in
the observable.

These observations propagate through to the final function model. More
concretely, given a set of observables $\\{O_{1},O_{2},\dots,O_{M}\\}$, we
denote the Fourier coefficients resulting from $O_{k}$ as $a_{\omega}^{(k)}$.
Then, by Eq. (4) the system output can be expressed as a Fourier series of the
form

$\displaystyle f_{\bm{\eta}}$
$\displaystyle=\sum_{\omega\in\Omega}b_{\omega}e^{i\omega x}\,,$ (15)

where $b_{\omega}=\sum_{k=1}^{M}\eta_{k}a_{\omega}^{(k)}$.

Thus we see that, similar to the Fourier series of a variational quantum
circuit, the encoding strategy determines the eigenvalues of the encoding
generator, and hence the Fourier frequencies. On the other hand, the Fourier
coefficients $b_{\omega}$ are independent of the input and determined by the
dynamics of the reservoir, the trainable weights and the choice of
observables.

In the case of vectorial inputs and a multivariate target function, the
expression of the system prediction is easily generalized to a multivariate
Fourier series, as shown in Ref. [16]. For concreteness, we spell this out in
Appendix A.1.

We further assume the inputs are encoded on each accessible qubit in parallel,
i.e. the encoding unitary applied on the accessible qubits is separable and
takes the tensor product form

$U(x)=U_{1}(x)\otimes U_{2}(x)\otimes\cdots\otimes U_{n_{A}}(x)\,,$ (16)

where $U_{k}(x)$ denotes the encoding of the $k$’th accessible qubit and is
given by

$U_{k}(x)=e^{iH_{k}x}\,.$ (17)

Note that $H_{k}$ is the generator of the $k$’th accessible qubit, while $H$
in Eq. (8) is the generator of the effective qudit representing all accessible
qubits. Let $\lambda^{(k)}_{1}$ and $\lambda^{(k)}_{2}$ be the eigenvalues of
$H_{k}$, then, as shown in [16], the set of achievable Fourier frequencies can
be written as

$\displaystyle\begin{split}\Omega&=\Bigl{\\{}(\lambda^{(1)}_{i_{1}}+\lambda^{(2)}_{i_{2}}+\cdots+\lambda^{(n_{A})}_{i_{n_{A}}})-\\\
&(\lambda^{(1)}_{j_{1}}+\lambda^{(2)}_{j_{2}}+\cdots+\lambda^{(n_{A})}_{j_{n_{A}}}):i_{k},j_{k}=0,1\Bigr{\\}}\end{split}$
(18)
$\displaystyle\begin{split}&=\Bigl{\\{}(\lambda^{(1)}_{i_{1}}-\lambda^{(1)}_{j_{1}})+(\lambda^{(2)}_{i_{2}}-\lambda^{(2)}_{j_{2}})+\\\
&\cdots+(\lambda^{(n_{A})}_{i_{n_{A}}}-\lambda^{(n_{A})}_{j_{n_{A}}}):i_{k},j_{k}=0,1\Bigr{\\}}\,,\end{split}$
(19)

where $i_{k}$ and $j_{k}$ are the indices for the $k$’th accessible qubit. The
set of indices for all accessible qubits $(i_{1},i_{2},\dots,i_{n_{A}})$ and
$(j_{1},j_{2},\dots,j_{n_{A}})$ correspond to $i$ and $j$ in Eq. (13)
respectively (i.e. $i$ corresponds to $i_{1}i_{2}\cdots i_{n_{A}}$ in binary).

The expression for $\Omega$ in Eq. (LABEL:Eq:Omega) implies that for a fixed
number of accessible qubits $n_{A}$ the spacing of eigenvalues of $H_{k}$
determines the richness of Fourier frequencies. If the differences between the
eigenvalues $(\lambda^{(k)}_{i_{k}}-\lambda^{(k)}_{j_{k}})$ are identical for
all $k$’s, then the number of achievable frequencies will be significantly
smaller, compared to the case when each $H_{k}$ provides distinguishable
differences of eigenvalues. The maximum number of possible distinct non-
negative frequencies is $1+(4^{n_{A}}-2^{n_{A}})/2$. However, often the
eigenvalues are distributed such that the number of distinct frequencies is
actually lower than this bound.

In the following, we analyse the frequencies generated from the proposed
encoding strategies and discuss the controllability of the associated Fourier
coefficients. We start by considering two typical encoding schemes and discuss
the richness of their frequencies, which are further linked to classical
simulability.

###  III.2 Encoding strategies

##### Pauli re-uploading.

A widely used strategy of encoding is Pauli re-uploading [42, 40, 8, 41],
which applies an identical single-qubit Pauli rotation gate on each of the
accessible qubits in parallel, as shown in Fig. 1. Taking $H_{k}=\sigma_{z}$
we have

$U_{k}(x)=e^{-i\sigma_{z}x/2},\ \ \forall\ k=1,2,\dots,n_{A}\,.$ (20)

As all the generators $-\sigma_{z}/2$ have eigenvalues $\pm 1/2$ from Eq.
(LABEL:Eq:Omega) we obtain the following achievable Fourier frequencies

$\Omega=\\{-n_{A},-n_{A}+1,\dots,0,\dots,n_{A}-1,n_{A}\\}\,.$ (21)

This is identical to the frequencies of a QNN using Pauli re-uploading [16,
44]. The output function contains all the integer frequencies up to $n_{A}$
and only $(n_{A}+1)$ non-negative frequencies are achievable.

##### Exponential Encoding.

In order to increase the richness of frequencies, the exponential encoding has
been proposed [45]. Instead of using the same generator for all accessible
qubits, the exponential encoding employs different generators with
exponentially scaled spacing of eigenvalues, as illustrated in panel (b) of
Fig. 1. For the $k$’th accessible qubit, the generator is

$H_{k}=-\frac{1}{2}\beta_{k}\sigma_{z}\,,$ (22)

where $\beta_{k}=3^{k-1}$ and $k=1,2,\dots,n_{A}$. By Eq. (LABEL:Eq:Omega), we
obtain the following achievable frequencies:

$\displaystyle\Omega=$
$\displaystyle\biggr{\\{}-\frac{3^{n_{A}}-1}{2},-\frac{3^{n_{A}}-1}{2}+1,\dots,1,$
(23) $\displaystyle
0,1,\dots,\frac{3^{n_{A}}-1}{2}-1,\frac{3^{n_{A}}-1}{2}\biggr{\\}}\,.$ (24)

The set consists of all the integer frequencies up to $(3^{n_{A}}-1)/2$,
totalling $1+(3^{n_{A}}-1)/2$ non-negative frequencies, which is exponential
in the number of accessible qubits.

Next, we demonstrate the predictive power of the two encodings on an
artificial classical dataset. To generate the dataset we first define a
function $f(x)=\sum_{k=1}^{3^{6}/2}a_{k}e^{ikx}$ where the $a_{k}$’s are
sampled uniformly in $[-1,1]$. We then consider the dataset
$\\{x_{i},f(x_{i})\\}_{i=1}^{5000}$ where $x_{i}$’s are placed equidistantly
in $[0,\pi]$.

Two extreme learning models with $n_{A}=6,n_{H}=0$ are trained, one with
exponential encoding and the other one with Pauli encoding. Both models have
the same reservoir, namely a Random Rotation reservoir with $10$ layers of
random single-qubit rotations followed by CNOT gates, and in both cases we
measure the same subset of randomly chosen Pauli observables at the end. The
training is then performed using an Ordinary Linear Regression model.

We expect the exponential encoding to be able to perfectly reconstruct $f$
given enough training data and observables because its frequency spectrum
$\Omega=\\{0,\cdots,\frac{3^{n_{A}}-1}{2}\\}$ completely covers that of $f$.
On the other hand, we expect Pauli encoding to fail in approximating $f$
because it can only cover frequencies from $0$ to $6$. In Fig. 2 the $R^{2}$
score of the two models is shown over the number of observables ($M$) used. We
can see that even with an exponential number of observables the Pauli encoding
cannot perform well.

Instead, the exponential encoding reaches score 1 when we use the same number
of observables as the frequencies in $f$. This simple example already
demonstrates that the exponential encoding, given its superior expressivity,
is able to outperform a more naive encoding. Crucially, however, the
exponential encoding only leads to better results provided there are enough
observables. This is discussed more in detail in the following section.

Figure 2: Comparison between two encoding schemes. The performance of two QEL
models with exponential and Pauli encoding using 6 encoding qubits over number
of observables.

###  III.3 Controllability of Fourier coefficients and Expressivity

In the previous section we discussed the range of possible frequencies for two
different encoding strategies. In particular, we suggested that the
exponential encoding strategy could be used to access exponentially many
frequencies. However, this does not mean the QELM’s prediction can always
completely explore the space spanned by those Fourier modes. More
specifically, in some cases the Fourier coefficients of the prediction can
correlate to each other. This means the trainable weights $\bm{\eta}$ cannot
fully control all the Fourier modes. Here, we investigate this controllability
and discuss the predictive power of QELM in terms of Fourier-expressivity
defined below.

Recall Eq. (4) and (11), the prediction of QELM is given by

$\displaystyle f_{\bm{\eta}}$
$\displaystyle=\sum_{k=1}^{M}\eta_{k}\expectationvalue{O_{k}}_{x}$ (25)
$\displaystyle=\sum_{\omega\in\Omega}b_{\omega}e^{i\omega x}\,.$ (26)

To assess the predictive power, we introduce the dimension of prediction’s
function space as a measure of expressivity. This is defined as the
cardinality of the smallest set of functions that form a complete basis for
the model’s prediction space.

######  Definition 1 (Fourier-expressivity of QELM).

Given a QELM as defined above with model prediction $f_{\bm{\eta}}$, let
$\mathcal{B}$ be a finite set of real functions, such that for any trainable
weight vector $\bm{\eta}$, $f_{\bm{\eta}}$ can be written as a linear
combination of the elements of $\mathcal{B}$, i.e.

$\\{f_{\bm{\eta}}(\cdot):\bm{\eta}\in\mathbb{R}^{M}\\}\subseteq
span(\mathcal{B})\,.$ (27)

We define the Fourier-expressivity of $f_{\bm{\eta}}$ as the cardinality of
the smallest possible $\mathcal{B}$, i.e.,

$\mathcal{F}\left[f_{\bm{\eta}}\right]:=\operatorname{min}|\mathcal{B}|\,,$
(28)

where the minimization is over all $\mathcal{B}$ satisfying Eq. (27).

On the one hand, the output $f_{\bm{\eta}}$ is a linear combination of $M$
outcomes, which implies that the number of observables $M$ upper bounds the
Fourier-expressivity $\mathcal{F}$. On the other hand, the prediction can be
written as a Fourier series of $|\Omega|$ frequencies. Since the terms of
different frequencies are orthogonal, $\mathcal{F}$ is also upper bounded by
$|\Omega|$. The locality of the measurements also limit the Fourier-
expressivity. Assuming $n_{O}$ qubits are measured, then any observable can be
written as a linear combination of $4^{n_{O}}$ Pauli strings. This implies
that no more information can be extracted than that obtained from measuring
$4^{n_{O}}$ observables. We further remark that the number of frequencies
$|\Omega|$ cannot be more than the number of possible distinct differences of
eigenvalues which is upper bounded by $4^{n_{A}}$. These arguments lead us to
the following Theorem, which is formally proved in App. A.2.

######  Theorem 1 (Upper bound of QELM’s Fourier-expressivity).

Consider a QELM, as defined above, with model prediction $f_{\bm{\eta}}$. Let
$M$ be the number of observables, $\Omega$ be the set of achievable
frequencies, and $n_{O}$ be the number of measured qubits, then

$\displaystyle\mathcal{F}\left[f_{\bm{\eta}}\right]$
$\displaystyle\leqslant\operatorname{min}\\{M,|\Omega|,4^{n_{O}}\\}\,,$ (29)

where $|\Omega|\leqslant 4^{n_{A}}$.

As the upper bound $4^{n_{O}}$ scales exponentially in number of measured
qubits, while the number of observables $M$ is in practice polynomially large
in the system size, in what follows we will assume that $M$ is always less
than $4^{n_{O}}$. In this case, the upper bound reduces to

$\mathcal{F}\left[f_{\bm{\eta}}\right]\leqslant\operatorname{min}\\{M,|\Omega|\\}\,.$
(30)

We are now left with two questions: first, when does the inequality in Eq.
(30) saturate? Second, what can we expect if $M\geqslant|\Omega|$ and if
$M<|\Omega|$? For the first question, we claim that in practice this upper
bound is always tight. We observe this numerically in Section III.4 for all
the practical reservoirs, including integrable reservoirs, chaotic reservoirs,
and scrambling reservoirs.

Next, we address the second question by comparing the following two regimes:

##### Full control regime - $M\geqslant{}|\Omega|$.

As long as we choose non-trivial observables such that the
$\expectationvalue{O_{k}}$’s are independent of each other, we have full
control over the Fourier coefficients $b_{\omega}$. In this regime, we have

$\mathcal{F}\left[f_{\bm{\eta}}\right]=|\Omega|$ (31)

and

$\\{f_{\bm{\eta}}(\cdot):\bm{\eta}\in\mathbb{R}^{M}\\}=\operatorname{span}(\\{e^{i\omega
x}:\omega\in\Omega\\})\,,$ (32)

meaning that the model can learn any target function whose Fourier
coefficients are within $\Omega$.

However, in practice, the number of measurements implemented can only scale at
most polynomially, i.e. $M\in\mathcal{O}(\mathrm{poly}(n))$. It follows that
the number of frequencies scales at most polynomially, i.e.
$|\Omega|\in\mathcal{O}(\mathrm{poly}(n))$. We recall that the prediction of a
QELM using Pauli re-uploading encoding scheme results in a polynomial number
of frequencies. As we discuss in Section III.5, such a QELM can be classically
surrogated, and hence does not yield quantum advantage.

##### Partial control regime - $M<|\Omega|$.

In this regime, the number of observables or the number of weights is less
than the number of Fourier frequencies. Hence, the Fourier coefficients
$b_{\omega}$ are not independent, and we can only partially control the model
prediction. Suppose the $\expectationvalue{O_{k}}$’s are independent of each
other, then we have

$\mathcal{F}\left[f_{\bm{\eta}}\right]=M$ (33)

and

$\\{f_{\bm{\eta}}(\cdot):\bm{\eta}\in\mathbb{R}^{M}\\}\subset\operatorname{span}(\\{e^{i\omega
x}:x\in\Omega\\})\,.$ (34)

That is, some Fourier series from the spectrum $\Omega$ cannot be predicted by
the QELM as the degrees of freedom are limited by the number of observables.
This regime includes the QELMs using exponential encoding strategies such that
$|\Omega|\in\mathcal{O}(\mathrm{exp}(n))$, that are potentially classically
non-surrogatable (as discussed later in Section III.5) and so might offer a
quantum advantage.

###  III.4 Role of reservoir

Figure 3: Exemplary Fourier spectra of a QELM with $n_{A}=4$ and $n_{H}=4$.
The Fourier coefficients of three observables, $O_{1}=X^{\otimes
4}\otimes\mathcal{I}$, $O_{2}=X\otimes Y\otimes Y\otimes Z\otimes\mathcal{I}$
and $O_{3}=O_{rand}\otimes\mathcal{I}$ (where $O_{rand}$ is a random Hermitian
in the accessible space), resulting from six $reservoirs$: no reservoir,
integrable Ising model ($J=-1,\ B_{x}=0.0,\ B_{z}=1$), chaotic Ising model
($J=-1,\ B_{x}=0.7,\ B_{z}=1.5$) and three different Haar random reservoirs.
Each row (from top to bottom) corresponds to an observable (from $O_{1}$ to
$O_{3}$ respectively) specified on the right-hand side, while each column
corresponds to a reservoir unitary indicated on the top.

In the regime of partial control, i.e. the regime where a quantum advantage
might be possible, the number of observables $M$ is much smaller than the
number of frequencies $|\Omega|$. Hence, the dimension of prediction’s
function space is $M$ and each readout $\expectationvalue{O_{k}}$ can be
viewed a linearly independent basis function. In the previous section, we
showed that exponentially many frequencies can be achieved. However, it might
be the case that despite a wide range of frequencies being enabled by the
encoding, the Fourier coefficients are sparse and close to zero. This may
limit the Fourier-expressivity of the model and make it prone to classical
simulation. In this part, we look into the Fourier spectra of these basis
functions and study the richness of their Fourier modes –the proportion of
non-zero Fourier coefficients. We find that the dynamics of the reservoir
significantly affects the Fourier spectra and the richness.

For concreteness, we consider a practically efficient measurement strategy,
namely measuring Pauli strings, and assume that only the accessible qubits
will be measured. We then compare four types of reservoir settings: no
reservoir, the integrable Ising model, the chaotic Ising model, and a typical
Haar random unitary. In particular, we consider the 1D Ising model,

$H_{\operatorname{Ising}}=J\sum_{i=1}^{n-1}Z_{i}{}Z_{i+1}+B_{z}\sum_{i}^{n}Z_{i}+B_{x}\sum_{i}^{n}{}X_{i}\,,$
(35)

and, following Ref. [46], use the parameters

  * •

Integrable regime: $J=-1,\ B_{x}=0,\ B_{z}=1$

  * •

Chaotic regime: $J=-1,\ B_{x}=0.7,\ B_{z}=1.5$ .

In Fig. 3 we provide examples of the Fourier spectrum induced by these
reservoirs for three different Pauli observables. We observe that the
integrable Ising model leads to a spectrum that only weakly deviates from
using no reservoir. In contrast, the chaotic Ising model and scrambling
reservoirs lead to more complex, anti-concentrated Fourier spectra basis
functions. In Appendix B, we analytically compute the expected spectrum for a
Haar random reservoir and use this to explain the anti-concentration of the
frequencies observed in Fig. 3. As the chaotic Ising model and a typical Haar
random unitary are both models of scramblers it is intuitive that their effect
on the observed frequencies, as observed here, is similar [47, 48, 46].

To quantify how many of the achievable frequencies –determined by encoding
strategy– have a non-zero coefficient, we plot the richness of Fourier modes
with respect to the number of accessible qubits for different reservoirs.
Given a reservoir, the richness is defined as the proportion of non-zero
Fourier coefficients averaged over all the Pauli strings in accessible space,
i.e.

$R:=\frac{1}{4^{n_{A}}}\sum_{k=1}^{4^{n_{A}}}{|\\{\omega\in\Omega:a_{\omega}^{(k)}\neq
0\\}|}\,,$ (36)

where the Fourier coefficients $a_{\omega}^{(k)}$ correspond to observables
$\big{\\{}\\{I,X,Y,Z\\}^{\otimes n_{A}}\otimes\mathcal{I}\big{\\}}$.

As shown in Fig. 4, without a reservoir and for a reservoir governed by the
integrable Ising model, the richness $R$ of the output model decreases
exponentially in the number of accessible qubits $n_{A}$. On the other hand,
the richness of the models using scrambling and chaotic Ising reservoirs
saturate at some constant value. Notably, the chaotic Ising model leads to
same richness $R$ as a Haar random reservoir.

Figure 4: Richness of Fourier modes. The richness of Fourier modes, i.e. the
proportion of non-zero Fourier coefficients averaged over all the Pauli
observables in the accessible space $\\{I,\ X,\ Y,\ Z\\}^{\otimes
n_{A}}\otimes\mathcal{I}$, are plotted on a logarithmic scale against the
number of accessible qubits $n_{A}$ (the number of hidden qubits is fixed to
$n_{H}=4$).

###  III.5 Classical surrogates and the potential for a quantum advantage

So far we have focused on the Fourier-expressivity and controllability of
QELMs. While a firm understanding of these aspects is crucial, for QELMs to
have a practical usefulness one also need to consider their potential
advantage over classical computers. In particular, studying the conditions
under which QELMs can be dequantized gives us a practical guideline of where
to look for a quantum advantage.

One popular approach to dequantize quantum machine learning models is via a
classical surrogate. Under this approach, a purely classical model (known as a
surrogate) is built to mimic a respective QML model. Intuitively, this can be
achieved by exploiting the known Fourier structure of model predictions
generated by these QML models. We now briefly discuss two methods for building
classical surrogates that were originally developed for quantum neural
networks and quantum kernels and discuss how they can be applied to QELMs.

The first method proposed in Ref. [17] is to directly implement the whole
Fourier series on a classical computer. This method can only be applied to
quantum models using a polynomial number of Fourier frequencies. To determine
the associated Fourier coefficients, some input-output data pairs from a
quantum model might be needed to fit the surrogate. After successfully
building the surrogate, the access to quantum models (as well as quantum
computers) is no longer needed and the prediction from the classical surrogate
is guaranteed to be as good as the quantum model.

Since the model predictions of the QELM takes the same Fourier form as the
QNNs, this surrogate method is directly applied to the QELM framework with
classical data. Particularly, the QELM with a Pauli embedding (and hence only
a polynomial number of frequencies) is classically surrogatable. If the
reservoir and measurements are classically simulable, the model becomes
surrogatable without any need for the quantum computer. On the other hand, for
more complex reservoirs and measurements, a polynomial number of measurements
must first be taken on the quantum computer; crucially, however, after
training the quantum computer will not be required to evaluate the function on
a new test input.

In the second method, known as Random Fourier Features (RFF) [18, 19], the key
idea is to sample Fourier frequencies weighted with the associated
coefficients to build a classical surrogate. This is in contrast to the first
method where the whole Fourier series is used by the surrogate. This classical
surrogate performs at least as well as the original quantum model on the
training dataset, but the surrogate could perform worse on unseen data if the
original quantum model has an inductive bias that better aligns with a target
function. One strength of the RFF method is that it could even classically
surrogate quantum models with exponentially many frequencies if Fourier
coefficients concentrate over polynomial regions. However, if the coefficients
are well spread throughout the whole spectrum range, it is inefficient to
surrogate by RFF. Similarly, the RFF method also applies to the QELMs.

Thus to achieve a quantum advantage with a QELM one should use an encoding
with an exponential number of frequencies and reservoirs/observables that
ensure the weights of these frequencies are anti-concentrated. In Fig. 3 we
show that a chaotic Ising or Haar random reservoir with Pauli observables give
rise to such anti-concentration. We further support these numerics with an
analytic calculation of variances for the case of the Haar random reservoir in
Appendix B. These results show that the coefficients are well spread and thus
suggest that some unitaries in the Haar random family are not surrogatable.

However, a QELM being non-surrogatable, does not guarantee a quantum
advantage. As we will demonstrate in the next section, the Haar random
reservoir leads to exponential concentration which causes a QELM to generalize
poorly. Therefore, while a QELM with a Haar random reservoir is classically
non-surrogatable, it generally will not be very useful. This exemplifies the
orthogonal directions that non-classical simulability and good prediction
power can take.

Thus, one may ask the following key question: Is there any room and hope for a
quantum advantage with QELMs?

We provide a contrived example that a QELM can provably achieve an exponential
quantum advantage over any classical model. Our example is heavily based on
Ref. [49] where the authors prove an advantage of a quantum kernel method to
solve a particular classification task. The core argument here is to start
with a trivial data space, where two classes are linearly separable
$\mathcal{X}_{\rm trivial}$, and then map this data to a non-trivial space
using a feature map based on the discrete log problem i.e., $\Phi_{\rm
discrete}:\mathcal{X}_{\rm trivial}\rightarrow\mathcal{X}_{\rm complex}$. In
this new space, the two classes appear to be random and training data is drawn
from this space.

To solve this problem, one simply needs to design a map to undo this first
feature map. However, since the discrete log problem is closely related to
prime factorization and strongly believed to be classically inefficient, there
exists no classical feature map and in turn no classical model capable of
solving this classification task efficiently. On the other hand, quantum
computers are well known to excel at this kind of problem and are widely
believed to be able to solve the discrete log problem exponentially faster
than classical computers. By carefully designing a data embedding based on
Shor’s algorithm $U_{\rm shor}(\bm{x})$, the effect of the first feature map
can be undone resulting in the original trivial data space. More precisely, in
the context of quantum kernel methods, there exist classically-hard model
predictions of the form

$\displaystyle
f(\bm{x})=\sum_{I=1}^{N_{tr}}\alpha^{*}_{i}\Tr[\rho(\bm{x}_{i})\rho(\bm{x})]\;,$
(37)

where $\rho(\bm{x})=U_{\rm shor}(\bm{x})\rho_{0}U^{\dagger}_{\rm
shor}(\bm{x})$ and $\alpha^{*}_{i}$ are the optimal coefficients obtained from
solving the support vector machine.

For the condition to translate this into the QELM framework, we can equate
both model predictions. That is, we have

$\displaystyle
f(\bm{x})=\sum_{k=1}^{N_{tr}}\alpha^{*}_{k}\Tr[\rho(\bm{x}_{k})\rho(\bm{x})]=\sum_{k=1}^{M}\eta^{*}_{k}\Tr[O_{k}\rho(\bm{x})]\;.$
(38)

One simple choice to achieve this is to take $\alpha^{*}_{k}=\eta^{*}_{k}$,
$\rho(\bm{x}_{k})=O_{k}$ with $M=N_{tr}$. This is a highly contrived example,
massaging the work of Ref. [49] into the quantum extreme learning formalism,
but it nonetheless shows that a quantum advantage can in theory be achieved
with a QELM.

##  IV Exponential Concentration in QELMs

In this section, we discuss the fundamental limitations of QELMs. As outlined
in the introduction, we demonstrate that QELM outputs input-independent
predictions when observables are concentrated exponentially with respect to
the system size. This is shown for four different scenarios: Haar-expressivity
of the model’s unitaries (Sec. IV.2), highly-entangled states (Sec. IV.3),
global observables (Sec. IV.4) and noisy evolution (Sec. IV.5).

###  IV.1 Definitions and its consequences

In general, ELMs are guaranteed to be trainable due to the convexity of their
loss landscape. This also extends to their quantum counterparts, where
training is performed via a linear regression of the outcome observables.
However, while in the classical case each observable can be computed exactly,
in QELM this is not the case. In quantum systems, physical quantities can only
be estimated through repeated measurements, owing to the statistical nature of
such systems. In order to efficiently estimate the observables, then, one must
be able to approximate its value precisely enough with only
$\mathcal{O}(\mathrm{poly}(n))$ measurements. In simple terms, we would like
our QELM to recognise, through an accurate estimation of the output
observables, that a certain input was fed into the model rather than any other
one. Hence, we need the observables to be input-dependent.

However, the four sources of concentration, which we will discuss in the
following sections, can result in an arbitrary observable concentrating
exponentially with the system size towards a fixed value, no matter the input.
We differentiate between probabilistic and deterministic exponential
concentration.

######  Definition 2 (Probabilistic exponential concentration).

Consider a quantity $Q(\bm{\theta})$ that depends on some variable
$\bm{\theta}$ which can be estimated from an $n$-qubit quantum computer as an
expectation value of some observable. $Q(\bm{\theta})$ is said to
probabilistically exponentially concentrate around a fixed value $\mu$ if

$\mathrm{Pr}_{\bm{\theta}}[|Q(\bm{\theta})-\mu|\geqslant\delta]\leqslant\dfrac{\beta}{\delta^{2}}\hskip
2.0pt,\;\;\beta\in\mathcal{O}(1/b^{n})\;,$ (39)

for some $b>1$. That is, the probability that $Q(\bm{\theta})$ deviates from
$\mu$ by a small amount $\delta$ is exponentially small for all $\bm{\theta}$.

Let us note that in Eq. (39), by applying Chebyschev’s inequality, $\beta$ can
readily be associated to ${\rm Var}_{\bm{\theta}}[Q(\bm{\theta})]$ with
$\mu=\mathbb{E}_{\bm{\theta}}[Q(\bm{\theta})]$. As a matter of fact, one often
bounds the variance to assess the degree of concentration for a given
observable.

######  Definition 3 (Deterministic exponential concentration).

Consider a quantity $Q(\bm{\theta})$ that depends on some variable
$\bm{\theta}$ which can be estimated from an $n$-qubit quantum computer as an
expectation value of some observable. $Q(\bm{\theta})$ is said to
deterministically exponentially concentrate around a fixed value $\mu$ if its
distance from it is bounded by an exponentially small value

$|Q(\bm{\theta})-\mu|\leqslant\beta\hskip
2.0pt,\;\;\beta\in\mathcal{O}(1/b^{n})\;,$ (40)

for some $b>1$. That is, $Q(\bm{\theta})$ does not deviate from $\mu$ for more
than $\beta$ for all $\theta$.

Definitions 2, 3 are rather general and can be applied to many instances. In
the context of QELM, we will consider $\bm{\theta}=\bm{x}$ or
$\bm{\theta}=U_{R}$ and $Q(\bm{\theta})=\expectationvalue{O}_{\bm{x}}$, where
$O$ can be any one of the observables out of the set used for training. In
this case, the probability in Eq. (39), as well as variance and mean of
$\expectationvalue{O}_{\bm{x}}$, would be taken over the set of all inputs
$\mathcal{X}$ or over an ensemble from which $U_{R}$ is drawn. In practice,
each observable can only be estimated by performing $N_{\text{meas}}$
measurements. This leads to a finite-shot error
$\epsilon\in\mathcal{O}(1/\sqrt{N_{\text{meas}}})$. Now, if the observable is
found to be exponentially concentrated, then Eq. (39) indicates that in order
to faithfully recognise $\expectationvalue{O}_{\bm{x}}$ from $\mu$, one would
need a resolution $\alpha\in\mathcal{O}(1/b^{n})$. This implies that the error
generated by the finite sampling scheme should be less than the resolution,
yielding $N_{\text{meas}}\geqslant b^{n/2}$. Such a dependence on the system
size $n$ makes the observable estimation highly inefficient.

In the regime of exponential concentration, training the QELM will still be
possible, as the model does not require training on the quantum device and is
instead trained through classical convex optimization. However, by employing
only a polynomial number of shots to approximate the observables, the model
will not learn on input-dependent observables and so it will not be able to
recognise the actual input from a completely random one. Hence, we remark that
the model’s trainability will not suffer from exponential concentration, but
its generalization capabilities will. If the model is trained on input data
that cannot be distinguished from random data, then the prediction on new data
will in turn be random. For a more formal discussion of these ideas see
Appendix C.

###  IV.2 Haar-expressivity-induced concentration

Loosely speaking, one can define the Haar-expressivity of an ensemble of
unitaries of dimension $d$ as a measure of the extent to which the ensemble
covers the unitary group $\mathcal{U}(d)$. Given a choice of unitary in the
encoding strategy of QELM, we can straightforwardly define the unitary
ensemble spanned by the encoding unitary

$\mathbb{U}_{\bm{x}}=\\{U(\bm{x}):\bm{x}\in\mathcal{X}\\}\,.$ (41)

To quantitatively measure the Haar-expressivity of $\mathbb{U}_{\bm{x}}$, one
can define the second moment of the Haar distribution in dimension
$d_{A}=2^{n_{A}}$ associated to the accessible space

$\mathcal{V}_{\text{Haar}}(\cdot)=\int_{\mathcal{U}(d_{A})}\,d\mu(V)V^{\otimes
2}(\cdot)(V^{\dagger})^{\otimes 2}\,.$ (42)

A $2$-design is an ensemble for which its distribution agrees with that of the
Haar measure up to the second moment. Hence, the following super-operator
defines the distance between $\mathbb{U}_{\bm{x}}$ and a $2$-design ensemble

$\mathcal{A}_{\mathbb{U}_{\bm{x}}}(\cdot):=\mathcal{V}_{\text{Haar}}(\cdot)-\int_{\mathbb{U}_{\bm{x}}}\,dU(\bm{x})U(\bm{x})^{\otimes
2}(\cdot)(U(\bm{x})^{\dagger})^{\otimes 2}\,.$ (43)

One can measure the Haar-expressivity of the ensemble $\mathbb{U}_{\bm{x}}$ by
how close it is to a $2$-design. So taking, for instance, the diamond norm of
Eq. (43) is a good measure of Haar-expressivity

$\varepsilon_{\diamond}^{\bm{x}}:=\norm{\mathcal{A}_{\mathbb{U}_{\bm{x}}}}_{\diamond}\,,$
(44)

where the superscript underlines the fact that in general the Haar-
expressivity will depend on the input ensemble $\mathcal{X}$. Alternatively,
one could also use the $1$-norm
$\varepsilon_{1}^{\bm{x}}:=\norm{\mathcal{A}_{\mathbb{U}_{\bm{x}}}}_{1}$,
however for most results we will rely on the diamond norm.

One can show that the encoding unitary can potentially generate exponential
concentration with respect to the number of accessible qubits $n_{A}$. Let us
formalize this in the following Theorem.

######  Theorem 2 (Encoding Haar-expressivity-induced concentration).

Consider the expectation value of an arbitrary observable as defined in Eq.
(3) and data-dependent unitary ensemble introduced in Eq. (41). Then we have
that

$\mathrm{Pr}_{\bm{x}}[|\expectationvalue{O}_{\bm{x}}-\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}]|\geqslant\delta]\leqslant\dfrac{G(\varepsilon_{\diamond}^{\bm{x}})}{\delta^{2}}\,,$
(45)

where $\mathbb{E}_{\bm{x}}[\cdot]$ is the expectation taken over
$\mathbb{U}_{\bm{x}}$ and the term on the RHS is:

$G(\varepsilon_{\diamond}^{\bm{x}})=\dfrac{\big{(}\Tr[\widetilde{O}_{\Lambda}]^{2}+\Tr[\widetilde{O}_{\Lambda}^{2}]\big{)}}{2^{n_{A}}(2^{n_{A}}+1)}+\varepsilon_{\diamond}^{\bm{x}}\norm{\Lambda(O)}_{\infty}^{2}\,,$
(46)

where
$\widetilde{O}_{\Lambda}=\Tr[(\mathcal{I}\otimes\outerproduct{0}{0})\Lambda(O)]$
with $\Lambda(\cdot)=U_{R}^{\dagger}(\cdot)U_{R}$.

A proof of this theorem is provided in Appendix D. Note that, generally, for
Pauli observables acting on the accessible space we have
$\Tr[O^{2}]=2^{n_{A}}$ and so the first term in the definition of
$G(\varepsilon_{\diamond}^{\bm{x}})$ is still exponentially small in the
number of accessible qubits. Theorem 2 indicates that if the encoding ensemble
is exponentially close to a 2-design such that
$\varepsilon_{\diamond}^{\bm{x}}$ is exponentially small, then the observable
will exponentially concentrate towards its expectation value.

We provide also numerics showcasing the phenomenon. We consider a $L$-layered
ansatz

$U(\bm{x})=\prod_{l=1}^{L}U_{l}(\bm{x})W_{l}$ (47)

where $U_{l}(\bm{x})=U_{l,1}(\bm{x})\otimes\dots\otimes U_{l,n_{A}}(\bm{x})$
are separable unitaries made up of single-qubit rotations, and $W_{l}$ are a
series of entangling gates between neighboring qubits. In Fig. 5, we show that
exponential concentration appears as the ansatz depth $L$ increases, and
therefore approaches a $2$-design.

Figure 5: Encoding Haar-expressivity-induced concentration. Variance of the
observable $Z_{1}Z_{2}$ over a set of inputs uniformly sampled from
$[-\pi,\pi]$, as a function of the number of accessible qubits $n_{A}$ and for
different depths of the encoding unitary as defined in Eq. (47).

Similarly to the encoding strategy, we can characterize the exponential
concentration stemming from the reservoir unitary evolution. As a matter of
fact, in Section III.4 we showed that more complex reservoir dynamics such as
the chaotic Ising model and a Haar random unitary can provide a richer Fourier
spectra, potentially providing quantum advantage for QELM. Now, we would like
to investigate if the scrambling degree of a reservoir unitary poses a
limitation in terms of exponential concentration.

Suppose that the reservoir unitary $U_{R}$ is drawn from an ensemble
$\mathbb{U}_{R}$. Then, similarly to Eq. (43), we can define its Haar-
expressivity super-operator as the distance between the Haar measure over the
unitary ensemble of dimension $d$ and the average over $\mathbb{U}_{R}$:

$\mathcal{A}_{\mathbb{U}_{R}}(\cdot):=\mathcal{V}_{\text{Haar}}(\cdot)-\int_{\mathbb{U}_{R}}\,dU_{R}U_{R}^{\otimes
2}(\cdot)(U_{R}^{\dagger})^{\otimes 2}\,.$ (48)

Then the diamond norm
$\varepsilon_{\diamond}^{R}:=\norm{\mathcal{A}_{\mathbb{U}_{R}}}_{\diamond}$
measures the Haar-expressivity of the reservoir. Depending on whether the
ensemble $\mathbb{U}_{R}$ forms a 2-design (such that
$\varepsilon_{\diamond}^{R}=0$), there may be a tendency for observables to
concentrate around their average. Let us formalize this in a Theorem.

######  Theorem 3 (Reservoir Haar-expressivity-induced concentration).

Consider a reservoir evolution $U_{R}\in\mathbb{U}_{R}$. Consider the
expectation value of an arbitrary Hermitian observable as defined in Eq. (3).
Then we have that

$\mathrm{Pr}_{U_{R}}[|\expectationvalue{O}_{\bm{x}}-\mathbb{E}_{U_{R}}[\expectationvalue{O}_{\bm{x}}]|\geqslant\delta]\leqslant\dfrac{G(\varepsilon_{\diamond}^{R})}{\delta^{2}}\,,$
(49)

where

$G(\varepsilon_{\diamond})=\dfrac{\big{(}\Tr[O]^{2}+\Tr[O^{2}]\big{)}}{2^{n}(2^{n}+1)}+\varepsilon_{\diamond}^{R}\norm{O}_{\infty}\,.$
(50)

The proof is similar to Theorem 2. Compared to Theorem 2, this implies a
stronger concentration given by the inverse exponential dependence on the
total space $d=2^{n}$. Crucially, Theorem 3 tells us that if the ensemble
$\mathbb{U}_{R}$ forms a $2$-design, the probability of picking a $U_{R}$ for
which the expectation value (for any given input) differs from $\mu$ by more
than $\delta$ is exponentially suppressed. Hence, we will need exponentially
many shots to recognise the observable from $\mu$. In Fig. 6, numerics support
this result by showing exponential concentration when the unitaries are deep
enough. Also in the case of the reservoir, unitaries similar to the one in Eq.
(47) are considered, with randomly chosen parameters instead of data inputs.

While these two theorems are given in terms of some classical input data, in
general they can be extended to quantum data. Suppose that the goal is to
learn some unknown quantum process [9, 10, 11, 12], and that to do so we are
given a set of states $\\{\rho_{k}\\}_{k=1}^{N_{tr}}$, along with some set of
expectation values associated to each state
$\\{\bm{y}^{(k)}\\}_{k=1}^{N_{tr}}$. We then perform a QELM learning task by
letting the input states evolve with the hidden space through some unitary
$U_{R}$, and perform measurements which we use as inputs of a simple linear
regression. While in this case the input data cannot be associated with
classical data, it is normally always true that these states must have
undergone some unitary evolution drawn from a unitary ensemble. Then, even if
we do not know the unitary ensemble, Theorem 2 holds as long as the underlying
unitary ensemble approaches a $2$-design. Furthermore, Theorem 3 made no
assumptions regarding the input data, which implies that its validity easily
extends also in this scenario.

Figure 6: Reservoir Haar-expressivity-induced concentration. Variance of the
observable $Z_{1}Z_{2}$ over a set of inputs uniformly sampled from
$[-\pi,\pi]$, as a function of the number of total qubits $n$ and for
different depths of the reservoir unitary similar to the definition in Eq.
(47).

###  IV.3 Entanglement-induced concentration

In this section we explore entanglement as another source of exponential
concentration. In particular, we find that if the subspace onto which the
observable acts non-trivially is highly entangled to the rest of the system,
then we expect a deterministic concentration when computing the expectation
value. Intuitively, tracing out qubits of highly entangled states leads to
reduced states which are close to maximally mixed. Let us formalize this in
the following Theorem.

######  Theorem 4 (Entanglement-induced concentration).

Suppose an observable that acts non-trivially on a subspace $\mathcal{H}_{k}$
of the entire Hilbert space $\mathcal{H}$, so that
$O=O_{k}\otimes\mathcal{I}_{\bar{k}}$. Then, the concentration of its
expectation value around the fixed point $\mu=\Tr[O]/2^{n}$ will be bounded by

$\left|\expectationvalue{O}_{\bm{x}}-\mu\right|\leqslant\norm{O_{k}}_{\infty}\sqrt{2\ln{2}}S\biggr{(}\widetilde{\rho}_{k}(\bm{x})\biggr{\lVert}\dfrac{\mathcal{I}_{k}}{2^{k}}\biggr{)}^{1/2}\,,$
(51)

where $S(\cdot\lVert\cdot)$ is the relative entropy and
$\widetilde{\rho}_{k}(\bm{x})=\Tr_{\bar{k}}(\widetilde{\rho}(\bm{x}))$
represents the final reduced state on subspace $\mathcal{H}_{k}$.

A proof of Theorem 4 is provided in Appendix D. Crucially, for states that
obey a volume-law scaling, i.e.
$S(\widetilde{\rho}_{k}(\bm{x})\lVert\mathcal{I}_{k}/2^{k})\in\mathcal{O}(2^{-n})$,
then the difference between the observable and $\Tr[O]/2^{n}$ will always be
exponentially small in the number of qubits. On the other hand, for states
that obey an area-law scaling, i.e.
$S(\widetilde{\rho}_{k}(\bm{x})\lVert\mathcal{I}_{k}/2^{k})\in\mathcal{O}(1)$,
the bound in Theorem 4 becomes loose and exponential concentration may be
avoided. However, we remind the reader that even in the case where we have
area-law scaling, this does not preclude concentration. Other sources of
exponential concentration might still play a role and therefore they ought to
be considered.

###  IV.4 Global-measurement-induced concentration

We now consider the effect of global measurements. Indeed, previous work [22,
30] has already shown that a global observable, which acts non-trivially on
all $n$ qubits, can lead to an exponential concentration of its expectation
value. In what follows, to distinguish this phenomenon from Haar-expressivity-
induced and entanglement-induced concentration, we consider a separable
initial state as well as encoding and reservoir unitaries in a tensor product
form. This setting ensures no entanglement and low Haar-expressivity for both
unitaries. By considering a projective measurement, we formalize this concept
in the following theorem:

######  Theorem 5 (Global measurement-induced concentration).

Suppose an observable $O=\outerproduct{m}{m}$, i.e. a projective measurement
onto state $\ket{m}=\ket{m_{1}\dots m_{n}}$. Consider an initial separable
state $\rho_{0}=\bigotimes_{k=1}^{n}\rho_{0}^{(k)}$. Suppose that the encoding
unitary creates no entanglement, so that:
$U(\bm{x})=\bigotimes_{k=1}^{n_{A}}U_{k}(x_{k})$ where $x_{k}$ is an input
component of $\bm{x}$, and all are uniformly sampled from $[-\pi,\pi]$.
Similarly, assume furthermore that the reservoir has the form
$U_{R}=\bigotimes_{k=1}^{n}V_{k}$. Then we have

$\mathrm{Pr}_{\bm{x}}[|\expectationvalue{O}_{\bm{x}}-\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}]\geqslant\delta]\leqslant\dfrac{\alpha\prod_{k=1}^{n_{A}}G_{k}(\varepsilon_{x_{k}})}{\delta^{2}}\,,$
(52)

where
$\varepsilon_{x_{k}}=\norm{\mathcal{A}_{\mathbb{U}_{x_{k}}}\biggr{(}\rho_{0}^{(k)^{\otimes
2}}\biggr{)}}_{1}$ is the Haar-expressivity measure of the local unitary
$U_{k}(x_{k})$ and
$\alpha=\prod_{j=n_{A}+1}^{n}|\innerproduct{0|V_{j}}{m_{j}}|^{2}$. The term
$G_{k}(\varepsilon_{x_{k}})$ is given by

$G_{k}(\varepsilon_{x_{k}})=\biggr{(}\frac{1}{3}+\varepsilon_{x_{k}}\biggr{(}\varepsilon_{x_{k}}+\sqrt{\frac{4}{3}}\biggr{)}\biggr{)}^{1/2}\,.$
(53)

A proof of the Theorem is given in Appendix D. This result suggests that using
global measurements, even in the case of simple encoding and/or reservoir
unitaries, is not advised as it can lead to exponential concentration of the
observable. In particular, Theorem 5 points out that for global measurements,
it is the Haar-expressivity of single-qubit unitaries that dictates the
exponential concentration. As shown in the plot provided in Fig. 7, low-depth
single-qubit unitaries already cause exponential concentration.

Figure 7: Global measurement-induced concentration Variance of a global
observable as a function of the system size $n$, varying the depth of the
encoding unitary. The variance is taken over an ensemble of inputs uniformly
sampled from $[-\pi,\pi]$.

###  IV.5 Noise-induced concentration

Noise is the last and final source of exponential concentration which can
hinder the performance of QELM. As of today, NISQ devices are in fact prone to
making errors caused by different phenomena, be it decoherence, dephasing or
other. These are one of the major obstacles yet to be overcome in order to
achieve full control of a quantum device. On top of this, Ref. [15] has
already shown the existence of noise-induced BPs. This is not limited to
gradient estimation, but also cost estimation in general [30]. In this
section, we show that Pauli noise, a quite general noise model, leads to
exponential concentration in a QELM model.

Figure 8: Noise-induced concentration Distance of
$\expectationvalue{Z_{1}}_{\bm{x}}$ from $\mu=0$ as a function of the number
of encoding layers, and for different noise parameters $p$. Here we consider
$n_{A}=7,\ n_{H}=1$. The distance is averaged over inputs uniformly sampled
from $[-\pi,\pi]$. Exponential concentration is seen in all cases, with
increasing slope as the noise in the system increases.

Consider a $L$-layered encoding, subject to Pauli noise. Then the embedded
state will be

$\rho(\bm{x})=\mathcal{N}\circ\mathcal{U}_{L}(\bm{x}_{L})\circ\mathcal{N}\circ...\circ\mathcal{N}\circ\mathcal{U}(\bm{x}_{1})\circ\mathcal{N}(\rho_{0})\,,$
(54)

where
$\mathcal{U}(\bm{x}_{i})(\cdot)=U(\bm{x}_{i})(\cdot)U(\bm{x}_{i})^{\dagger}$
and $\\{\bm{x}_{i}\\}_{i=1}^{L}$ are some functions of $\bm{x}$. Moreover,
each noise term
$\mathcal{N}=\mathcal{N}_{1}\otimes...\otimes\mathcal{N}_{n_{A}}$ acts on each
single qubit in the following way

$\mathcal{N}_{j}(\sigma)=q_{\sigma}\sigma,\hskip 28.45274pt\forall
j=1,...,n\hskip 28.45274pt\sigma\in\\{X,Y,Z\\}\,.$ (55)

Finally let us define the characteristic noise parameter
$q=\max\\{|q_{X}|,|q_{Y}|,|q_{Z}|\\}$. Then, the following theorem holds true.

######  Theorem 6 (Noise-induced concentration).

Consider the $L$-layered encoding as defined in Eq. (54) with $q<1$. Then, the
concentration around a fixed point of the expectation value of an observable
as defined in Eq. (3) can be bounded as

$\biggr{|}\expectationvalue{O}_{\bm{x}}-\dfrac{\Tr[\widetilde{O}_{\Lambda}]}{2^{n_{A}}}\biggr{|}\leqslant\norm{\Lambda(O)}_{\infty}\biggr{(}\dfrac{1}{b}q^{b(L+1)}S_{2}\biggr{(}\rho_{0}\biggr{\lVert}\frac{\mathcal{I}}{2^{n_{A}}}\biggr{)}\biggr{)}^{\frac{1}{2}}\,,$
(56)

where
$\widetilde{O}_{\Lambda}=\Tr[\Lambda(O)(\mathcal{I}\otimes\outerproduct{0}{0})]$,
$b=1/(2\ln{2})$ and $S_{2}(\cdot\lVert\cdot)$ denotes the sandwiched $2$-Rényi
relative entropy.

The inequality in Eq. (56) points out that if $L\in\mathcal{O}(n_{A})$, then
the deviation of the observable from an input-independent fixed value will be
exponentially vanishing with respect to the dimension of the accessible space.
Numerics in Fig. 8 demonstrate the characteristic exponential dependence on
the depth of the encoding for different noise parameters.

##  V Discussion

We have conducted an analytical and numerical study on the interplay between
the classical data encoding and exponential concentration phenomena on the
expressivity and prediction capabilities of QELMs. The quantum substrate of a
QELM framework here consists of three components: a classical data encoder, a
quantum reservoir, and a measurement readout. The unitary encoding strategy
determines achievable Fourier frequencies. The quantum reservoir acts as a
feature map induced by many-body quantum dynamics.

The measurement readout consists of several observables, each of which selects
a function from the class of classical mappings defined by the reservoir. The
net result of the reservoir and measurement steps is a set of basis functions.
The model is then trained by fitting a linear combination of these functions
to the training data.

Based on this framework, we started by discussing the performance of a QELM
from two perspectives: its Fourier-expressivity and whether the model could be
replaced by a classical surrogate. In particular, we found that the Fourier-
expressivity of a QELM is upper bounded by the number of frequencies resulting
from the encoding, the number of observables, and the globality of
observables. Hence, the encoding and measurement jointly determine the
Fourier-expressivity. We recall that a QELM model which yields a Fourier-
concentrated prediction can be efficiently simulated on a classical computer
[17, 18, 19] and so using an encoding strategy that results in exponentially
many achievable frequencies is a necessary condition to achieve quantum
advantage. On this basis we discourage the use of Pauli encodings.

Our study highlights that the reservoir dynamics has a significant effect on
the Fourier spectra of a QELM model. We compared the Fourier spectra resulting
from four reservoir settings: no reservoir, integrable Ising reservoir,
chaotic Ising reservoir, and Haar random reservoir and defined the richness of
Fourier modes as the proportion of non-zero Fourier coefficients averaged over
Pauli strings. We found that the richness decreases exponentially with the
system size for the first two reservoir settings, and saturates for the last
two reservoirs. As adding exponentially many Fourier modes is classically
inefficient, selecting a quantum reservoir with rich dynamics may lead to
QELMs that can outperform classical surrogates.

However, there is a balance to be struck in this regard. While chaotic Ising
and Haar random reservoirs (i.e., scrambling reservoirs) lead to a rich set of
basis functions, such reservoirs are also prone to exponential concentration.
This washes out the effect of the input data, hindering the model’s
generalization power and thus limiting the scalability of such QELMs.
Crucially, this implies that there exists a trade-off between Fourier-
expressivity and generalizability: The highly expressive encoding unitaries
and global measurements enhance the Fourier-expressivity of the prediction,
but lead to exponential concentration, making the model insensitive to input
data. More generally, we identified four sources of exponential concentration:
the Haar-expressivity of both encoding and reservoir unitaries, entanglement,
global measurement, and noise.

Our work also provides insights for understanding the limitations and
advantages of using quantum computational substrate in the context of
(classical) ELMs. Compared with a back-propagation trained feed-forward
network, one major disadvantage of ELMs is the need for a very large number of
hidden neurons (e.g. 15680 hidden neurons to learn the MNIST-database of
handwritten digits [50]) to achieve a comparable accuracy. The number of
hidden neurons somewhat corresponds to the number of observables in QELMs,
which cannot be efficiently increased by using a quantum computational
substrate. Hence, for such tasks the number of measurements needs to be of the
same magnitude as the number of data features and this limitation may still
restrict the performance of QELMs. Nevertheless, in this work we showed that
the quantum computational substrate can provide additional activation
functions which are potentially inefficient for a classical computer, in
particular Fourier series consisting of exponentially many modes.
Consequently, QELMs create opportunities to solve learning tasks, for which
common activation functions are not suited.

We remark that the role of hidden qubits has not been discussed in this work.
More specifically, the Fourier-expressivity is independent of number of hidden
qubits $n_{H}$. Further work is hence required to ascertain the effect of
$n_{H}$ on the QELM’s prediction. In particular, it would be valuable to
explore if a larger hidden space would lead to some general improvements of
QELM, or it would just amount to a different inductive bias, such that $n_{H}$
should be purely viewed as a hyperparameter. It would also be interesting to
compare performance of other reservoir types and of reservoirs with different
$n_{H}$ on a given task and investigate a strategy of optimizing $n_{H}$.

Given the close relationship between QELMs and Quantum Reservoir Computing
(QRC), which employs a quantum reservoir for time-series prediction, our
analysis can be extended to examine the expressivity and the exponential
concentration in QRC. This understanding is key to designing QRC that forecast
dynamical systems based on classical data encoding and measurement readout
[13, 14, 51, 52, 53, 54]. As the measurement readout can introduce issues of
exponential concentration, the QRC prediction on unseen time-series data might
also become input-agnostic when the size of a quantum reservoir grows large.
Our results indicate that adopting QRC that outputs quantum data [11, 10], or
its variant such as Quantum Next Generation Reservoir Computing that forecasts
future quantum states [55], may circumvent the scalability issues imposed by
exponential concentration by working directly with structured quantum data.
However, we leave the detailed analysis of quantum reservoir systems for time-
series prediction for future work.

##  VI Acknowledgements

TC acknowledges funding support from the NSRF via the Program Management Unit
for Human Resources & Institutional Development, Research and Innovation
[grant number B37G660011], and from Thailand Science Research and Innovation
Fund Chulalongkorn University (IND66230005). ST and ZH acknowledge support
from the Sandoz Family Foundation-Monique de Meuron program for Academic
Promotion.

## References

  * Huang  _et al._ [2004] G.-B. Huang, Q.-Y. Zhu, and C.-K. Siew, Extreme learning machine: a new learning scheme of feedforward neural networks, in  _2004 IEEE international joint conference on neural networks (IEEE Cat. No. 04CH37541)_, Vol. 2 (Ieee, 2004) pp. 985–990.
  * Ding  _et al._ [2015] S. Ding, H. Zhao, Y. Zhang, X. Xu, and R. Nie, Extreme learning machine: algorithm, theory and applications, Artificial Intelligence Review 44, 103 (2015).
  * Wang  _et al._ [2022a] J. Wang, S. Lu, S.-H. Wang, and Y.-D. Zhang, A review on extreme learning machine, Multimedia Tools and Applications 81, 41611 (2022a).
  * Huang  _et al._ [2015] G. Huang, G.-B. Huang, S. Song, and K. You, Trends in extreme learning machines: A review, Neural Networks 61, 32 (2015).
  * Goodfellow  _et al._ [2016] I. Goodfellow, Y. Bengio, and A. Courville,  _Deep Learning_ (MIT Press, 2016).
  * Huang  _et al._ [2006] G.-B. Huang, Q.-Y. Zhu, and C.-K. Siew, Extreme learning machine: theory and applications, Neurocomputing 70, 489 (2006).
  * Huang  _et al._ [2011] G.-B. Huang, H. Zhou, X. Ding, and R. Zhang, Extreme learning machine for regression and multiclass classification, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 42, 513 (2011).
  * Mujal  _et al._ [2021] P. Mujal, R. Martí nez-Peña, J. Nokkala, J. García-Beni, G. L. Giorgi, M. C. Soriano, and R. Zambrini, Opportunities in quantum reservoir computing and extreme learning machines, Advanced Quantum Technologies 4, 2100027 (2021).
  * Innocenti  _et al._ [2023] L. Innocenti, S. Lorenzo, I. Palmisano, A. Ferraro, M. Paternostro, and G. M. Palma, Potential and limitations of quantum extreme learning machines, Communications Physics 6, 118 (2023).
  * Ghosh  _et al._ [2019a] S. Ghosh, T. Paterek, and T. C. H. Liew, Quantum neuromorphic platform for quantum state preparation, Phys. Rev. Lett. 123, 260404 (2019a).
  * Ghosh  _et al._ [2019b] S. Ghosh, A. Opala, M. Matuszewski, T. Paterek, and T. C. H. Liew, Quantum reservoir processing, npj Quantum Information 5, 35 (2019b).
  * Suprano  _et al._ [2023] A. Suprano, D. Zia, L. Innocenti, S. Lorenzo, V. Cimini, T. Giordani, I. Palmisano, E. Polino, N. Spagnolo, F. Sciarrino, _et al._ , Experimental property-reconstruction in a photonic quantum extreme learning machine, arXiv preprint arXiv:2308.04543 10.48550/arXiv.2308.04543 (2023).
  * Fujii and Nakajima [2017] K. Fujii and K. Nakajima, Harnessing disordered-ensemble quantum dynamics for machine learning, Physical Review Applied 8, 024030 (2017).
  * Nakajima  _et al._ [2019] K. Nakajima, K. Fujii, M. Negoro, K. Mitarai, and M. Kitagawa, Boosting computational power through spatial multiplexing in quantum reservoir computing, Phys. Rev. Appl. 11, 034021 (2019).
  * Wang  _et al._ [2021] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Noise-induced barren plateaus in variational quantum algorithms, Nature Communications 12, 1 (2021).
  * Schuld  _et al._ [2021] M. Schuld, R. Sweke, and J. J. Meyer, Effect of data encoding on the expressive power of variational quantum-machine-learning models, Physical Review A 103, 032430 (2021).
  * Schreiber  _et al._ [2023] F. J. Schreiber, J. Eisert, and J. J. Meyer, Classical surrogates for quantum learning models, Physical Review Letters 131, 100803 (2023).
  * Landman  _et al._ [2022] J. Landman, S. Thabet, C. Dalyac, H. Mhiri, and E. Kashefi, Classically approximating variational quantum machine learning with random fourier features, arXiv preprint arXiv:2210.13200 (2022).
  * Sweke  _et al._ [2023] R. Sweke, E. Recio, S. Jerbi, E. Gil-Fuster, B. Fuller, J. Eisert, and J. J. Meyer, Potential and limitations of random fourier features for dequantizing quantum machine learning, arXiv preprint arXiv:2309.11647 (2023).
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications 9, 1 (2018).
  * Holmes  _et al._ [2022] Z. Holmes, K. Sharma, M. Cerezo, and P. J. Coles, Connecting ansatz expressibility to gradient magnitudes and barren plateaus, PRX Quantum 3, 010313 (2022).
  * Cerezo  _et al._ [2021a] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shallow parametrized quantum circuits, Nature Communications 12, 1 (2021a).
  * Sharma  _et al._ [2022] K. Sharma, M. Cerezo, L. Cincio, and P. J. Coles, Trainability of dissipative perceptron-based quantum neural networks, Physical Review Letters 128, 180505 (2022).
  * Cerezo and Coles [2021] M. Cerezo and P. J. Coles, Higher order derivatives of quantum neural networks with barren plateaus, Quantum Science and Technology 6, 035006 (2021).
  * Holmes  _et al._ [2021a] Z. Holmes, A. Arrasmith, B. Yan, P. J. Coles, A. Albrecht, and A. T. Sornborger, Barren plateaus preclude learning scramblers, Physical Review Letters 126, 190501 (2021a).
  * Marrero  _et al._ [2021] C. O. Marrero, M. Kieferová, and N. Wiebe, Entanglement-induced barren plateaus, PRX Quantum 2, 040316 (2021).
  * Uvarov and Biamonte [2021] A. Uvarov and J. D. Biamonte, On barren plateaus and cost function locality in variational quantum algorithms, Journal of Physics A: Mathematical and Theoretical 54, 245301 (2021).
  * Arrasmith  _et al._ [2021] A. Arrasmith, M. Cerezo, P. Czarnik, L. Cincio, and P. J. Coles, Effect of barren plateaus on gradient-free optimization, Quantum 5, 558 (2021).
  * Arrasmith  _et al._ [2022] A. Arrasmith, Z. Holmes, M. Cerezo, and P. J. Coles, Equivalence of quantum barren plateaus to cost concentration and narrow gorges, Quantum Science and Technology 7, 045015 (2022).
  * Thanasilp  _et al._ [2022] S. Thanasilp, S. Wang, M. Cerezo, and Z. Holmes, Exponential concentration and untrainability in quantum kernel methods, arXiv preprint arXiv:2208.11060 (2022).
  * Rudolph  _et al._ [2023] M. S. Rudolph, S. Lerch, S. Thanasilp, O. Kiss, S. Vallecorsa, M. Grossi, and Z. Holmes, Trainability barriers and opportunities in quantum generative modeling, arXiv preprint arXiv:2305.02881 (2023).
  * Ragone  _et al._ [2023] M. Ragone, B. N. Bakalov, F. Sauvage, A. F. Kemper, C. O. Marrero, M. Larocca, and M. Cerezo, A unified theory of barren plateaus for deep parametrized quantum circuits, arXiv preprint arXiv:2309.09342 (2023).
  * Fontana  _et al._ [2023] E. Fontana, D. Herman, S. Chakrabarti, N. Kumar, R. Yalovetzky, J. Heredge, S. Hari Sureshbabu, and M. Pistoia, The adjoint is all you need: Characterizing barren plateaus in quantum ansätze, arXiv preprint arXiv:2309.07902 (2023).
  * García-Martín  _et al._ [2023] D. García-Martín, M. Larocca, and M. Cerezo, Deep quantum neural networks form gaussian processes, arXiv preprint arXiv:2305.09957 (2023).
  * Cerezo  _et al._ [2023] M. Cerezo, M. Larocca, D. García-Martín, N. Diaz, P. Braccia, E. Fontana, M. S. Rudolph, P. Bermejo, A. Ijaz, S. Thanasilp, _et al._ , Does provable absence of barren plateaus imply classical simulability? or, why we need to rethink variational quantum computing, arXiv preprint arXiv:2312.09121 https://doi.org/10.48550/arXiv.2312.09121 (2023).
  * Gan  _et al._ [2023] B. Y. Gan, D. Leykam, and S. Thanasilp, A unified framework for trace-induced quantum kernels, arXiv preprint arXiv:2311.13552 https://doi.org/10.48550/arXiv.2311.13552 (2023).
  * Goto  _et al._ [2021] T. Goto, Q. H. Tran, and K. Nakajima, Universal approximation property of quantum machine learning models in quantum-enhanced feature spaces, Physical Review Letters 127, 090506 (2021).
  * Gonon and Jacquier [2023] L. Gonon and A. Jacquier, Universal approximation theorem and error bounds for quantum neural networks and quantum reservoirs, arXiv preprint arXiv:2307.12904 10.48550/arXiv.2307.12904 (2023).
  * Fujii and Nakajima [2021] K. Fujii and K. Nakajima, Quantum reservoir computing: A reservoir approach toward quantum machine learning on near-term quantum devices, Reservoir Computing: Theory, Physical Implementations, and Applications , 423 (2021).
  * Wang  _et al._ [2022b] Y. Wang, K.-Y. Lin, S. Cheng, and L. Li, Variational quantum extreme learning machine, Neurocomputing 512, 83 (2022b).
  * Sainz de la Maza Gamboa [2022] U. Sainz de la Maza Gamboa,  _Quantum extreme learning machine for classification tasks_ , Ph.D. thesis, Universidad del Pais Vasco (2022).
  * Sakurai  _et al._ [2022] A. Sakurai, M. P. Estarellas, W. J. Munro, and K. Nemoto, Quantum extreme reservoir computation utilizing scale-free networks, Physical Review Applied 17, 064044 (2022).
  * Negoro  _et al._ [2021] M. Negoro, K. Mitarai, K. Nakajima, and K. Fujii, Toward nmr quantum reservoir computing, Reservoir Computing: Theory, Physical Implementations, and Applications , 451 (2021).
  * Caro  _et al._ [2021] M. C. Caro, E. Gil-Fuster, J. J. Meyer, J. Eisert, and R. Sweke, Encoding-dependent generalization bounds for parametrized quantum circuits, Quantum 5, 582 (2021).
  * Shin  _et al._ [2023] S. Shin, Y. Teo, and H. Jeong, Exponential data encoding for quantum supervised learning, Physical Review A 107, 012422 (2023).
  * Geller  _et al._ [2022] M. R. Geller, A. Arrasmith, Z. Holmes, B. Yan, P. J. Coles, and A. Sornborger, Quantum simulation of operator spreading in the chaotic ising model, Physical Review E 105, 035302 (2022).
  * Roberts and Yoshida [2017] D. A. Roberts and B. Yoshida, Chaos and complexity by design, Journal of High Energy Physics 2017, 121 (2017).
  * Holmes  _et al._ [2021b] Z. Holmes, A. Arrasmith, B. Yan, P. J. Coles, A. Albrecht, and A. T. Sornborger, Barren plateaus preclude learning scramblers, Physical Review Letters 126, 190501 (2021b).
  * Liu  _et al._ [2021] Y. Liu, S. Arunachalam, and K. Temme, A rigorous and robust quantum speed-up in supervised machine learning, Nature Physics , 1 (2021).
  * De Chazal  _et al._ [2015] P. De Chazal, J. Tapson, and A. Van Schaik, A comparison of extreme learning machines and back-propagation trained feed-forward networks processing the mnist database, in  _2015 IEEE international conference on acoustics, speech and signal processing (ICASSP)_ (IEEE, 2015) pp. 2165–2168.
  * Kutvonen  _et al._ [2020] A. Kutvonen, K. Fujii, and T. Sagawa, Optimizing a quantum reservoir computer for time series prediction, Scientific Reports 10, 14687 (2020).
  * Kubota  _et al._ [2023] T. Kubota, Y. Suzuki, S. Kobayashi, Q. H. Tran, N. Yamamoto, and K. Nakajima, Temporal information processing induced by quantum noise, Phys. Rev. Res. 5, 023057 (2023).
  * Fry  _et al._ [2023] D. Fry, A. Deshmukh, S. Y.-C. Chen, V. Rastunkov, and V. Markov, Optimizing quantum noise-induced reservoir computing for nonlinear and chaotic time series prediction, arXiv preprint arXiv:2303.05488 10.48550/arXiv.2303.05488 (2023).
  * Wudarski  _et al._ [2023] F. Wudarski, D. O‘Connor, S. Geaney, A. A. Asanjan, M. Wilson, E. Strbac, P. A. Lott, and D. Venturelli, Hybrid quantum-classical reservoir computing for simulating chaotic systems, arXiv preprint arXiv:2311.14105 10.48550/arxiv.2311.14105 (2023).
  * Sornsaeng  _et al._ [2023] A. Sornsaeng, N. Dangniam, and T. Chotibut, Quantum next generation reservoir computing: An efficient quantum algorithm for forecasting quantum dynamics, arXiv preprint arXiv:2308.14239 (2023).
  * Cerezo  _et al._ [2021b] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shallow parametrized quantum circuits, Nature Communications 12, 1 (2021b).
  * Tsybakov [2009] A. B. Tsybakov,  _Introduction to Nonparametric Estimation_ (Springer, 2009).

one´

Appendix

##  Appendix A Fourier decomposition analysis

###  A.1 Fourier decomposition for vector input

In this appendix, we generalize the case of scalar input addressed in the main
text and show that the prediction of a QELM with vector input
$\bm{x}\in\mathbb{R}^{d_{x}}$ can be expressed as a multivariate Fourier
series. Let the initial state of the accessible qubits before encoding be
$\rho_{0}=\sum_{i,j}\alpha_{ij}\ket{i}\bra{j}$. We consider an encoding
unitary of the form

$U(\bm{x})=e^{iH_{1}x_{1}}\otimes{}e^{iH_{2}x_{2}}\otimes\cdots\otimes{}e^{iH_{d_{x}}x_{d_{x}}}\,,$
(57)

where the generator $H_{l}$ of dimension $\zeta_{l}$ corresponding to the
$l$-th component of $\bm{x}$ has eigenvalues
$\\{\lambda^{(l)}_{1},\lambda^{(l)}_{2},\dots,\lambda^{(l)}_{\zeta_{l}}\\}$
for $l=1,2,\dots,d_{x}$. Then, the state of accessible qubits after encoding
is

$\displaystyle\rho(\bm{x})$
$\displaystyle=U(\bm{x})\rho_{0}U(\bm{x})^{\dagger}$ (58)
$\displaystyle=\sum_{i,j}\left(\prod_{l=1}^{d_{x}}e^{(\lambda^{(l)}_{\nu{}(j;l)}-\lambda^{(l)}_{\nu{}(i;l)})x_{l}}\right)\alpha_{ij}\ket{i}\bra{j}$
(59)
$\displaystyle=\sum_{i,j}e^{i(\bm{\lambda}_{j}-\bm{\lambda}_{i})\cdot\bm{x}}\alpha_{ij}\ket{i}\bra{j}\,.$
(60)

In the second line, the function $\nu{}(i;l)$ gives the eigenstate index of
the subspace, within which the input component $x_{l}$ is encoded, when the
qudit representing all accessible qubits is in state $\ket{i}$. In the third
line, the vector of eigenvalues is defined as
$\bm{\lambda}_{i}:=\left(\lambda^{(1)}_{\nu(i;1)},\
\lambda^{(2)}_{\nu(i;2)},\cdots,\
\lambda^{(d_{x})}_{\nu(i;d_{x})}\right)^{\intercal}$.

Compared with Eq. (10), we observe that, in comparison to the scalar input,
the state after encoding a vector input only differs in the Fourier basis.
Instead of $e^{i(\lambda_{j}-\lambda_{i})x}$ for scalar input data, we have
here $e^{i(\bm{\lambda}_{j}-\bm{\lambda}_{i})\cdot\bm{x}}$. Analogously, by
Eq. (2) and (3), we obtain the expectation value of readout observable

$\expectationvalue{O}_{x}=\sum_{\bm{\omega}\in\Omega}a_{\bm{\omega}}e^{i\bm{\omega}\cdot\bm{x}}\,,$
(61)

where the set of vectorial Fourier frequencies are given by

$\Omega=\\{\bm{\lambda}_{j}-\bm{\lambda}_{i}:i,j=1,2,\dots,2^{n_{A}}\\}\,,$
(62)

and the corresponding Fourier coefficients are

$a_{\bm{\omega}}=\sum_{i,j\mathrm{\,s.t.\,}\bm{\lambda}_{j}-\bm{\lambda}_{i}=\bm{\omega}}\alpha_{ij}\bra{j,0}U_{R}^{\dagger}{}OU_{R}\ket{i,0}\,.$
(63)

Consequently, by Eq. (4), the prediction of a QELM with a vector input can be
expressed as a multivariate Fourier series

$\displaystyle f_{\bm{\eta}}$
$\displaystyle=\sum_{\bm{\omega}\in\Omega}b_{\bm{\omega}}e^{i\bm{\omega}\cdot\bm{x}}\,,$
(64)

where $b_{\bm{\omega}}=\sum_{k=1}^{M}\eta_{k}a_{\bm{\omega}}^{(k)}$.

###  A.2 Upper bound of Fourier-expressivity

In this Appendix, we rigorously prove the upper bound of Fourier-expressivity
given by Theorem 1 in main text.

######  Theorem 1 (Upper bound of QELM’s Fourier-expressivity).

Consider a QELM as defined above with model prediction $f_{\bm{\eta}}$. Let
$M$ be the number of observables, $\Omega$ be the set of achievable
frequencies, and $n_{O}$ be the number of measured qubits, then

$\displaystyle\mathcal{F}\left[f_{\bm{\eta}}\right]$
$\displaystyle\leqslant\operatorname{min}\\{M,|\Omega|,4^{n_{O}}\\}\,,$ (65)

where $|\Omega|\leqslant 4^{n_{A}}$.

###### Proof.

We recall (Eq. (11) and (26)) the measurement outcome can be written as

$\expectationvalue{O_{k}}_{x}=\sum_{\omega\in\Omega}a^{(k)}_{\omega}e^{i\omega{x}}\,$
(66)

and the prediction of the QELM is

$\displaystyle f_{\bm{\eta}}$
$\displaystyle=\sum_{k=1}^{M}\eta_{k}\expectationvalue{O_{k}}_{x}$ (67)
$\displaystyle=\sum_{\omega\in\Omega}b_{\omega}e^{i\omega x}\,.$ (68)

As both consist of a linear combination of terms, it is convenient to use a
matrix representation. Recall that we write the vector of trainable weights as
$\bm{\eta}=[\eta_{1},\cdots\eta_{M}]^{\intercal}$ and the prediction’s Fourier
coefficients as $\bm{b}=[b_{\omega_{1}},\cdots
b_{\omega_{|\Omega|}}]^{\intercal}$. We further define
$\bm{A}\in\mathbb{C}^{|\Omega|\crossproduct{}M}$ to be the matrix consisting
of the Fourier coefficients of each of the $M$ observables as its columns,
i.e.,

$\bm{A}=\begin{pmatrix}a_{\omega_{1}}^{(1)}&a_{\omega_{1}}^{(2)}&\cdots&a_{\omega_{1}}^{(M)}\\\
a_{\omega_{2}}^{(1)}&a_{\omega_{2}}^{(2)}&\cdots&a_{\omega_{2}}^{(M)}\\\
\vdots&\vdots&\ddots&\vdots\\\
a_{\omega_{|\Omega|}}^{(1)}&a_{\omega_{|\Omega|}}^{(2)}&\cdots&a_{\omega_{|\Omega|}}^{(M)}\end{pmatrix}\,.$
(69)

From Eq. (66) and (67), we can write

$\bm{b}=\bm{A}\cdot\bm{\eta}\,.$ (70)

We observe from Eq. (26) that the prediction is a linear combination of
Fourier single mode functions which are orthogonal. Hence, the Fourier-
expressivity $\mathcal{F}$ is exactly the degrees of freedom of the
coefficients $\\{b_{\omega_{1}},\cdots b_{\omega_{|\Omega|}}\\}$, which are
components of $\bm{b}$. Moreover, in Eq. (70) each component of $\bm{b}$ is a
linear combination of column vectors of matrix $\bm{A}$ with trainable weights
$\bm{\eta}$. Hence, the degrees of freedom of $\bm{b}$’s components equals the
rank of $\bm{A}$ and we obtain

$\mathcal{F}\left[f_{\bm{\eta}}\right]=\operatorname{rank}(A)\,.$ (71)

Since the elements of $\bm{A}$ are controlled by both the reservoir unitary
and the measurement, we next decompose $\bm{A}$ into a product of two
matrices, which represent the dynamics of reservoir and the measurement,
respectively. Recall that any Hermitian observable can be expanded in Pauli
basis. We assume $n_{O}$ qubits are measured ($n_{O}\leqslant n_{A}+n_{H}$),
and let $\\{{P_{1}},{P_{2}},\dots,{P}_{4^{n_{O}}}\\}$ denote the Pauli basis,

$\Bigl{\\{}{P_{r}}=\left(\bigotimes_{i=1}^{n_{O}}\sigma_{i}\right)\otimes\mathcal{I}:\sigma_{i}\in\\{\sigma_{x},\sigma_{y},\sigma_{z},I\\}\Bigr{\\}}\,,$
(72)

whose elements form a complete operator basis. Therefore, any Hermitian
observable can be written as a linear combination of these Pauli strings, i.e.

$O_{k}=\sum_{r=1}^{4^{n_{O}}}\gamma_{r}^{(k)}{P_{r}}\,,$ (73)

where $\gamma_{r}^{(k)}\in\mathbb{R}$. We denote the Fourier coefficients
associated to ${P_{r}}$ as

$p^{(r)}_{\omega}:=\sum_{i,j\mathrm{\,s.t.\,}\lambda_{j}-\lambda_{i}=\omega}\alpha_{ij}\bra{j,0}U_{R}^{\dagger}{}{P_{r}}U_{R}\ket{i,0}\,.$
(74)

From Eq. (14) we observe that the Fourier coefficients $a_{\omega}^{(k)}$ are
linear in $O_{k}$. Thus, by substituting Eq. (73) into Eq. (14), we obtain

$a_{\omega}^{(k)}=\sum_{r=1}^{4^{n_{O}}}\gamma_{r}^{(k)}p^{(r)}_{\omega}\,.$
(75)

We now write this equation into matrix form again

$\bm{A}=\bm{P}\,\bm{\Gamma},$ (76)

where matrices $\bm{P}\in\mathbb{R}^{|\Omega|\crossproduct 4^{n_{O}}}$ and
$\bm{\Gamma}\in\mathbb{R}^{4^{n_{O}}\crossproduct M}$ are respectively defined
as

$\bm{P}:=\begin{pmatrix}p^{(1)}_{\omega_{1}}&p^{(2)}_{\omega_{1}}&\cdots&p^{(4^{n_{O}})}_{\omega_{1}}\\\
p^{(1)}_{\omega_{2}}&p^{(2)}_{\omega_{2}}&\cdots&p^{(4^{n_{O}})}_{\omega_{2}}\\\
\vdots&\vdots&\ddots&\vdots\\\
p^{(1)}_{\omega_{|\Omega|}}&p^{(2)}_{\omega_{|\Omega|}}&\cdots&p^{(4^{n_{O}})}_{\omega_{|\Omega|}}\end{pmatrix}\,$
(77)

and

$\bm{\Gamma}=\begin{pmatrix}\gamma_{1}^{(1)}&\gamma_{1}^{(2)}&\cdots&\gamma_{1}^{(M)}\\\
\gamma_{2}^{(1)}&\gamma_{2}^{(2)}&\cdots&\gamma_{2}^{(M)}\\\
\vdots&\vdots&\ddots&\vdots\\\
\gamma_{4^{n_{O}}}^{(1)}&\gamma_{4^{n_{O}}}^{(2)}&\cdots&\gamma_{4^{n_{O}}}^{(M)}\end{pmatrix}\,.$
(78)

Finally, from Eq. (71) and (76), we obtain the following upper bound of the
Fourier-expressivity in terms of the rank of matrix $\bm{A}$.

$\displaystyle\mathcal{F}\left[f_{\bm{\eta}}\right]$
$\displaystyle=\operatorname{rank}(\bm{A})$ (79)
$\displaystyle\leqslant\operatorname{min}\\{\operatorname{rank}(\bm{P}),\operatorname{rank}(\bm{\Gamma})\\}$
(80) $\displaystyle=\operatorname{min}\\{M,|\Omega|,4^{n_{O}}\\}\,.$ (81)

We remark that $|\Omega|<4^{n_{A}}$ since, by Eq. (13), the achievable
frequencies are differences of eigenvalues. For $n_{A}$ accessible qubits, the
encoding unitary has $2^{n_{A}}$ eigenvalues which provide at most $4^{n_{A}}$
distinct differences of the eigenvalues.

∎

##  Appendix B Statistics of Fourier Coefficients in QELMs

In this Appendix we analyse the statistics of the Fourier coefficients of a
QELM with a Haar random reservoir. We assume Pauli string observables on the
entire space (accessible + hidden), and recall that they satisfy the following
properties

$\Tr[O]=0\ \operatorname{and}\ \Tr[O^{2}]=2^{n}\;,$ (82)

where $O$ is one of the Pauli string from the observable set. We start by
computing mean, variance and covariance of the Fourier coefficients. Let us
formalize the results in the following Proposition.

######  Proposition 1 (Statistics of Fourier Coefficients).

For all summand of Fourier coefficients defined in Eq. (14), denoted as
$a_{uv}:=\alpha_{uv}\bra{u,0}U_{R}^{\dagger}{}OU_{R}\ket{v,0}$ where $O$ is a
Pauli string, we have

$\mathbb{E}_{U_{R}}[a_{uv}]=0\;,$ (83)

and

${\rm
Var}_{U_{R}}(|a_{uv}|)=\begin{dcases}|\alpha_{uv}|^{2}\dfrac{d}{d^{2}-1}&\quad\operatorname{for}\
u\neq v\\\ |\alpha_{uv}|^{2}\dfrac{1}{d+1}&\quad\operatorname{for}\ u=v\;,\\\
\end{dcases}$ (84)

where for both expectation values the reservoirs are sampled from Haar measure
and $d=2^{n}$ corresponds to the system size. Moreover, the covariance of
summands has the following property

${\rm
Cov}_{U_{R}}(a_{uv},a_{jk})=\begin{dcases}-\alpha_{uv}^{*}\alpha_{jk}\dfrac{1}{d^{2}-1}&\quad\operatorname{for}\
u=v\operatorname{and}j=k\\\ 0&\quad\operatorname{for\ all\ distinct}\
u,v,j,k\;.\end{dcases}$ (85)

###### Proof.

We start with the expectation value of any summand, by its linearity we obtain

$\displaystyle\mathbb{E}_{U_{R}}[a_{uv}]$
$\displaystyle=\alpha_{uv}\int_{\mathbb{U}(d)}d\mu(U)\bra{u,0}U_{R}^{\dagger}OU_{R}\ket{v,0}$
(86)
$\displaystyle=\alpha_{uv}\bra{u,0}\left(\int_{\mathbb{U}(d)}d\mu(U)U_{R}^{\dagger}OU_{R}\right)\ket{v,0}$
(87) $\displaystyle=\alpha_{uv}\bra{u,0}\frac{\Tr[O]}{d}\mathcal{I}\ket{v,0}$
(88) $\displaystyle=\alpha_{uv}\frac{\Tr[O]}{d}\delta_{uv}\,,$ (89)

where in the third line we use standard Haar integral identities [56]. Recall
that Pauli strings are trace less, and so

$\mathbb{E}_{U_{R}}[a_{uv}]=0\,.$ (90)

Next, we analyse the correlation among summands. By the properties of the Haar
integral, we obtain

$\displaystyle\mathbb{E}_{U_{R}}[a^{*}_{uv}a_{jk}]$
$\displaystyle=\alpha^{*}_{uv}\alpha_{jk}\bra{v,0}\otimes\bra{j,0}\int_{\mathbb{U}(d)}d\mu(U)U_{R}^{{\dagger}\otimes
2}O^{\otimes 2}U_{R}^{\otimes 2}\ket{u,0}\otimes\ket{k,0}$ (91)
$\displaystyle=\alpha^{*}_{uv}\alpha_{jk}\frac{1}{d^{2}-1}\left(\bra{v,0}\otimes\bra{j,0}\left(\left(\Tr^{2}[O]-\frac{1}{d}\Tr[O^{2}]\right)\mathcal{I}+\left(\Tr[O^{2}]-\frac{1}{d}\Tr^{2}[O])\right)\text{SWAP}\right)\ket{u,0}\otimes\ket{k,0}\right)$
(92)
$\displaystyle=\alpha^{*}_{uv}\alpha_{jk}\frac{1}{d^{2}-1}\left(\left(\Tr^{2}[O]-\frac{1}{d}\Tr[O^{2}]\right)\delta_{uv}\delta_{jk}+\left(\Tr[O^{2}]-\frac{1}{d}\Tr^{2}[O]\right)\delta_{uj}\delta_{vk}\right)\;,$
(93)

where SWAP is a swap operator between two copies.

Let $u=j$ and $v=k$, we obtain:

${\rm
Var}_{U_{R}}(|a_{uv}|)=\mathbb{E}_{U_{R}}\left[\absolutevalue{a_{uv}}^{2}\right]=\begin{dcases}|\alpha_{uv}|^{2}\frac{1}{d^{2}-1}\left(\Tr[O^{2}]-\frac{1}{d}\Tr^{2}[O]\right)&\quad\operatorname{for}\
u\neq v\\\
|\alpha_{uv}|^{2}\frac{1}{d(d+1)}\biggr{(}\Tr[O^{2}]+\Tr^{2}[O]\biggr{)}&\quad\operatorname{for}\
u=v\\\ \end{dcases}$ (94)

By the properties of Pauli strings $\Tr[O^{2}]=d$ and $\Tr[O]=0$, we obtain

${\rm
Var}_{U_{R}}(|a_{uv}|)=\begin{dcases}|\alpha_{uv}|^{2}\frac{d}{d^{2}-1}&\quad\operatorname{for}\
u\neq v\\\ |\alpha_{uv}|^{2}\frac{1}{d+1}&\quad\operatorname{for}\ u=v\\\
\end{dcases}$ (95)

Finally, by Eq. (91) we also obtain the desired properties of covariance of
the summands

${\rm
Cov}_{U_{R}}(a_{uv},a_{jk})=\begin{dcases}-\alpha_{uv}^{*}\alpha_{jk}\dfrac{1}{d^{2}-1}&\quad\operatorname{for}\
u=v\operatorname{and}j=k\\\ 0&\quad\operatorname{for\ distinct}\
u,v,j,k\end{dcases}$ (96)

∎

These results enable us to investigate the statistics of Fourier coefficients,
which are given by

$a_{\omega}=\sum_{u,v\text{ s.t. }\lambda_{u}-\lambda_{v}=\omega}a_{uv}\,.$
(97)

To further explore the effect of encoding strategies, we eliminate the bias
induced from the initial state by setting $\alpha_{uv}=1/d_{A}$ where
$d_{A}=2^{n_{A}}$, i.e. we assume that the initial state of accessible qubits
is $\rho_{0}=(\outerproduct{+}{+})^{\otimes{}n_{A}}$. As illustrated in Fig.
9, the analytical results on the variances for both encodings agree with the
simulations. Furthermore, Fig. 9 shows the mean absolute value of the
coefficients and standard deviations. We see that the spectrum for Haar random
reservoirs is rich and anti-concentrated, which allows room for a potential
quantum advantage, as discussed in Section III.4 and III.5. Finally, Fig. 10
shows the correlations between Fourier coefficients.

Figure 9: Left: Variance of Fourier coefficients for different encodings. We
plot the variance of the Fourier coefficients $a_{uv}$ over the Haar random
distribution with $n_{A}=4$ encoding qubits and $n_{H}=2$ hidden qubits for an
exponential encoding (up) and the Pauli re-uploading (down). The observable is
a $Z$ measurement on the first encoding qubit. Right: Mean absolute value of
Fourier coefficients. Here we plot the mean and standard deviation of the
Fourier components over 1000 Haar random reservoir unitaries. The simulation
is done with $n_{A}=4$ encoding qubits and $n_{H}=2$ hidden qubits and we
consider measuring the $Z$ Pauli observable. Figure 10: Covariance matrix of
Fourier coefficients. The absolute value of the covariance matrix of the
Fourier coefficients for the exponential encoding. The settings are the same
as Fig. 9.

We remark that, if $n_{H}=0$, then for the exponential encoding we have
$\mathbb{E}[|a_{0}|^{2}]=0$. This means that for any reservoir and any
observable, $a_{0}=0$. Thus the prediction after performing the linear
regression does not contain an input-independent offset value corresponding to
Fourier frequency $\omega=0$. In this case, it is necessary to include an
additional component $\eta_{0}$ during training.

##  Appendix C Practical consequences of exponential concentration on QELM

In this section, we investigate how exponential concentration of expectation
values over input data $\bm{x}$ and different instances of reservoir dynamics
deteriorates the QELM performance. In particular, we analytically show that,
when estimating these observables with a polynomial number of measurement
shots, the trained QELM becomes insensitive to input data which leads to data-
independent model predictions on unseen input data and in turn poor
generalization.

###  C.1 Refresher on some key concepts

####  C.1.1 Exponential concentration

We begin with recalling the definition of probabilistic and deterministic
exponential concentration discussed in the main text. We differentiate between
probabilistic and deterministic exponential concentration:

######  Definition 4 (Probabilistic exponential concentration).

Consider a quantity $Q(\bm{\theta})$ that depends on some variable
$\bm{\theta}$ which can be estimated from an $n$-qubit quantum computer as an
expectation value of some observable. $Q(\bm{\theta})$ is said to
probabilistically exponentially concentrate around a fixed value $\mu$ if

$\mathrm{Pr}_{\bm{\theta}}[|Q(\bm{\theta})-\mu|\geqslant\delta]\leqslant\dfrac{\beta}{\delta^{2}}\hskip
2.0pt,\;\;\beta\in\mathcal{O}(1/b^{n})\;,$ (98)

for some $b>1$. That is, the probability that $Q(\bm{\theta})$ deviates from
$\mu$ by a small amount $\delta$ is exponentially small for all $\bm{\theta}$.

We remark that to satisfy Eq. (98) for probabilistically exponential
concentration it is sufficient to show that the variance over the variables
${\rm Var}_{\bm{\theta}}[Q(\bm{\theta})]$ is exponentially small with the
number of qubits. This is due to Chebyshev’s inequality which states that

$\displaystyle{\rm
Pr}_{\bm{\theta}}\left[\left|Q(\bm{\theta})-\mathbb{E}_{\bm{\theta}}[Q(\bm{\theta})]\right|\geqslant\delta\right]\leqslant\dfrac{{\rm
Var}_{\bm{\theta}}[Q(\bm{\theta})]}{\delta^{2}}\;,$ (99)

where $\mathbb{E}_{\bm{\theta}}[Q(\bm{\theta})]$ is an average of
$Q(\bm{\theta})$ over $\bm{\theta}$. That is, we have
$\mu=\mathbb{E}_{\bm{\theta}}[Q(\bm{\theta})]$ and $\beta={\rm
Var}_{\bm{\theta}}[Q(\bm{\theta})]$ in the presence of exponential
concentration. We now recall the definition of deterministic exponential
concentration:

######  Definition 5 (Deterministic exponential concentration).

Consider a quantity $Q(\bm{\theta})$ that depends on some variable
$\bm{\theta}$ which can be estimated from an $n$-qubit quantum computer as an
expectation value of some observable. $Q(\bm{\theta})$ is said to
deterministically exponentially concentrate around a fixed value $\mu$ if its
distance from it is bounded by an exponentially small value

$|Q(\bm{\theta})-\mu|\leqslant\beta\hskip
2.0pt,\;\;\beta\in\mathcal{O}(1/b^{n})\;,$ (100)

for some $b>1$. That is, $Q(\bm{\theta})$ does not deviate from $\mu$ for more
than $\beta$ for all $\theta$.

In the context of QELM, we focus on two scenarios regarding the variables
$\bm{\theta}$. The first is when we have exponential concentration over the
input data i.e., $\bm{\theta}=\bm{x}$ induced by the data encoding part while
the other one is the concentration induced by reservoir dynamics i.e.,
$\bm{\theta}=U_{R}$.

####  C.1.2 Estimating QELM predictions in practice

We recall that a QELM model prediction with weights
$\bm{\eta}=[\eta_{1},...,\eta_{M}]^{T}$ is of the form

$\displaystyle f_{\bm{\eta}}(\bm{x})=\sum_{k=1}^{M}\eta_{k}\langle
O_{k}\rangle_{\bm{x}}\;,$ (101)

with

$\displaystyle\langle
O_{k}\rangle_{\bm{x},U_{R}}=\Tr[O_{k}U_{R}(\rho(\bm{x})\otimes\outerproduct{0}{0})U^{\dagger}_{R}]\;,$
(102)

where $O_{k}$ is an observable from a set $\\{O_{1},...,O_{M}\\}$, $U_{R}$ is
a reservoir unitary, $\rho(\bm{x})$ is an encoded quantum state associated
with an input $\bm{x}$ (or, simply an input-data state in the case of quantum
data) and $\outerproduct{0}{0}$ is the initial state in the hidden space.

In practice, the exact expectation values of these observables are
inaccessible. Instead, their statistical estimates are obtained with
measurement shots from quantum computers. More precisely, consider an
expectation value of an observable $O=O_{k}$ with respect to a quantum state
$\rho=U_{R}(\rho(\bm{x})\otimes\outerproduct{0}{0})U^{\dagger}_{R}$. The
observable can be decomposed as $O=\sum_{i}o_{i}|o_{i}\rangle\langle o_{i}|$
where $o_{i}$ and $|o_{i}\rangle$ are eigenvalues and associated eigenstates.
After $N$ measurements, we can estimate the expectation value using the
empirical mean of the outcome measurements as

$\displaystyle\widehat{O}=\frac{1}{N}\sum_{m=1}^{N}\lambda_{m}\;,$ (103)

where $\lambda_{m}$ is the $m^{\rm th}$ measurement outcome which can be
treated as a random variable with a probability $\Tr[\rho|o_{i}\rangle\langle
o_{i}|]$ to take a value $o_{i}$. Once we have gathered these statistical
estimates for all the observables, the model prediction can be computed by
classical post-processing of these estimates with the trainable weights.

####  C.1.3 Hypothesis testing

Here, we give some background overview of hypothesis testing which is an
essential tool for showing the effect of exponential concentration on QELM.
For more details about the topic, we refer the readers to Ref. [57].

######  Lemma 1.

Consider two probability distributions $\mathcal{P}$ and $\mathcal{Q}$ over
some finite outcomes $\mathcal{S}$. Suppose we are given a single sample $S$
drawn from either $\mathcal{P}$ or $\mathcal{Q}$ (with an equal probability).
We have the following hypotheses

  * •

Null hypothesis: $S$ is drawn from $\mathcal{P}$

  * •

Alternative hypothesis: $S$ is drawn from $\mathcal{Q}$

The success probability of making the right decision is

$\displaystyle{\rm Pr}[``{\rm
right\;decision}"]=\frac{1}{2}+\frac{\|\mathcal{P}-\mathcal{Q}\|_{1}}{4}\;$
(104)

where $\norm{\mathcal{P}-\mathcal{Q}}_{1}=\sum_{s\in\mathcal{S}}|p(s)-q(s)|$
is the distance between the two distributions expressed as a $1$-norm.

###### Proof.

Define $\mathcal{A}\subseteq\mathcal{S}$ as a subset where $p(s)>q(s)$. The
optimal decision we can make is to say that $s$ is drawn from $\mathcal{P}$ if
$s\in\mathcal{A}$, otherwise it is drawn from $\mathcal{Q}$. Then, the
probability of making the right decision is

$\displaystyle\Pr[``{\rm right\;decision}"]$
$\displaystyle=\Pr[S\in\mathcal{A}|S\sim\mathcal{P}]\Pr[S\sim\mathcal{P}]+\Pr[S\notin\mathcal{A}|S\sim\mathcal{Q}]\Pr[S\sim\mathcal{Q}]$
(105)
$\displaystyle=\dfrac{1}{2}\biggr{(}\Pr[S\in\mathcal{A}|S\sim\mathcal{P}]+\Pr[S\notin\mathcal{A}|S\sim\mathcal{Q}]\biggr{)}$
(106)
$\displaystyle=\dfrac{1}{2}\biggr{(}\sum_{s\in\mathcal{A}}p(s)+\sum_{s\notin\mathcal{A}}q(s)\biggr{)}\,\;,$
(107)

where we use $\Pr[S\sim\mathcal{P}]=\Pr[S\sim\mathcal{Q}]=\frac{1}{2}$ in the
second line.

Now consider the $1$-norm distance

$\displaystyle\norm{\mathcal{P}-\mathcal{Q}}_{1}=\sum_{s\in\mathcal{S}}|p(s)-q(s)|=\sum_{s\in\mathcal{A}}(p(s)-q(s))+\sum_{s\notin\mathcal{A}}(q(s)-p(s))\,.$
(108)

Finally, let us expand the following quantity (using the fact that the
probabilities sum to $1$)

$\displaystyle\dfrac{1}{2}(2+\norm{\mathcal{P}-\mathcal{Q}}_{1})$
$\displaystyle=\dfrac{1}{2}\biggr{(}\sum_{s\in\mathcal{S}}p(s)+\sum_{s\in\mathcal{S}}q(s)+\sum_{s\in\mathcal{A}}(p(s)-q(s))+\sum_{s\notin\mathcal{A}}(q(s)-p(s))\biggr{)}$
(109)
$\displaystyle=\sum_{s\in\mathcal{A}}p(s)+\sum_{s\notin\mathcal{A}}q(s)\,,$
(110)

which corresponds to the expression in Eq. (107), thus completing the proof. ∎

We now extend this hypothesis testing into a scenario where we obtain multiple
samples (instead of a single sample). In this case, the following lemma holds

######  Lemma 2.

Given a set of $N$ samples which is drawn from either $\mathcal{P}^{N}$ or
$\mathcal{Q}^{N}$ (with uniform probability), consider the two following
hypotheses

  * •

Null hypothesis: samples are drawn from $\mathcal{P}^{N}$

  * •

Alternative hypothesis: samples are drawn from $\mathcal{Q}^{N}$

The success probability of making a right decision is upper bounded by

$\displaystyle{\rm Pr}[``{\rm
right\;decision}"]\leqslant\frac{1}{2}+\frac{N\|\mathcal{P}-\mathcal{Q}\|_{1}}{4}\;.$
(111)

###### Proof.

We can consider the whole sample set as an effective single sample drawn from
either $\mathcal{P}^{N}$ or $\mathcal{Q}^{N}$. By invoking Lemma 1, we have

$\displaystyle{\rm Pr}[``{\rm right\;decision}"]$
$\displaystyle=\frac{1}{2}+\frac{\|\mathcal{P}^{N}-\mathcal{Q}^{N}\|_{1}}{4}\;$
(112)
$\displaystyle\leqslant\frac{1}{2}+\frac{N\|\mathcal{P}-\mathcal{Q}\|_{1}}{4}\;,$
(113)

where the last line is due to this useful identity
$\|\mathcal{P}^{N}-\mathcal{Q}^{N}\|_{1}\leqslant
N\|\mathcal{P}-\mathcal{Q}\|_{1}$. ∎

###  C.2 Statistical indistinguishability of QELM model predictions

We are now ready to tackle a practical consequence of exponential
concentration on QELM performance. In what follows, we provide analytical
results indicating that the QELM model predictions become independent of
unseen input data when data-dependent expectation values $\\{\langle
O_{k}\rangle_{\bm{x},U_{R}}\\}_{k=1}^{N}$ are estimated with the polynomial
number of measurement shots in the presence of exponential concentration.

To begin with, we assume that the expectation values exponentially concentrate
towards some fixed point either over the input data $\bm{x}$ or the reservoir
dynamics $U_{R}$. That is, we have

$\displaystyle\forall k\;,\;\;{\rm Var}_{\bm{\theta}}\left[\langle
O_{k}\rangle_{\bm{x},U_{R}}\right]\leqslant\beta\;,\;\;\beta\in\mathcal{O}(1/b^{n})$
(114)

where we have $\bm{\theta}=\bm{x}$ for exponential concentration over input
data and $\bm{\theta}=U_{R}$ for exponential concentration over a choice of
reservoirs 111We only consider the effect of probabilistically exponential
concentration as the same result can be directly applied to the deterministic
case.. We note that sources that lead to exponential concentration are
investigated in details in Appendix D. We further consider the scenario where
each observable in the set has half of the eigenvectors corresponding to $+1$
eigenvalue and the other half corresponding to $-1$ eigenvalue. In addition,
the fixed point $\mu$ is assumed to be zero that is

$\displaystyle\forall k\;,\;\;\mathbb{E}_{\bm{\theta}}\left[\langle
O_{k}\rangle_{\bm{x},U_{R}}\right]=0\;.$ (115)

An example of this is a set of Pauli operators.

In the presence of exponential concentration, when estimating a given data-
dependent expectation value from quantum computers, the probabilities of
obtaining $\pm 1$ outcomes are both exponentially close to $1/2$. To see this,
let us decompose the expectation value of $O_{k}$ as

$\displaystyle\langle
O_{k}\rangle_{\bm{x},U_{R}}=p_{+}^{(k)}(\bm{x},U_{R})-p_{-}^{(k)}(\bm{x},U_{R})\;,$
(116)

where $p_{\pm}^{(k)}(\bm{x},U_{R})$ are probabilities of $\pm 1$ outcomes.
Together with the normalization condition
$p_{+}^{(k)}(\bm{x},U_{R})+p_{-}^{(k)}(\bm{x},U_{R})=1$, we have

$\displaystyle\mathbb{E}_{\bm{\theta}}\left[p_{+}^{(k)}(\bm{x},U_{R})\right]=\mathbb{E}_{\bm{\theta}}\left[p_{-}^{(k)}(\bm{x},U_{R})\right]=\frac{1}{2}\;,$
(117)

for the means of the probabilities, as well as

$\displaystyle{\rm Var}_{\bm{\theta}}\left[\langle
O_{k}\rangle_{\bm{x},U_{R}}\right]$ $\displaystyle={\rm
Var}_{\bm{\theta}}\left[p_{+}^{(k)}(\bm{x},U_{R})\right]+{\rm
Var}_{\bm{\theta}}\left[p_{-}^{(k)}(\bm{x},U_{R})\right]-2{\rm
Cov}_{\bm{\theta}}\left[p_{+}^{(k)}(\bm{x},U_{R}),p_{-}^{(k)}(\bm{x},U_{R})\right]\;,$
(118) $\displaystyle 0$ $\displaystyle={\rm
Var}_{\bm{\theta}}\left[p_{+}^{(k)}(\bm{x},U_{R})\right]+{\rm
Var}_{\bm{\theta}}\left[p_{-}^{(k)}(\bm{x},U_{R})\right]+2{\rm
Cov}_{\bm{\theta}}\left[p_{+}^{(k)}(\bm{x},U_{R}),p_{-}^{(k)}(\bm{x},U_{R})\right]\;,$
(119)

which leads to

$\displaystyle{\rm
Var}_{\bm{\theta}}\left[p_{+}^{(k)}(\bm{x},U_{R})\right],{\rm
Var}_{\bm{\theta}}\left[p_{-}^{(k)}(\bm{x},U_{R})\right]\in\mathcal{O}(1/b^{n})\;,$
(120)

for the variances of the probabilities. Therefore, we have the exponential
concentration of outcome probabilities towards $1/2$.

We are now ready to state the main formal result which addresses the practical
consequence of exponential concentration.

######  Proposition 2.

Assume exponential concentration of data-dependent expectation values as
defined in Eq. (114). For a given input data $\bm{x}$ and a choice of
reservoirs $U_{R}$, define the probability distribution
$\mathcal{P}_{\bm{x},U_{R}}=\\{p_{+}^{(k)}(\bm{x},U_{R}),p_{-}^{(k)}(\bm{x},U_{R})\\}$.
In addition, define a fixed data-independent distribution
$\mathcal{P}_{0}=\\{1/2,1/2\\}$. Given a set of $N$ samples/outcomes
$\mathcal{M}$ (with $N\in\mathcal{O}(\operatorname{poly}(n))$) from either
$\mathcal{P}_{0}$ or $\mathcal{P}_{\bm{x},U_{R}}$ with an equal probability,
consider the following two hypotheses

  * •

Null hypothesis: $\mathcal{M}$ is drawn from $\mathcal{P}^{N}_{0}$

  * •

Alternative hypothesis: $\mathcal{M}$ is drawn from
$\mathcal{P}^{N}_{\bm{x},U_{R}}$

The success probability of making a right decision is exponentially close to a
random guessing such that

$\displaystyle{\rm Pr}[``{\rm right\;decision}"]$
$\displaystyle\leqslant\frac{1}{2}+\epsilon_{n}\;,\;\;\epsilon_{n}\in\mathcal{O}(1/b^{\prime
n})\;,$ (121)

for some $b^{\prime}>1$.

###### Proof.

The success probability can be upper bounded as

$\displaystyle{\rm Pr}[``{\rm right\;decision}"]$
$\displaystyle=\int_{0}^{1}{\rm Pr}\left(``{\rm
right\;decision}"\Big{|}\,p_{+}^{(k)}(\bm{x},U_{R})=p\right){\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp$ (122)
$\displaystyle\leqslant\int_{0}^{1}\left[\frac{1}{2}+\frac{N\|\mathcal{P}_{\bm{x},U_{R}}-\mathcal{P}_{0}\|_{1}}{4}\right]{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp$ (123)
$\displaystyle=\int_{0}^{1}\left[\frac{1}{2}+\frac{N\left(|p-1/2|+|(1-p)-1/2|\right)}{4}\right]{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp$ (124)
$\displaystyle=\frac{1}{2}+\frac{N}{2}\int_{0}^{1}\left|p-\frac{1}{2}\right|{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp\;,$ (125)

where the first equality is due to Bayes’ theorem which introduces the
conditional probability of making the right decision given that
$p_{+}^{(k)}(\bm{x},U_{R})=p$ and then integrating all possible values of
$p_{+}^{(k)}(\bm{x},U_{R})$ to obtain the marginal probability and then the
first inequality is by invoking Lemma 2.

The integral can be interpreted as how far apart is $p$ from $1/2$ on average
and intuitively this is exponentially small due to the exponential
concentration. For convenience, denote $\sigma=\sqrt{{\rm
Var}_{\bm{\theta}}\left[\langle O_{k}\rangle_{\bm{x},U_{R}}\right]}$ and
$\mu=1/2$. We can further bound the integral as

$\displaystyle\int_{0}^{1}\left|p-\frac{1}{2}\right|{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp$
$\displaystyle=\int_{0}^{1/2-\sqrt{\sigma}}\left|p-\frac{1}{2}\right|{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp$ (126)
$\displaystyle+\int_{1/2-\sqrt{\sigma}}^{1/2+\sqrt{\sigma}}\left|p-\frac{1}{2}\right|{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp$ (127)
$\displaystyle+\int_{1/2+\sqrt{\sigma}}^{1}\left|p-\frac{1}{2}\right|{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp$ (128) $\displaystyle\leqslant$
$\displaystyle\int_{1/2-\sqrt{\sigma}}^{1/2+\sqrt{\sigma}}\left|p-\frac{1}{2}\right|{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp+\sigma$ (129)
$\displaystyle\leqslant$
$\displaystyle\sqrt{\sigma}\int_{1/2-\sqrt{\sigma}}^{1/2+\sqrt{\sigma}}{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp+\sigma$ (130)
$\displaystyle\leqslant$ $\displaystyle\sqrt{\sigma}+\sigma$ (131)
$\displaystyle\in$ $\displaystyle\mathcal{O}\left(\frac{1}{b^{n/2}}\right)\;,$
(132)

where the first inequality is by invoking Chebyshev’s inequality i.e., ${\rm
Pr}[|p-\mu|>\delta]\leqslant\sigma^{2}/\delta^{2}$ with $\delta=\sqrt{\sigma}$
and $\mu=1/2$. The second inequality is by taking the maximum value of the
integral and the third inequality is by extending the integration range back
which leads to $\int_{0}^{1}{\rm
Pr}\left(p_{+}^{(k)}(\bm{x},U_{R})=p\right)dp=1$. The last line follows from
exponential concentration in Eq. (120). ∎

Proposition 2 implies that we cannot reliably distinguish between samples
obtained from quantum computers and those obtained from a fixed data-
independent distribution. In other words, estimates of expectation values have
no information about input data. Consequently, QELM model predictions in Eq.
(101) which are obtained by classically post-processing these data-independent
statistical estimates are clearly insensitive to input data.

##  Appendix D Sources of exponential concentration for QELM

###  D.1 Expressibility-induced concentration

First, recall the definition of the Schatten $p$-norm, whereby
$\norm{X}_{p}=(\Tr[|X|^{p}])^{1/p}$ and $|X|=\sqrt{X^{\dagger}X}$.
Particularly, $\norm{X}_{1}=\Tr[|X|]$ and $\norm{X}_{\infty}=\sigma_{max}(X)$
where $\sigma_{max}(X)$ is the maximal eigenvalue of $X$. Now, let us define
the diamond norm of an arbitrary superoperator $S_{A}$ acting on a Hilbert
space $\mathcal{H}_{A}$

$\norm{S_{A}}_{\diamond}:=\sup_{n}\sup_{X_{AB}}\dfrac{\norm{(S_{A}\otimes\mathcal{I}_{B}^{(n)})(\text{X}_{AB})}_{1}}{\norm{X_{AB}}_{1}}\,,$
(133)

where $X_{AB}\in\mathcal{L}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ and
$\mathcal{I}_{B}^{(n)}$ is the identity acting on the $n$-dimensional Hilbert
space $\mathcal{H}_{B}$.

Now, we start by recalling and proving the encoding Haar-expressivity-induced
theorem

######  Theorem 2 (Encoding Haar-expressivity-induced concentration).

Consider the expectation value of an arbitrary observable as defined in Eq.
(3). Then we have that

$\mathrm{Pr}_{\bm{x}}[|\expectationvalue{O}_{\bm{x}}-\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}]|\geqslant\delta]\leqslant\dfrac{G(\varepsilon_{\diamond}^{\bm{x}})}{\delta^{2}}\,,$
(134)

where

$G(\varepsilon_{\diamond})=\dfrac{\big{(}\Tr[\widetilde{O}_{\Lambda}]^{2}+\Tr[\widetilde{O}_{\Lambda}^{2}]\big{)}}{2^{n_{A}}(2^{n_{A}}+1)}+\varepsilon_{\diamond}^{\bm{x}}\norm{\Lambda(O)}_{\infty}\,.$
(135)

where
$\widetilde{O}_{\Lambda}=\Tr[(\mathcal{I}_{A}\otimes\outerproduct{0}{0})\Lambda(O)]$
with $\Lambda(\cdot)=U_{R}^{\dagger}(\cdot)U_{R}$.

Proof: Let us note that ${\rm
Var}_{s}[\expectationvalue{O}_{\bm{x}}]\leqslant\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}^{2}]$.
Hence

$\displaystyle\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}^{2}]$
$\displaystyle=\int_{\mathbb{U}_{\bm{x}}}\,dU(\bm{x})\Tr[\Lambda(O)\biggr{(}U(\bm{x})\rho_{0}U(\bm{x})^{\dagger}\otimes\outerproduct{0}{0}\biggr{)}]^{2}$
(136)
$\displaystyle=\int_{\mathbb{U}_{\bm{x}}}\,dU(\bm{x})\Tr[\Lambda(O)^{\otimes
2}\biggr{(}U(\bm{x})^{\otimes 2}\rho_{0}^{\otimes
2}(U(\bm{x})^{\dagger})^{\otimes 2}\otimes\outerproduct{0}{0}^{\otimes
2}\biggr{)}]$ (137) $\displaystyle=\Tr[\Lambda(O)^{\otimes
2}\biggr{(}\biggr{(}\mathcal{V}_{\text{Haar}}(\rho_{0}^{\otimes
2})-\mathcal{A}_{\mathbb{U}_{s}}(\rho_{0}^{\otimes
2})\biggr{)}\otimes\outerproduct{0}{0}^{\otimes 2}\biggr{)}]$ (138)
$\displaystyle\leqslant\Tr[\Lambda(O)^{\otimes
2}\biggr{(}\mathcal{V}_{\text{Haar}}(\rho_{0}^{\otimes
2})\otimes\outerproduct{0}{0}^{\otimes 2}\biggr{)}]+\norm{\Lambda(O)^{\otimes
2}\biggr{(}\mathcal{A}_{\mathbb{U}_{s}}(\rho^{\otimes
2})\otimes\outerproduct{0}{0}\biggr{)}}_{1}$ (139)
$\displaystyle\leqslant\Tr[\Lambda(O)^{\otimes
2}\biggr{(}\mathcal{V}_{\text{Haar}}(\rho_{0}^{\otimes
2})\otimes\outerproduct{0}{0}^{\otimes
2}\biggr{)}]+\norm{\mathcal{A}(\rho_{0}^{\otimes
2})}_{1}\norm{\Lambda(O)}_{\infty}^{2}$ (140)
$\displaystyle\leqslant\Tr[\Lambda(O)^{\otimes
2}\biggr{(}\mathcal{V}_{\text{Haar}}(\rho_{0}^{\otimes
2})\otimes\outerproduct{0}{0}^{\otimes
2}\biggr{)}]+\varepsilon_{\diamond}^{\bm{x}}\norm{\Lambda(O)}_{\infty}^{2}\,,$
(141)

where in the second equality we utilized the basic identity
$\Tr[A]^{2}=\Tr[A^{\otimes 2}]$, in the third equality we inserted the
definition of $\mathcal{A}_{\mathbb{U}_{\bm{x}}}(\rho_{0}^{\otimes 2})$, in
the first inequality we took the absolute value and applied the triangle
inequality, in the second inequality we applied Hölder’s inequality to the
second term and the last inequality was achieved by noting that
$\norm{\mathcal{E}(X)}_{1}\leqslant\norm{\mathcal{E}}_{\diamond}\norm{X}_{1}$
Let us now compute explicitly the first term

$\displaystyle\Tr[\Lambda(O)^{\otimes
2}\biggr{(}\mathcal{V}_{\text{Haar}}(\rho_{0}^{\otimes
2})\otimes\outerproduct{0}{0}^{\otimes 2}\biggr{)}]$
$\displaystyle=\int_{\mathcal{U}(d)}\,d\mu(U)\Tr[\Lambda(O)^{\otimes
2}\biggr{(}U^{\otimes 2}\rho_{0}^{\otimes 2}(U^{\dagger})^{\otimes
2}\otimes\outerproduct{0}{0}^{\otimes 2}\biggr{)}]$ (142)
$\displaystyle=\Tr[\Lambda(O)^{\otimes
2}\biggr{(}\int_{\mathcal{U}(d)}\,d\mu(U)U^{\otimes 2}\rho_{0}^{\otimes
2}(U^{\dagger})^{\otimes 2}\otimes\outerproduct{0}{0}^{\otimes 2}\biggr{)}]$
(143) $\displaystyle=\dfrac{1}{2^{n_{A}}(2^{n_{A}}+1)}\Tr[\Lambda(O)^{\otimes
2}\biggr{(}\biggr{(}\mathcal{I}^{\otimes
2}+\mathrm{SWAP}\biggr{)}\otimes\outerproduct{0}{0}^{\otimes 2}\biggr{)}]$
(144)
$\displaystyle=\dfrac{\Tr[\widetilde{O}_{\Lambda}]^{2}+\Tr[\widetilde{O}_{\Lambda}^{2}]}{2^{n_{A}}(2^{n_{A}}+1)}\,,$
(145)

where the second equality is obtained by exchanging the trace and the Haar
integral, and in the third equality we explicitly compute the second moment of
the Haar integral. In the last equality we instead regroup the terms to
recognise $\widetilde{O}_{\Lambda}$ and apply the identity
$\Tr[\widetilde{O}_{\Lambda}^{\otimes
2}\mathrm{SWAP}]=\Tr[\widetilde{O}_{\Lambda}^{2}]$ where $\mathrm{SWAP}$ is
the swap operator in the accessible space. Finally, we get

${\rm
Var}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}]\leqslant\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}^{2}]\leqslant\dfrac{\Tr[\widetilde{O}_{\Lambda}]^{2}+\Tr[\widetilde{O}_{\Lambda}^{2}]}{2^{n_{A}}(2^{n_{A}}+1)}+\varepsilon_{\diamond}^{\bm{x}}\lVert\Lambda(O)\rVert_{\infty}^{2}.$
(146)

By applying Chebyschev’s inequality, we complete the proof. $\square$

######  Corollary 1.

Suppose $O$ is a Pauli observable, i.e. $O\in\\{X,Y,Z,I\\}^{\otimes
n}/\\{I^{\otimes n}\\}$ where $\\{X,Y,Z\\}$ are the single-qubit Pauli
observables. Suppose furthermore that
$\mathcal{E}_{R}(\cdot)=U_{R}(\cdot)U_{R}^{{}^{\dagger}}$. Then we have

$G(\varepsilon_{\diamond})=\dfrac{1}{2^{n_{A}}+1}+\varepsilon_{\diamond}\,.$
(147)

Therefore, if the conditions of Corollary 1 are fulfilled and the encoding
ansatz is expressible enough, so that $\varepsilon_{\diamond}^{\bm{x}}\simeq
0$, then the expectation value will exponentially concentrate toward a fixed
value

$\mathrm{Pr}_{\bm{x}}[|\expectationvalue{O}_{\bm{x}}-\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}]|\geqslant\delta]\in\mathcal{O}\biggr{(}\dfrac{1}{2^{n}}\biggr{)}\,.$
(148)

We now turn to the reservoir unitary-induced exponential concentration.

######  Theorem 3 (Reservoir Haar-expressivity-induced concentration).

Consider a reservoir evolution $U_{R}\in\mathbb{U}_{R}$. Consider the
expectation value of an arbitrary Hermitian observable as defined in Eq. (3).
Then we have that

$\mathrm{Pr}_{U_{R}}[|\expectationvalue{O}_{\bm{x}}-\mathbb{E}_{R}[\expectationvalue{O}_{\bm{x}}]|\geqslant\delta]\leqslant\dfrac{G(\varepsilon_{\diamond}^{R})}{\delta^{2}}\,,$
(149)

where

$G(\varepsilon_{\diamond})=\dfrac{\big{(}\Tr[O]^{2}+\Tr[O^{2}]\big{)}}{2^{n}(2^{n}+1)}+\varepsilon_{\diamond}^{R}\norm{O}_{\infty}\,.$
(150)

Proof: The proof is equivalent to the encoding Haar-expressivity-induced
concentration. $\square$

Notice that, if $U_{R}$ is drawn from a $2$-design, the average of the
expectation value over $\mathbb{U}_{R}$ is independent of the input $\bm{x}$

$\displaystyle\mathbb{E}_{U_{R}}[\expectationvalue{O}_{\bm{x}}]$
$\displaystyle=\int_{\mathbb{U}_{R}}\,dU_{R}\Tr[U_{R}\rho(\bm{x})U_{R}^{\dagger}O]=\int_{\mathcal{U}(d)}\,d\mu(U)\Tr[U\rho(\bm{x})U^{\dagger}O]$
(151)
$\displaystyle=\dfrac{\Tr[\rho(\bm{x})]\Tr[O]}{d}=\dfrac{\Tr[O]}{d}=\mu\,.$
(152)

Crucially, Theorem 3 tells us that if $\mathbb{U}_{R}$ forms a $2$-design, or
equivalently if $U_{R}$ is a scrambling unitary, the probability for the
expectation value to differ from $\mu$ (which is independent of the input) by
more than $\delta$ is exponentially small in the number of qubits. Hence, we
will need exponentially many shots to recognise the observable from $\mu$.

###  D.2 Entanglement-induced concentration

######  Theorem 4 (Entanglement-induced concentration).

Suppose an observable that acts non-trivially on a subspace $\mathcal{H}_{k}$
of the entire Hilbert space $\mathcal{H}$, so that
$O=O_{k}\otimes\mathcal{I}_{\bar{k}}$. Then, the concentration of its
expectation value around a fixed point will be bounded by

$\left|\expectationvalue{O}_{\bm{x}}-\dfrac{\Tr[O]}{2^{n}}\right|\leqslant\norm{O_{k}}_{\infty}\sqrt{2\ln{2}}S\biggr{(}\widetilde{\rho}_{k}(\bm{x})\biggr{\lVert}\dfrac{\mathcal{I}_{k}}{2^{k}}\biggr{)}^{1/2}\,,$
(153)

where $S(\cdot\lVert\cdot)$ is the relative entropy and
$\widetilde{\rho}_{k}(\bm{x})=\Tr_{\bar{k}}(\widetilde{\rho}(\bm{x}))$
represents the final reduced state on subspace $\mathcal{H}_{k}$.

Proof: Note that

$\displaystyle\left|\expectationvalue{O}_{\bm{x}}-\dfrac{\Tr[O]}{2^{n}}\right|$
$\displaystyle=\left|\Tr[O\biggr{(}\widetilde{\rho}(\bm{x})-\dfrac{\mathcal{I}}{2^{n}}\biggr{)}]\right|$
(154)
$\displaystyle=\left|\Tr_{k}\biggr{[}O_{k}\biggr{(}\widetilde{\rho}_{k}(\bm{x})-\dfrac{\mathcal{I}_{k}}{2^{k}}\biggr{)}\biggr{]}\right|$
(155)
$\displaystyle\leqslant\norm{O_{k}\biggr{(}\widetilde{\rho}_{k}(\bm{x})-\dfrac{\mathcal{I}_{k}}{2^{k}}\biggr{)}}_{1}$
(156)
$\displaystyle\leqslant\norm{O_{k}}_{\infty}\norm{\widetilde{\rho}_{k}(\bm{x})-\dfrac{\mathcal{I}_{k}}{2^{k}}}_{1}$
(157)
$\displaystyle\leqslant\norm{O_{k}}_{\infty}\sqrt{2\ln{2}}S\biggr{(}\widetilde{\rho}_{k}(\bm{x})\biggr{\lVert}\dfrac{\mathcal{I}_{k}}{2^{k}}\biggr{)}^{1/2}\,,$
(158)

where the first equality is given by using the definition of
$\expectationvalue{O}_{\bm{x}}$, the second equality by applying the
definition of the observable as stated in Theorem 4, the first inequality is
obtained by applying the triangle inequality, the second inequality by
applying Hölder’s inequality and for the final inequality we used Pinsker’s
inequality. $\square$

###  D.3 Global measurement-induced concentration

######  Theorem 5 (Global measurement-induced concentration).

Suppose an observable $O=\outerproduct{m}{m}$, i.e. a projective measurement
onto state $\ket{m}=\ket{m_{1}\dots m_{n}}$. Consider an initial separable
state $\rho_{0}=\bigotimes_{k=1}^{n}\rho_{0}^{(k)}$. Suppose that the encoding
unitary creates no entanglement, so that:
$U(\bm{x})=\bigotimes_{k=1}^{n_{A}}U_{k}(x_{k})$ where $x_{k}$ is an input
component of $\bm{x}$, and all are uniformly sampled from $[-\pi,\pi]$.
Similarly, assume furthermore that the reservoir has the form
$U_{R}=\bigotimes_{k=1}^{n}V_{k}$. Then we have

$\mathrm{Pr}_{\bm{x}}[|\expectationvalue{O}_{\bm{x}}-\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}]\geqslant\delta]\leqslant\dfrac{\alpha\prod_{k=1}^{n_{A}}G_{k}(\varepsilon_{x_{k}})}{\delta^{2}}\,,$
(159)

where
$\varepsilon_{x_{k}}=\norm{\mathcal{A}_{\mathbb{U}_{x_{k}}}\biggr{(}\rho_{0}^{(k)^{\otimes
2}}\biggr{)}}_{1}$ is the Haar-expressivity measure of the local unitary
$U_{k}(x_{k})$ and
$\alpha=\prod_{j=n_{A}+1}^{n}|\innerproduct{0|V_{j}}{m_{j}}|^{2}$. The term
$G_{k}(\varepsilon_{x_{k}})$ is given by

$G_{k}(\varepsilon_{x_{k}})=\biggr{(}\frac{1}{3}+\varepsilon_{x_{k}}\biggr{(}\varepsilon_{x_{k}}+\sqrt{\frac{4}{3}}\biggr{)}\biggr{)}^{1/2}\,.$
(160)

Proof: Let us start by noting that:

$\displaystyle\mathbb{E}_{\bm{x}}[\expectationvalue{O}_{\bm{x}}^{2}]$
$\displaystyle=\int_{\mathbb{U}_{s}}\,dU(\bm{x})\Tr[\widetilde{\rho}(\bm{x})\outerproduct{m}{m}]^{2}$
(161)
$\displaystyle=\int_{\mathbb{U}_{\bm{x}}}\,dU(\bm{x})\Tr[(\rho(\bm{x})\otimes\outerproduct{0}{0})\outerproduct{m^{\prime}}{m^{\prime}}]^{2}$
(162)
$\displaystyle=\int_{\mathbb{U}_{\bm{x}}}\,dU(\bm{x})\Tr[(\rho(\bm{x})^{\otimes
2}\otimes\outerproduct{0}{0}^{\otimes
2})\outerproduct{m^{\prime}}{m^{\prime}}^{\otimes 2}],$ (163)

where the first equality is obtained by using the definition of the
observable, the second inequality is achieved by defining
$\ket{m^{\prime}}=\bigotimes_{k=1}^{n}\ket{m_{k}^{\prime}}=V_{R}^{\dagger}\ket{m}=\bigotimes_{k=1}^{n}V_{k}^{\dagger}\ket{m_{k}}$
and the third equality is obtained by using the identity
$\Tr[A]^{2}=\Tr[A^{\otimes 2}]$. Then

$\displaystyle\int_{\mathbb{U}_{\bm{x}}}\,dU(\bm{x})\Tr[\rho(\bm{x})^{\otimes
2}\outerproduct{m^{\prime}}{m^{\prime}}^{\otimes 2}]$
$\displaystyle=\int_{\mathbb{U}_{\bm{x}}}\,dU(\bm{x})\Tr[U(\bm{x})^{\otimes
2}\rho_{0}^{\otimes 2}(U^{\dagger}(\bm{x}))^{\otimes
2}\outerproduct{m^{\prime}}{m^{\prime}}^{\otimes 2}]$ (164)
$\displaystyle=\prod_{k=1}^{n_{A}}\Tr[\int_{\mathbb{U}_{x_{k}}}\,dU_{k}(x_{k})U_{k}(x_{k})^{\otimes
2}\big{(}\rho_{0}^{(k)}\big{)}^{\otimes 2}(U_{k}^{\dagger}(x_{k}))^{\otimes
2}\outerproduct{m_{k}^{\prime}}{m_{k}^{\prime}}^{\otimes
2}]\prod_{j=n_{A}+1}^{n}|\innerproduct{0}{m^{\prime}_{j}}|^{2}$ (165)
$\displaystyle=\alpha\prod_{k=1}^{n_{A}}\Tr[\biggr{(}\mathcal{V}_{\text{Haar}}\biggr{(}\big{(}\rho_{0}^{(k)}\big{)}^{\otimes
2}\biggr{)}-\mathcal{A}_{\mathbb{U}_{x_{k}}}\biggr{(}\big{(}\rho_{0}^{(k)}\big{)}^{\otimes
2}\biggr{)}\biggr{)}\outerproduct{m_{k}^{\prime}}{m_{k}^{\prime}}^{\otimes
2}]$ (166)
$\displaystyle\leqslant\alpha\prod_{k=1}^{n_{A}}\norm{\biggr{(}\mathcal{V}_{\text{Haar}}^{(k)}-\mathcal{A}_{\mathbb{U}_{x_{k}}}^{(k)}\biggr{)}\outerproduct{m_{k}^{\prime}}{m_{k}^{\prime}}^{\otimes
2}}_{1}$ (167)
$\displaystyle\leqslant\alpha\prod_{k=1}^{n_{A}}\norm{\mathcal{V}_{\text{Haar}}^{(k)}-\mathcal{A}_{\mathbb{U}_{x_{k}}}^{(k)}}_{2}\norm{\outerproduct{m_{k}^{\prime}}{m_{k}^{\prime}}^{\otimes
2}}_{2}$ (168)
$\displaystyle=\alpha\prod_{k=1}^{n_{A}}\biggr{(}\Tr[\biggr{(}\mathcal{V}_{\text{Haar}}^{(k)}\biggr{)}^{2}]+\Tr[\mathcal{A}_{\mathbb{U}_{x_{k}}}^{(k)}\biggr{(}\mathcal{A}_{\mathbb{U}_{x_{k}}}^{(k)}-2\mathcal{V}_{\text{Haar}}^{(k)}\biggr{)}]\biggr{)}^{1/2}$
(169)
$\displaystyle\leqslant\alpha\prod_{k=1}^{n_{A}}\biggr{(}\dfrac{1}{3}+\norm{\mathcal{A}_{\mathbb{U}_{x_{k}}}^{(k)}}_{2}\norm{\mathcal{A}_{\mathbb{U}_{x_{k}}}^{(k)}-2\mathcal{V}_{\text{Haar}}^{(k)}}_{2}\biggr{)}^{1/2}$
(170)
$\displaystyle\leqslant\alpha\prod_{k=1}^{n_{A}}\biggr{(}\dfrac{1}{3}+\varepsilon_{\mathbb{U}_{x_{k}}}\biggr{(}\varepsilon_{\mathbb{U}_{x_{k}}}+\sqrt{\dfrac{4}{3}}\biggr{)}\biggr{)}^{1/2}\,,$
(171)

where the first equality is straightforward by using the definition of the
embedded state, the second equality is obtained by applying the separability
of the encoding unitary and the initial state, as well as the projective
$\ket{m^{\prime}}$. The third equality is given by introducing the Haar-
expressivity superoperator defined in Eq. (43) for each single qubit and
defining $\alpha=\prod_{j=n_{A}+1}^{n}|\innerproduct{0}{m_{j}^{\prime}}|^{2}$.
In Eq. (167) we define
$\mathcal{V}_{\text{Haar}}^{(k)}:=\mathcal{V}_{\text{Haar}}\big{(}\big{(}\rho_{0}^{(k)}\big{)}^{\otimes
2}\big{)}$ and
$\mathcal{A}_{\mathbb{U}_{x_{k}}}^{(k)}:=\mathcal{A}_{\mathbb{U}_{x_{k}}}\big{(}\big{(}\rho_{0}^{(k)}\big{)}^{\otimes
2}\big{)}$ to ease the notation, and we apply the triangle inequality. In Eq.