# Encoding-dependent generalization bounds for
parametrized quantum circuits

Matthias C. Caro  Department of Mathematics, Technical University of Munich,
85748 Garching, Germany  Munich Center for Quantum Science and Technology
(MCQST), 80799 Munich, Germany  Elies Gil-Fuster  Dahlem Center for Complex
Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany  Fraunhofer
Heinrich Hertz Institute, 10587 Berlin, Germany  Johannes Jakob Meyer  Dahlem
Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin,
Germany  Jens Eisert  Dahlem Center for Complex Quantum Systems, Freie
Universität Berlin, 14195 Berlin, Germany  Fraunhofer Heinrich Hertz
Institute, 10587 Berlin, Germany  Helmholtz-Zentrum Berlin für Materialien und
Energie, 14109 Berlin, Germany  Ryan Sweke  Dahlem Center for Complex Quantum
Systems, Freie Universität Berlin, 14195 Berlin, Germany

(2021-10-28)

###### Abstract

A large body of recent work has begun to explore the potential of parametrized
quantum circuits (PQCs) as machine learning models, within the framework of
hybrid quantum-classical optimization. In particular, theoretical guarantees
on the out-of-sample performance of such models, in terms of generalization
bounds, have emerged. However, none of these generalization bounds depend
explicitly on how the classical input data is encoded into the PQC. We derive
generalization bounds for PQC-based models that depend explicitly on the
strategy used for data-encoding. These imply bounds on the performance of
trained PQC-based models on unseen data. Moreover, our results facilitate the
selection of optimal data-encoding strategies via structural risk
minimization, a mathematically rigorous framework for model selection. We
obtain our generalization bounds by bounding the complexity of PQC-based
models as measured by the Rademacher complexity and the metric entropy, two
complexity measures from statistical learning theory. To achieve this, we rely
on a representation of PQC-based models via trigonometric functions. Our
generalization bounds emphasize the importance of well-considered data-
encoding strategies for PQC-based models.

##  1 Introduction

Recent years have witnessed a surge of interest in the question of whether and
how quantum computers can meaningfully address computational problems in
machine learning [1, 2]. This development has been largely driven by two
factors. On the one hand, there is evidence that some quantum machine learning
algorithms may lead to an increased performance over classical algorithms for
the analysis of classical data with respect to important figures of merit [3,
4, 5, 6, 7]. On the other hand, the increasing availability of quantum
computational devices provides significant stimulus. While these “noisy
intermediate-scale quantum” (NISQ) devices are still a far cry from full-scale
fault-tolerant quantum computers, there exists growing evidence that they may
be able to out-perform classical computers on some highly-tailored tasks [8].
Given the inherent limitations of NISQ devices, most current approaches to
near-term quantum-enhanced machine learning fall under the umbrella of hybrid
quantum-classical algorithms [9]. Of particular prominence are variational
quantum algorithms in which a parametrized quantum circuit (PQC) is used to
define a machine learning model which is then updated via a classical
optimizer [10, 11, 12].

There is a wealth of architectural choices for PQC-based machine learning
models. These include the width and depth of the quantum circuit, the precise
layout and structure of trainable gates, as well as the mechanism via which
classical data is encoded into the quantum circuit. The flexibility in design
choices for PQCs is often only perceived strongly in terms of the structure
and layout of the trainable gates [13, 14]. However, when using a PQC to
define a machine learning model for classical data, the data-encoding strategy
becomes a necessary architectural design choice, which has received comparably
little attention. Despite this, it has recently been shown that the data-
encoding strategy is directly related to the expressive power of PQC-based
models [15, 16, 17]. In this work, we further the study of data-encoding
strategies for PQC-based supervised learning models by investigating the
effect of data-encoding strategies on generalization performance.

More specifically, we consider the following fundamental question: Given a
PQC-based model which has been trained on a specific data set, can we place
any guarantees on its expected out-of-sample performance, i.e., its expected
accuracy on new data, drawn from the same distribution as the training set?
This question is motivated by the key insight that one should not choose the
model or architecture which performs best on the available training data, but
rather the model for which one expects the best out-of-sample performance.
Typically, one refers to the difference between the accuracy of a model on a
given training set and its expected out-of-sample accuracy as the
generalization gap. We call a (probabilistic) upper bound on this
generalization gap a generalization bound. Historically, techniques for both
proving generalization bounds and for using generalization bounds for
principled model selection have been developed under the umbrella of
statistical learning theory [18, 19, 20].

We start by presenting a selection of central notions in statistical learning
theory. Of particular interest is the relation between generalization bounds
and complexity measures of different types. Indeed, due to a large body of
existing literature, bounding the generalization gap of a learning model
typically reduces to bounding some quantifiable property of the hypothesis
class used for learning. There are many examples of such complexity measures
(also known as _capacity metrics_ or just _expressivity measures_), and based
on their specifics they are used for different learning models, either quantum
or not. In this work, we employ generalization bounds based on the Rademacher
complexity and the metric entropy. However, we want to mention that there are
also other important approaches to generalization not taken here, such as
stability [21], compression [22], or the PAC-Bayesian framework [23].

Given the fundamental role of generalization bounds, there has recently been a
strong and steady stream of works contributing to the derivation of
generalization bounds for PQC-based models [24, 25, 26, 27, 28, 29, 30, 31,
32]. However, as discussed in detail in Section 4, these prior works all
differ from our results in a variety of ways. Firstly, they considered only
“encoding-first” PQC architectures, in which the PQC-based models are assumed
to consist of an initial data-encoding block, mapping a classical input to a
data-dependent quantum state, followed by a circuit consisting only of fixed
and trainable gates. In contrast, we consider PQC-based models incorporating
data re-uploading [17], in which trainable circuit blocks are interleaved with
data-encoding circuit blocks. This is particularly relevant given the results
of Refs. [33, 15], which have illuminated the significant effects of data re-
uploading on the expressive power of PQC-based models.

Additionally, our work is the first to provide a generalization bound from
which it is immediately clear how altering the data-encoding strategy
influences the generalization performance of the model. This is possible
because our bound depends _explicitly_ on architectural hyper-parameters
associated with the data-encoding strategy. This sets our results apart from
prior art where the data-encoding figured only _implicitly_ , if at all. We
discuss this difference between implicitly and explicitly encoding-dependent
generalization bounds more concretely in Section 4.

In order to obtain our generalization bounds, we rely strongly on a
representation of PQC-based models via generalized trigonometric polynomials
(GTPs), which has been previously derived in Refs. [33, 15]. In particular, we
exploit the fact that the data-encoding strategy of the PQC-based model
directly determines the frequency spectrum of the corresponding GTPs. As such,
the number of accessible frequencies in the GTP representation provides a
natural measure of the complexity of a particular data-encoding strategy.
Given this, we first derive generalization bounds for GTPs, which exhibit a
dependence on the square root of the number of accessible frequencies. We then
proceed to determine, for different data-encoding strategies, upper bounds on
the number of accessible frequencies in the GTP representation. We use these
results to identify a variety of natural data-encoding strategies for which
the number of accessible frequencies, and therefore the associated
generalization bounds, scale polynomially with the number of data-encoding
gates. While one cannot use generalization bounds alone to recommend an
optimal data-encoding strategy, we discuss how these generalization bounds can
be combined with empirical risk estimates, via structural risk minimization,
to facilitate the selection of an optimal data-encoding strategy for a given
problem.

###  1.1 Structure of this work

Figure 1: A flowchart of the argument presented in this work.

This work is structured as follows: Section 2 gives a pedagogical introduction
to statistical learning theory, explains the importance of generalization
bounds, and discusses the structural risk minimization principle. After
establishing these concepts, we formulate the main questions addressed in this
work. In Section 3, we begin by introducing the PQC-based learning models used
in this work. We then present a detailed discussion of the approach of Ref.
[33], which demonstrates how the functions implemented by a PQC-based model
can be represented by generalized trigonometric polynomials. In particular, we
emphasize how the data encoding strategy of the PQC-based model translates to
the accessible frequencies of the generalized trigonometric polynomials.
Section 4 then provides a detailed review of prior work on generalization in
quantum machine learning. In Section 5, we establish generalization bounds for
classes of generalized trigonometric polynomials in terms of the number of
accessible frequencies. We present one approach via the Rademacher complexity
(Section 5.1) and another via covering numbers (Section 5.2). Section 6 then
expands upon Section 3 by deriving upper bounds on the number of accessible
frequencies, in the generalized trigonometric polynomial representation of the
PQC-based models associated with different data-encoding strategies. This
analysis allows us to use the results from Section 5 to state explicitly
encoding-dependent generalization bounds for PQC-based models, and to compare
different encoding strategies from a generalization perspective. We discuss
the implications of our results in Section 7. In particular, we emphasize how
our results are complementary to many prior works, but also describe how the
different approaches can be combined. Additionally, we sketch some directions
for future research. Section 8 contains a short summary of our work. The
logical flow of this manuscript is visualized in Figure 1.

##  2 Motivation: Generalization bounds, sample complexities and model
selection

To motivate the content of this work and to define the setting, we start with
a brief and select introduction to the framework of _statistical learning
theory_. Interested readers are referred to Refs. [20] and [34] for a more
detailed presentation. Within this framework, any supervised learning problem
is defined by a _domain_ $\mathcal{X}$, a _co-domain_ $\mathcal{Y}$, a
_probability distribution_ $P$ over $\mathcal{X}\times\mathcal{Y}$ and a _loss
function_ $\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}$. We assume
that $\mathcal{X},\mathcal{Y}$ and $\ell$ are known, while $P$ is unknown. We
will denote the set of all functions from $\mathcal{X}$ to $\mathcal{Y}$ as
$\mathcal{Y}^{\mathcal{X}}$. To gain intuition, it is useful to think of the
situation in which there exists a deterministic rule for assigning predictions
to domain elements. We can model this in the framework outlined above with an
unknown target function $f\in\mathcal{Y}^{\mathcal{X}}$, as well as some
unknown probability distribution $P_{\mathcal{X}}$ over $\mathcal{X}$, such
that samples from $P$ are obtained by first drawing a domain element
$\boldsymbol{x}\in\mathcal{X}$ from $P_{\mathcal{X}}$, and then outputting the
tuple $(\boldsymbol{x},f(\boldsymbol{x}))$, i.e.

$\displaystyle
P(\boldsymbol{x},y)=\begin{cases}P_{\mathcal{X}}(\boldsymbol{x})\quad&\text{
if }y=f(\boldsymbol{x}),\\\ 0&\text{ if }y\neq f(\boldsymbol{x}).\end{cases}$
(1)

In general, however, it may be the case that there exists $y_{1}\neq y_{2}$
for which both $P(\boldsymbol{x},y_{1})>0$ and $P(\boldsymbol{x},y_{2})>0$,
i.e., that the underlying process for labeling data points is not
deterministic.

Additionally, we are given a training data set

$S=\\{(\boldsymbol{x}_{i},y_{i})\sim P\,|\,i\in\\{1,\ldots,m\\}\\}$ (2)

of $m$ tuples drawn independently from (the unknown distribution) $P$, and our
goal is to design a _learning algorithm_ $\mathcal{A}$ which, given $S$ as
input, outputs a hypothesis $h\in\mathcal{Y}^{\mathcal{X}}$ that achieves a
sufficiently small risk

$R(h)=\int_{\mathcal{X}\times\mathcal{Y}}\ell(y,h(\boldsymbol{x}))\leavevmode\nobreak\
\mathrm{d}P(\boldsymbol{x},y).$ (3)

Informally, we often refer to the risk $R(h)$ as characterizing the out-of-
sample performance of the hypothesis $h$, as it is this quantity which tells
us how well we can expect the hypothesis $h$ to perform on (possibly
previously unseen) future data drawn from $P$. It is critical to note,
however, that as the underlying probability distribution $P$ is unknown, given
a hypothesis $h\in\mathcal{Y}^{\mathcal{X}}$, one cannot directly evaluate
$R(h)$. In light of this, a natural alternative is to evaluate the empirical
risk of $h$ with respect to $S$, which is defined as the average loss over the
training samples

$\hat{R}_{S}(h)=\frac{1}{|S|}\sum_{(\boldsymbol{x}_{i},y_{i})\in
S}\ell(y_{i},h(\boldsymbol{x}_{i})).$ (4)

In contrast to the risk $R(h)$, the empirical risk $\hat{R}(h)$ characterizes
the in-sample performance of $h$ with respect to the data set $S$, which has
been sampled from $P$.

Naively, one might hope to be able to construct learning algorithms which
could in principle output any $h\in\mathcal{Y}^{\mathcal{X}}$. However, the
“no-free-lunch” theorem rules out the possibility of meaningful learning in
this case [35], and therefore we typically consider learning algorithms whose
range is some subset $\mathcal{F}\subseteq\mathcal{Y}^{\mathcal{X}}$. We then
refer to $\mathcal{F}$ as the hypothesis class associated with the learning
algorithm which is, by assumption, also known to the learning algorithm. To
gain some intuition, one could think of $\mathcal{F}$ as the set of all
functions realizable by neural networks of some fixed width and depth, or, as
we describe in Section 3, as the set of all functions realizable by a
parametrized quantum circuit model with some fixed architecture. With respect
to this setting, the following natural question arises: Suppose we have a
learning algorithm $\mathcal{A}$ with hypothesis class $\mathcal{F}$, which
has been run on a randomly drawn data set of $m$ samples $S\sim P^{m}$ and
outputs some hypothesis $h\in\mathcal{F}$, as well as some “training log”
which we denote by $\mathrm{hist}(\mathcal{A},S)$111Such a training log could
for example record the value of the empirical risk, or properties of the trial
hypotheses (such as weight matrices for neural networks), at each stage of an
iterative optimization procedure.. Given the achieved empirical risk
$\hat{R}_{S}(h)$, can we put an upper bound on the true risk $R(h)$, which
holds with high probability over the randomly drawn data set $S$? More
specifically, can we make a statement of the form: For all $\delta\in(0,1)$,
with probability $1-\delta$ over $S\sim P^{m}$, for all $h\in\mathcal{F}$ we
have that

$R(h)\leq\hat{R}_{S}(h)+g(\mathcal{F},h,m,S,\mathcal{A},\mathrm{hist}(\mathcal{A},S),\delta).$
(5)

We refer to such a statement as a generalization bound, and note that the
function $g$ appearing in Eq. (5) provides a (probabilistic) upper bound on
the quantity $R(h)-\hat{R}_{S}(h)$, which we call generalization gap (of $h$
with respect to $S$). Such bounds are desirable because they allow us to
leverage the information we have access to – i.e., the empirical risk, and
properties of the learning algorithm, data set and optimization procedure – to
upper bound $R(h)$, which is the quantity we do not have access to, but are
ultimately interested in. In general, as indicated explicitly in Eq. (5), the
upper bound $g$ on the generalization gap could depend on properties of the
achieved hypothesis $h$, properties of the data set $S$, properties of the
learning algorithm $\mathcal{A}$, and details of the optimization that led to
$h$. However, in this work we will focus on uniform generalization bounds of
the form: for all $\delta\in(0,1)$, with probability $1-\delta$ over $S\sim
P^{m}$, we have for all $h\in\mathcal{F}$ that

$R(h)\leq\hat{R}_{S}(h)+g(\mathcal{F},m,\delta).$ (6)

To be specific, we focus on generalization bounds for which the upper bound on
the generalization gap – i.e., the function $g$ – depends only on properties
of the hypothesis class $\mathcal{F}$, the data set size $m$ and the desired
probability $\delta$. We note that the term “uniform” is used when describing
such generalization bounds to indicate that, with respect to a fixed data set
size $m$ and probability threshold $\delta$, the upper bound on the
generalization gap will be the same – i.e., uniform – for all
$h\in\mathcal{F}$. While it is known that there exist scenarios in which
uniform generalization bounds are not tight [36, 37], we postpone a discussion
of these issues to Section 7.

As motivated above, given a uniform generalization bound for a hypothesis
class $\mathcal{F}$, one typical application is as follows: Given a data set
$S$ sampled from $P$, with $|S|=m$, run some learning algorithm to obtain a
hypothesis $h\in\mathcal{F}$, evaluate its empirical risk $\hat{R}_{S}(h)$,
and then use the generalization bound to place a (probabilistic) upper bound
on the true risk $R(h)$. However, we can also often straightforwardly use such
a generalization bound to answer the following natural question: Given some
$\epsilon>0$ and some $\delta\in(0,1)$, what is the minimum size of $S$
sufficient to ensure that, with probability $1-\delta$, for all
$h\in\mathcal{F}$, the generalization gap satisfies
$R(h)-\hat{R}_{S}(h)\leq\epsilon$? To see this, note that if we have a uniform
generalization bound, then by setting

$g(\mathcal{F},m,\delta)\leq\epsilon$ (7)

and solving for $m$, it is often possible to find some function
$f(\epsilon,\delta,\mathcal{F})$ such that, with probability $1-\delta$ over
$S\sim P^{m}$,

$m\geq f(\epsilon,\delta,\mathcal{F})\Rightarrow\forall
h\in\mathcal{F}:R(h)-\hat{R}_{S}(h)\leq g(\mathcal{F},m,\delta)\leq\epsilon.$
(8)

As the generalization bound may not be tight, we therefore see that
$f(\epsilon,\delta,\mathcal{F})$ provides an upper bound on the minimum size
of $S$ sufficient to probabilistically guarantee a generalization gap less
than $\epsilon$ for all $h\in\mathcal{F}$.

Finally, apart from the fundamental applications of allowing us to bound the
out-of-sample performance of a hypothesis, or upper bound the minimum sample-
size sufficient to guarantee a certain generalization gap, generalization
bounds also allow us to address the issue of model selection, via the
framework of structural risk minimization [20]. Importantly, we note that one
cannot simply use only the function $g(k,m,\delta)$ for model selection: A
trivial learning model, which outputs the same hypothesis independently of the
input data, has $g(k,m,\delta)=0$, but cannot achieve good prediction
performance on interesting tasks. Structural risk minimization thus suggests
combining a generalization bound with an empirical risk evaluation on a
specific data-set to choose the model with the smallest upper-bound on the
true risk. More specifically, let us assume that our hypothesis class depends
on some “architectural hyper-parameter” $k$, with some notion of ordering such
that

$k_{1}\leq k_{2}\implies\mathcal{F}_{k_{1}}\subseteq\mathcal{F}_{k_{2}}.$ (9)

For example, $\mathcal{F}_{k}$ could be the set of all neural networks of
fixed width and depth $k$. Given this, how should we choose the hypothesis
class – or model complexity – that we use for a given learning problem? As
illustrated in Figure 2, generalization bounds, when combined with empirical
risk evaluations, can allow us to answer this question. In particular, assume
that we have a uniform generalization bound of the form: For all
$\delta\in(0,1)$, with probability $1-\delta$ over $S\sim P^{m}$, for all
$h\in\mathcal{F}_{k}$,

$R(h)\leq\hat{R}_{S}(h)+g(k,m,\delta),$ (10)

where $g(k,m,\delta)$ is non-decreasing with respect to $k$. Here, we have
written $g(k,m,\delta)$ rather than $g(\mathcal{F}_{k},m,\delta)$ to emphasize
the assumption that the hyper-parameter $k$ is the only property of
$\mathcal{F}_{k}$ on which the generalization bound depends explicitly. While
increasing $k$ increases the expressivity of the hypothesis class and
therefore typically leads to smaller empirical risk, it also increases the
upper bound $g(k,m,\delta)$ on the generalization gap and may therefore lead
to hypotheses with worse out-of-sample performance. As such, a natural
strategy to find an optimal hypothesis – in the sense of having the smallest
probabilistic upper bound on the true risk – is as follows:

Figure 2: Illustration of structural risk minimization (adapted from Ref.
[20]). Increasing the complexity of a hypothesis class typically allows one to
obtain hypotheses with decreasing empirical risk. However, in many cases
increasing the complexity of a hypothesis class also leads to a larger upper
bound on the generalization gap. Structural risk minimization aims to identify
a hypothesis with the smallest upper bound on the true risk that quantifies
the out-of-sample performance by combining an evaluation of the empirical risk
of candidate hypotheses with an upper bound on the generalization gap of the
relevant hypothesis class.

  1. 1.

For $k$ in $\\{k_{1},\ldots,k_{n}\\}$, run the learning algorithm
$\mathcal{A}_{k}$, with hypothesis class $\mathcal{F}_{k}$, and obtain the
hypothesis $h_{k}$.

  2. 2.

Calculate
$k_{\mathrm{opt}}=\mathrm{argmin}_{k}[\hat{R}_{S}(h_{k})+g(k,m,\delta)]$.

  3. 3.

Output $h_{k_{\mathrm{opt}}}$.

We refer to such a procedure as structural risk minimization222We note that
the term “structural risk minimization” is sometimes used to refer to the
strategy of minimizing a regularized empirical risk, with an additive
regularization term which penalizes high model complexity. However, we follow
Ref. [20] in our definition and presentation., and contrast this with
empirical risk minimization, which simply outputs the hypothesis minimizing
the empirical risk. In light of the above discussion, we note that, given a
family of hypothesis classes $\\{\mathcal{F}_{k}\\}$, each specified by some
architectural hyper-parameter $k$ and satisfying the condition of Eq. (9), we
would ideally like to obtain an upper bound on the generalization gap
$g(k,m,\delta)$ which grows slowly with respect to $k$. In particular, we can
now understand this from two different but complementary perspectives:

Firstly, from the structural risk minimization (or model selection)
perspective, we see from Figure 2 that slow growth of $g(k,m,\delta)$ is
indicative of our ability to exploit the expressivity of more complex
hypothesis classes, i.e. those with larger $k$, without risking poor
generalization performance due to overfitting. More specifically, under the
assumption of monotonically decreasing empirical risk, the slower
$g(k,m,\delta)$ grows, the longer we can expect the quantity
$\hat{R}_{S}(h_{k})+g(k,m,\delta)$ to decrease before reaching a minimum, and
therefore the smaller we can expect our ultimate upper bound on the true risk
of the optimal hypothesis $h_{k_{\mathrm{opt}}}$ to be. In contrast, if
$g(k,m,\delta)$ grows too fast with respect to $k$, then even if we can
achieve very small empirical risk by increasing model complexity, we do not
expect to be able to achieve a sufficiently small upper bound on the true risk
of the optimal hypothesis $h_{k_{\mathrm{opt}}}$.

Secondly, from the sample complexity perspective, let us denote by
$f(\epsilon,\delta,k)$ the complementary upper bound on the minimum sample
sample size $m$ sufficient to probabilistically ensure a generalization gap
less than $\epsilon>0$, which typically follows from $g(k,m,\delta)$ (as we
recall from the discussion around Eqs. (7) and (8)). As we naturally expect
$g(k,m,\delta)$ to be decreasing with increasing $m$, slow growth of
$g(k,m,\delta)$ with respect to $k$ typically implies slow growth of
$f(\epsilon,\delta,k)$ with respect to $k$. In other words, slow growth of
$g(k,m,\delta)$ typically implies slow growth, with respect to model
complexity, of the minimum amount of data one has to use before being able to
probabilistically guarantee a certain generalization gap for all output
hypotheses. As generating data (i.e., sampling from the distribution $P$) may
be expensive or difficult, and as the run-time of learning algorithms
typically scales with respect to the data set size, slow growth of
$g(k,m,\delta)$ therefore facilitates the process of learning with models of
higher complexity.

Given the above observations, we can finally understand the motivation of this
work in an informal way. In particular, in the following section we will see
that parametrized quantum circuits (PQCs) naturally give rise to hypothesis
classes with multiple architectural hyper-parameters, each reflecting a
different aspect of the circuit architecture, such as circuit depth, circuit
width, the total number of gates or the total number of data-encoding gates of
a particular type. In Section 4 we will then see that a body of previous work
has resulted in a collection of generalization bounds for PQC-based models,
each of which depend explicitly on some subset of architectural hyper-
parameters, but not on others. As of yet, however, there exist no
generalization bounds which depend explicitly on hyper-parameters associated
with the data-encoding strategy, despite the important role such strategies
play in determining the expressive power of PQC-based hypothesis classes [33].
As such, the questions which we address in this work are as follows:

  1. (a)

Can we derive generalization bounds for PQC-based hypothesis classes which
depend explicitly on hyper-parameters associated with the data-encoding
strategy?

  2. (b)

Can we use such bounds to identify data-encoding strategies for which the
upper bounds on the generalization gap grow polynomially with respect to the
architectural hyper-parameter relevant to the encoding strategy?

As will be discussed in Section 7, apart from filling a gap in our
understanding of the manner in which the data-encoding influences
generalization, such bounds would also complement existing works, in that they
would allow one to perform structural risk minimization with respect to
multiple architectural hyper-parameters simultaneously. With this motivation
in mind, before proceeding it is worth briefly mentioning how (uniform)
generalization bounds are typically obtained. Intuitively, one might expect
that the generalization performance of a hypothesis class is related to how
complex (or how expressive) the hypothesis class is, and thus one might hope
for the existence of a complexity measure for hypothesis classes from which
generalization bounds follow. This intuition is indeed correct, and in fact a
large amount of work in statistical learning theory has resulted in a variety
of suitable complexity measures – such as the VC dimension [38], Rademacher
complexity [39], pseudo-dimension [40] and metric-entropy amongst others – all
of which directly give rise to generalization bounds [20, 34, 35]. As a
result, given a hypothesis class $\mathcal{F}_{k}$, one typically proves a
uniform generalization bound for $\mathcal{F}_{k}$, which depends explicitly
on the architectural hyper-parameter $k$, by first characterizing the
dependence of a suitable complexity measure $C$ on $k$ (i.e., by
writing/bounding ${C}(\mathcal{F}_{k})$ explicitly in terms of $k$), and then
writing down the known generalization bound which follows from
$C(\mathcal{F}_{k})$. We also follow such a strategy in this work by first
characterizing both the Rademacher complexity and metric-entropy of PQC-based
models in terms of architectural hyper-parameters related to the data-encoding
strategy and then presenting generalization bounds in terms of these
complexity measures. At this stage it is hopefully clear, both why
generalization bounds are desirable, and how (at least intuitively) one might
obtain such bounds. Given this, we proceed in the following section to define
more precisely the PQC-based hypothesis classes considered in this work.

##  3 Parametrized quantum circuit based model classes

Figure 3: Circuit model considered in this work. We assume that the circuit
consists of gates which are parametrized either by the data $\boldsymbol{x}$
(data-encoding gates), or the trainable parameters $\boldsymbol{\theta}$
(trainable gates). The data encoding gates are assumed to implement the time
evolution of a data-encoding Hamiltonian, with evolution time given by some
data coordinate $x^{(i)}=\boldsymbol{e}^{(i)}\boldsymbol{x}$. The model output
is then given by the expectation value of an observable $M$.

_Parametrized quantum circuits (PQCs)_ are ubiquitous in the field of near-
term quantum computing [9, 11, 10] and can be used to construct quantum
machine learning models [12]. We will consider qubit-based quantum systems.
The focus of this work lies on _variational quantum machine learning models_
that are constructed from a PQC $U_{\boldsymbol{\theta}}(\boldsymbol{x})$ that
depends on trainable parameters $\boldsymbol{\theta}\in\Theta$ and on data
inputs $\boldsymbol{x}\in\mathcal{X}$. A prediction in the co-domain
$\mathcal{Y}=\mathbb{R}$ is then obtained by evaluating the expectation value
of a fixed observable $M$, which can be efficiently evaluated, as

$\displaystyle f_{\boldsymbol{\theta}}(\boldsymbol{x})=\langle
0|U^{\dagger}_{\boldsymbol{\theta}}(\boldsymbol{x})MU_{\boldsymbol{\theta}}(\boldsymbol{x})|0\rangle.$
(11)

In the following, we assume that the data inputs are $d$-dimensional real-
valued vectors with entries in the interval $[0,2\pi)$, i.e.,
$\mathcal{X}=[0,2\pi)^{d}$. This choice is somewhat arbitrary, as data can
always be rescaled to fit into a particular interval. However, $[0,2\pi)$ is a
natural choice because quantum gates available on actual hardware are usually
parametrized in terms of _angles_. As will become apparent later, we need not
make any assumptions on the nature of the trainable parameters, but in most
cases they will also be angles, i.e., $\Theta=[0,2\pi)^{p}$, where $p$ is the
number of trainable parameters.

We also make some assumptions on the structure of the circuit
$U_{\boldsymbol{\theta}}(\boldsymbol{x})$. Our model is motivated by the
actual quantum circuits that can be executed on NISQ devices. These devices
usually only allow fixed gates and parametrized evolutions under device-
specific Hamiltonians [41, 42, 43]. In our model, the data inputs
$\boldsymbol{x}$ and the trainable parameters $\boldsymbol{\theta}$ enter the
circuit through different gates. The unitaries parametrized by
$\boldsymbol{\theta}$, denoted by $\\{W_{i}(\boldsymbol{\theta})\\}$,
constitute the trainable part of the model. Fixed unitaries can be absorbed
into the trainable unitaries.

We assume that the gates through which the data enters the circuit are time
evolutions under some Hamiltonian, where the “evolution time” is given by one
of the data coordinates $x^{(i)}$. We denote the $j$-th gate that encodes the
data coordinate $x^{(i)}$ as

$\displaystyle
S^{(i)}_{j}(\boldsymbol{x})=\exp\left(-ix^{(i)}H_{j}^{(i)}\right)=\exp\left(-i\boldsymbol{e}^{(i)}\boldsymbol{x}H_{j}^{(i)}\right),$
(12)

where we rewrote the encoding gate in terms of the input data vectors by
recognizing that $x^{(i)}=\boldsymbol{e}^{(i)}\boldsymbol{x}$, where
$\boldsymbol{e}^{(i)}$ is a standard basis vector. It is of course possible to
consider more general dependencies of the evolution time on the input data,
i.e. in terms of linear combinations or even non-linear functions of the data
coordinates. However, we choose not to include models with such classical pre-
processing of the data, in order to isolate the part of the model which is
truly quantum. Indeed, if one allowed for arbitrary pre-processing, then one
could just use a very complicated neural network to find suitable evolution
times for good predictions, but that would miss the point of using a quantum
learning model at all. We note though that our definition still encompasses
such approaches after a suitable reparametrization of the inputs, which will
usually result in a larger number of input coordinates.

For our analysis, no restriction on the placement of the trainable gates and
the data-encoding gates in the circuit is necessary. Thus, we assume that they
can be arranged arbitrarily, as depicted in Figure 3. However, we will refer
to the choice of data-encoding Hamiltonians per data coordinate as
$\mathcal{D}^{(i)}=\\{H_{j}^{(i)}\\}$ and call the union of these sets over
all data coordinates the _data-encoding strategy_

$\displaystyle\mathcal{D}=\big{(}\mathcal{D}^{(1)},\mathcal{D}^{(2)},\dots,\mathcal{D}^{(d)}\big{)}.$
(13)

The total number of encoding gates per data coordinate is
$N^{(i)}=|\mathcal{D}^{(i)}|$ and the total number of data-encoding gates is
$N=\sum_{i=1}^{d}N^{(i)}$.

A data-encoding strategy $\mathcal{D}$ together with a fixed circuit structure
and a choice of trainable gates defines a parametrized quantum circuit
$U_{\boldsymbol{\theta}}(\boldsymbol{x})$. We denote the fact that this
circuit uses the encoding strategy $\mathcal{D}$ as
$U_{\boldsymbol{\theta}}(\boldsymbol{x})\sim\mathcal{D}$. When we fix an
observable $M$ to generate the predictions, this defines a function class

$\displaystyle\mathcal{F}_{\Theta,\mathcal{D},M}\coloneqq\\{[0,2\pi)^{d}\ni\boldsymbol{x}\mapsto\langle
0|U^{\dagger}_{\boldsymbol{\theta}}(\boldsymbol{x})MU_{\boldsymbol{\theta}}(\boldsymbol{x})|0\rangle\,|\,\boldsymbol{\theta}\in\Theta,U_{\boldsymbol{\theta}}(\boldsymbol{x})\sim\mathcal{D}\\},$
(14)

which is obtained by considering all possible parametrizations
$\boldsymbol{\theta}\in\Theta$ of the trainable gates. This function class
depends explicitly on the parametrization of the trainable parts of the
circuit and on the data-encoding strategy. As we ultimately want to obtain
generalization bounds that depend on the hyper-parameters associated with the
encoding strategy – such as the number of encoding gates $N$ – it will be
helpful for us to reformulate the function class in a way that makes it more
amenable to the analyses in the following sections. To this end, we draw on
the results of Refs. [15, 33], which show that the nature of the data encoding
gates as Hamiltonian evolutions allows us to expand the model output as a
_generalized trigonometric polynomial (GTP)_. A GTP “generalizes” the notion
of a trigonometric polynomial by allowing arbitrary frequencies as in

$\displaystyle
f_{\boldsymbol{\theta}}(\boldsymbol{x})=\sum_{\boldsymbol{\omega}\in\Omega(\mathcal{D})}c_{\boldsymbol{\omega}}(\boldsymbol{\theta},M)e^{-i\boldsymbol{\omega}\boldsymbol{x}}.$
(15)

While the GTP’s coefficients $\\{c_{\boldsymbol{\omega}}\\}$ depend on the
particular parametrization and observable, the set of frequencies
$\Omega(\mathcal{D})$ depends solely on the chosen data-encoding strategy
$\mathcal{D}$, in particular on the spectra of the Hamiltonians
$\\{H_{j}^{(i)}\\}$ that yield the data encoding evolutions
$\\{S^{(i)}_{j}(\boldsymbol{x})\\}$. We describe the procedure for obtaining
such a GTP representation in more detail below. The fact that the expectation
value is always real is reflected by
$c_{\boldsymbol{\omega}}=c_{-\boldsymbol{\omega}}^{*}$ and by the observation
that $\boldsymbol{\omega}\in\Omega(\mathcal{D})$ implies that also
$-\boldsymbol{\omega}\in\Omega(\mathcal{D})$. Additionally, we note that the
absolute value of any expectation value obtained from measuring $M$ is upper
bounded by its operator norm $\lVert M\rVert_{\infty}$, and therefore, if we
assume that $\lVert M\rVert_{\infty}\leq B$, then

$\displaystyle\mathcal{F}_{\Theta,\mathcal{D},M}\subseteq\mathcal{F}_{\Omega}^{B}\coloneqq\left\\{[0,2\pi)^{d}\ni\boldsymbol{x}\mapsto
f(\boldsymbol{x})=\sum\limits_{\boldsymbol{\omega}\in\Omega}c_{\boldsymbol{\omega}}\exp(-i\boldsymbol{\omega}\boldsymbol{x})\,\Big{|}\,(c_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega}\text{
such that }\left\lVert f\right\rVert_{\infty}\leq B\right\\},$ (16)

where $\Omega=\Omega(\mathcal{D})$. We have thus defined a function class that
solely depends on the data-encoding strategy. We stress that this function
class subsumes all possible ways to parametrize the trainable parts of a
circuit with fixed data-encoding strategy $\mathcal{D}$ and fixed observable
$M$, but also goes beyond this by allowing all possible choices of observable
$M$ such that $\lVert M\rVert_{\infty}\leq B$. Therefore, it also contains
models where not only the parameters of the trainable gates, but also the
measurement itself is subject to optimization. In going from
$\mathcal{F}_{\Theta,\mathcal{D},M}$ to $\mathcal{F}_{\Omega}^{B}$, we
effectively allow for a universal trainable part and observable, which enables
us to focus on the encoding strategy. Studying intermediate classes between
$\mathcal{F}_{\Theta,\mathcal{D},M}$ and $\mathcal{F}_{\Omega}^{B}$ could
constitute a path towards tighter generalization bounds that depend on both
the data-encoding and the trainable part of the PQC-based model.

In Section 5, we will first prove generalization bounds for
$\mathcal{F}_{\Omega}^{B}$, which depend explicitly on properties of $\Omega$,
before exploring in detail in Section 6 how these relevant properties of
$\Omega$ depend on the data-encoding strategy $\mathcal{D}$. Exploiting the
fact that, for a given $B\geq\lVert M\rVert_{\infty}$,
$\mathcal{F}_{\Theta,\mathcal{D},M}\subseteq\mathcal{F}_{\Omega(\mathcal{D})}^{B}$
then automatically yields explicitly encoding-dependent generalization bounds
for $\mathcal{F}_{\Theta,\mathcal{D},M}$.

As the connection between the data-encoding strategy $\mathcal{D}$ and the set
$\Omega(\mathcal{D})$ plays a crucial role, we illustrate this connection for
a generic data-encoding strategy here. We first consider the action of a
single encoding evolution $S(\boldsymbol{x})$ in the density matrix picture,
where it acts via the quantum channel

$\displaystyle\mathcal{S}(\boldsymbol{x})[\rho]=\exp\left(-i\boldsymbol{e}\boldsymbol{x}H\right)\rho\exp\left(i\boldsymbol{e}\boldsymbol{x}H\right),$
(17)

where the Hamiltonian $H$ takes the role of any of the above Hamiltonian terms
$H_{j}^{(i)}$ and $\boldsymbol{e}$ can be any basis vector. We can expand
$\rho$ in the eigenbasis of the Hamiltonian
$H|\lambda_{k}\rangle=\lambda_{k}|\lambda_{k}\rangle$ and obtain

$\displaystyle\mathcal{S}(\boldsymbol{x})[\rho]$
$\displaystyle=\mathcal{S}(\boldsymbol{x})\left[\sum_{k,l}\rho_{k,l}\,|\lambda_{k}\rangle\\!\langle\lambda_{l}|\right]$
(18)
$\displaystyle=\sum_{k,l}\rho_{k,l}\,\mathcal{S}(\boldsymbol{x})\left[|\lambda_{k}\rangle\\!\langle\lambda_{l}|\right]$
(19)
$\displaystyle=\sum_{k,l}\rho_{k,l}\,\exp(-i(\lambda_{k}-\lambda_{l})\boldsymbol{e}\boldsymbol{x})|\lambda_{k}\rangle\\!\langle\lambda_{l}|.$
(20)

We see that the differences of the eigenvalues $\lambda_{k}$ of the
Hamiltonian $H$ determine the frequencies with which the different elements of
the expansion of $\rho$ are multiplied. We can combine the different
frequencies with the weight vector $\boldsymbol{e}$ to obtain the set of all
available frequencies

$\displaystyle\Omega(H)=\\{\boldsymbol{\omega}_{k,l}=(\lambda_{k}-\lambda_{l})\boldsymbol{e}\,|\,\lambda_{k},\lambda_{l}\in\operatorname{spec}(H)\\}.$
(21)

With this notation, we can simplify our expression for
$\mathcal{S}(\boldsymbol{x})[\rho]$ to obtain

$\displaystyle\mathcal{S}(\boldsymbol{x})[\rho]$
$\displaystyle=\sum_{\boldsymbol{\omega}\in\Omega(H)}\exp(-i\boldsymbol{\omega}\boldsymbol{x})\rho_{\boldsymbol{\omega}},$
(22)

where the operators $\rho_{\boldsymbol{\omega}}$ are given by collecting the
terms in the above sum for which the frequency differences are the same, i.e.

$\displaystyle\rho_{\boldsymbol{\omega}}=\sum_{(k,l)\in
I(\boldsymbol{\omega})}\rho_{k,l}|\lambda_{k}\rangle\\!\langle\lambda_{l}|,\text{
where
}I(\boldsymbol{\omega})=\\{(k,l)\,|\,(\lambda_{k}-\lambda_{l})\boldsymbol{e}=\boldsymbol{\omega}\\}.$
(23)

As $\rho$ is Hermitian, we have that
$\rho_{\boldsymbol{\omega}}=\rho_{-\boldsymbol{\omega}}^{*}$. The frequency
structure carries over if we measure the expectation value of an arbitrary
observable $M$ for the state $\mathcal{S}(\boldsymbol{x})[\rho]$ to obtain a
prediction

$\displaystyle f(\boldsymbol{x})$
$\displaystyle=\operatorname{Tr}\\{\mathcal{S}(\boldsymbol{x})[\rho]M\\}=\sum_{\boldsymbol{\omega}\in\Omega(H)}\exp(-i\boldsymbol{\omega}\boldsymbol{x})\operatorname{Tr}\\{\rho_{\boldsymbol{\omega}}M\\}=\sum_{\boldsymbol{\omega}\in\Omega(H)}{c_{\boldsymbol{\omega}}}\exp(-i\boldsymbol{\omega}\boldsymbol{x}).$
(24)

As a result, we obtain a GTP with coefficients
$c_{\boldsymbol{\omega}}=\operatorname{Tr}\\{\rho_{\boldsymbol{\omega}}M\\}$.
Note that, as $\rho_{\boldsymbol{\omega}}=\rho_{-\boldsymbol{\omega}}^{*}$, we
have that $c_{\boldsymbol{\omega}}=c_{-\boldsymbol{\omega}}^{*}$, which
ensures that $f(\boldsymbol{x})$ is real-valued as expected. The coefficients
of this series could depend intricately on the circuit that was used to
construct $\rho$ and on the specific observable $M$, but a profound
understanding of this relation is an open question. However, this does not
pose an obstacle for us, as only the set $\Omega$ is relevant for our study.

We have just derived the frequency structure for one encoding gate, but for
more complicated circuits we have to understand the action of multiple
encoding gates, potentially interleaved with some trainable unitaries. The
intermediary unitaries, however, will only result in a basis change, not
affecting the set of combined frequencies. We can therefore ignore them and
just consider the repeated action of two distinct encoding gates with
Hamiltonians $H_{1}$ and $H_{2}$, resulting in

$\displaystyle\mathcal{S}_{2}(\boldsymbol{x})[\mathcal{S}_{1}(\boldsymbol{x})[\rho]]$
$\displaystyle=\mathcal{S}_{2}(\boldsymbol{x})\left[\sum_{{\boldsymbol{\omega}_{1}\in\Omega(H_{1})}}\exp(-i\boldsymbol{\omega}_{1}\boldsymbol{x})\rho_{\boldsymbol{\omega}_{1}}\right]$
(25)
$\displaystyle=\sum_{\boldsymbol{\omega}_{1}\in\Omega(H_{1})}\exp(-i\boldsymbol{\omega}_{1}\boldsymbol{x})\sum_{\boldsymbol{\omega}_{2}\in\Omega(H_{2})}\exp(-i\boldsymbol{\omega}_{2}\boldsymbol{x})\rho_{\boldsymbol{\omega}_{1},\boldsymbol{\omega}_{2}}$
(26)
$\displaystyle=\sum_{\boldsymbol{\omega}_{1}\in\Omega(H_{1})}\sum_{\boldsymbol{\omega}_{2}\in\Omega(H_{2})}\exp(-i[\boldsymbol{\omega}_{1}+\boldsymbol{\omega}_{2}]\boldsymbol{x})\rho_{\boldsymbol{\omega}_{1},\boldsymbol{\omega}_{2}}.$
(27)

At this point, we precisely understand that the application of the second gate
results in new frequencies that encompass all possible sums of the different
frequencies. We can again consolidate this if we consider the sumset (or
Minkowski sum) of the two sets of frequencies $\Omega(H_{1})$ and
$\Omega(H_{2})$ defined as

$\displaystyle\Omega(\\{H_{1},H_{2}\\})\coloneqq\Omega(H_{1})+\Omega(H_{2})\coloneqq\\{\boldsymbol{\omega}_{1}+\boldsymbol{\omega}_{2}\,|\,\boldsymbol{\omega}_{1}\in\Omega(H_{1}),\boldsymbol{\omega}_{2}\in\Omega(H_{2})\\}.$
(28)

With that we have

$\displaystyle\mathcal{S}_{2}(\boldsymbol{x})[\mathcal{S}_{1}(\boldsymbol{x})[\rho]]$
$\displaystyle=\sum_{{\boldsymbol{\omega}\in\Omega(H_{1})+\Omega(H_{2})}}\exp(-i\boldsymbol{\omega}\boldsymbol{x})\rho_{\boldsymbol{\omega}}.$
(29)

Note again that the values of specific components $\rho_{\boldsymbol{\omega}}$
depend on the specific initial state $\rho$ and possible intermediate
unitaries, but, in this work, we are only interested in $\Omega$ itself. We
can apply the same logic recursively to see that the set of accessible
frequencies for any encoding strategy $\mathcal{D}$ is given by the sumset of
all the individual sets of frequencies $\Omega(H^{(i)}_{j})$ for each gate:

$\displaystyle\Omega(\mathcal{D})=\sum_{\mathcal{D}^{(i)}\in\mathcal{D}}\sum_{H\in\mathcal{D}^{(i)}}\Omega(H)=\sum_{i=1}^{d}\sum_{j=1}^{N^{(i)}}\\{(\lambda_{k}-\lambda_{l})\boldsymbol{e}^{(i)}\,|\,\lambda_{k},\lambda_{l}\in\operatorname{spec}(H_{j}^{(i)})\\}.$
(30)

##  4 Prior and related work

Before presenting our explicitly encoding-dependent generalization bounds for
PQC-based models in the next two sections, we discuss how our results compare
to prior work. While there is a massive amount of prior and ongoing work on
the generalization capacity of classical models, see for example the survey in
Ref. [37], such results have only recently begun to emerge for PQC-based
models. Here, we focus on a comparison with these latter results.
Additionally, while the following paragraphs constitute a detailed review of
existing generalization bounds for PQC-based models, we stress that no
knowledge of these prior works is necessary to understand our proofs and
results. In particular, the presentation here is intended to establish context
for our work and to place prior works in relation to each other, but the
remainder of this manuscript can safely be read independently of the review
presented here.

Given the discussions in the previous two sections, we note that, at a high
level, all prior work on generalization bounds for PQC-based models can be
classified via the following three criteria:

  1. 1.

Which restrictions – if any – are placed on the architecture/structure of the
PQCs generating the model class considered?

  2. 2.

In terms of which architectural hyper-parameters, or experimentally accessible
quantities, are the generalization bounds expressed?

  3. 3.

Via which complexity measure are the generalization bounds derived?

Given this, we will use the above questions as guidelines for understanding
and relating existing results. Throughout this discussion, keep in mind that,
as explained in Section 1, all prior works are restricted to encoding-first
models, whereas we allow for data re-uploading.

Additionally, while some of the following works study the same complexity
measures as the ones examined here – namely, Rademacher complexity and
covering numbers – all of them differ from ours in both the restriction to
encoding-first PQC-based models and in a lack of explicit dependence on the
data-encoding strategy. Given this, we split our survey into two parts. First,
in Section 4.1, we discuss those prior works which derive encoding-independent
generalization bounds. In Section 4.2, we then discuss existing works deriving
generalization bounds which depend on the data-encoding strategy, but with a
dependence which is implicit, and not necessarily clear a priori.

###  4.1 Encoding-independent complexity and generalization bounds

Ref. [24] is an early study of the complexity and generalization capacity of
quantum circuit based models, which presents encoding-independent bounds on
the pseudo-dimension of function classes associated with encoding-first
$2$-local (unitary or CPTP) PQCs, polynomial in the size (number of gates) and
depth of the trainable part of the circuit (in which all gates were considered
trainable). Such pseudo-dimension bounds then yield generalization bounds,
which also depend polynomially on the size and depth of the trainable circuit.
Ref. [44] has extended the generalization bounds of Ref. [24] to the agnostic
setting. In a similar vein, Ref. [29] has recently derived encoding-
independent covering number bounds for encoding-first PQC-based models, which
depend explicitly on the number of gates in the PQC, and the operator norm of
the measured observable. Once again, using standard tools from statistical
learning theory, the authors of Ref. [29] are then able to use these covering
number bounds to provide an encoding-independent generalization bound.

Working from the perspective of kernel methods, Ref. [32] has recently
investigated the complexity of encoding-first PQC-based models in terms of
properties of the parametrized measurement which follows data-encoding. More
specifically, they interpret the entire parametrized circuit following the
data-encoding as a parametrized measurement, and provide bounds for the VC-
dimension of the model class in terms of the rank of the parametrized
observable, and for the fat-shattering dimension in terms of the Frobenius
norm of the parametrized observable. These bounds on standard complexity
measures then allow them to prove generalization bounds which depend
explicitly on either the rank or the Frobenius norm of the accessible
observables. However, similarly the perspective we advocate in this work, the
authors of Ref. [32] stress the application of generalization bounds for model
selection, via structural risk minimization.

Finally, Ref. [27] has recently initiated a resource-theoretic approach by
providing encoding-independent bounds on both the Rademacher and Gaussian
complexity of encoding-first PQC-based models, in terms of the number of
repetitions of resource channels allowed in the PQC. These Rademacher and
Gaussian complexity bounds have then been used to derive generalization
bounds, which depend on the same quantities, and therefore provide an
encoding-independent resource-theoretic perspective on generalization in
encoding-first PQC-based models.

###  4.2 Encoding-dependent complexity and generalization bounds

We proceed by discussing prior work deriving generalization bounds which do
depend on the data-encoding strategy. While the dependence on the data-
encoding could take various forms, in this manuscript we aim to derive
generalization bounds which depend explicitly on architectural hyper-
parameters related to the data-encoding strategy (such as the number of
encoding gates of a specific type), and therefore facilitate the
straightforward implementation of model selection via structural risk
minimization. This is in contrast to all of the prior encoding-dependent
generalization bounds, which are written in terms of some quantity which
depends on the data-encoding strategy, but with an implicit dependence which
is not a priori clear, and needs to be assessed experimentally. Given this
fundamental difference between our generalization bounds and those of the
prior works we discuss here, a natural open question is whether the implicitly
encoding-dependent quantities used in the following works can be written
explicitly in terms of architectural hyper-parameters related to the data-
encoding strategy. If possible, this would immediately provide explicitly
encoding-dependent generalization bounds comparable to those we derive in this
work.

With this in mind, we begin our survey of implicitly encoding-dependent
generalization bounds with Ref. [25], which has suggested a complexity measure
based on the classical Fisher information, called the effective dimension, and
demonstrated that one can indeed state generalization bounds in terms of the
effective dimension. Utilizing the empirical Fisher information as a tool for
approximating the effective dimension, Ref. [25] presented numerical
experiments which demonstrate a clear dependence of the effective dimension on
the encoding-strategy. However, the explicit dependence of the effective
dimension on the encoding strategy is not clear and needs to be evaluated
experimentally. Additionally, Ref. [25] also provided a comparison between the
effective dimension of PQC-based models and comparable classical models, and
demonstrated that PQC-based models can exhibit a higher effective dimension.
While not discussed explicitly in Ref. [25], we stress, however, that one
should not use model complexity (e.g., effective dimension) as the sole
criterion for model selection, since model classes with higher effective
dimension may have worse generalization behavior than models with a lower
effective dimension. Instead, as we advocate in this work, one should ideally
use a framework such as structural risk minimization to select a model with
the smallest upper bound on out-of-sample performance.

Also working from an information theoretic perspective, and with a focus on
the role of data-encoding, Ref. [31] has recently presented generalization
bounds for PQC-based models in terms of information-theoretic quantities
describing a notion of mutual information between the post-encoding quantum
state $\rho(\boldsymbol{x})$ and the classical data. While these
generalization bounds have a strong implicit dependence on the data-encoding
strategy, it is once again not immediately clear, apart from in a few special
cases, how to explicitly express the suggested complexity measure in terms of
architectural hyper-parameters related to the data-encoding strategy.

From a resource theoretic perspective, and complementing Ref. [27], the series
of works [26, 28] have further studied the Rademacher complexity of encoding-
first PQC-based models. However, unlike in Ref. [27], the Rademacher
complexity bounds of Refs. [26, 28] are given in terms of quantities that
exhibit an implicit dependence on the data-encoding strategy. More
specifically, Ref. [28] provides Rademacher complexity bounds in terms of the
size, depth and amount of magic available as a resource. Additionally, Ref.
[26] also studies noisy PQC-based models and provides Rademacher complexity
bounds in terms of either the Rademacher complexity of the associated
noiseless circuit or the free-robustness of the model.

Recently, Ref. [45] has studied generalization for PQC-based models using a
hardware efficient ansatz with a specific choice of data-encoding. For this
setting, they proved VC-dimension bounds that scale polynomially with the
minimum of the number of qubits and the number of trainable layers. In their
proofs, they combine light cone arguments with a trigonometric function
representation for functions implemented by their ansatz.

Finally, we mention Ref. [30] which has developed techniques for evaluating
the potential advantages of quantum kernels over classical kernels. These
results are of relevance to this work due to the close relationship between
PQC-based models and kernel methods [16]. In a first step, the authors of Ref.
[30] suggest the evaluation of a geometric quantity which depends on the
chosen quantum feature map and the available training data instances. If the
quantum machine learning model passes this first test, a model complexity
parameter, which now depends on the quantum encoding and the training data
(both instances and labels), should be computed. While these complexity
measures can be classically computed in time polynomial in the training data
size, analytically determining their exact dependence on the data-encoding can
be challenging. This is in contrast to our model complexity bounds, which
depend straightforwardly on hyper-parameters associated with the data-encoding
strategy, such as the number of encoding gates of a specific type.

##  5 Generalization bounds for generalized trigonometric polynomials

We recall (from Section 3) that we can prove generalization bounds on
$\mathcal{F}_{\Theta,\mathcal{D},M}$, the hypothesis class of interest for a
given PQC-based model, by proving generalization bounds on
$\mathcal{F}_{\Omega}^{B}$. Recall that $\mathcal{F}_{\Omega}^{B}$ has been
defined as the class of generalized trigonometric polynomials (GTPs) with
frequencies in $\Omega$ and infinity-norm bounded by $B$ as

$\displaystyle\mathcal{F}_{\Omega}^{B}=\Bigg{\\{}[0,2\pi)^{d}$
$\displaystyle\ni\boldsymbol{x}\mapsto
f(\boldsymbol{x})=\sum\limits_{\boldsymbol{\omega}\in\Omega}c_{\boldsymbol{\omega}}\exp(-i\boldsymbol{\omega}\boldsymbol{x})\,\Big{|}\,(c_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega}\text{
such that }\left\lVert f\right\rVert_{\infty}\leq B\Bigg{\\}}.$ (31)

In order to prove generalization bounds for $\mathcal{F}_{\Omega}^{B}$, it
will be convenient to work with the cosine and sine representation of the
complex exponential, and with the norm of the vector of coefficients instead
of the norm of the function. Note that, since we have observed in Section 3
that $c_{-\boldsymbol{\omega}}=c_{\boldsymbol{\omega}}^{\ast}$, we can define,
for every $\boldsymbol{\omega}\in\Omega$

$\displaystyle a_{\boldsymbol{\omega}}$ $\displaystyle\coloneqq
c_{\boldsymbol{\omega}}+c_{-\boldsymbol{\omega}}\in\mathbb{R},$ (32)
$\displaystyle b_{\boldsymbol{\omega}}$
$\displaystyle\coloneqq\frac{1}{i}(c_{\boldsymbol{\omega}}-c_{-\boldsymbol{\omega}})\in\mathbb{R}.$
(33)

With these, it further follows that

$\displaystyle
c_{\boldsymbol{\omega}}e^{-i\boldsymbol{\omega}\boldsymbol{x}}+c_{-\boldsymbol{\omega}}e^{i\boldsymbol{\omega}\boldsymbol{x}}$
$\displaystyle=a_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x})+b_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x}),$
(34)

which allows us to rewrite the sum in Eq. (31) as a sum of real terms only. If
we were only considering frequencies given by real numbers, then it would
suffice to sum over the non-negative frequencies in the real sum
representation. However, we are dealing with frequency vectors. As this is the
case, we start by removing the zero vector from the set of frequencies to
obtain $\Omega^{\ast}\coloneqq\Omega\setminus\\{0\\}$. Note that this is
meaningful as $0\in\Omega$ for any $\Omega$ of the form introduced in Section
3. Next, we divide $\Omega^{\ast}$ into two disjoint parts
$\Omega^{\ast}=\Omega_{+}\cup\Omega_{-}$, with
$\Omega_{+}\cap\Omega_{-}=\emptyset$, such that for every
$\boldsymbol{\omega}\in\Omega_{+}$ we have that
$-\boldsymbol{\omega}\in\Omega_{-}$. We again note that this is possible due
to the specific form of the sets $\Omega$ discussed in Section 3. In
particular, we then have $|\Omega|=2|\Omega_{+}|+1$. Additionally, we make use
of a shorthand notation for the vectors
$(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}}$ and
$(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}}$: We keep the
indices outside of the parentheses, but remove the indexing set. Namely we
write
$(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})$
in place of
$(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}})$.
We only explicitly write the indexing set at certain points to avoid
confusion.

With these notational points in mind, we can rewrite the hypothesis class
$\mathcal{F}_{\Omega}^{B}$ as

$\displaystyle\begin{split}\mathcal{F}_{\Omega}^{B}=\Bigg{\\{}[0,2\pi)^{d}&\ni\boldsymbol{x}\mapsto
f(x)=\frac{a_{0}}{2}+\sum\limits_{\boldsymbol{\omega}\in\Omega_{+}}\left(a_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x})+b_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x})\right)\\\
&\Bigg{|}\leavevmode\nobreak\
(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\text{
such that }\left\lVert f\right\rVert_{\infty}\leq B\Bigg{\\}},\end{split}$
(35)

and, for $\tilde{B}>0$, we define the class $\mathcal{H}_{\Omega}^{\tilde{B}}$
via

$\displaystyle\begin{split}\mathcal{H}_{\Omega}^{\tilde{B}}\coloneqq\Bigg{\\{}[0,2\pi)^{d}&\ni\boldsymbol{x}\mapsto\frac{a_{0}}{2}+\sum\limits_{\boldsymbol{\omega}\in\Omega_{+}}\left(a_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x})+b_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x})\right)\hskip
35.56593pt\\\ &\Bigg{|}\leavevmode\nobreak\
\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{2}\leq\tilde{B}\Bigg{\\}},\end{split}$
(36)

where the $2$-norm is given by

$\displaystyle\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{2}\coloneqq\sqrt{a_{0}^{2}+\sum_{\boldsymbol{\omega}\in\Omega_{+}}(a_{\boldsymbol{\omega}}^{2}+b_{\boldsymbol{\omega}}^{2})}.$
(37)

We assume for the purposes of this section that $\tilde{B}>0$ is chosen such
that $\mathcal{F}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$ holds
true. In the special case of frequency vectors with integer entries, i.e.,
$\Omega\subseteq\mathbb{Z}^{d}$, we can always choose $\tilde{B}=2B$. This can
be seen as follows: For a function $f\in\mathcal{F}_{\Omega}^{B}$ given by
$f(\boldsymbol{x})=\sum_{\boldsymbol{\omega}\in\Omega}\exp(-i\boldsymbol{\omega}\boldsymbol{x})c_{\boldsymbol{\omega}}={a_{0}}/{2}+\sum_{\boldsymbol{\omega}\in\Omega_{+}}\left(a_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x})+b_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x})\right)$,
we obtain

$\displaystyle\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}})\right\rVert_{2}$
$\displaystyle=2\left\lVert(c_{0},(c_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega^{\ast}})\right\rVert_{2}=\frac{2}{(2\pi)^{\nicefrac{{d}}{{2}}}}\left\lVert
f\right\rVert_{2}\leq 2\left\lVert f\right\rVert_{\infty}\leq 2B,$ (38)

so we can take $\tilde{B}=2B$ to ensure
$\mathcal{F}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$. Here, we
used that $\Omega\subseteq\mathbb{Z}^{d}$ implies orthogonality of the
functions $\boldsymbol{x}\mapsto\exp(-i\boldsymbol{\omega}\boldsymbol{x})$,
$\boldsymbol{\omega}\in\Omega$, which in turn implies $\left\lVert
f\right\rVert_{2}=(2\pi)^{\nicefrac{{d}}{{2}}}\left\lVert(c_{0},(c_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega^{\ast}})\right\rVert_{2}$
since each of those functions has $2$-norm equal to
$(2\pi)^{\nicefrac{{d}}{{2}}}$. As a consequence of the assumption that
$\mathcal{F}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$,
generalization bounds uniform over $\mathcal{H}_{\Omega}^{\tilde{B}}$ imply
generalization bounds uniform over $\mathcal{F}_{\Omega}^{B}$. Therefore, we
focus on proving generalization bounds for $\mathcal{H}_{\Omega}^{\tilde{B}}$.

We conjecture that the inclusion
$\mathcal{F}_{\Theta,\mathcal{D},M}\subseteq\mathcal{F}_{\Omega}^{B}$ observed
in Section 3 can be strengthened:

######  Conjecture 1.

For any PQC-based model, we have

$\displaystyle\begin{split}\mathcal{F}_{\Theta,\mathcal{D},M}\subseteq\tilde{\mathcal{F}}_{\Omega}^{B}\coloneqq\Bigg{\\{}[0,2\pi)^{d}&\ni\boldsymbol{x}\mapsto
f(\boldsymbol{x})=\sum\limits_{\boldsymbol{\omega}\in\Omega}c_{\boldsymbol{\omega}}\exp(-i\boldsymbol{\omega}\boldsymbol{x})\,\\\
&\Big{|}\,(c_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega}\text{ s.t.
}\left\lVert f\right\rVert_{\infty}\leq B\text{ and
}\left\lVert(c_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega}\right\rVert_{\infty}\leq
B\Bigg{\\}}.\end{split}$ (39)

If this conjecture is correct, then it implies that
$\mathcal{F}_{\Theta,\mathcal{D},M}\subseteq\tilde{\mathcal{F}}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$
holds with $\tilde{B}=2\sqrt{\lvert\Omega\rvert}B$ and $\left\lVert
M\right\rVert_{\infty}\leq B$ for general frequency spectra
$\Omega=\Omega(\mathcal{D})$, because we have the inequalities
$\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{2}\leq\sqrt{\lvert\Omega\rvert}\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{\infty}\leq
2\sqrt{\lvert\Omega\rvert}\left\lVert(c_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega}\right\rVert_{\infty}$.
Thus, conditional on Conjecture 1, generalization bounds for
$\mathcal{H}_{\Omega}^{\tilde{B}}$ with suitable
$\tilde{B}=2\sqrt{\lvert\Omega\rvert}\left\lVert M\right\rVert_{\infty}$ imply
generalization bounds for PQCs with general encoding strategies and
potentially non-integer frequency spectra.

Our bounds focus on the dependence of generalization on the frequency spectrum
$\Omega$. We obtain these bounds from bounds on the complexity of
$\mathcal{H}_{\Omega}^{\tilde{B}}$, measured in terms of two complexity
measures from classical learning theory, namely the _Rademacher complexity_
and the _metric entropy_. We first recall the definitions of these important
quantities and then give an overview over our results and proof strategy.

######  Definition 2 ((Empirical) Rademacher complexity).

Let $\mathcal{Z}$ be some data space,
$\mathcal{F}\subseteq\mathbb{R}^{\mathcal{Z}}$ a function class, and
$S=(\boldsymbol{z}_{1},\ldots,\boldsymbol{z}_{m})\in\mathcal{Z}^{m}$. The
_empirical Rademacher complexity_ of $\mathcal{F}$ with respect to $S$ is
defined as

$\displaystyle\hat{\mathcal{R}}_{S}(\mathcal{F})\coloneqq\underset{\boldsymbol{\sigma}\sim
U(\\{-1,1\\}^{m})}{\mathbb{E}}\Big{[}\sup\limits_{f\in\mathcal{F}}\frac{1}{m}\sum\limits_{i=1}^{m}\sigma_{i}f(\boldsymbol{z}_{i})\Big{]},$
(40)

where $U(\\{-1,1\\}^{m})$ denotes the uniform distribution on
$\\{-1,1\\}^{m}$. The i.i.d. random variables $\sigma_{1},\ldots,\sigma_{m}$
are often called _Rademacher random variables_.

For later use, we note that, if
$\mathcal{F}\subseteq\mathcal{G}\subseteq\mathbb{R}^{\mathcal{Z}}$, then, for
any $S\in\mathcal{Z}^{m}$ we have
$\hat{\mathcal{R}}_{S}(\mathcal{F})\leq\hat{\mathcal{R}}_{S}(\mathcal{G})$.
Next, we introduce our second complexity measure:

######  Definition 3 (Covering nets, covering number, and metric entropy).

Let $(X,d)$ be a (pseudo-)metric space. Let $K\subseteq X$ and let
$\varepsilon>0$. We call $N\subseteq K$ an (interior) $\varepsilon$-covering
net of $K$ if for all $x\in K$ there exists a $y\in N$ such that
$d(x,y)\leq\varepsilon$. The _covering number_ $\mathcal{N}(K,d,\varepsilon)$
is defined as the smallest possible cardinality of an (interior)
$\varepsilon$-covering net of $K$. Finally, we define the _metric entropy_
$\log_{2}\mathcal{N}(K,d,\varepsilon)$ via a logarithm of the covering number.

For our purposes, the relevant covering numbers are those of
$\mathcal{H}_{\Omega}^{\tilde{B}}$ with respect to the pseudo-metrics induced
by the data-dependent semi-norms
$\left\lVert\cdot\right\rVert_{2,S\rvert_{x}}$, which, given training data
$S=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{m}$, are defined as

$\left\lVert
f\right\rVert_{2,S\rvert_{x}}\coloneqq\sqrt{\frac{1}{m}\sum_{i=1}^{m}\,\lvert
f(\boldsymbol{x}_{i})\rvert^{2}}.$ (41)

In Section 5.1, we prove Rademacher complexity bounds for
$\mathcal{H}_{\Omega}^{\tilde{B}}$. We do so by understanding
$\mathcal{H}_{\Omega}^{\tilde{B}}$ as (a subset of) a class of functions
implemented by a simple classical _neural network_ (NN) with a single hidden
layer and with sinusoidal activation functions in the hidden layer. For such
NN architectures, we can then apply already known Rademacher complexity
bounds. This strategy leads to

$\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{F}_{\Omega}^{B})\leq\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{H}_{\Omega}^{\tilde{B}})\leq\tilde{\mathcal{O}}\left(\sqrt{\frac{\lvert\Omega\rvert}{m}}\right)$
(42)

for a training data set $S$ of size $m$, with data instances
$S\rvert_{x}=\\{x_{i}\\}_{i=1}^{m}$. Here, the $\tilde{\mathcal{O}}$ refers to
the asymptotic behavior as $\lvert\Omega\rvert,m\to\infty$ and hides a
logarithmic dependence on $\lvert\Omega\rvert$. (As we are most interested in
the dependence on $\lvert\Omega\rvert$, we also hide the dependence on $B$ and
$\tilde{B}$ here.) With these Rademacher complexity bounds at hand, we can
then derive generalization guarantees for $\mathcal{H}_{\Omega}^{\tilde{B}}$,
and thus $\mathcal{F}_{\Omega}^{B}$, using a standard generalization bound in
terms of the Rademacher complexity. We obtain that for a bounded Lipschitz
loss function, with probability $\geq 1-\delta$, the generalization error
satisfies

$R(f)-\hat{R}_{S}(f)\leq\tilde{\mathcal{O}}\left(\sqrt{\frac{\lvert\Omega\rvert}{m}}+\sqrt{\frac{\log(\nicefrac{{1}}{{\delta}})}{m}}\right),$
(43)

uniformly over $f\in\mathcal{H}_{\Omega}^{\tilde{B}}$ for training data $S$ of
size $m$. Again, we emphasize the leading-order dependence on
$\lvert\Omega\rvert$ and hide other parameters. We note that, without further
assumptions, as in classical agnostic learning scenarios, we do not expect a
better scaling with respect to $m$ than the Hoeffding-like
$\sim\nicefrac{{1}}{{\sqrt{m}}}$.

In Section 5.2, we bound the covering number and metric entropy of
$\mathcal{H}_{\Omega}^{\tilde{B}}$,and thus of $\mathcal{F}_{\Omega}^{B}$.We
achieve this by constructing a covering net for
$\mathcal{H}_{\Omega}^{\tilde{B}}$ from a suitable (finer-grained) covering
net of the allowed vectors of Fourier coefficients. Here, we crucially use
that $\lvert\Omega\rvert$ determines the dimension of the space in which we
have to take these covering nets. With this reasoning, we obtain a metric
entropy bound of

$\log_{2}\mathcal{N}(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{\infty},\varepsilon)\leq\log_{2}\mathcal{N}(\mathcal{H}_{\Omega}^{\tilde{B}},\left\lVert\cdot\right\rVert_{\infty},\frac{\varepsilon}{2})\leq\tilde{\mathcal{O}}\left(\lvert\Omega\rvert\log(\nicefrac{{1}}{{\varepsilon}})\right),$
(44)

where the $\tilde{\mathcal{O}}$ hides logarithmic dependencies on $B$ and
$\lvert\Omega\rvert$. Given these metric entropy bounds, we then use the
chaining method to derive empirical Rademacher complexity bounds. Again
assuming a bounded Lipschitz loss function, this method yields, with
probability $\geq 1-\delta$, a generalization error bound of

$R(f)-\hat{R}_{S}(f)\leq\tilde{\mathcal{O}}\left(\sqrt{\frac{\lvert\Omega\rvert}{m}}+\sqrt{\frac{\log(\nicefrac{{1}}{{\delta}})}{m}}\right),$
(45)

simultaneously for all
$f\in\mathcal{F}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$,
assuming training data of size $m$ and hiding both logarithmic terms in
$\lvert\Omega\rvert$ or $\tilde{B}$ as well as dependencies on $B$, the
Lipschitz constant, and the bound on the loss. While we see that, with the
above definition of $\mathcal{F}_{\Omega}^{B}$ and
$\mathcal{H}_{\Omega}^{\tilde{B}}$, the strategies of Sections 5.1 and 5.2
lead to the same generalization bound in leading order, we nevertheless
present both approaches because they yield different results if the assumption
on the Fourier coefficients appearing in $\mathcal{F}_{\Omega}^{B}$ or
$\mathcal{H}_{\Omega}^{\tilde{B}}$ is changed from a $2$-norm bound to a
general $p$-norm bound.

In the light of the discussion in Section 3, these generalization bounds for
classes of generalized trigonometric polynomials imply generalization bounds
for PQCs. As we have focused on the dependence on the frequency spectrum in
the former, we obtain a focus on the encoding-dependence in the latter. We
provide and discuss these results in Section 6.

###  5.1 Generalization bounds for generalized trigonometric polynomials via
Rademacher complexity

We begin our analysis by stating our Rademacher complexity bound for
$\mathcal{H}_{\Omega}^{\tilde{B}}$. As we will see, this bound is obtained by
combining two partial results, and will lead directly to a generalization
bound. For ease of notation, we write
$K_{i}\coloneqq\max_{\boldsymbol{\omega}\in\Omega_{+}}\\{\lvert\omega_{i}\rvert\\}$
for $i\in\\{1,\ldots,d\\}$ and $K\coloneqq\sum_{i}K_{i}$.

######  Lemma 4 (Rademacher complexity bounds for GTPs).

Let $d,m\in\mathbb{N}$. Let $S\rvert_{x}\in([0,2\pi)^{d})^{m}$. Let
$\mathcal{H}_{\Omega}^{\tilde{B}}$ be as defined in Eq. (36). The empirical
Rademacher complexity of $\mathcal{H}_{\Omega}^{\tilde{B}}$ with respect to
$S\rvert_{x}\coloneqq(\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{m})$ can be
upper-bounded as

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{H}_{\Omega}^{\tilde{B}})$
$\displaystyle\leq\mathcal{O}\left(\frac{\min\left\\{\sqrt{\log(2d)}\max\\{K,\tilde{B}\sqrt{\lvert\Omega\rvert}\\},\tilde{B}\sqrt{\lvert\Omega\rvert\log(\lvert\Omega\rvert)}\right\\}}{\sqrt{m}}\right).$
(46)

In order to prove Lemma 4 we state and show two partial results, namely Lemmas
5 and 6. These two Lemmata have slightly different proof strategies, but both
are motivated by thinking of generalized trigonometric polynomials as being
realized by certain neural network architectures.

######  Lemma 5 (Empirical Rademacher complexity of
$\mathcal{H}_{\Omega}^{\tilde{B}}$—Version $1$).

Let $d,m$, $S\rvert_{x}$, and $\mathcal{H}_{\Omega}^{\tilde{B}}$ be as in
Lemma 4. Then, the empirical Rademacher complexity of
$\mathcal{H}_{\Omega}^{\tilde{B}}$ with respect to $S\rvert_{x}$ can be upper-
bounded as

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{H}_{\Omega}^{\tilde{B}})$
$\displaystyle\leq\mathcal{O}\left(\frac{1}{\sqrt{m}}\max\\{K,\tilde{B}\sqrt{\lvert\Omega\rvert}\\}\sqrt{\log(2d)}\right).$
(47)

###### Proof.

We prove this statement by constructing a function class that contains
$\mathcal{H}_{\Omega}^{\tilde{B}}$ and whose empirical Rademacher complexity
we are able to upper bound by viewing it as arising from a simple layered
neural network (NN) architecture. More specifically, we consider the following
class of functions

$\displaystyle\begin{split}\mathcal{G}^{\tilde{B}}_{\Omega}\coloneqq\Bigg{\\{}[0,2\pi)^{d}&\ni\boldsymbol{x}\mapsto\frac{d_{0}}{2}+\sum_{\boldsymbol{\omega}\in\Omega_{+}}d_{\boldsymbol{\omega}}\sin(\boldsymbol{\alpha}_{\boldsymbol{\omega}}\boldsymbol{x}+\gamma_{\boldsymbol{\omega}})\\\
&\Bigg{|}\,\left\lVert(d_{0},(d_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{2}\leq\tilde{B},\,\boldsymbol{\alpha}_{\boldsymbol{\omega}}\in\prod\limits_{i=1}^{d}[-K_{i},K_{i}],\,\gamma_{\boldsymbol{\omega}}\in[-\pi,\pi)\Bigg{\\}},\end{split}$
(48)

which can be realized by a NN with a single hidden layer of neurons with sine
activation functions, and a linear activation at the output neuron. Here,
again $(d_{\boldsymbol{\omega}})_{\boldsymbol{\omega}}$ stands for the vector
$(d_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}}$. Also, note
that for every $\boldsymbol{\omega}\in\Omega_{+}$,
$\boldsymbol{\alpha}_{\boldsymbol{\omega}}$ is a $d$-dimensional vector and
$\gamma_{\boldsymbol{\omega}}$ a real number.

We claim that
$\mathcal{H}_{\Omega}^{\tilde{B}}\subseteq\mathcal{G}^{\tilde{B}}_{\Omega}$.
We can prove this inclusion directly by finding the corresponding parameters
$(d_{0},(d_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})$,
$(\gamma_{\boldsymbol{\omega}})_{\boldsymbol{\omega}}$ and
$(\boldsymbol{\alpha}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}}$ for each
element $f\in\mathcal{H}_{\Omega}^{\tilde{B}}$, specified by the corresponding
$(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})$.
We can find a valid assignment term by term. We start by noting $d_{0}=a_{0}$.
Next, we spell out the term corresponding to the frequency vector
$\boldsymbol{\omega}$ with the well-known angle sum trigonometric identity

$\displaystyle
d_{\boldsymbol{\omega}}\sin(\boldsymbol{\alpha}_{\boldsymbol{\omega}}\boldsymbol{x}+\gamma_{\boldsymbol{\omega}})$
$\displaystyle=d_{\boldsymbol{\omega}}\cos(\gamma_{\boldsymbol{\omega}})\sin(\boldsymbol{\alpha}_{\boldsymbol{\omega}}\boldsymbol{x})+d_{\boldsymbol{\omega}}\sin(\gamma_{\boldsymbol{\omega}})\cos(\boldsymbol{\alpha}_{\boldsymbol{\omega}}\boldsymbol{x}).$
(49)

Now, for any given $(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}}$ and
$(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}}$, we can set

$\displaystyle d_{\boldsymbol{\omega}}$
$\displaystyle\coloneqq\sqrt{a_{\boldsymbol{\omega}}^{2}+b_{\boldsymbol{\omega}}^{2}},\leavevmode\nobreak\
\boldsymbol{\alpha}_{\boldsymbol{\omega}}\coloneqq\boldsymbol{\omega},\text{
and
}\gamma_{\boldsymbol{\omega}}\coloneqq\arctan(b_{\boldsymbol{\omega}}/a_{\boldsymbol{\omega}}).$
(50)

At this point, it is important to confirm that the assignment is valid within
the restrictions imposed in Eq. (48). To begin with, we note that the $2$-norm
bound from Eq. (38), i.e.
$\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{2}\leq\tilde{B}$,
translates directly into
$\left\lVert(d_{0},(d_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{2}\leq\tilde{B}$,
since
$d_{\boldsymbol{\omega}}^{2}=a_{\boldsymbol{\omega}}^{2}+b_{\boldsymbol{\omega}}^{2}$
for all $\boldsymbol{\omega}$. Additionally, one can also see that the
components of $\boldsymbol{\alpha}_{\boldsymbol{\omega}}$ are nothing but the
frequencies $\omega_{i}$ for each data coordinate, which fall in the interval
$[-K_{i},K_{i}]$ by construction. Finally, as a function $\arctan$ can output
any angle, choosing the branch $[-\pi,\pi)$ is valid. With these, we reach

$\displaystyle
d_{\boldsymbol{\omega}}\sin(\boldsymbol{\alpha}_{\boldsymbol{\omega}}\boldsymbol{x}+\gamma_{\boldsymbol{\omega}})$
$\displaystyle=a_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x})+b_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x}),$
(51)

which has been our goal.

As $\mathcal{G}^{\tilde{B}}_{\Omega}$ arises from a NN whose activation
functions are $1$-Lipschitz, continuous and anti-symmetric, we can use Lemma
17 (stated in Appendix A). For that, we require upper bounds for the $1$-norm
of the weight vector going into each neuron and for the moduli of the biases.
For every neuron in the hidden layer, there are $d$ incoming weights, one for
each data dimension, corresponding to the $d$ input neurons. Each component of
those weight vectors ($\boldsymbol{\alpha}_{\boldsymbol{\omega}}$ in Eq. (48))
takes values in $\in[-K_{i},K_{i}]$ for some $i\in\\{1,\ldots,d\\}$, so the
$1$-norm of such a weight vector is upper bounded by $K$.

At the output neuron, there are $\lvert\Omega_{+}\rvert$ incoming weights
($d_{\boldsymbol{\omega}}$ in Eq. (48)) and we have a bound on the $2$-norm of
this weight vector. Therefore, Hölder’s inequality applied to the $2$-norm
gives the $1$-norm bound

$\left\lVert(d_{\boldsymbol{\omega}})_{\boldsymbol{\omega}}\right\rVert_{1}\leq\tilde{B}\sqrt{\lvert\Omega_{+}\rvert}.$
(52)

With that, we now know that the $1$-norm of any weight vector in the NN is
upper bounded by $\max\\{K,\tilde{B}\sqrt{\lvert\Omega_{+}\rvert}\\}$.

Next, we note that the modulus of the biases is at most $\pi$ in the hidden
layer, and $\tilde{B}$ in the output layer. As a result, we have that the
moduli of the biases in the NN are upper bounded by $\max\\{\pi,\tilde{B}\\}$.
Now that we have collected all the ingredients, we can plug them into Lemma 17
and obtain the bound

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{G}^{\tilde{B}}_{\Omega})$
$\displaystyle\leq\frac{1}{\sqrt{m}}\left(2\pi\max\\{K,\tilde{B}\sqrt{\lvert\Omega_{+}\rvert}\\}\sqrt{2\log(2d)}+\max\\{\pi,\tilde{B}\\}\right)$
(53)
$\displaystyle\leq\mathcal{O}\left(\frac{1}{\sqrt{m}}\max\\{K,\tilde{B}\sqrt{\lvert\Omega\rvert}\\}\sqrt{\log(2d)}\right),$
(54)

where the $\mathcal{O}$ notation refers to the scaling in $|\Omega|$. As
$\mathcal{G}^{\tilde{B}}_{\Omega}$ contains $\mathcal{H}_{\Omega}^{\tilde{B}}$
as a subset, this bound directly implies

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{H}_{\Omega}^{\tilde{B}})\leq\mathcal{O}\left(\frac{1}{\sqrt{m}}\max\\{K,\tilde{B}\sqrt{\lvert\Omega\rvert}\\}\sqrt{\log(2d)}\right),$
(55)

which completes the proof. ∎

In the proof of Lemma 5, we do not bound the empirical Rademacher complexity
of $\mathcal{H}_{\Omega}^{\tilde{B}}$ directly, rather we embed it into a
larger class $\mathcal{G}^{\tilde{B}}_{\Omega}$ whose complexity we then
bound. However, whereas only a discrete set of frequencies is used in
$\mathcal{H}_{\Omega}^{\tilde{B}}$, the class
$\mathcal{G}^{\tilde{B}}_{\Omega}$ allows for a continuum of frequencies. In
Lemma 6, we modify the idea of the previous proof to avoid this overcounting
of frequencies.

######  Lemma 6 (Empirical Rademacher complexity of
$\mathcal{H}_{\Omega}^{\tilde{B}}$—Version $2$).

Let $d,m$, $S\rvert_{x}$, and $\mathcal{H}_{\Omega}^{\tilde{B}}$ be as in
Lemma 4. Then, the empirical Rademacher complexity of
$\mathcal{H}_{\Omega}^{\tilde{B}}$ with respect to $S\rvert_{x}$ can be upper-
bounded as

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{H}_{\Omega}^{\tilde{B}})$
$\displaystyle\leq\mathcal{O}\left(\frac{\tilde{B}}{\sqrt{m}}\sqrt{\lvert\Omega\rvert\log(\lvert\Omega\rvert)}\right).$
(56)

###### Proof.

Analogously to the proof of Lemma 5, we provide an empirical Rademacher
complexity upper bound for a larger function class
$\tilde{\mathcal{H}}_{\Omega}^{\tilde{B}}$. Along the way, we see that the
inclusion
$\mathcal{H}_{\Omega}^{\tilde{B}}\subseteq\tilde{\mathcal{H}}_{\Omega}^{\tilde{B}}$
holds, so that the uniform bound we derive for the larger set is immediately
inherited for the smaller one. We start by defining an auxiliary set of
functions: let $\mathcal{M}_{\Omega}$ be the set of generalized trigonometric
monomials over $\mathbb{R}^{d}$ with frequency values in $\Omega_{+}$, defined
as

$\displaystyle\mathcal{M}_{\Omega}$
$\displaystyle\coloneqq\\{0\\}\cup\left\\{[0,2\pi)^{d}\ni\boldsymbol{x}\mapsto\cos(\boldsymbol{\omega}\boldsymbol{x})\,|\,\boldsymbol{\omega}\in\Omega_{+}\right\\}\cup\left\\{[0,2\pi)^{d}\ni\boldsymbol{x}\mapsto\sin(\boldsymbol{\omega}\boldsymbol{x})\,|\,\boldsymbol{\omega}\in\Omega_{+}\right\\}.$
(57)

Now, recalling that $|\Omega|=2|\Omega_{+}|+1$, we can define the function
class of our current interest as

$\displaystyle\begin{split}\tilde{\mathcal{H}}_{\Omega}^{\tilde{B}}\coloneqq\Bigg{\\{}[0,2\pi)^{d}&\ni\boldsymbol{x}\mapsto
b_{0}+\left\langle\boldsymbol{w},\vec{h}(\boldsymbol{x})\right\rangle\,\\\
&\Bigg{|}\,\vec{h}\in(\mathcal{M}_{\Omega})^{\lvert\Omega\rvert},\text{ and
}b_{0}\in\mathbb{R},\,\boldsymbol{w}\in\mathbb{R}^{\lvert\Omega\rvert}\text{
such that
}\lVert(b_{0},\boldsymbol{w})\rVert_{2}\leq\tilde{B}\Bigg{\\}},\end{split}$
(58)

where we use the notation $\langle\cdot,\cdot\rangle$ for the standard inner
product. Notice how $\tilde{\mathcal{H}}_{\Omega}^{\tilde{B}}$ can be seen as
a class of functions implemented by a single neuron with identity activation
and $2$-norm bounded weights, where the input signals have been pre-processed
by functions from the specified class $\mathcal{M}_{\Omega}$. With this, we
note the inclusion
$\mathcal{H}_{\Omega}^{\tilde{B}}\subseteq\tilde{\mathcal{H}}_{\Omega}^{\tilde{B}}$.

Next, we use Lemma 16 (stated in Appendix A). To use the result, we note that
the activation function of the neuron is the identity $x\mapsto x$ (which is a
$1$-Lipschitz, anti-symmetric function); that $\mathcal{M}_{\Omega}$ contains
the $0$-function; that the modulus of the bias is upper bounded by
$\tilde{B}$; and that we can again use Hölder’s inequality applied to the
$2$-norm to upper bound the $1$-norm of the weight vector as
$\lVert(b_{0},\boldsymbol{w})\rVert_{1}\leq\sqrt{\lvert\Omega\rvert}\lVert(b_{0},\boldsymbol{w})\rVert_{2}\leq\tilde{B}\sqrt{\lvert\Omega\rvert}.$
With these, Lemma 16 gives us the upper bound

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\tilde{\mathcal{H}}_{\Omega}^{\tilde{B}})$
$\displaystyle\leq\frac{\tilde{B}}{\sqrt{m}}+2\cdot\tilde{B}\sqrt{\lvert\Omega\rvert}\,\,\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{M}_{\Omega}).$
(59)

Hence, in order to proceed we need to find an upper bound for the empirical
Rademacher complexity of $\mathcal{M}_{\Omega}$.

We apply Massart’s Lemma (which we recall as Lemma 18 in Appendix A for
completeness) for this last step. Let $A$ be the set of generalized
trigonometric monomials with frequencies in $\Omega_{+}$, evaluated on every
element of $S\rvert_{x}=(\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{m})$, i.e.,

$\displaystyle A$
$\displaystyle\coloneqq\left\\{\left(0_{\vphantom{1}},\ldots,0\right)\right\\}\cup\left\\{\left(\cos({\boldsymbol{\omega}}\boldsymbol{x}_{1}),\ldots,\cos({\boldsymbol{\omega}}\boldsymbol{x}_{m})\right)\,|\,{\boldsymbol{\omega}}\in\Omega_{+}\right\\}\cup\left\\{\left(\sin({\boldsymbol{\omega}}\boldsymbol{x}_{1}),\ldots,\sin({\boldsymbol{\omega}}\boldsymbol{x}_{m})\right)\,|\,{\boldsymbol{\omega}}\in\Omega_{+}\right\\}\subseteq\mathbb{R}^{m}.$
(60)

Note that, by Hölder’s inequality, again applied to the $2$-norm, and since
sine and cosine take values in $[-1,1]$, we have that
$A\subseteq\mathcal{B}_{\sqrt{m}}(0)$, where $\mathcal{B}_{r}(\boldsymbol{c})$
is the ball of radius $r$ in $2$-norm centered at $\boldsymbol{c}$. Now, we
can rewrite the empirical Rademacher complexity and apply Massart’s lemma
(Lemma 18) to get

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{M}_{\Omega})$
$\displaystyle\coloneqq\mathbb{E}_{\sigma}\left[\sup_{h\in\mathcal{M}_{\Omega}}\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\,h(\boldsymbol{x}_{i})\right]$
(61) $\displaystyle=\mathbb{E}_{\sigma}\left[\sup_{\boldsymbol{a}\in
A}\frac{1}{m}\boldsymbol{\sigma}\boldsymbol{a}\right]$ (62)
$\displaystyle\leq\frac{\sqrt{m}}{m}\sqrt{2\log(|A|)}$ (63)
$\displaystyle\leq\frac{1}{\sqrt{m}}\sqrt{2\log(\lvert\Omega\rvert)}.$ (64)

Plugging this into Eq. (59), we obtain

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\tilde{\mathcal{H}}_{\Omega}^{\tilde{B}})$
$\displaystyle\leq\frac{\tilde{B}}{\sqrt{m}}+2\cdot\tilde{B}\sqrt{\lvert\Omega\rvert}\cdot\frac{1}{\sqrt{m}}\sqrt{2\log(\lvert\Omega\rvert)}$
(65)
$\displaystyle\leq\mathcal{O}\left(\frac{\tilde{B}}{\sqrt{m}}\sqrt{\lvert\Omega\rvert\log(\lvert\Omega\rvert)}\right).$
(66)

Recalling again that
$\mathcal{H}_{\Omega}^{\tilde{B}}\subseteq\tilde{\mathcal{H}}_{\Omega}^{\tilde{B}}$
then yields the claimed bound. ∎

###### Proof of Lemma 4.

This follows directly from combining Lemmas 5 and 6. ∎

With this Rademacher complexity bound at hand, we can make use of standard
tools from classical statistical learning theory to derive a generalization
bound.

######  Theorem 7 (Generalization bound for GTPs—Version $1$).

Let $d,m\in\mathbb{N}$. Let $\mathcal{H}_{\Omega}^{\tilde{B}}$ be as defined
in Eq. (36). Let $\ell:\mathbb{R}\times\mathbb{R}\to[0,c]$ be a bounded loss
function such that $\mathbb{R}\ni z\mapsto\ell(y,z)$ is $L$-Lipschitz for all
$y\in\mathbb{R}$. For any $\delta\in(0,1)$ and for any probability measure $P$
on $[0,2\pi)^{d}\times\mathbb{R}$, with probability $\geq 1-\delta$ over the
choice of i.i.d. training data
$S=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{m}\in([0,2\pi)^{d}\times\mathbb{R})^{m}$
of size $m$, for every $f\in\mathcal{H}_{\Omega}^{\tilde{B}}$, the
generalization error can be upper-bounded as

$\displaystyle R(f)-\hat{R}_{S}(f)$
$\displaystyle\leq\mathcal{O}\left(\frac{L\min\left\\{\max\\{K,\tilde{B}\sqrt{\lvert\Omega\rvert}\\}\sqrt{\log(2d)},\tilde{B}\sqrt{\lvert\Omega\rvert\log(\lvert\Omega\rvert)}\right\\}}{\sqrt{m}}+\frac{\sqrt{\log(\nicefrac{{1}}{{\delta}})}}{\sqrt{m}}\right).$
(67)

###### Proof.

The proof of this theorem consists in combining the standard generalization
bound in terms of Rademacher complexity with the Rademacher complexity bounds
from Lemma 4. More precisely, we define
$\smash{\mathcal{G}\subseteq[0,c]^{[0,2\pi)^{d}\times\mathbb{R}}}$ to be the
class of functions that can be obtained by post-composing elements of
$\mathcal{H}_{\Omega}^{\tilde{B}}$ with the loss function $\ell$ – i.e. we
define

$\displaystyle\mathcal{G}$
$\displaystyle\coloneqq\left\\{[0,2\pi)^{d}\times\mathbb{R}\ni(\boldsymbol{x},y)\mapsto\ell(y,f(\boldsymbol{x}))\leavevmode\nobreak\
|\leavevmode\nobreak\ f\in\mathcal{H}_{\Omega}^{\tilde{B}}\right\\}.$ (68)

We then have the following generalization bound (see, e.g., Theorem $3.3$ in
Ref. [20] or Theorem $1.15$ in Ref. [35]): For any probability measure $P$ on
$[0,2\pi)^{d}\times\mathbb{R}$ and for any $\delta>0$, with probability $\geq
1-\delta$ over the choice of an i.i.d. training data set
$S=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{m}\in([0,2\pi)^{d}\times\mathbb{R})^{m}$
of size $m$ drawn according to $P$, we have, for every $g\in\mathcal{G}$,

$\displaystyle\mathbb{E}_{(\boldsymbol{x},y)\sim
P}[g(\boldsymbol{x},y)]-\frac{1}{m}\sum\limits_{i=1}^{m}g(\boldsymbol{x}_{i},y_{i})$
$\displaystyle\leq
2\hat{\mathcal{R}}_{S}(\mathcal{G})+3c\sqrt{\frac{\log(\nicefrac{{2}}{{\delta}})}{2m}}.$
(69)

Note that, when writing $g\in\mathcal{G}$ as
$g(\boldsymbol{x},y)=\ell(y,f(\boldsymbol{x}))$ for some
$f\in\mathcal{H}_{\Omega}^{\tilde{B}}$, we directly have

$\displaystyle\mathbb{E}_{(\boldsymbol{x},y)\sim
P}[g(\boldsymbol{x},y)]-\frac{1}{m}\sum\limits_{i=1}^{m}g(\boldsymbol{x}_{i},y_{i})$
$\displaystyle=R(f)-\hat{R}_{S}(f).$ (70)

That is, Eq. (69) indeed provides a high-probability bound on the
generalization error. Therefore, we now upper-bound the empirical Rademacher
complexity $\hat{\mathcal{R}}_{S}(\mathcal{G})$. To this end, we use
Talagrand’s Lemma (going back to Ref. [46]) and our bounds for the empirical
Rademacher complexity of $\mathcal{H}_{\Omega}^{\tilde{B}}$. As we assume that
$\mathbb{R}\ni z\mapsto\ell(y,z)$ is $L$-Lipschitz for all $y\in\mathbb{R}$,
we can apply Talagrand’s Lemma (Lemma 19) and Lemma 4 to obtain

$\displaystyle\hat{\mathcal{R}}_{S}(\mathcal{G})$
$\displaystyle=\frac{1}{m}\mathbb{E}_{\sigma}\left[\sup\limits_{g\in\mathcal{G}}\sum\limits_{i=1}^{m}\sigma_{i}g(x_{i},y_{i})\right]$
(71)
$\displaystyle=\frac{1}{m}\mathbb{E}_{\sigma}\left[\sup\limits_{f\in\mathcal{H}_{\Omega}^{\tilde{B}}}\sum\limits_{i=1}^{m}\sigma_{i}\ell(y_{i},f(x_{i}))\right]$
(72)
$\displaystyle\leq\frac{L}{m}\mathbb{E}_{\sigma}\left[\sup\limits_{f\in\mathcal{H}_{\Omega}^{\tilde{B}}}\sum\limits_{i=1}^{m}\sigma_{i}f(x_{i})\right]$
(73)
$\displaystyle=L\hat{\mathcal{R}}_{S|_{x}}(\mathcal{H}_{\Omega}^{\tilde{B}})$
(74)
$\displaystyle\leq\mathcal{O}\left(L\frac{\min\left\\{\sqrt{\log(2d)}\max\\{K,\tilde{B}\sqrt{\lvert\Omega\rvert}\\},\tilde{B}\sqrt{\lvert\Omega\rvert\log(\lvert\Omega\rvert)}\right\\}}{\sqrt{m}}\right),$
(75)

where we have denoted by $S|_{x}\coloneqq\\{\boldsymbol{x}_{i}\\}_{i=1}^{m}$
the set of unlabeled training data points. Inserting this bound into Eq. (69)
now gives the stated generalization error bound. ∎

The generalization bound of Theorem 7 can be rewritten as an upper bound on
the number of labeled training examples that suffice to guarantee small
generalization error.

######  Corollary 8 (Number of labeled training examples sufficient for a
small generalization error—Version $1$).

For any $\varepsilon,\delta\in(0,1)$ and for any probability measure $P$ on
$[0,2\pi)^{d}\times\mathbb{R}$, a training data size

$\displaystyle m=m(\varepsilon,\delta)$
$\displaystyle\leq\mathcal{O}\left(\frac{L^{2}\min\left\\{\max\\{K^{2},\tilde{B}^{2}\lvert\Omega\rvert\\}\log(2d),\tilde{B}^{2}\lvert\Omega\rvert\log(\lvert\Omega\rvert)\right\\}}{\varepsilon^{2}}+\frac{c^{2}\log(\nicefrac{{1}}{{\delta}})}{\varepsilon^{2}}\right)$
(76)

suffices to guarantee that, with probability $\geq 1-\delta$ over the choice
of i.i.d. training data $S\in([0,2\pi)^{d}\times\mathbb{R})^{m}$ of size $m$,
$R(f)-\hat{R}_{S}(f)\leq\varepsilon$ holds for every
$f\in\mathcal{H}_{\Omega}^{\tilde{B}}$.

###### Proof.

We set the upper bound on the generalization error proven in Theorem 7 equal
to $\varepsilon$ and solving for $m$. ∎

######  Remark 9.

The proof strategy for obtaining Rademacher complexity bounds of generalized
trigonometric polynomials presented here easily extends beyond the case in
which the $2$-norm of the vector of Fourier coefficients is assumed to be
bounded. Namely, if we consider, for $1\leq p\leq\infty$, the class

$\displaystyle\mathcal{H}_{\Omega}^{\tilde{B},p}\coloneqq\left\\{[0,2\pi)^{d}\ni\boldsymbol{x}\mapsto\frac{a_{0}}{2}+\sum\limits_{\boldsymbol{\omega}\in\Omega_{+}}\left(a_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x})+b_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x})\right)\leavevmode\nobreak\
\Bigg{|}\leavevmode\nobreak\
\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{p}\leq\tilde{B}\right\\},$
(77)

with Fourier coefficients of a bounded $p$-norm, we obtain, with essentially
the same proof, an empirical Rademacher complexity bound of

$\displaystyle\hat{\mathcal{R}}_{S\rvert_{x}}(\mathcal{H}_{\Omega}^{\tilde{B},p})$
$\displaystyle\leq\tilde{\mathcal{O}}\left(\frac{\tilde{B}\lvert\Omega\rvert^{\frac{1}{q}}}{\sqrt{m}}\right),$
(78)

where $q\in[0,1]$ is the Hölder conjugate of $p$, i.e.,
$\nicefrac{{1}}{{p}}+\nicefrac{{1}}{{q}}=1$, and the $\tilde{\mathcal{O}}$
hides a logarithmic dependence on $\lvert\Omega\rvert$. This, in turn, leads
(for $c$-bounded $L$-Lipschitz loss) to a generalization error bound of

$\displaystyle R(f)-\hat{R}_{S}(f)$
$\displaystyle\leq\tilde{\mathcal{O}}\left(\frac{L\tilde{B}\lvert\Omega\rvert^{\frac{1}{q}}+c\sqrt{\log(\nicefrac{{1}}{{\delta}})}}{\sqrt{m}}\right),$
(79)

which holds with probability $\geq 1-\delta$ uniformly over
$\mathcal{H}_{\Omega}^{\tilde{B},p}$, for training data of size $m$. These
bounds based on $p$-norms might be of independent interest. For example,
depending on the structure of the trainable part of the PQC, a detailed
analysis might lead to additional structural properties (such as sparsity) of
the set of admissible Fourier coefficients, which could then lend themselves
to an analysis in terms of $p$-norms for $p\neq 2$.

###  5.2 Generalization bounds for generalized trigonometric polynomials via
covering numbers

Similarly to Section 5.1, we first prove a bound on a complexity measure for
the hypothesis class $\mathcal{F}_{\Omega}^{B}$ and then derive a
generalization bound from it. This subsection differs from the previous one in
that we discuss a different complexity measure, covering numbers.

######  Lemma 10 (Covering number bound for GTPs).

Let $d\in\mathbb{N}$ and $\varepsilon>0$. Let $\mathcal{F}_{\Omega}^{B}$ be as
defined in Eq. (16). Also, let $\tilde{B}>0$ be such that
$\mathcal{F}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$. The
$\varepsilon$-covering number of $\mathcal{F}_{\Omega}^{B}$ with respect to
$\left\lVert\cdot\right\rVert_{\infty}$ can be upper-bounded as

$\displaystyle\mathcal{N}(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{\infty},\varepsilon)$
$\displaystyle\leq\mathcal{N}(\mathcal{H}_{\Omega}^{\tilde{B}},\left\lVert\cdot\right\rVert_{\infty},\nicefrac{{\varepsilon}}{{2}})\leq\left(\frac{2\cdot
3\cdot\tilde{B}\sqrt{\lvert\Omega\rvert}}{\varepsilon}\right)^{\lvert\Omega\rvert}.$
(80)

Therefore, the corresponding metric entropy can be upper-bounded as

$\displaystyle\log_{2}\mathcal{N}(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{\infty},\varepsilon)$
$\displaystyle\leq\mathcal{O}\left(\lvert\Omega\rvert[\log(\tilde{B})+\log(\lvert\Omega\rvert)+\log(\nicefrac{{1}}{{\varepsilon}})]\right).$
(81)

###### Proof.

By our assumption on the choice of $\tilde{B}$, we have
$\mathcal{F}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$.
Therefore, according to the approximate monotonicity of covering numbers (see,
e.g., Exercise $4.2.10$ in [47]), we have, for every $\varepsilon>0$,

$\displaystyle\mathcal{N}(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{\infty},\varepsilon)$
$\displaystyle\leq\mathcal{N}(\mathcal{H}_{\Omega}^{\tilde{B}},\left\lVert\cdot\right\rVert_{\infty},\nicefrac{{\varepsilon}}{{2}}).$
(82)

Thus, it remains to prove a covering number bound for
$\mathcal{H}_{\Omega}^{\tilde{B}}$.

Let $\mathcal{N}_{\tilde{\varepsilon}}$ be an $\tilde{\varepsilon}$-covering
net of the ball

$\displaystyle\mathcal{B}$
$\displaystyle\coloneqq\left\\{\boldsymbol{\xi}=(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}})\in\mathbb{R}^{\lvert\Omega\rvert}\,\Big{|}\,\left\lVert\boldsymbol{\xi}\right\rVert_{2}\leq\tilde{B}\right\\}$
(83)

with respect to the metric induced by $\left\lVert\cdot\right\rVert_{2}$ on
$\mathbb{R}^{\lvert\Omega\rvert}$. By definition of
$\mathcal{H}_{\Omega}^{\tilde{B}}$, to every
$f\in\mathcal{H}_{\Omega}^{\tilde{B}}$ we can associate a point
$(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}})\in\mathcal{B}$
such that

$\displaystyle
f(x)=\frac{a_{0}}{2}+\sum_{\boldsymbol{\omega}\in\Omega_{+}}\left(a_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x})+b_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x})\right).$
(84)

Given such a vector of coefficients
$(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}})\in\mathcal{B}$
– which, again, for the sake of notational ease, we write as
$(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}}))$,
omitting the $\Omega_{+}$ everywhere – we can find an element
$(\tilde{a}_{0},(\tilde{a}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}},(\tilde{b}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}\in\Omega_{+}})\in\mathcal{N}_{\tilde{\varepsilon}}$
of the cover that is $\tilde{\varepsilon}$ close in $2$-norm to the
coefficients of $f$, i.e., such that

$\displaystyle\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})-(\tilde{a}_{0},(\tilde{a}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(\tilde{b}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{2}\leq\tilde{\varepsilon}.$
(85)

Define $\tilde{f}$ as the function specified by these new coefficients,

$\displaystyle\tilde{f}(x)$
$\displaystyle=\frac{\tilde{a}_{0}}{2}+\sum_{\boldsymbol{\omega}\in\Omega_{+}}\left(\tilde{a}_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x})+\tilde{b}_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x})\right).$
(86)

We now bound the infinity norm distance between $f$ and $\tilde{f}$ in terms
of the $2$-norm distance between the corresponding coefficients as

$\displaystyle\left\lVert f-\tilde{f}\right\rVert_{\infty}$
$\displaystyle\coloneqq\sup_{\boldsymbol{x}\in[0,2\pi)}\left\lvert
f(\boldsymbol{x})-\tilde{f}(\boldsymbol{x})\right\rvert$ (87)
$\displaystyle\leq\left\lvert\frac{a_{0}}{2}-\frac{\tilde{a}_{0}}{2}\right\rvert+\sup_{\boldsymbol{x}}\sum_{\boldsymbol{\omega}\in\Omega_{+}}\left\lvert(a_{\boldsymbol{\omega}}-\tilde{a}_{\boldsymbol{\omega}})\cos(\boldsymbol{\omega}\boldsymbol{x})+(b_{\boldsymbol{\omega}}-\tilde{b}_{\boldsymbol{\omega}})\sin(\boldsymbol{\omega}\boldsymbol{x})\right\rvert$
(88) $\displaystyle\leq\lvert
a_{0}-\tilde{a}_{0}\rvert+\sum_{\boldsymbol{\omega}\in\Omega_{+}}\left(\lvert
a_{\boldsymbol{\omega}}-\tilde{a}_{\boldsymbol{\omega}}\rvert+\lvert
b_{\boldsymbol{\omega}}-\tilde{b}_{\boldsymbol{\omega}}\rvert\right)$ (89)
$\displaystyle=\left\lVert(a_{0},(a_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(b_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})-(\tilde{a}_{0},(\tilde{a}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(\tilde{b}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\right\rVert_{1}$
(90) $\displaystyle\leq\sqrt{\lvert\Omega\rvert}\,\tilde{\varepsilon}.$ (91)

Here, we have used the triangle inequality and the fact that sine and cosine
can only take values in $[-1,1]$, as well as (in the last step) Hölder’s
inequality with respect to the $2$-norm. That means, if we denote by
$\mathcal{N}_{\mathcal{F}}$ the set of GTPs whose coefficients come from the
cover $\mathcal{N}_{\tilde{\varepsilon}}$, i.e.,

$\displaystyle\mathcal{N}_{\mathcal{F}}\coloneqq\Bigg{\\{}[0,2\pi)^{d}\ni\boldsymbol{x}\mapsto\frac{\tilde{a}_{0}}{2}+\sum_{\boldsymbol{\omega}\in\Omega_{+}}\left(a_{\boldsymbol{\omega}}\cos(\boldsymbol{\omega}\boldsymbol{x})+b_{\boldsymbol{\omega}}\sin(\boldsymbol{\omega}\boldsymbol{x})\right)\Bigg{|}\leavevmode\nobreak\
(\tilde{a}_{0},(\tilde{a}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}},(\tilde{b}_{\boldsymbol{\omega}})_{\boldsymbol{\omega}})\in\mathcal{N}_{\tilde{\varepsilon}}\Bigg{\\}},$
(92)

and if we fix $\tilde{\varepsilon}$ to be
$\tilde{\varepsilon}=\varepsilon/\sqrt{\lvert\Omega\rvert}$, then
$\mathcal{N}_{\mathcal{F}}$ is an $\varepsilon$-covering net of
$\mathcal{H}_{\Omega}^{\tilde{B}}$ with respect to
$\left\lVert\cdot\right\rVert_{\infty}$.
Thus, to finish the proof, it remains to upper bound the cardinality
$\lvert\mathcal{N}_{\mathcal{F}}\rvert\leq\lvert\mathcal{N}_{\tilde{\varepsilon}}\rvert$.
To obtain such a bound, we recall that we only require
$\mathcal{N}_{\tilde{\varepsilon}}$ to be an $\tilde{\varepsilon}$-cover of a
$2$-norm ball of radius $\tilde{B}$ in $\mathbb{R}^{\lvert\Omega\rvert}$ with
respect to the $2$-norm. A simple volumetric argument (presented, e.g., in
section $4$ of Ref. [47]) shows that there exists such a
$\tilde{\varepsilon}$-cover $\mathcal{N}_{\tilde{\varepsilon}}$ of
$\mathcal{B}$ with cardinality

$\displaystyle\lvert\mathcal{N}_{\tilde{\varepsilon}}\rvert$
$\displaystyle\leq\left(\frac{3\cdot\tilde{B}}{\tilde{\varepsilon}}\right)^{\lvert\Omega\rvert}=\left(\frac{3\cdot\tilde{B}\sqrt{\lvert\Omega\rvert}}{\varepsilon}\right)^{\lvert\Omega\rvert}.$
(93)

All in all, we have proven that there exists an $\varepsilon$-covering net of
$\mathcal{H}_{\Omega}^{\tilde{B}}$ with respect to
$\left\lVert\cdot\right\rVert_{\infty}$ whose cardinality is bounded by

$\displaystyle\left(\frac{3\cdot\tilde{B}\sqrt{\lvert\Omega\rvert}}{\varepsilon}\right)^{\lvert\Omega\rvert}.$
(94)

This is exactly the claimed upper bound on the $\varepsilon$-covering number
of $\mathcal{H}_{\Omega}^{\tilde{B}}$, thus completing the proof. ∎

The covering number bound just established implies a generalization bound for
GTPs.

######  Theorem 11 (Generalization bound for generalized trigonometric
polynomials—Version $2$).

Let $d,m\in\mathbb{N}$. Let $\mathcal{F}_{\Omega}^{B}$ be as defined in Eq.
(16). Let $\tilde{B}>0$ be such that
$\mathcal{F}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$. Let
$\ell:\mathbb{R}\times\mathbb{R}\to[0,c]$ be a bounded loss function such that
$\mathbb{R}\ni z\mapsto\ell(y,z)$ is $L$-Lipschitz for all $y\in\mathbb{R}$.
For any $\delta\in(0,1)$ and for any probability measure $P$ on
$[0,2\pi)^{d}\times\mathbb{R}$, with probability $\geq 1-\delta$ over the
choice of i.i.d. training data $S\in([0,2\pi)^{d}\times\mathbb{R})^{m}$ of
size $m$, for every $f\in\mathcal{F}_{\Omega}^{B}$, the generalization error
can be upper-bounded as

$\displaystyle R(f)-\hat{R}_{S}(f)$
$\displaystyle\leq\mathcal{O}\left(BL\sqrt{\frac{\lvert\Omega\rvert(\log(\lvert\Omega\rvert)+\log(\tilde{B}))}{m}}+c\,\sqrt{\frac{\log(\nicefrac{{1}}{{\delta}})}{m}}\right)$
(95)

###### Proof.

The proof consists of three steps. First, we use the chaining technique from
random process theory to upper bound the (empirical) Rademacher complexity in
terms of an integral over the square root of the uniform empirical metric
entropy. Second, we show that the metric entropy with respect to
$\left\lVert\cdot\right\rVert_{\infty}$ upper-bounds the uniform empirical
metric entropy, so we can use the bound in Lemma 10 to upper-bound the
(empirical) Rademacher complexity of generalized trigonometric polynomials.
Third, we again use the standard generalization bound based on empirical
Rademacher complexities.

Similarly to the proof of Theorem 7, we define

$\displaystyle\mathcal{G}$
$\displaystyle\coloneqq\left\\{[0,2\pi)^{d}\times\mathbb{R}\ni(\boldsymbol{x},y)\mapsto\ell(y,f(\boldsymbol{x}))\leavevmode\nobreak\
\big{|}\leavevmode\nobreak\ f\in\mathcal{F}_{\Omega}^{B}\right\\}.$ (96)

Again, since we assume that $\mathbb{R}\ni z\mapsto\ell(y,z)$ is $L$-Lipschitz
for all $y\in\mathbb{R}$, Talagrand’s Lemma (Lemma 19 in Appendix A) tells us
that

$\displaystyle\hat{\mathcal{R}}_{S}(\mathcal{G})\leq
L\hat{\mathcal{R}}_{S|_{x}}(\mathcal{F}_{\Omega}^{B}),$ (97)

where we have denoted by $S|_{x}\coloneqq\\{\boldsymbol{x}_{i}\\}_{i=1}^{m}$
the unlabeled training data points. Next, Dudley’s Theorem (which we recall as
Theorem 20 in Appendix A), yields

$\displaystyle\hat{\mathcal{R}}_{S|_{x}}(\mathcal{F}_{\Omega}^{B})$
$\displaystyle\leq\frac{12}{\sqrt{m}}\int\limits_{0}^{\gamma_{0}}\sqrt{\log\mathcal{N}(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{2,S|_{x}},\beta)}\leavevmode\nobreak\
\mathrm{d}\beta,$ (98)

where $\left\lVert\cdot\right\rVert_{2,S|_{x}}$ is the (data-dependent) semi-
norm on $\mathbb{R}^{\mathbb{R}^{d}}$ defined as $\left\lVert
f\right\rVert_{2,S|_{x}}:=\left(\frac{1}{m}\sum_{i=1}^{m}\lvert
f(\boldsymbol{x}_{i})\rvert^{2}\right)^{\nicefrac{{1}}{{2}}}$, and we have
defined $\gamma_{0}\coloneqq\sup_{f\in\mathcal{F}_{\Omega}^{B}}\left\lVert
f\right\rVert_{2,S}$.

Now, we note that, for every $f\in\mathcal{F}_{\Omega}^{B}$, $\left\lVert
f\right\rVert_{2,S\rvert_{x}}\leq\left\lVert f\right\rVert_{\infty}$.
Therefore, we have both that
$\gamma_{0}\leq\sup_{f\in\mathcal{F}_{\Omega}^{B}}\left\lVert
f\right\rVert_{\infty}\leq B$ and, that for every $\beta>0$,
$\mathcal{N}(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{2,S\rvert_{x}},\beta)\leq\mathcal{N}(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{\infty},\beta)$.
Hence, we can combine Eq. (98) with our covering number bound from Lemma 10
and further upper bound

$\displaystyle\hat{\mathcal{R}}_{S|_{x}}(\mathcal{F}_{\Omega}^{B})$
$\displaystyle\leq\frac{12}{\sqrt{m}}\int\limits_{0}^{\gamma_{0}}\sqrt{\lvert\Omega\rvert\left(\log(3\cdot\tilde{B})+\log(\sqrt{\lvert\Omega\rvert})+\log\left(\frac{2}{\beta}\right)\right)}\leavevmode\nobreak\
\mathrm{d}\beta$ (99)
$\displaystyle\leq\frac{12}{\sqrt{m}}\sqrt{\lvert\Omega\rvert}\left(\gamma_{0}\sqrt{\log(3\cdot\tilde{B})+\frac{1}{2}\log(\lvert\Omega\rvert)}+\int\limits_{0}^{\gamma_{0}}\sqrt{\log\left(\frac{2}{\beta}\right)}\leavevmode\nobreak\
\mathrm{d}\beta\right)$ (100)
$\displaystyle\leq\frac{12}{\sqrt{m}}\sqrt{\lvert\Omega\rvert}\Bigg{(}B\sqrt{\log(3\cdot\tilde{B})+\frac{1}{2}\log(\lvert\Omega\rvert)}$
(101)
$\displaystyle\hphantom{\leq\frac{12}{\sqrt{m}}\sqrt{\lvert\Omega\rvert}\Bigg{(}\leavevmode\nobreak\
}+B\sqrt{\log\left(\frac{1}{\tilde{B}}\right)}-\frac{\sqrt{\pi}}{2}\operatorname{erf}\left(\sqrt{\log\left(\frac{1}{\tilde{B}}\right)}\right)\Bigg{)}$
(102)
$\displaystyle\leq\mathcal{O}\left(B\sqrt{\frac{\lvert\Omega\rvert(\log(\tilde{B})+\log(\lvert\Omega\rvert))}{m}}\right),$
(103)

where we have used the integral

$\int\sqrt{\log\nicefrac{{1}}{{x}}}\leavevmode\nobreak\
\mathrm{d}x=x\sqrt{\log\nicefrac{{1}}{{x}}}-(\nicefrac{{\sqrt{\pi}}}{{2}})\cdot\operatorname{erf}(\sqrt{\log\nicefrac{{1}}{{x}}}),$
(104)

with the error function defined as

$\operatorname{erf}(x):=\frac{2}{\sqrt{\pi}}\int_{0}^{x}\exp(-t^{2})\leavevmode\nobreak\
\mathrm{d}t.$ (105)

At this point, we again have a bound on the empirical Rademacher complexity at
our disposal. So, just like in the proof of Theorem 7, we can now apply the
standard Rademacher complexity generalization bound. This then tells us that,
for any probability measure $P$ on $[0,2\pi)^{d}\times\mathbb{R}$ and for any
$\delta>0$, with probability $\geq 1-\delta$ over the choice of an i.i.d.
training data set $S$ of size $m$, we have, for every
$f\in\mathcal{F}_{\Omega}^{B}$,

$\displaystyle R(f)-\hat{R}_{S}(f)$ $\displaystyle\leq
2\hat{\mathcal{R}}_{S}(\mathcal{G})+3c\sqrt{\frac{\log(\nicefrac{{2}}{{\delta}})}{2m}}$
(106)
$\displaystyle\leq\mathcal{O}\left(BL\sqrt{\frac{\lvert\Omega\rvert(\log(\lvert\Omega\rvert)+\log(\tilde{B}))}{m}}+c\sqrt{\frac{\log(\nicefrac{{1}}{{\delta}})}{m}}\right),$
(107)

as claimed. ∎

Also for this generalization bound, we provide the reformulation in terms of a
bound on the sample size sufficient to guarantee small generalization error.

######  Corollary 12 (Number of labeled training examples sufficient for a
small generalization error—Version $2$).

Let $d\in\mathbb{N}$. Let $\mathcal{F}_{\Omega}^{B}$ be as defined in Eq.
(16). Let $\tilde{B}>0$ be such that
$\mathcal{F}_{\Omega}^{B}\subseteq\mathcal{H}_{\Omega}^{\tilde{B}}$. Let
$\ell:\mathbb{R}\times\mathbb{R}\to[0,c]$ be an $L$-Lipschitz loss function.
For any $\varepsilon,\delta\in(0,1)$ and for any probability measure $P$ on
$[0,2\pi)^{d}\times\mathbb{R}$, a training data size

$\displaystyle m=m(\varepsilon,\delta)$
$\displaystyle\leq\mathcal{O}\left(B^{2}L^{2}\frac{\lvert\Omega\rvert(\log(\lvert\Omega\rvert)+\log(\tilde{B}))}{\varepsilon^{2}}+c^{2}\frac{\log(\nicefrac{{1}}{{\delta}})}{\varepsilon^{2}}\right),$
(108)

suffices to guarantee that, with probability $\geq 1-\delta$ over the choice
of i.i.d. training data $S\in(\mathbb{R}^{d}\times\mathbb{R})^{m}$ of size
$m$, $R(f)-\hat{R}_{S}(f)\leq\varepsilon$ holds for every
$f\in\mathcal{F}_{\Omega}^{B}$.

###### Proof.

We set the upper bound on the generalization error proven in Theorem 11 equal
to $\varepsilon$ and solving for $m$. ∎

######  Remark 13.

Our metric entropy bounds of trigonometric polynomials presented here again
extend beyond the case of bounded $2$-norm of the vector of Fourier
coefficients to a general bounded $p$-norm. However, if we again consider, for
$1\leq p\leq\infty$, the class $\mathcal{H}_{\Omega}^{\tilde{B},p}$ defined in
Remark 9, our proof strategy here yields essentially – i.e., to leading order
in $\lvert\Omega\rvert$ – the same metric entropy and generalization bounds as
for $p=2$. The reason is that the dimension of the space in which we take
covering nets in the proof of Lemma 10 remains proportional to
$\lvert\Omega\rvert$, independently of $p$. We only see improvements for
$1\leq p<2$ in the terms depending logarithmically on $\lvert\Omega\rvert$.
Therefore, in the case of a constant $\tilde{B}$, while the proof strategies
of Sections 5.1 and 5.2 give essentially the same generalization guarantees
for $p=2$, the approach of Section 5.1 adapts nicely to the case $p<2$,
whereas the reasoning of Section 5.2 is typically preferable for $p>2$.

######  Remark 14.

The proof of Theorem 11 extends beyond Lipschitz loss functions. For example,
suppose that $\mathbb{R}\ni z\mapsto\ell(y,z)$ is $\alpha$-Hölder continuous
with Hölder coefficient $A>0$ for all $y\in\mathbb{R}$, where
$\alpha\in(0,1)$. Then, with the notation of the above proof,

$\displaystyle\mathcal{N}(\mathcal{G},\left\lVert\cdot\right\rVert_{2,S},\beta)\leq\mathcal{N}\left(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{2\alpha,S\rvert_{x}},\left(\nicefrac{{\beta}}{{A}}\right)^{\nicefrac{{1}}{{\alpha}}}\right).$
(109)

We can thus apply Dudley’s Theorem to upper bound

$\displaystyle\hat{\mathcal{R}}_{S}(\mathcal{G})$
$\displaystyle\leq\frac{12}{\sqrt{m}}\int\limits_{0}^{\tilde{\gamma}_{0}}\sqrt{\mathcal{N}\left(\mathcal{F}_{\Omega}^{B},\left\lVert\cdot\right\rVert_{2\alpha,S\rvert_{x}},\left(\nicefrac{{\beta}}{{A}}\right)^{\nicefrac{{1}}{{\alpha}}}\right)}\leavevmode\nobreak\
\mathrm{d}\beta.$ (110)

Now, we again observe that
$\left\lVert\cdot\right\rVert_{2\alpha,S\rvert_{x}}\leq\left\lVert\cdot\right\rVert_{\infty}$
and upper bound the covering number integral, using our result from Lemma 10.
The parameters of the Hölder continuity enter the final Rademacher complexity
bound via a term scaling with $\sqrt{\nicefrac{{\log(A)}}{{\alpha}}}$.

##  6 Encoding-dependent generalization bounds for parametrized quantum
circuits

We are finally in a position to answer the questions posed in Section 2.
Recall that our first goal was to derive generalization bounds for PQC-based
models which depend explicitly on architectural hyper-parameters related to
the data-encoding strategy. We showed in Section 3 how PQC-based model classes
can be viewed as a subset of generalized trigonometric polynomials (GTPs),
whose set of frequencies $\Omega$ is determined solely by the data-encoding
strategy $\mathcal{D}$. We then derived complexity and generalization bounds
for GTPs in terms of the number of different frequencies
$|\Omega(\mathcal{D})|$. In order to provide explicitly encoding-dependent
generalization bounds for PQC-based models, it remains to express
$|\Omega(\mathcal{D})|$ in terms of the relevant architectural hyper-
parameters associated with different data-encoding strategies.

To do so, we recall that the data-encoding strategy of a PQC-based model class
is defined as a collection of lists of data-encoding Hamiltonians
$\mathcal{D}^{(i)}=\\{H_{j}^{(i)}\\}$ associated with each coordinate
$x^{(i)}$. We distinguish different data-encoding strategies according to the
different assumptions made on the structure of the data-encoding Hamiltonians
$H\in\mathcal{D}^{(i)}$. Given a particular assumption, for example that all
$H$ are tensor products of Pauli operators or at most $\kappa$-local, the
natural hyper-parameter associated with the data encoding strategy is the
number $N=\sum_{i=1}^{d}|\mathcal{D}^{(i)}|$ of data-encoding Hamiltonians of
the assumed type. Hence, our goal in this section is to derive, for different
data-encoding strategies, upper bounds on $|\Omega(\mathcal{D})|$ that depend
on $N$ as well as as on other relevant properties of the data-encoding
Hamiltonians (such as, e.g., the locality $\kappa$). By substituting these
upper bounds on $|\Omega|$ into the GTP generalization bounds of the previous
section, we then obtain generalization bounds for PQC-based model classes
which depend explicitly on properties of the data-encoding strategy.

We first recall the definition of $\Omega$ from Eq. (30). If we denote the
Hamiltonians of the data-encoding strategy associated with $x^{(i)}$ as
$\\{H_{j}^{(i)}\\}$, we can group the frequencies associated with each data
coordinate into a separate sumset $\Omega^{(i)}$:

$\displaystyle\Omega(\mathcal{D})=\sum_{i=1}^{d}\sum_{j=1}^{N^{(i)}}\Omega\left(H_{j}^{(i)}\right)=\sum_{i=1}^{d}\Omega^{(i)}.$
(111)

The frequencies belonging to the different coordinates $\\{x^{(i)}\\}$ are
linearly independent because they were defined to be multiples of different
standard basis vectors $\boldsymbol{e}^{(i)}$. This implies that the
cardinality of the full set is equal to the product of the individual
cardinalities,

$\displaystyle|\Omega|=\prod_{i=1}^{d}|\Omega^{(i)}|,$ (112)

thus allowing us to multiply bounds on the cardinalities obtained for the
separate data-encoding strategies, $|\Omega^{(i)}|$, to obtain a bound on
$|\Omega|$.

As the underlying frequencies in $\Omega^{(i)}$ are all scalar multiples of
the same basis vector $\boldsymbol{e}^{(i)}$, the analysis of $\Omega^{(i)}$
comes down to the different frequencies generated by the Hamiltonians that are
used to encode $x^{(i)}$. For a given single Hamiltonian $H$, we denote this
set by

$\displaystyle\Delta(H)\coloneqq\\{\lambda_{i}-\lambda_{j}\,|\,\lambda_{i},\lambda_{j}\in\operatorname{spec}(H)\\}$
(113)

so that

$\displaystyle\Omega(H)=\left\\{\left.\delta\boldsymbol{e}\,\right|\,\delta\in\Delta\left(H\right)\right\\},$
(114)

where $\boldsymbol{e}$ is the basis vector associated to the respective
coordinate. Next, we derive some bounds on $|\Omega^{(i)}|$ for different
assumptions on the underlying Hamiltonians.

Worst case upper bounds. We first derive the worst-case limits of
$|\Omega^{(i)}|$ for $\kappa$-local encoding Hamiltonians. A $\kappa$-local
Hamiltonian $H$ has local dimension $2^{\kappa}$ and the number of possible
differences of eigenvalues in the spectrum is thus upper bounded as

$\displaystyle|\Delta(H)|\leq\frac{2^{\kappa}(2^{\kappa}-1)}{2}+1=\mathcal{O}(2^{2{\kappa}}).$
(115)

One can in principle construct a Hamiltonian that saturates this bound by
choosing $\operatorname{spec}(H_{\max})=\\{0,3,9,\dots,3^{2^{\kappa}}\\}$, but
this is a rather synthetic example that we do not expect to encounter on real
hardware. Eq. (115) implies that repeating $N^{(i)}$ $\kappa$-local
Hamiltonians will, in the case where there are no duplicates in the frequency
set, imply a cardinality of at most

$\displaystyle|\Omega^{(i)}|\leq\left(\frac{2^{\kappa}(2^{\kappa}-1)}{2}+1\right)^{N^{(i)}}=\mathcal{O}(2^{2{\kappa}N^{(i)}}).$
(116)

Again, this bound can be saturated by choosing Hamiltonians with ever-larger
spectra, namely by choosing $H_{1}^{(i)}=H_{\max}$ and
$\operatorname{spec}(H_{j+1}^{(i)})=\max(\operatorname{spec}(H_{j}^{(i)}))\cdot\operatorname{spec}(H_{\max})$.

Repeated Hamiltonians. We now consider the case where the same Hamiltonian
$H^{(i)}$ is used $N^{(i)}$ times to encode the coordinate $x^{(i)}$. Due to
the underlying symmetry of the definition of $\Delta(H^{(i)})$, we have that

$\displaystyle\Delta(H^{(i)})=\\{0,\pm\delta_{1},\dots,\pm\delta_{T}\\}$ (117)

for some $T$, and therefore
$|\Delta(H^{(i)})|=2T+1=|\Omega_{j}^{(i)}|=|\Omega_{0}^{(i)}|$, where we have
denoted the repeated set of frequencies common to all encoding gates as
$\Omega_{0}^{(i)}$. Using the results on the maximum size of the spectrum of a
$\kappa$-local Hamiltonian in Eq. (115), we can deduce that $T\leq
2^{\kappa-2}(2^{\kappa}-1)$. We now quantify the number of different
frequencies in $\Omega^{(i)}$ in terms of $T$. $N^{(i)}$ repetitions of the
fixed Hamiltonian with frequencies $\Omega_{0}^{(i)}$ result in a set of
frequencies that contains all possible combinations of $N^{(i)}$ vectors
$\boldsymbol{\omega}_{j}$ from $\Omega_{0}^{(i)}$:

$\displaystyle\Omega^{(i)}$
$\displaystyle=\left\\{\left.\sum_{j=1}^{N^{(i)}}\boldsymbol{\omega}_{j}\,\right|\,\boldsymbol{\omega}_{j}\in\Omega_{0}^{(i)}\text{
for all }j\right\\}$ (118)

We can reformulate this by counting how often the $2T+1$ different elements of
$\Omega_{0}^{(i)}$ are present in a particular instance of the above sum, and
get

$\displaystyle\Omega^{(i)}$
$\displaystyle=\left\\{\left.\sum_{\boldsymbol{\omega}\in\Omega_{0}^{(i)}}N_{\boldsymbol{\omega}}\boldsymbol{\omega}\,\right|\,N_{\boldsymbol{\omega}}\geq
0,\sum_{\boldsymbol{\omega}\in\Omega_{0}^{(i)}}N_{\boldsymbol{\omega}}=N^{(i)}\right\\}.$
(119)

To bound the size of this set, we exploit the symmetry of the underlying
frequencies $\delta_{j}\in\Delta(H^{(i)})$. Let us outline the idea: We will
first count how we can distribute the number $N^{(i)}$ of repetitions over the
different non-negative frequencies $\delta_{j}$ and then multiply this with
the number of different frequencies that can be created by repeating
$\delta_{j}$ and $-\delta_{j}$. To improve the scaling we get at the end, we
will resort to a small trick and actually group the frequency $0$, which we
know to always be present in the spectrum, with the first other frequency,
therefore considering the combinatoric problem of distributing $N^{(i)}$
“balls” over $T$ distinguishable “bins” where some bins can be empty. The
different possible ways to achieve this task are given by counting the _weak
compositions_ of $N^{(i)}$ into $T$ parts, $\mathcal{C}(N^{(i)},T)$. The
number of such weak compositions is

$\displaystyle|\mathcal{C}(N^{(i)},T)|$
$\displaystyle=\begin{pmatrix}N^{(i)}+T-1\\\ N^{(i)}\end{pmatrix}$ (120)
$\displaystyle=\frac{(N^{(i)}+T-1)!}{N^{(i)}!(T-1)!}$ (121)
$\displaystyle=\frac{(N^{(i)}+T-1)(N^{(i)}+T-2)\dots(N^{(i)}+1)}{(T-1)!}$
(122) $\displaystyle=\mathcal{O}((N^{(i)})^{T-1}).$ (123)

We will denote such a composition as
$(N_{j}^{(i)})_{j=1}^{T}\in\mathcal{C}(N^{(i)},T)$. A simple counting argument
reveals that there are $2N_{1}^{(i)}+1$ possible sums with $N_{1}^{(i)}$
elements from the set $\\{0,\delta_{1},-\delta_{1}\\}$ and $N_{j}^{(i)}+1\leq
2N_{j}^{(i)}+1$ possible sums with $N_{j}^{(i)}$ elements from the set
$\\{\delta_{j},-\delta_{j}\\}$. We can therefore bound

$\displaystyle|\Omega^{(i)}|$
$\displaystyle\leq\sum_{(N_{k}^{(i)})\in\mathcal{C}(N^{(i)},T)}\prod_{k=1}^{T}\left(2N_{k}^{(i)}+1\right)$
(124)
$\displaystyle\leq\sum_{(N_{k}^{(i)})\in\mathcal{C}(N^{(i)},T)}\left(\frac{2\sum_{k=1}^{T}N_{k}^{(i)}}{T}+1\right)^{T}$
(125)
$\displaystyle\leq\sum_{(N_{k}^{(i)})\in\mathcal{C}(N^{(i)},T)}\left(\frac{2N^{(i)}}{T}+1\right)^{T}$
(126)
$\displaystyle=|\mathcal{C}(N^{(i)},T)|\left(\frac{2N^{(i)}}{T}+1\right)^{T}$
(127) $\displaystyle=\mathcal{O}((N^{(i)})^{2T-1}),$ (128)

where we have used the arithmetic-geometric mean inequality to obtain the
second inequality. From this inequality, we see that by repeating the same
Hamiltonian for an encoding, we obtain a polynomial scaling in the number of
repetitions whose exponent depends on the number of different frequencies
generated by the repeated Hamiltonian.

Pauli encodings. Encodings performed with Hamiltonians that are a tensor
product of Pauli operators, $H=\bigotimes_{k=1}^{n}P^{(k)}$ where
$P^{(k)}\in\\{\mathbb{I},X,Y,Z\\}$, have been analyzed in Ref. [33]. Therein,
it was shown that $N^{(i)}$ repetitions of such encodings of arbitrary
dimension will result in $|\Omega^{(i)}|=2N^{(i)}+1$ and
$\Omega^{(i)}\subseteq\boldsymbol{e}^{(i)}\mathbb{Z}\subseteq\mathbb{Z}^{d}$.

Summary. We can easily connect the different upper bounds on $|\Omega^{(i)}|$
to upper bounds on $|\Omega|$ via the arithmetic-geometric mean inequality,
i.e.,

$\displaystyle\prod_{i=1}^{d}|\Omega^{(i)}|\leq\left(\sum_{i=1}^{d}\frac{|\Omega^{(i)}|}{d}\right)^{d},$
(129)

and by noting that, for $q\geq 1$,

$\displaystyle\sum_{i=1}^{d}\frac{(N^{(i)})^{q}}{d}\leq\frac{\left(\sum_{i=1}^{d}N^{(i)}\right)^{q}}{d}=\frac{N^{q}}{d}.$
(130)

Table 1 summarizes the different upper bounds on $|\Omega^{(i)}|$ for
individual parameters $x^{(i)}$ derived in this section as well as the
associated bounds on $|\Omega|$.

Table 1: Scaling of the different upper bounds for the number of different frequencies for the encoding of a single parameter $|\Omega^{(i)}|$, as well as the associated bounds for the scaling of the number of different frequencies for the total data-encoding strategy, $|\Omega|$. $N^{(i)}$ denotes the number of gates used for encoding the input $x^{(i)}$, $N$ denotes the total number of gates for all inputs. Encoding strategy | Upper bound on $|\Omega^{(i)}|$ | Upper bound on $|\Omega|$
---|---|---
Repetition of arbitrary Pauli encodings | $\displaystyle\mathcal{O}\left(N^{(i)}\right)$ | $\displaystyle\mathcal{O}\left(\left(\frac{N}{d}\right)^{d}\right)$
Repetition of the same encoding
with $2T+1$ frequencies | $\displaystyle\mathcal{O}\left((N^{(i)})^{2T-1}\right)$ | $\displaystyle\mathcal{O}\left(\left(\frac{N^{2T-1}}{d}\right)^{d}\right)$
Repetition of the same $\kappa$-local encoding | $\displaystyle\mathcal{O}\left((N^{(i)})^{2^{\kappa+1}-1}\right)$ | $\displaystyle\mathcal{O}\left(\left(\frac{N^{2^{\kappa+1}-1}}{d}\right)^{d}\right)$
Different $\kappa$-local encodings | $\displaystyle\mathcal{O}\left(2^{2\kappa N^{(i)}}\right)$ | $\displaystyle\mathcal{O}\left(2^{2\kappa N}\right)$

Given these results, we are finally in a position to provide a concrete answer
to the first question posed in Section 2. More specifically, by substituting
the upper bounds on $|\Omega|$ given in Table 1 into the generalization bounds
for GTPs given in Section 5, we can obtain generalization bounds for PQC-based
model classes which depend explicitly on architectural hyper-parameters
associated with the data-encoding strategy. Recall that we denoted the
function class associated with a particular set of parameters $\Theta$, an
encoding strategy $\mathcal{D}$ and an observable $M$, as
$\mathcal{F}_{\Theta,\mathcal{D},M}$. We then obtain from Theorems 7 and 11
the following Corollary:

######  Corollary 15 (Generalization bound for PQCs—From Theorems 7 and 11).

Let $d,m\in\mathbb{N}$. Let $\ell:\mathbb{R}\times\mathbb{R}\to[0,c]$ be a
bounded loss function such that $\mathbb{R}\ni z\mapsto\ell(y,z)$ is
$L$-Lipschitz for all $y\in\mathbb{R}$. For any $\delta\in(0,1)$ and for any
probability measure $P$ on $[0,2\pi)^{d}\times\mathbb{R}$, with probability
$\geq 1-\delta$ over the choice of i.i.d. training data
$S=\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{m}\in([0,2\pi)^{d}\times\mathbb{R})^{m}$
of size $m$ and every $f\in\mathcal{F}_{\Theta,\mathcal{D},M}$, where
$\mathcal{D}$ is an encoding strategy with $N$ gates in total, we have that,

  1. (a)

if $\mathcal{D}$ denotes any data-encoding strategy consisting of Hamiltonians
that are tensor products of Pauli operators,

$\displaystyle R(f)-\hat{R}_{S}(f)\leq\tilde{\mathcal{O}}\left(\frac{L\lVert
M\rVert_{\infty}}{\sqrt{m}}\left(\frac{N}{d}\right)^{\frac{d}{2}}+c\sqrt{\frac{\log\nicefrac{{1}}{{\delta}}}{m}}\right),$
(131)

  2. (b)

if $\mathcal{D}$ denotes any data-encoding strategy consisting of the same
single Hamiltonian with $T$ integer frequencies per data coordinate,

$\displaystyle R(f)-\hat{R}_{S}(f)\leq\tilde{\mathcal{O}}\left(\frac{L\lVert
M\rVert_{\infty}}{\sqrt{m}}\left(\frac{N^{2T-1}}{d}\right)^{\frac{d}{2}}+c\sqrt{\frac{\log\nicefrac{{1}}{{\delta}}}{m}}\right),$
(132)

  3. (c)

if $\mathcal{D}$ denotes any data-encoding strategy consisting of the same
single $\kappa$-local Hamiltonian with integer frequencies per data
coordinate,

$\displaystyle R(f)-\hat{R}_{S}(f)\leq\tilde{\mathcal{O}}\left(\frac{L\lVert
M\rVert_{\infty}}{\sqrt{m}}\left(\frac{N^{2^{\kappa+1}-1}}{d}\right)^{\frac{d}{2}}+c\sqrt{\frac{\log\nicefrac{{1}}{{\delta}}}{m}}\right),$
(133)

  4. (d)

if $\mathcal{D}$ denotes any data-encoding strategy consisting of possibly
different $\kappa$-local Hamiltonians with integer frequencies per data
coordinate,

$\displaystyle R(f)-\hat{R}_{S}(f)\leq\tilde{\mathcal{O}}\left(\frac{L\lVert
M\rVert_{\infty}}{\sqrt{m}}\,2^{\kappa
N}+c\sqrt{\frac{\log\nicefrac{{1}}{{\delta}}}{m}}\right).$ (134)

While we consider only four specific data-encoding strategies in this
corollary, the generalization bounds from Theorems 7 and 11 can in principle
be applied to PQC-based models with _any_ data-encoding strategy. To use the
bounds, the corresponding $\lvert\Omega(\mathcal{D})\rvert$ has to be
identified, which can then be readily combined with our generalization bounds
for GTPs. Additionally, if Conjecture 1 is correct, then the statements of
Corollary 15(b)-(d) are true also for data-encoding Hamiltonians leading to
non-integer frequencies.

###  6.1 Comparison of data-encoding strategies from a generalization
perspective

The results of the previous subsection give a concrete answer to the first
question posed in Section 2, namely explicitly encoding-dependent
generalization bounds for PQC-based models. However, recall from Section 2
that we also aimed to use such bounds to identify data-encoding strategies
which give rise to a slow (polynomial) growth of model complexity with respect
to increasingly complex data-encoding strategies, and therefore facilitate
meaningful model selection via structural risk minimization. The results of
the previous section now allow us to address this additional goal.

Given an assumption or constraint on the structure of the data-encoding
Hamiltonians in a possible data-encoding strategy, the most natural data-
encoding hyper-parameter for structural risk minimization is the number $N$ of
encoding Hamiltonians. We see that using either repeated Pauli Hamiltonians, a
repeated (but fixed) $\kappa$-local Hamiltonian, or the repetition of a fixed
Hamiltonian with $2T+1$ frequencies, leads to a complexity bound and