# High Dimensional Quantum Machine Learning With Small Quantum Computers

S. C. Marshall<EMAIL_ADDRESS>C. Gyurik  V. Dunjko  Leiden
University, Leiden, The Netherlands

###### Abstract

Quantum computers hold great promise to enhance machine learning, but their
current qubit counts restrict the realisation of this promise. In an attempt
to placate this limitation techniques can be applied for evaluating a quantum
circuit using a machine with fewer qubits than the circuit naively requiresTo
deal with this limitation the community has produced a set of techniques for
evaluating large quantum circuits on smaller quanutm devices. These techniques
work by evaluating many smaller circuits on the smaller machine, that are then
combined in a polynomial to replicate the output of the larger machine. This
scheme requires more circuit evaluations than are practical for general
circuits. However, we investigate the possibility that for certain
applications many of these subcircuits are superfluous, and that a much
smaller sum is sufficient to estimate the full circuit. We construct a machine
learning model that may be capable of approximating the outputs of the larger
circuit with much fewer circuit evaluations. We successfully apply our model
to the task of digit recognition, using simulated quantum computers much
smaller than the data dimension. The model is also applied to the task of
approximating a random 10 qubit PQC with simulated access to a 5 qubit
computer, even with only relatively modest number of circuits our model
provides an accurate approximation of the 10 qubit PQCs output, superior to a
neural network attempt. The developed method might be useful for implementing
quantum models on larger data throughout the NISQ era.

††preprint: APS/123-QED

##  I Introduction

Quantum machine learning is often listed as one of the most promising
applications of a near term quantum computer [preskill2018], with important
early successes in a range of problems, from classification
[havlivcek2019supervised, schuld2019quantum] to generative modelling
[liu2018differentiable]. However the broader roll out of these methods to real
world problems is tempered, in part, by the limited size of quantum computers.
Among other limitations, current quantum computers lack enough qubits to run
large circuits. Some “circuit partitioning schemes” [bravyi2016, peng2020,
mitarai2021constructing] have been proposed to simulate larger circuits on
smaller devices by partitioning the full circuit into a set of smaller
circuits (see figure 1). However, the exponential number of circuits needed by
these schemes is completely intractable for most applications, with billions
of sub-circuit evaluations required for even modest quantum machine learning
instances.

In this work we examine the necessity of each subcircuit in producing an
approximation of some partitioned circuit, presenting reasoning that a smaller
amount of circuits could be sufficient in some cases. We then use this as
inspiration for a new machine learning technique, which reconciles the need
for larger circuit instances with affordable runtimes. Our new technique takes
the same form as a given generic machine learning architecture that has been
partitioned using the aforementioned techniques but with vastly fewer terms.

We develop the basic theory behind this technique in Section III, consider its
generalisation error in Section IV and test it experimentally in Section VI on
an instances of handwritten digit recognition using a 64 qubit ansatz with
access to only a simulated 8 qubit computer (without use of excessive
dimensionality reduction, such as dimensional principal component analysis).
We also include an experiment testing the model’s ability to replicate the
output of larger unpartitioned circuits. Error analysis and the specifics of
an evaluation and training schemes are presented in Section V.

Figure 1: The fundamental notion of circuit partitioning. A potential
partition (peach coloured and mint coloured) exists but is joined by a 2-qubit
gate, $G$. By expressing $G$ as a sum of single qubit unitaries $u_{i}$ and
$u_{i}^{\prime}$ we can simulate the ouput of the large circuit by only
running circuits on either element of the partition (which requires a smaller
quantum computer).

##  II Related work

We are not the first to consider how the partitioning schemes [bravyi2016,
peng2020, mitarai2021constructing] could be made more efficient, whereas other
research lines have focused on minimising the computational cost of applying
the exact partitioning schemes (e.g. by minimising the number of gates cut),
we focus on shrinking the number of subcircuits to approximate the output. As
such many of the techniques in this section can be composed with our method to
create an even more efficient scheme.

In [tang2021cutqc] an automated cutting procedure is applied to [peng2020] to
produce the minimum number of subcircuits needed, similarly
[perlin2021quantum] uses maximum likelihood fragment tomography to improve
both the cutting process and the reconstruction of output states. Other
authors have considered how the set of subcircuits could be run more
effectively by utilising distributed computational resources
[saleem2021quantum, bechtold2021bringing].

Using partitioning schemes produces an additional benefit: reduced noise,
stemming from the smaller circuit size [tang2021cutqc, avron2021quantum], this
can be the motivation for cut selection, even when the full circuit would
“fit” on a quantum machine [basu2021qer]. This noise reduction is similar to
the increased accuracy we may be able to provide to gradients in our model.
The potential link between this, and the avoidance of barren plateaus in our
model we will discuss in Section V.

After developing our technique we will demonstrate its use on high
dimensionality data, specifically handwritten digit recognition. This problem
has been tackled before with quantum hardware. In [haug2021large],
dimensionality reduction techniques (such as principal component analysis) are
used to reduce the dimensionality of the digits to a feature vector small
enough to fit on their 8 qubit machine. Similarly, in [li2021quantum]
handwritten digits are classified on an 8 qubit machine, in this instance the
size of the data is not reduced, the full data is carefully encoded into the
quantum computer, first with amplitude encoding, and then by using 11 layers
of parameterised gates. Our approach is fundamentally different from either of
these. We use the same sized data (8$\times$8 pixels) but do not apply
dimensionality reduction as in [haug2021large], or reuse qubits for multiple
data points as in [li2021quantum]. We follow a simple encoding: giving each
pixel its own qubit, which we can achieve as we are approximating a 64 qubit
machine, while only using an 8 qubit machine.

Other works have addressed high dimensionality data by pushing the limit of
the size of quantum machine learning models on current devices
[peters2021machine]. Some have employed quantum circuits as components of some
larger algorithm to tackle bigger problems: [fujii2022deep] recursively
applies PQCs to the outputs of PQCs and [yuan2021quantum] uses quantum
circuits as part of a hybrid tensor network but both do not address the task
of partitioning a larger circuit and running it efficiently as we do here.

##  III Model Motivation and Specification

In this section we introduce parameterised quantum circuits (PQCs), a popular
concept in quantum machine learning; and circuit partitioning, a method of
evaluating quantum circuits that requires a number of qubits greater than what
is accessible. By applying these circuit partitioning schemes to PQCs we can
produce a more powerful machine learning model than the smaller device naively
allows, at the cost of unreasonable runtime. We then go on to develop a novel
QML method which intuitively may be as useful requiring only a fraction of the
runtime.

###  III.1 Parameterised Quantum Circuits

Parameterised quantum circuits (PQCs) are a varied and promising method for
quantum machine learning. In general they consist of some set of circuits,
$\mathbb{U}$, parameterised by a weight vector, $\bm{\theta}$. In the most
common forms the input datum, $\bm{x}$, also parameterises gates in the
circuit. The set can be indexed as $\mathbb{U}=\\{U(\bm{x};\bm{\theta})\\}$.
These circuits yield functions when we specify an initial state,
$|{\phi}\rangle$, and an observable, $M$:

$f_{\bm{\theta},M,|{\phi}\rangle}(x)=\langle{\phi}|U^{\dagger}(\bm{\theta},\bm{x})MU(\bm{\theta},\bm{x})|{\phi}\rangle$
(1)

We can assume $|{\phi}\rangle$ is some fiducial state, such as
$|{0}\rangle^{\otimes n}$ in the computational basis, without loss of
generality.

As each setting of $\bm{\theta}$ defines a (not necessarily unique) function,
$f_{\bm{\theta},M,|{\phi}\rangle}:\bm{x}\mapsto\mathbb{R}$ (with range limited
by the spectrum of $M$), the set of unitaries defines a set of functions. We
call this set the hypothesis class, to coincide with the common usage in
machine learning. PQCs have been studied in other contexts, such as quantum
chemistry or condensed matter physics [kandala2017hardware], although it is
likely our approaches might generalise to these areas, in this work we focus
on its application to machine learning.

######  Definition III.1 (PQC hypothesis class).

The hypothesis class generated by the family of parameterised quantum circuits
$\mathbb{U}$ together with an observable $M$ is given by

$\displaystyle\mathcal{F}_{\mathbb{U},M}=$
$\displaystyle\Big{\\{}f_{\bm{\theta}}(\bm{x})=\langle{0}|U^{\dagger}(\bm{\theta},\bm{x})MU(\bm{\theta},\bm{x})|{0}\rangle:\bm{\theta}\in[0,2\pi)^{N_{\mathrm{PS}}}\Big{\\}},$

where $N_{\mathrm{PS}}$ is the number of parameters in the model.

These PQCs have proven popular, but the implementation of PQCs is currently
tempered hindered by the NISQ machines they run on. Notably the limited number
of qubits available limits the width (defined henceforth as number of qubits
the circuit acts on) of the circuit that can be run. It is the central concern
of this work to produce a model as useful as PQCs of width larger than what
the available machines naively permit.

###  III.2 Circuit Partitioning

In [bravyi2016, peng2020, mitarai2021constructing] the authors propose methods
to simulate large quantum circuits on smaller quantum machines by partitioning
the circuit into smaller disconnected blocks. In this section we will
introduce and then employ these methods on PQCs to decrease the size of
quantum computer needed. In our work the decompositions are based on the
result of [bravyi2016] however extension to the results of [peng2020,
mitarai2021constructing] are also possible. We present only the approach of
[bravyi2016] as they are, for our purposes, very similar.

Consider a partition of the $N$ qubits into blocks, $\\{p_{i}\\}_{i}$, where
$p_{i}\subset[N]$ (where $\\{B_{i}\\}_{i}$, where $B_{i}\subset[N]$
($[N]:=1,2,\ldots,N$) such that $\bigcup_{i}p_{i}=[N]$ and $p_{i}\cap
p_{j}=\emptyset$ $\bigcup_{i}B_{i}=[N]$ and $B_{i}\cap B_{j}=\emptyset$
$\forall i\neq j$ (i.e. each qubit is in one and only one block of the
partition). We use the fact that any unitary matrix can be decomposed into a
sum of weighted tensor products of single qubit unitaries. In [bravyi2016]
this fact is used to decompose any particular 2-qubit gate into a gate of the
form:

$U=\sum\alpha_{i}u_{i}\otimes u^{\prime}_{i}$ (2)

for some complex $\alpha_{i}$ such that $\sum|\alpha_{i}|^{2}=1$ and for 2
dimensional unitaries, $u_{i}$ and $u_{i}^{\prime}$. The number of terms of
the sum needed for any particular gate is given by its Schmidt number
[balakrishnan2011operator], generically this number is 4 for 2-qubit
entangling gates but for some important cases (including the CNOT and
controlled-Z) only 2 terms are needed. For example, we can decompose the
Controlled-Z gate into single qubit gates as:

$\mathrm{Controlled-Z}=\frac{1}{1+i}\left(S\otimes S+iS^{\dagger}\otimes
S^{\dagger}\right)$ (3)

where $S$ is the phase gate. The identity (2) allows us to rewrite any
particular 2-qubit gate as the sum of products of single qubit operators.
Applying this method to every 2-qubit gate connecting two blocks of the
partition decomposes the full unitary into a sum of tensor products of
unitaries which individually act only on each block of the partition (figure
1).

An example is useful in illustrating this point, suppose we are given a
unitary $W$ which consists of two disconnected blocks apart from one 2-qubit
gate, $G$, connecting the otherwise disjoint blocks, top and bottom (as in
figure 1):

$W=(U_{\mathrm{top}}\otimes U_{\mathrm{bot}})G(V_{\mathrm{top}}\otimes
V_{\mathrm{bot}})$ (4)

We can decompose this 2-qubit gate as $G=\sum_{i}\alpha_{i}u_{i}\otimes
u^{\prime}_{i}$. The full unitary can thus be written as:

$\begin{split}W=&(U_{\mathrm{top}}\otimes
U_{\mathrm{bot}})(\sum_{i}\alpha_{i}u_{i}\otimes
u^{\prime}_{i})(V_{\mathrm{top}}\otimes V_{\mathrm{bot}})\\\
=&\sum_{i}\alpha_{i}(U_{\mathrm{top}}\otimes U_{\mathrm{bot}})(u_{i}\otimes
u^{\prime}_{i})(V_{\mathrm{top}}\otimes V_{\mathrm{bot}})\\\
=&\sum_{i}\alpha_{i}(U_{\mathrm{top}}u_{i}V_{\mathrm{top}})\otimes(U_{\mathrm{bot}}u^{\prime}_{i}V_{\mathrm{bot}})\end{split}$
(5)

Suppose the initial state is $|{0}\rangle^{\otimes n}$ (which we will simply
refer to as $|{0}\rangle$) and the measurement is the projection,
$|{0}\rangle\\!\langle{0}|$ (using the previous notation for
$|{0}\rangle^{\otimes n}$), we then have that

$\displaystyle\langle{0}|W|{0}\rangle$
$\displaystyle=\langle{0}|\sum_{i}\alpha_{i}(U_{\mathrm{top}}u_{i}V_{\mathrm{top}})\otimes(U_{\mathrm{bot}}u^{\prime}_{i}V_{\mathrm{bot}})|{0}\rangle$
$\displaystyle=\sum_{i}\alpha_{i}\langle{0}|(U_{\mathrm{top}}u_{i}V_{\mathrm{top}})|{0}\rangle\cdot\langle{0}|(U_{\mathrm{bot}}u^{\prime}_{i}V_{\mathrm{bot}})|{0}\rangle$

and the expectation value is given by:

$\displaystyle\Big{|}\langle{0}|W|{0}\rangle\Big{|}^{2}\\!=\\!\sum_{i,j}\bar{\alpha_{i}}\alpha_{j}$
$\displaystyle\langle{0}|(U_{\mathrm{top}}u_{i}V_{\mathrm{top}})^{\dagger}|{0}\rangle\\!\langle{0}|(U_{\mathrm{top}}u_{j}V_{\mathrm{top}})|{0}\rangle$
$\displaystyle\cdot$
$\displaystyle\langle{0}|(U_{\mathrm{bot}}u^{\prime}_{i}V_{\mathrm{bot}})^{\dagger}|{0}\rangle\\!\langle{0}|(U_{\mathrm{bot}}u^{\prime}_{j}V_{\mathrm{bot}}|{0}\rangle.$

which is the product of inner products local to either element of the
partition. This allows us to evaluate each smaller inner product individually
and then combine them in a product and sum to replicate the expectation value
of the full circuit. Depending on the observable it may be preferable to
calculate the expectation value (i.e. the previous equation) or to calculate
the inner product presented in the equation before and then square the answer
to calculate the expectation value.

These results provide us with a clear path to solve the central goal of this
paper thus far, “How to fit a larger model on a smaller machine”. It is simply
a matter of specifying a large PQC, then deciding on a partition
$\\{p_{i}\\}_{i}$ $\\{B_{i}\\}_{i}$ that separates its initial state and
measurement nicely. This partition defines a set of closely related circuits
that differ only by the replacement of 2-qubit gates with single qubit gates.
The next theorem encapsulates the partitioning of PQCs into a set of a set of
smaller subcircuits, and the recombination of them to recreate the result of
the larger PQC.

######  Theorem III.1 (Partitioned model).

For every function $f_{\bm{\theta}}\in\mathcal{F}_{\mathbb{U},M}$ and qubit
partition $\\{n_{k}\\}_{k\in[K]}$ $\\{B_{k}\\}_{k\in[K]}$ with observable
$M=\bigotimes_{k\in[K]}M_{k}$, there exists a set of coefficients
$\\{c_{i}\\}_{i\in[T]}$ and unitaries
$\tilde{\mathbb{U}}=\\{U^{i,k}(\bm{\theta},\bm{x}),U^{\prime
i,k}(\bm{\theta},\bm{x})\\}_{i\in[T],\text{ }k\in[K]}$ (where each $U^{i,k}$
and $U^{\prime i,k}$ acts on $n_{k}$ qubits) which can be combined in a
function:

$\tilde{f}_{\bm{\theta}}(\bm{x})=\sum_{i=1}^{T}c_{i}\prod_{k=1}^{K}\langle{0}|U^{\prime
i,k\dagger}(\bm{\theta},\bm{x})M_{k}U^{i,k}(\bm{\theta},\bm{x})|{0}\rangle,$
(6)

such that $f_{\bm{\theta}}(\bm{x})=\tilde{f}_{\bm{\theta},M}(\bm{x})$ for
every $\bm{\theta},\bm{x}$. For arbitrary gates the number of terms $T$ grows
as $16^{r}$, where r is the number of gates across the partition, but for cut
gates with known Schmidt number $T$ is the product of the Schmidt number
squared of each cut gate.

######  Remarks.

In many cases the same subcircuit (or its complex conjugate) appears multiple
times in equation 6. By storing its value in classical memory the total number
of circuit evaluations can be brought down to $6^{r}$ where $r$ is the number
of gates across the partition (as mentioned in [bravyi2016]). Bounding the
number of evaluations needed for a given circuit is a task studied in
[mitarai2021overhead] in the context of the scheme in
[mitarai2021constructing].

It must also be noted that Equation 6 is composed of inner products, not
expectation values, thus requiring 2 circuits to evaluate. Further details on
this and the effects of error are considered in Section V.

Mapping this theorem onto our example $K=2$, the set of coefficients would be
$\\{\overline{\alpha}_{i}\alpha_{j}\\}$ and the set of unitaries would be

${\color[rgb]{1,0,0}\sout{\big{\\{}\left\\{U_{\mathrm{top}}u_{i}V_{\mathrm{top}},U_{\mathrm{top}}u_{j}V_{\mathrm{top}},\right\\},\left\\{U_{\mathrm{bot}}u^{\prime}_{i}V_{\mathrm{bot}},U_{\mathrm{bot}}u^{\prime}_{j}V_{\mathrm{bot}}\right\\}\big{\\}}_{i,j}.}}$
${\color[rgb]{0,0,1}\uwave{\big{\\{}\left\\{U_{\mathrm{top}}u_{i}V_{\mathrm{top}},U_{\mathrm{top}}u_{j}V_{\mathrm{top}},\right\\},\left\\{U_{\mathrm{bot}}u^{\prime}_{i}V_{\mathrm{bot}},U_{\mathrm{bot}}u^{\prime}_{j}V_{\mathrm{bot}}\right\\}\big{\\}}_{i,j}.}}$

This example also illustrates the similarity of terms in equation 6, for every
“top” circuit is identical up to the replacement of $u_{i},u_{j}$.

Theorem III.1 is useful to our goal, we can fit any large PQC on a small
machine, however we have paid a huge price in the need to run an exponential
number of smaller circuits. Indeed given that most QML models are relatively
densely connected and increasing depth can lead to improved performance, this
exponential overhead in number of cut connections is impractically costly. For
example a 2-block division of the hardware efficient ansatz up to depth 6,
such as those considered in [jerbi2021variational] to solve a simple task
would require over 2 billion distinct sub-circuit evaluations. This rough
estimation motivates us to revise our goal to “how to fit a larger model on a
smaller machine in an acceptable number of circuit evaluations”.

If we are interested in exactly recreating the output of the circuit, this
goal might be unattainable, unless we can find an exponential number of terms
that perfectly cancel each other. There are fortunately several acceptable
simplifications we can make to our goal. First, we are not concerned with the
exact replication of the unitary. Since our input states are fixed to
$|{0}\rangle$ we only care about the action of our recreated unitary on this
state. Second, we may be content with approximate results, or perhaps even
approximate results for most input data. Finally, our ultimate goal for a
machine learning model, in many cases, is simply to output a binary classifier
[mohri2018foundations] (or another simpler discrete set of outputs) so we are
not interested in keeping terms which contribute similarly as other terms in
the final assignment of a class label.

With this in mind we will now define the subset partition model as the best
possible approximation of the full result in theorem III.1 keeping only $L$
terms.

######  Definition III.2 (Subset partition model).

For a partitioned model, $\tilde{f}_{\bm{\theta}}(\bm{x})$, with set of
unitaries $\tilde{\mathbb{U}}$, we define the $L$-subset partition model as a
function using the optimal $L$-sized subset of terms
$I\subset\tilde{\mathbb{U}}$ given by:

$\displaystyle\tilde{f}^{I}_{\bm{\theta}}(\bm{x})=$ $\displaystyle\sum_{i\in
I}\lambda_{i}\prod_{k=1}^{K}\langle{0}|U^{\prime
i,k\dagger}(\bm{\theta},\bm{x})M_{k}U^{i,k}(\bm{\theta},\bm{x})|{0}\rangle.$

where we have introduced free parameters $\lambda_{i}$ that can also be
optimised over. In the above definition $I$ and $\bm{\lambda}$ are optimised
to produce the best approximation of $\tilde{f}_{\bm{\theta}}(\bm{x})$, for
some given success metric.

This model is a step towards our goal, if we are given the model it would be
possible to run some approximation of the partitioned circuit on a small
computer in acceptable time. However we lack the capacity to chose the optimal
set of “small circuits” $I$, in general choosing this set corresponds to a
combinatorial optimisation problem. In the next section we will describe why
this problem is challenging and produce a model that can work around it.

###  III.3 Reduced Partition Model

In the last section we tackled the problem of how to fit a large model on a
smaller machine, but it required us to run an impractical number of circuits
to achieve our goal, we introduced a model to get around this but it was
impractical to optimise. We now consider a situation where we are given a
runtime “budget”, a hypothetical number of circuits, $L$, that we can afford
to evaluate. Choosing which $L$ circuits to evaluate from the set generated by
the partitioning to perform optimally is an incredibly challenging
combinatoric optimisation problem. This process is additionally complicated by
the apparent need to use a quantum computer to assess if the circuits can be
ignored. In this section we propose a relaxation of the problem: by
parameterising the gates that replaced the 2-qubit gates in the circuit
cutting process (henceforth called partition gates) such that all terms in the
sum are identical up to these introduced parameters. The problem of optimising
circuit selection becomes one of optimising the parameters of the partition
gates.

The first step of this process is parameterising the gates introduced by the
partition. There are many options for doing this, for example when cutting the
controlled Z we get the decomposition in equation 3, replacing the 2-qubit
gate on either qubit by $S$ or $S^{\dagger}$. We then wish to create a new
parameterised gate which takes a parameter $\zeta$ such that the parameterised
gate is $S$ when $\zeta=0$ and $S^{\dagger}$ when $\zeta=1$. $Z^{\zeta}$
composed with $S^{\dagger}$ is one choice. Defining $\zeta$ this way also
allows us to extrapolate gates for $\zeta\notin\\{0,1\\}$, creating a
continuous parameter we can use for e.g. gradient descent.

We can use this partitioned-gate-parameterisation trick to replace the set
$\\{U^{i,k}(\bm{\theta},\bm{x}),U^{\prime
i,k}(\bm{\theta},\bm{x})\\}_{i,\text{ }k}$, with a new set,
$\\{U^{k}(\bm{\theta},\bm{x},\zeta)\\}_{k\in[K]}$, with just one parameterised
unitary for each block of the partition, with different terms of the sum
differentiated only by different parameters $\zeta$.

######  Lemma III.1.

For every $\tilde{f}_{\bm{\theta}}\in\mathcal{F}^{L}_{\mathbb{U},M}$, there
exists a set of unitaries
$\\{U^{k}(\bm{\theta},\bm{x},\bm{\zeta})\\}_{k\in[K]}$ and parameters
$\bm{\lambda},\bm{\zeta}$ defining a function:

$\displaystyle\bar{f}_{\bm{\theta},\bm{\zeta},\bm{\lambda}}(\bm{x})=$ (7)
$\displaystyle\sum_{i\in[L]}{\lambda_{i}}\prod_{k\in[K]}\langle{0}|U^{k\dagger}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k})M_{k}U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k+K})|{0}\rangle,$
(8)

such that
$\tilde{f}_{\bm{\theta}}(\bm{x})=\bar{f}_{\bm{\theta},\bm{\zeta},\bm{\lambda}}(\bm{x})$
for every $\bm{\theta},\bm{x}$ and for every observable that can be written as
tensor product on the elements of the partition $M=\bigotimes_{k}M_{k}$.

In this lemma we have used our new free parameter $\bm{\zeta}$ to parameterise
the partition gates, the parameters needed for these partition gates could be
calculated from the partitioning theorem or trained through gradient descent.
As mentioned, the advantage of this step is that now all terms of the sum are
equivalent to each other up to weight parameters $\lambda_{i}$ and
$\bm{\zeta}_{i,k}$. This is useful in the final model, where we reduce the
number of terms to $L$ and then allow these parameters to learn freely, making
the model capable of replicating any $L$ terms present in the original model
by changing $\lambda_{i}$ and $\bm{\zeta}_{i,k}$.

######  Definition III.3 (Reduced partition model).

For a PQC hypothesis class $\mathcal{F}_{U,M}$, we define the reduced
$L$-subset partition model as the family of functions
$\overline{\mathcal{F}^{L}_{\mathbb{U},M}}=\big{\\{}\bar{f}_{\bm{\theta},\bm{\zeta},\bm{\lambda}}\big{\\}}$
where each function is given by

$\displaystyle\bar{f}_{\bm{\theta},\bm{\zeta},\bm{\lambda}}(\bm{x})=$ (9)
$\displaystyle\sum_{i\in[L]}\lambda_{i}\prod_{k\in[K]}\langle{0}|U^{k\dagger}(\bm{\theta},\bm{x},\zeta_{i,k})M_{k}U^{k}(\bm{\theta},\bm{x},\zeta_{i,k+K})|{0}\rangle$
(10)

where the unitaries $U^{k}$ are those described in Lemma III.1 and we have
introduced entirely free parameters $\bm{\lambda}$ and $\bm{\zeta}$ that can
be optimised over. This can also be referred to as a “reduced partition model”
when $L$ is to be specified later.

This new model introduces more free parameters, $\bm{\zeta}$, into our model,
fortunately only $2L\times$ number of cut gates are introduced.

The reduced partition model can now use the similarity of the terms of the
equation 9 (they are identical up to the weight vector, $\bm{\zeta}$) to
replicate any subset of terms taken from the partitioned model by simply
adjusting the parameters $\bm{\lambda}$ and $\bm{\zeta}$. This is stated
formally in the following theorem.

######  Theorem III.2.

For any PQC hypothesis class $\mathcal{F}_{\mathbb{U},M}$, the $L$-subset
partition hypothesis class $\mathcal{F}^{L}_{\mathbb{U},M}$ is included in the
hypothesis class of the reduced $L$-subset partition model
$\overline{\mathcal{F}^{L}_{\mathbb{U},M}}$, i.e.,

$\mathcal{F}^{L}_{\mathbb{U},M}\subset\overline{\mathcal{F}^{L}_{\mathbb{U},M}}$
(11)

I.e., if a given classifier can be sufficiently well approximated by
considering only $L$ terms, then the hypothesis class of the reduced partition
model can do at least as well as this approximation. This is the potential
advantage of our model. Additionally, the relaxation from manually picking
terms to optimising $\bm{\zeta}$ allows us to apply gradient based methods,
generally yielding much easier optimisation, but in general suffers as the
solutions of the relaxation do not encode meaningful solutions of the original
problem (which is discrete in nature). However in our case, since we deal with
QML, all this achieves is expanding the hypothesis class, where any solution
is meaningful, and optimisation (if done completely) can only yield better
results with respect to the training error. Although, when expanding the
hypothesis class, the problem may become worse generalisation performance,
often evidenced by looser/worse generalisation bounds. We analyse these in the
next section.

##  IV Generalisation Error

In creating the reduced partition model, we partitioned the circuit and
removed terms, which intuitively makes the model simpler, but then introduced
free parameters, making the model more complicated and increasing the size of
the (reduced model) hypothesis class. In this section we will formalise this
change in simplicity with the notion of generalisation error, defined roughly
as the gap between performance on a training set and performance on unseen
data from the same distribution. We will only briefly and roughly define a few
concepts that are needed, readers keen to see a more are referred to
[mohri2018foundations].

We define a supervised learning task on a domain, $\mathcal{X}$, and co-
domain, $\mathcal{Y}$ with a probability distribution over
$\mathcal{X}\times\mathcal{Y}$, $P$, and loss function,
$\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}$ as the task of
outputting a hypothesis, $h\in\mathcal{Y}^{\mathcal{X}}$, such that the risk,
$R(h)$ is minimised. We define the risk for a hypothesis $h$ on a continuous
space as the expected loss:

$R(h)=\int_{\mathcal{X}\times\mathcal{Y}}\ell(h(x),y)dP(x,y).$ (12)

In practical settings we normally lack access to the underlying probability
distribution, so the true risk cannot be evaluated. Instead we are supplied
with training data drawn from $P$, $S=\\{(x_{i},y_{i})\sim P\,|\,i\in[m]\\}$,
and must settle for evaluating the risk on this finite set. We call this the
empirical risk of $h$ with respect to $S$:

$\hat{R}_{S}(h)=\frac{1}{|S|}\sum_{(x_{i},y_{i})\in S}\ell(h(x_{i}),y_{i})$
(13)

Optimising our hypothesis on the training data optimises the empirical risk,
which is generally a good proxy for the true risk. The gap between these two
risks is bounded by generalisation bounds, specifically by a generalisation
gap function, $g$, which can depend on many properties given the setting. For
our purpose we will consider it as a function of the hypothesis class,
$\mathcal{F}$, the size of the training set, $m$, and the probability of the
output classifier satisfying the bound, $1-\delta$.

We can aim for a probabilistic bound on generalisation gap for all
$\delta\in(0,1)$:

$P\left(R(h)<\hat{R}_{S}(h)+g(\mathcal{F},m,\delta)\right)>1-\delta$ (14)

Intuitively the gap has to do with the concept of “overfitting”. Simple models
tend to have much smaller generalisation gaps. A function which outputs random
labels and does no learning has a generalisation gap of $0$ but a large
empirical risk. In contrast, some complex and large models are found to
“overfit” data, where the empirical risk drops to near 0 but the
generalisation of the model is very poor, with poor performance on data points
not seen during training. Since our model contains more parameters than the
model we derived it from, we might fear we have slid into the poor
generalisation-good empirical risk category.

We study this question by using two well-known methods to study the
generalisation performance of quantum circuits [caro2021encoding] and
[caro2020pseudo]. In the analysis we will see that the first method does not
distinguish our model from the PQC it was derived from. This is positive from
the perspective that the new parameters did decrease performance according to
this bound, but negative as these bounds do not identify $L$ as a parameter
influencing model complexity at all, which intuitively it should. To overcome
this, we analyse the additive property of the Rademacher complexity to examine
how adding terms to our model increases the generalisation error.

###  IV.1 Encoding Dependent Generalisation Gap

One insightful analysis of generalisation performance is given in
[caro2021encoding], we will show that its bounds apply directly to our model.
The analysis first imports a result shown in [schuld2021effect, gil2020input],
that the function implemented by any PQC, $f_{\bm{\theta}}(x)$, is as a
generalised trigonometric polynomial(GTP):

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

where the effect of all the parameterised gates and the measurement is only
reflected in the coefficients $\\{c_{\omega}\\}$. The frequencies available in
the GTP ($\Omega$) are determined entirely by the input data’s encoding
strategy, specifically the eigenvalue spectra of Hamiltonians encoding the
input data, typically as rotation gates. Further study of the spectra of
frequencies, $\Omega$, is available in the aforementioned works.

With a very similar analysis it can also be shown that a GTP of this form
exists for each term of our sum: Consider a single term, $T_{i}$

$T_{i}=\lambda_{i}\prod_{k\in[K]}\langle{\phi_{k}}|U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k})M_{k}U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k+K})|{\phi_{k}}\rangle$
(16)

this is equivalent to reuniting $|{\phi_{k}}\rangle$ and $M_{k}$ from product
form, and combining
$\bigotimes_{k\in[K]}U^{k}(\bm{\theta},\bm{x},\zeta_{i,k+K})=:U(\bm{\theta},x,\bm{\zeta}_{i})$
into:

$T_{i}=\lambda_{i}\langle{\phi}|U(\bm{\theta},\bm{x},\bm{\zeta}_{i})MU(\bm{\theta},\bm{x},\bm{\zeta}^{\prime}_{i})|{\phi}\rangle$
(17)

this term is now an inner product of an incredibly similar form to the PQC it
is derived from, indeed if the encoding gates are untouched by the
partitioning scheme then $T_{i}$ has the same encoding gates and it can be
shown admits a representation as a GTP of the same form, with the exact same
spectra, $\Omega$. Our new GTP will contain different (and now possibly
complex) $\\{c_{\omega}\\}$.

Since each term can be represented as a GTP with the same $\Omega$ we are able
to combine them into another GTP:

$\begin{split}\bar{f}_{\bm{\theta},\bm{\zeta},\bm{\lambda}}(\bm{x})=\sum_{i\in[L]}\lambda_{i}\sum_{\omega\in\Omega}c_{\omega}(\bm{\theta},\zeta_{i},M)e^{-i\omega\bm{x}}=\\\
\sum_{\omega\in\Omega}e^{-i\omega\bm{x}}\sum_{i\in[L]}\lambda_{i}c_{\omega}(\bm{\theta},\bm{\zeta}_{i},M)=\sum_{\omega\in\Omega}e^{-i\omega\bm{x}}c^{\prime}_{\omega}(\bm{\theta},\bm{\zeta},M)\end{split}$
(18)

with new weights:
$\\{c_{\omega}^{\prime}=\sum_{i\in[L]}\lambda_{i}c_{\omega}(\bm{\theta},\zeta_{i},M)^{\prime}\\}$.

This defines a new GTP of the same degree and the same $\Omega$ as the full
sized circuit which we originally partitioned. Performing the analysis of type
presented in [caro2021encoding] for our circuit gives identical bounds as for
the whole (unpartitioned) model.

As our model dramatically differs in the number of terms (which ought to
decrease the gap), yet is much more general in the parameters that are free
(which should increase the complexity), we see that this bounding technique is
quite coarse grained. In particular, even just pure product models (no
entangling gates) which are trivially classically simulatable have the same
bounds. The fact that the GTP approach yields somewhat loose bounds was
emphasized in [caro2021encoding] . We and as we have only bounded that bound
we must tighten our analysis to achieve a meaningful bound, in the next
section we will achieve this.

###  IV.2 Term-Based Generalisation Gap

Under the previous analysis In the previous subsection we saw that the best
upper bounds of one encoding dependent generalisation error analysis for the
unpartitioned model matched those of our new model. Since that analysis only
considered the encoding (an element that we assumed was unperturbed by our
modification) it seems prudent to consider another approach, one that
fundamentally considers the increasing number of terms.

In this subsection we will use the additive property of the Rademacher
complexity (a metric that can be used to bound the generalisation gap) to
examine how adding terms to the form of our model increases the generalisation
error. Towards the end of this section we also begin to analyse how the
structure of a circuit effects its generalisation bounds. Specifically, we use
that for two families of functions $\mathcal{F}$ and $\mathcal{G}$In this
section we will introduce a complexity measure, the Rademacher complexity, we
find a bound that scales linearly as terms are increased.

The Rademacher complexity [wolf2018mathematical] is measure of a function
family’s ability to assign arbitrary labelling to a set of input data. Given
some particular input dataset $S=(x_{1},x_{2},\ldots,x_{m})$ the Rademacher
complexity of the family $\mathcal{F}+\mathcal{G}$ (i.e., is

${\color[rgb]{0,0,1}\uwave{\mathcal{R}_{S}(\mathcal{F})=\frac{1}{m}\mathbb{E}_{\sigma}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{m}\sigma_{i}f(x_{i})\right]}}$

Where the expectation is over $m$ i.i.d. random variables, $\sigma$, with
equal chance of being $+1$ or $-1$. These random variables should be thought
of as the labels of the so-called Minkowski sum, in this case the set of sums
of function pairs from F and G) is bounded by [wolf2018mathematical,
bartlett2002rademacher] data points, by maximising the function on
$\sum_{i=1}^{m}\sigma_{i}f(x_{i})$ we select the function that best captures
this divide. The expectation then asks how well the function family does at
finding a good hypothesis for any arbitrary labelling. Our results hold for
any given dataset so we will omit $S$ and use just $\mathcal{R}(\mathcal{F})$

As Rademacher complexity follows the triangle inequality
[wolf2018mathematical, bartlett2002rademacher]:

$\displaystyle\mathcal{R}\big{(}\mathcal{F}+\mathcal{G}\big{)}\leq\mathcal{R}\big{(}\mathcal{F}\big{)}+\mathcal{R}\big{(}\mathcal{G}\big{)}.$
(19)

The extension of this result to our case is then trivial. As in the previous
section we consider a single term of the sum and combine the product into a
single inner product and view this as a function

${\color[rgb]{1,0,0}\sout{f_{\bm{\theta}}(\bm{x})=\lambda\langle{\phi}|U(\bm{\theta},\bm{x},\zeta_{i})MU(\bm{\theta},\bm{x},\bm{\zeta}^{\prime}_{i})|{\phi}\rangle.}}$

If the Rademacher complexity of the function familyof these individual terms
$\big{\\{}f_{\bm{\theta}}(x)\big{\\}}_{\theta}$ is upper bounded by For two
families of functions $\mathcal{F}$ and $\mathcal{G}$. Taking $R_{T}$ , then
by applying Eq. directly to our classifier we find that as the maximum
Rademacher complexity of any of the Rademacher complexity of the partitioned
model (i.e., when we consider summands in our model we can bound the whole
model’s Rademacher complexity by $O(R_{T}L)$, a linear increase with the
number of terms in our model! This bound implicitly depends also on $k$ as we
suspect that increasing $k$ necessitates a larger $L$terms $f_{\bm{\theta}})$
is upper bounded by $O(R_{T}L)$. It is not surprising that we can limit the
generalisation error by including fewer terms since every term makes the model
more expressive. This fact is also reassuring, limiting the number of terms
not only saves us in generalisation risk but also in runtime. This means that
the hyperparameter of the model $L$ can be used to perform structural risk
minimisation. .

If we denote the Rademacher complexity of the original unpartitioned model by
$R_{PQC}$, then it seems very likely that generally $R_{T}\leq R_{PQC}$, as
the term is of the same form as the original PQC but with some 2-qubit gates
cut. For intuition why this should be the case consider the extremal case of a
(deep) circuit with single-qubit parametrized gates intertwined with CNOTs.
This is a universal circuit if of sufficient depth, so is highly expressive.
In contrast, the extreme variant where all CNOT gates are removed renders this
a product model, which will indeed collapse to a single layer of parameterized
(arbitrary) single qubit gates, which is less expressive than universal
circuits of the same size. is bounde

$\displaystyle{\color[rgb]{1,0,0}\sout{\mathcal{R}\leq C\sqrt{\frac{\gamma
log(\gamma)}{m}}}}$

where $C$ is some universal constant originating from the transition from
pseudodimension to Rademacher complexity, similar to a result in
[caro2021generalization]. Thus this bound applies to each of the terms of our
model.

Cutting 2-qubit gates across the partition presents opportunities to absorb
gates acting on the same qubits into a single gate, reducing $\gamma$. The
exact effect this has on our bound of the Rademacher complexity for each term
(Comparing $R_{T}$ ) will vary for each architecture and each partition. If we
consider the circuit in figure 1, cutting the 2-qubit gate between peach
coloured and mint blocks naively increases the number of gates. However now
the partitions are not linked we can absorb all the gates on either partition
into just to the Rademacher of the larger model presents challenges: In
general, intuition tells us that removing connections from a circuit should
reduce the expressivity. However cases can be constructed where removing 2
unitaries, one for the top partition and one for the bottom. The new unitaries
are equal to the product of all the unitaries on each partition. For this
circuit, cutting the 2-qubit gate across the partitions reduces the gate count
from 6 to 2, lowering the bound on Rademacher complexity qubit gates increases
generalisation (an example is presented in appendix A).

The effect of cutting many gates can be much more extreme: for example in a
setting with many 1 and 2 qubit gates, due to non-commutativity, we can end up
with circuits of arbitrary depths. However, if we cut all 2-qubit gates and
use the fact that fully parametrised gates can absorb neighbouring fully-
parameterised gates, we can reduce the entire circuit to a tensor product of
$n$ single qubit unitaries, with a dramatically tighter upper bound on the
pseudodimension and hence Rademacher complexity.

Note that in the above analysis we used the fact that the circuit model upon
which the psedudodimension bounds operate work with fully parametrised gates,
and allow certain re-writings, which allowed us to lower the bounds – it is
not the case that per-se, the pseudodimenson approach in any way “counts” or
measures the entangling capacities directly, but rather this is achieved via
cutting and rewriting. Further work could focus on using the cutting and
rewriting we present here to improve existing generalisation results.

In some cases applying similar rewriting logic can also improve the bounds
obtained by the GTP approach of the last subsection. For example consider the
case with two commuting encoding gates ($\exp(itH_{1})$ and
$\exp(itH_{2})$)are separated by some 2-qubit gate which doesn’t commute with
either encoding gate. The removal of this 2-qubit gate (or just some of its
partitioned terms) means the two encoding gates can be combined into a single
gate, reducing the available set of frequencies ($\Omega$) and lowering the
resulting generalisation bound. The scope of such rewriting methods to obtain
tighter bounds (which are then circuit-structure-sensitive) is of course very
much dependent on the particularities of the circuit, but a possible
interesting area of study. We leave the further details for future work.

Thus we are unable to Simplify the Rademacher bound any further while
remaining maximally general.

##  V Evaluation and training of reduced partition model

In this section we look at how one can evaluate the circuits, what error this
would entail, and how it might be trained, we speculate on a possible feature
of partitioned PQCs that might placate the effects of so-called “barren
plateaus”.

###  V.1 Evaluation

Evaluation of the reduced partition model is a non-trivial task, the terms are
composed not of expectation values (which can be evaluated with simple
circuits) but of inner products, with different unitaries on either side of
the observable. Fortunately this is not an insurmountable problem. To evaluate
these inner products we can employ the Hadamard test shown in figure 2. The
most challenging component of this circuit is the application of a
controlled-$U/V$, naively this would require controlled gates for every gate
in $U$ and in $V$. Fortunately this is not the case. Since $U$ and $V$ differ
only by the partition gates, the controlled-circuits can be constructed with
controlled operations only on these partition gates, which is a small subset
of the total number of gates in the circuit.

Figure 2: The hadamard test to be used for calculating the real component of
some $\langle{0}|UM_{k}V|{0}\rangle$. The controlled $U/V$ circuit implements
$U$ if the control is 0 and $V$ if the control is 1. It is important to note
that the controlled $U/V$ circuit only requires on control on a few gates,
since only the partition gates differentiate $U$ and $V$ most gates are
identical and do not require control. This circuit can be modified to
calculate the imaginary component as described in [bravyi2016]

As with all NISQ applications we must also concern ourselves with the impact
of errors on our results. To analyse this in our model we will consider a
first order additive error and find the total error satisfactoryinspect how
our algorithm will perform on a noisy device. By bounding the variance we find
the noise scaling very reasonable.

First, let us replace the non-random inner products,
$\langle{\phi_{k}}|U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k})M_{k}U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k+K})|{\phi_{k}}\rangle$,
with random variables $X_{i,k}$ which are unbiased estimators of the inner
product (that is
$\langle{\phi_{k}}|U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k})M_{k}U^{k}(\bm{\theta},\bm{x},\zeta_{i,k+K})|{\phi_{k}}\rangle=\overline{X_{i,k}}$
where the bar now represents the expectation value). These random variables
represent an estimation of the inner product with a non-infinite number of $m$
shots on a quantum computer. We are interested in the difference between this
noisy estimation and $f_{\bm{\theta,\zeta,\lambda}}$. That is:

err = ∑_i ∈[L] λ_i ∏_k∈[K] X_i,k - ∑_i ∈[L] λ_i ∏_k∈[K]

Using an approximation (${X_{i,k}}=\overline{X_{i,k}}+\varepsilon_{i,k}$) and
combining the sums we can expand the problem:

err = ∑_i ∈[L] λ_i ∏_k∈[K] ( +ε_i,k) - ∏_k∈[K]

expanding the sum and ignoring terms higher than linear in
$\varepsilon_{i,k}$:

err = ∑_i ∈[L] λ_i ∑_k∈[K]ε_i,k∏_j∈[K]∖k

Assuming the magnitude of each inner product is bounded by $B$ (which for
Pauli string observables is bounding the probability that the difference
between the estimate and the average exceeds some $\epsilon$ by $\delta$.

${\color[rgb]{0,0,1}\uwave{P\left(\left|\sum_{i\in[L]}\lambda_{i}\prod_{k\in[K]}X_{i,k}-\sum_{i\in[L]}\lambda_{i}\prod_{k\in[K]}\overline{X_{i,k}}\right|>\epsilon\right)\leq\delta}}$
(20)

We can achieve this bound by considering the variance. If we assume the
observable and each $\lambda$ are bounded by 1) and that each
$\varepsilon_{i,k}=\varepsilon$ we have our final error: , we find the
variance scales with the number of shots [286787]:

${\color[rgb]{0,0,1}\uwave{\mathbb{E}\left[\left(\sum_{i\in[L]}\lambda_{i}\prod_{k\in[K]}X_{i,k}-\sum_{i\in[L]}\lambda_{i}\prod_{k\in[K]}\overline{X_{i,k}}\right)^{2}\right]}}$
${\color[rgb]{0,0,1}\uwave{\leq\frac{4K^{2}L}{m}}}$

$a:=\left|\sum_{i\in[L]}\lambda_{i}\prod_{k\in[K]}X_{i,k}-\sum_{i\in[L]}\lambda_{i}\prod_{k\in[K]}\overline{X_{i,k}}\right|$
to make the following lines clearer. Rewriting the expectation value then
gives:

${\color[rgb]{0,0,1}\uwave{\frac{4K^{2}L}{m}\geq\mathbb{E}[(a)^{2}]=\int_{0}^{1}P_{a}\,a\,da=\int_{0}^{\epsilon}P_{a}\,a\,da+\int_{\epsilon}^{1}P_{a}\,a\,da}}$
${\color[rgb]{0,0,1}\uwave{\geq\int_{\epsilon}^{1}P_{a}\,\epsilon\,da=\epsilon\int_{\epsilon}^{1}P_{a}\,da=\epsilon
P(A>\epsilon)}}$

err ≤ελ_1 B^k-1 K

We recall that the dimension of $\bm{\lambda}$ is L, so this error is
approximately linear in both K and L, an acceptable errorShowing that 20 holds
when the number of shots satisfies $m=\frac{4K^{2}L}{\epsilon\delta}$.

###  V.2 Training

Training with a gradient based approach is easy to apply in our model too. The
derivative distributes on terms of the sum and can be evaluated by applying
the chain rule to the product in each term. Indeed since most parameters
appear in only one gate on one qubit on one side of the partition, the chain
rule evaluates to 0 on all but 1 element of the product. Evaluating the
gradient then takes at most $L$ times the number of evaluations required to
evaluate the gradient of one of the smaller circuits. In this case we find
that evaluating the gradient for any parameter, $\bm{\theta}^{t}$, that exists
only in the $k^{\prime}$th partition is:

$\begin{split}&\frac{\partial}{\partial\bm{\theta}^{t}}\bar{f}_{\bm{\theta},\bm{\zeta},\bm{\lambda}}(\bm{x})=\\\
&\sum_{i\in[L]}\lambda_{i}\frac{\partial}{\partial\bm{\theta}^{t}}\prod_{k\in[K]}\langle{\phi_{k}}|U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k})M_{k}U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k+K})|{\phi_{k}}\rangle=\\\
&\sum_{i\in[L]}\lambda_{i}\frac{\partial}{\partial\bm{\theta}^{t}}\langle{\phi_{k^{\prime}}}|U^{k^{\prime}}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k^{\prime}})M_{k^{\prime}}U^{k^{\prime}}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k^{\prime}+K})|{\phi_{k^{\prime}}}\rangle\times\\\
&\prod_{k\in[K]\setminus
k^{\prime}}\langle{\phi_{k}}|U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k})M_{k}U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k+K})|{\phi_{k}}\rangle\end{split}$
(21)

The same applies for the $\zeta$ parameters. In many instances the gradient
can be made easier to compute, since we have often already evaluated the non-
derivative expression before looking for the gradient most of the circuit
evaluations are already done, with only the derivative expression for a single
inner product requiring a new evaluation. Which can be done in the standard
manner (e.g. parameter shift rule [crooks2019gradients]).

###  V.3 Barren Plateaus

A well studied problem [mcclean2018barren] with PQCs is the “barren plateaus”
phenomenon, where large parts of the parameter landscape have an exponentially
small gradient, effectively crippling optimisation. This is a manageable
problem for currently implementable PQCs due to their limited size, but as
PQCs become larger (and their gradient decreases) the problem intensifies
[mcclean2018barren]. While our model is not immune to barren plateaus we may
be able to reduce their effect on our model relative to the size of their
effect on the unpartitioned circuit.

Each term of our model is a multiplicative separable function (it can be
written as: $f_{T}(x_{1},\ldots,x_{K})=f_{1}(x_{1})\times\ldots\times
f_{K}(x_{K})$, where $f_{i}$ is an inner product and, $x_{i}$ is the input to
the inner product, including the data and weights) we simplify to assuming $x$
is a single parameter, for illustrative purposes. To calculate the gradient we
apply the chain rule to the product, for most architectures any particular
parameter will only appear on one block of the partition, then one term of the
chain rule will be non zero

$\partial_{x_{i}}f_{T}(x_{1},\ldots,x_{K})=f_{1}(x_{1})\ldots\left(\partial_{x_{i}}f_{i}(x_{i})\right)\ldots
f_{K}(x_{K})$.

The gradient is thus determined by multiplying together the many amplitudes
stemming from the subcircuits of the sum with this lone gradient term
(equation LABEL:grad). Two aspects may make this overall gradient small: First
the gradient may be small as it is a PQC and is prone to barren plateaus,
however the individual subcircuits generically have larger gradient than the
full unpartitioned circuit as they are smaller [mcclean2018barren] (i.e., the
barrenness of the plateaus heavily depends on the number of qubits in the
circuit). Second, the multiplication with other terms may cause it to decay to
zero as we are dealing with a product of terms which are absolute value below
1, the product then decays exponentially in the number of multiplicative terms
to some small number. However in our case we are not directly facing this
radically smaller number, we fundamentally have more information about the
gradient, knowing the total gradient, but also the terms that are combined to
form it. We know the effect that varying any of these subterms has on the
gradient of the complete circuit. One possible use of this information is to
identify which term is driving the gradient to a small value, and to revert
its parameters back to an earlier instance which we have stored in memory,
through this method the impact of barren plateaus could be mitigated. A
technique similar to [sack2022avoiding] could be developed, to avoid low
gradient directions, but utilising the more information present in our case.

There is quite a bit of research on additive separable functions, which may
transfer to our case [wright2015coordinate]. This could lead to significantly
easier training. We plan to develop this method of training in a follow-up
work.

##  VI Numerics

Experiment |  Model
Type |  Accuracy(A)/
MSE
---|---|---
MNIST handwriting |  Neural Net RPM |  100%A 96.4%A
Approximating
larger PQC |  Neural Net RPM |  0.424MSE 0.0322MSE
Table 1: Comparison of the numerics performed in this paper, our model is
compared to Neural networks of varying sizes and architecture

In the previous sections we laid out a model with considered theoretical
underpinning, in this section we will demonstrate that model’s basic utility
by showing it can learn a simple large problem, the MNIST handwritten digit
recognition, by utilising an ansatz much larger than the computer it has
simulated access to. We also present an experiment designed to test if an
adequate approximation of a random circuit output can be made with much fewer
terms, we then apply our model on the same random circuits output to test its
performance on synthetic data.

###  VI.1 A Large Problem: Handwriting

Figure 3: An example datum of the handwriting task, the number 6. The picture
is then cut into 8 elements (as given by its columns) with each element as
input to a different PQC. This resolution data was chosen so as to be fine
enough to be human readable. Figure 4: The loss on an unseen data set
evaluated alongside the training of a reduced partition model to recognise
handwritten digits. Increasing the number of terms has a positive effect on
the ability of the model.

Reading handwritten numbers is one of the most basic tasks in undergraduate
machine learning courses. The MNIST [deng2012mnist] data set presents a
relatively simple task, identify which digit is written in an $28\times 28$
pixel image, but even this simple task is difficult for current generation
quantum machines due to its high dimensionality, with quantum attempts only
succeeding recently through careful encoding of the problem (e.g. in
[li2021quantum]). Often dimensionality reduction techniques such as principal
component analysis are applied [2021data] but for a simple problem like MNIST
handwriting this reduces the learning problem to a triviality. Here we
preserve the learning problem by downsampling the image to just 64 pixels,
which is importantly still human readable. Here we will show that even simple
cases of our model perform adequately and by increasing $L$ (the number of
terms of our model) we increase that performance.

For purposes of comparison we reduce the problem to differentiating 3 and 6,
as in [farhi2018classification]. Our model is based on an 8 block partitioning
of the 64 qubit, depth 3 hardware efficient ansatz (of the same form as in
[jerbi2021variational]) into 8 qubit blocks, a model which would normally be
far outside of our computational power. An unseen validation set is evaluated
at every step of training and the results are shown in figure 4. The final
training loss (MSE), testing loss (MSE) are shown in the following table table
2, we also apply a step function to the output (to convert its real valued
output into a binary label) and list its accuracy.

L |  $loss_{training}$ losstraining |  $loss_{testing}$ losstesting | acc%
---|---|---|---
1 | 0.0521 | 0.0499 | 92.8
3 | 0.0488 | 0.0465 | 92.8
5 | 0.0479 | 0.0454 | 94.7
10 | 0.0432 | 0.0422 | 96.2
20 | 0.0359 | 0.0341 | 96.4
Neural Net | 0.0025 | 0.0031 | 100
Table 2: Final loss on training/validation sets and ultimate accuracy of the
reduced partition model on the handwriting recognition task. Different values
of the hyperparameter $L$ are listed. A neural network is also trained on the
task and found to perform very well.

Data augmentation (skews and rotations) were used to generate more data for
the model. Without this augmentation high $L$ terms began to overfit,
increasing the training performance while decreasing the validation
performance. With data augmentation we can see that our model is behaving
well, even in the 1 term case we find that it selects a good arrangement of
weights, although with relatively few additional terms the performance
increases, for contrast to run this model using the complete circuit
partitioning scheme would require the evaluation of over 46000 subcircuits. A
neural network with a convolution layer and a single dense 128 neuron hidden
layer is provided for comparison. We must consider that our results are on
MNIST handwriting, which is known to have many problems and cannot be used to
claim that our model excels on all similarly large tasks [tweet].

###  VI.2 Tests on Synthetic Data

This work is built around the assumption that many terms in the partitioned
equation for a given circuit are redundant, and a good approximation of the
complete circuit can be made by our model. In this section we test this
assumption with our first experiment, and then test our complete model on
learning a synthetic data set in the second and third experiments.

We take a width 10, depth 3 instance of the hardware efficient ansatz with
random weights. Using this circuit we generate a synthetic data set by
recording its output on $10000$ random inputs, we normalise these outputs to
to a mean squared average of 1. We then instantiate a modified version of our
model corresponding to a partitioning of the full circuit into 2 blocks of
width 5. The model is modified from the general model we have described above
by fixing $\bm{\theta}$ (the weights present from the unpartitioned PQC) and
only training $\bm{\zeta}$ and $\bm{\lambda}$ (the weights we introduced when
creating the model). This modification allows us to examine directly our claim
that introduction of the free parameters, $\bm{\zeta}$ and $\bm{\lambda}$, is
sufficient to approximate the output of the full PQC without evaluating the
many subcircuits that would be required in theorem III.1. After this
experiment we free $\theta$ (apply the full model) and examine the increased
performance this gives us.

Figure 5: The performance of our model on replicating the output of a un-
partitioned VQC when $\theta$ is fixed to that of the un-partitioned model,
and only the parameters meant to replicate the partitioning process are
trained. The amount of terms included is varied according to the Legend in the
top right.

The results of our experiment are shown in figure 5. The benefits of
increasing $L$ are more apparent than in the digit recognition experiment, we
can see better approximations being made at higher $L$. For some applications
more accuracy might be required, it seems increasing $L$ further will continue
improve this accuracy. Noteably all $L$ considered are orders of magnitude
below the amount of terms or circuits needed to apply the existing
partitioning schemes. The final mean squared error for unseen data averaged
over 5 random data sets is presented in the following table :

table 3.

L | Final validation MSE
---|---
1 | 0.366
5 | 0.168
10 | 0.111
20 | 0.0717
40 | 0.0481
80 | 0.0362
120 | 0.0322
Neural Net | 0.424
Table 3: Results of experiment comparing the validity of our assumptions. We
fix the value’s of $\theta$ and set the reduced partition model to learn the
output of a larger PQC, to simulate the larger PQC exactly using [bravyi2016]
would require $L=16,777,216$, the model is only able to select which
parameters to put on the gates resulting from the partition. Different values
of the hyperparameter $L$ are listed for comparison. A neural network is also
trained and performs poorly. Results are averaged over 5 runs.

Where we have included a neural network with a single dense hidden layer of
256 neurons for comparison purposes, other nerual neural network architectures
(1 and 2 hidden layers were tried, with 64 and 256 neurons per layer for each)
were tried without meaningful improvement, although it is possible that with
thorough tuning these architectures or others could be made to perform
strongly.

The previous results are sufficient to show that the training of just the
parameters $\bm{\zeta}$ and $\bm{\lambda}$ can lead to models with
substantially fewer terms, $L$, while still sufficiently approximating the
full circuit in this instance. This approximation was achieved with just the
training of $\bm{\zeta}$ and $\bm{\lambda}$, while fixing the $\bm{\theta}$ to
those that were used to generate the data. However it is not clear, a-priori,
that the reduced model should use the same $\bm{\theta}$ parameters to best
mimic the full model. We now allow $\bm{\theta}$ to deviate from that of the
generating PQC, the resulting mean squared error for unseen data after 20
epochs is presented in the following table : table 4.

L | Final validation MSE
---|---
1 | 0.176
5 | 0.112
10 | 0.0855
20 | 0.0600
40 | 0.0434
80 | 0.0334
120 | 0.0289
Neural Net | 0.424
Table 4: Mean squared error of the reduced partition model on learning the
output of a larger PQC, unlike table 2 all parameters are now free and we can
directly test the RPM’s capabilities on this task. Different values of the
hyperparameter $L$ are listed for comparison. A neural network is also trained
and performs very poorly. Results averaged over 5 runs.

This improvement in performance is unsurprising as the unrestricted model
includes the hypothesis of the model without training $\bm{\theta}$, however
it was not clear before the experiment that the model would be able to find
this higher performance, as the introduction of more parameters may have
created too many local optima for efficient optimisation. On the other hand we
may have expected a larger increase in performance, as $\bm{\theta}$ makes up
the majority of parameters, we should expect releasing $\bm{\theta}$ to
correspond to a big increase in performance. The lack of this increase could
be taken as weak evidence that our approximation (that a smaller set $L$ can
approximate the output of the whole circuit) to be relatively accurate in this
case, even without retraining $\bm{\theta}$.

Finally we use the synthetic data set as a training set for our model, with
random initialisation of weights. This third experiment allows us to test our
models performance on a task which a classical algorithm (the neural network)
performs poorly on, without prior knowledge of good parameters.

L | Final validation MSE
---|---
1 | 0.183
5 | 0.113
10 | 0.0944
20 | 0.0703
40 | 0.0540
80 | 0.0357
120 | 0.0362
Neural Net | 0.424

These performances are strong and comparable to the previous two experiments,
where $\bm{\theta}$ was given, showing that our model performs well on this
task, much better than the neural network we compare it to. This final
experiment is an excellent demonstration of our model as it would be deployed,
and demonstrates that it can learn a non-trivial task where a higher number of
qubits would naively be required.

###  VI.3 Open Source Code

Open source code is provided at https://github.com/simon-marshall in ipython
notebook format with an MIT licence to allow for easy reuse. 2 versions of the
code are provided, one to replicate either experiment.

##  VII Conclusion and future work

In this work we applied previously developed circuit cutting techniques to
parameterised quantum circuits. While it is obvious that this naive approach
used too many circuit evaluations to be computationally practical we noted
there may exist a smaller set of circuits which would sufficiently approximate
the original circuit, although we speculate that finding it would itself be
computationally intractable even if it did exist. Instead we proposed a new
model based on the relaxation of fixed gates into parameterised gates, such
that all circuits were identical up to the weights of these newly
parameterised gates. We showed our models hypothesis class contained the
relevant unparameterised hypothesis class, that its generalisation error was
well behaved and then went on to test it experimentally. The first experiment
showed the model was capable of tackling large problem sizes (handwriting). We
also tested the ability of a parameterised subset of circuits of the partition
to approximate the full unpartitioned output of a random circuit and found a
very satisfying approximation, although a larger amount of terms was needed
than with the handwriting task, suggesting a link between the problem and the
number of terms needed to achieve a given accuracy.

Further work is needed in establishing how many terms ($L$) might be required
for any given task, and what factors influence this requirement. Future work
could also focus around the application of this model, testing it out on
larger cutting edge problems, or on achieving higher accuracy. Improvements to
the model could come from a development of a robust training procedure to
avoid barren plateaus (Section V) or from integrating our work with some of
the excellent work already done on improving divide and conquer schemes
(Section II). Our work has opened the door for experimentation with much
larger “partially quantum” models both implicitly as we have done here, but
potentially explicitly, integrating more classical resources into a quantum
machine learning setting.

##  VIII Acknowledgements

The authors would like to thank Matthias Caro for his insights, particularly
on the link between different complexity measures and Elies Gil-Fuster. SCM
thanks Radoica Draškić and Yash Patel for their useful discussion. The authors
thank Andrea Skolik, Elies Gil-Fuster and Charles Moussa for helpful comments.
VD and SCM acknowledge the support by the project NEASQC funded from the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No 951821). VD and SCM also acknowledge partial funding by an
unrestricted gift from Google Quantum AI. VD and CG were supported by the
Dutch Research Council (NWO/OCW), as part of the Quantum Software Consortium
programme (project number 024.003.037).

##  Appendix A Example of increased complexity after the removal of a 2-qubit
gate

Consider the following circuit

where the encoding gates are RzRy. With the CNOT in place the state vector at
the end will always be $|{11}\rangle$, irregardless of the input vector.
Removing the CNOT entirely produces the following circuit:

produces the final state $\exp(-ix_{1})|{10}\rangle$. Which (when combined
with a larger circuit , in a way that utilises the presently just global
phase) can be used to differentiate points. With the cnot removed the final
state is $\cos(x_{1})|{10}\rangle+\sin(x_{1})|{11}\rangle$, which depends on
the input, $x_{1}$. In this way it is clear how a circuit making use of this
(rather pointless) gate would increase expressivety. No one would
realistically propose this circuit, but its existence prevents blanket
statements about the effect of removing 2 qubit gates on complexity and
therefore generalisation.

While no one would seriously implement this ansatz it serves to prove that in
some cases removing 2-qubit gates can infact increase the complexity

##  Appendix B Proofs of theorems

###  B.1 Proof of theorem III.1

For any given circuit, $U$, [bravyi2016] provides a decomposition:

${\color[rgb]{0,0,1}\uwave{U=\sum_{i=1}^{T}a_{i}\prod_{k=1}^{K}U^{i,k}}}$

For every element of our parameterised family we will be able to apply this
decomposition. The proof is just a matter of putting the decomposed circuits
of each family into a family of decomposed circuits which is trivial for
finite sizes.

###  B.2 Proof of lemma III.1

This is a trivial extension of the last theorem. For fixed $i,k$ we have to
find $U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k+K})$ such that

${\color[rgb]{0,0,1}\uwave{U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k})=U^{i,k}(\bm{\theta},\bm{x})}}$

We can achieve this by defining our new circuit family
$\\{U^{k}(\bm{\theta},\bm{x},\bm{\zeta}_{i,k})\\}_{\bm{\theta},\bm{x},\bm{\zeta}_{i,k}}$
to the equality when $\bm{\zeta}_{i,k}$ is (say) the one hot vector, such that
a 1 in the $i$’th position of the vector achieves the equality.

###  B.3 Proof of theorem III.2

${\color[rgb]{0,0,1}\uwave{\mathcal{F}^{L}_{\mathbb{U},M}\subset\overline{\mathcal{F}^{L}_{\mathbb{U},M}}}}$
(22)

The definitions of the functions in
$\overline{\mathcal{F}^{L}_{\mathbb{U},M}}$ are of precisely the same form as
shown to be equal to any function in $\mathcal{F}^{L}_{\mathbb{U},M}$, thus
the second class is contained in the first.


# Can we predict the Most Replayed data of video streaming platforms?

Alessandro Duico  Delft University of Technology  Ombretta Strafforello  Delft
University of Technology  TNO  Jan van Gemert  Delft University of Technology

###### Abstract

Predicting which specific parts of a video users will replay is important for
several applications, including targeted advertisement placement on video
platforms and assisting video creators. In this work, we explore whether it is
possible to predict the _Most Replayed_ (MR) data from YouTube videos. To this
end, we curate a large video benchmark, the _YTMR500_ dataset, which comprises
500 YouTube videos with MR data annotations. We evaluate Deep Learning (DL)
models of varying complexity on our dataset and perform an extensive ablation
study. In addition, we conduct a user study to estimate the human performance
on MR data prediction. Our results show that, although by a narrow margin, all
the evaluated DL models outperform random predictions. Additionally, they
exceed human-level accuracy. This suggests that predicting the MR data is a
difficult task that can be enhanced through the assistance of DL. Finally, we
believe that DL performance on MR data prediction can be further improved, for
example, by using multi-modal learning. We encourage the research community to
use our benchmark dataset to further investigate automatic MR data prediction.

##  1 Introduction

Video streaming has emerged as a dominant mode of online communication,
representing 73% of all internet traffic in 2017 (8), with YouTube leading the
way as the most popular platform. Video streaming platforms accumulate, in
addition to video data, a substantial amount of metadata, pertaining to users’
watching habits and interests. Notably, in May 2022 YouTube released a new
feature that shows a line chart of the most frequently replayed moments of
each video, the _Most Replayed_ data. In addition to aiding YouTube users
during video playback, this data can serve various other potential
applications, such as optimizing advertisement placement and giving feedback
to content creators – for instance, suggesting uninteresting scenes to remove.
In both cases, it is desirable to predict the Most Replayed data _before_
publishing a video. For advertisers, it enables placing advertisements
optimally from the very first views, thereby maximizing profits. For content
creators, it allows cutting the video appropriately before it reaches the
audience, preventing the reputational damage caused by re-uploading a video
after collecting the data.

In this work, we investigate whether it is possible to predict the Most
Replayed data using Deep Learning (DL). To this end, we collect YTMR500, a
dataset of 500 vlog and travel videos with their corresponding Most Replayed
data and pre-extracted video features. For a comprehensive description of our
dataset collection process, readers are referred to the Supplementary Material
(Section 1). We evaluate two DL models on YTMR500, consisting in a fully-
connected network and an attention-based architecture, inspired by the PGL-SUM
model that Apostolidis _et al_. (3) proposed for video summarization. We
compare the results of DL against human performance, which we estimate through
a crowdsourced user study.

We make the following contributions: (1) We introduce YTMR500, a dataset of
500 videos and the corresponding Most Replayed data, that can foster research
on most replayed data predictions in videos; (2) We design a variant of the
PGL-SUM (3) architecture, adapted to predict the Most Replayed data for unseen
videos; (3) We perform a user study to evaluate human performance on MR data
prediction. Our results show that predicting the Most Replayed data is
challenging for human annotators and that our model surpasses human
performance. The YTMR500 dataset and our code are publicly
available111https://github.com/ombretta/most-replayed-data.

##  2 Predicting the Most Replayed data in a video

###  2.1 Problem statement

Given a sequence of segments $\bm{V}$ in a video, we design a model to learn a
function $F$ that maps $\bm{V}$ into the Most Replayed (MR) data $Y$.
Specifically, the input is a sequence of 1024-dimensional video features,
$\bm{v_{t}}$, and the output is a sequence of scores $y\in[0,1]$. Formally,

$\displaystyle\bm{V}$
$\displaystyle=\\{\bm{v_{t}}\\}_{0}^{T},\bm{v_{t}}\in\mathbb{R}^{N=1024}$ (1)
$\displaystyle Y$ $\displaystyle=\\{y_{i}\\}_{0}^{I},I=100,y_{i}\in[0,1]$ (2)
$\displaystyle F$ $\displaystyle:\bm{V}\to Y.$ (3)

We want the model to determine the relative MR data of video segments when
compared to one another, while we do not care about predicting the exact value
of the Most Replayed data. Thus, instead of training the model using a Mean
Squared Error loss, as in (3), we opt for a ranking loss, namely PyTorch’s
MarginRankingLoss.

$\mathcal{L}(\hat{y}_{i},\hat{y}_{j},s)=\max(0,{-}s_{i,j}\cdot(\hat{y}_{i}{-}\hat{y}_{j})+\text{margin})$
(4)

To match this setup, we construct a ranking of video segments based on the
ground-truth (GT) $y_{i}$ and predicted $\hat{y}_{i}$ MR data scores. The
MarginRankingLoss forces the model to predict MR scores that result in a
ranking as close as possible to the GT. Concretely, the loss is applied to the
video segments in a pairwise fashion. In Equation 4, the targets $s_{i,j}$
must be one of $\\{1,-1,0\\}$. Here, $1$ indicates $y_{i}>y_{j}$, $-1$
indicates $y_{i}<y_{j}$, and $0$ indicates $y_{i}=y_{j}$. To obtain these
targets $s_{i,j}$, during training, we generate a comparison matrix of size
$T\times T$ given by $S_{i,j}=\text{sgn}(y_{i}-y_{j})$. Therefore, the ranking
of each pair of predictions $\\{\hat{y}_{i},\hat{y}_{j}\\}$ is encouraged to
match the ranking of the GT $\\{y_{i},y_{j}\\}$.

#### Interpolation

While the Most Replayed data in the YTMR500 dataset have fixed length, the
number of video features varies with the duration of the videos. To use a
recurrent or attention-based model, the length of the inputs and that of the
outputs must match. We overcome this issue in two different ways:

  1. 1.

interpolating the ground truth to match the size of the frame features;

  2. 2.

computing a binned average of the frame features, to match the size of the
ground truth.

In Case 1, the GT $Y$ is interpolated from its fixed size $100$ into a
variable size $T$. As a result, the interpolated GT $\widetilde{Y}$ has a
different size for each of the videos, depending on the video duration.
Considering that the number of frame features $T$ is always greater than
$100$, this type of interpolation allows us to supply a larger amount of input
data to the model, as compared to case 2. Since the number of comparisons in
the matrix $S$ grows quadratically with the size of the input, during training
we randomly sample a subset of 10,000 comparisons, for each iteration and each
video. Furthermore, the random sampling ensures that each video has the same
contribution to the loss, independently of $T$.

In Case 2, we divide the frame features $\bm{V}$ in $100$ bins of uniform size
and compute the average of the features within each bin. Therefore, the binned
frame features $\bm{\widetilde{V}}$ have a constant cardinality of $100$,
regardless of the video length. Using this strategy, the training becomes
computationally easier, as there are fewer elements to be ranked.

###  2.2 DL models

#### Fully connected model

As a baseline, we use a fully-connected model with two linear layers. We
include a Dropout layer to mitigate overfitting on the training set. The final
layer uses a Sigmoid activation function to coalesce the outputs into the
$[0,1]$ range, similarly to the GT. It is worth noting that this architecture
does not capture any temporal relationships between different segments of the
video.

#### Attention-based model

We investigate whether considering the temporal relationships across segments
improves the MR prediction accuracy beyond our baseline. We use an attention-
based model, following the architecture of PGL-SUM (Apostolidis _et al_. (3))
as closely as possible. PGL-SUM is based on Multi-Head Attention (MAH)
performed globally, _i.e_., for the whole duration of the video, and locally,
on a number of time windows – 4 in our setup – obtained from a partitioning of
the video. In the global attention module, we use 8 parallel attention heads,
similarly to (3) and to the original Transformer (20). In the local attention
modules we use 4 heads. An illustration of the deployed models is provided in
the Supplementary Material (Section 2).

###  2.3 User study

Since there exists no prior work on predicting the most replayed data in a
video, there are no indications on the feasibility and difficulty of the task.
We perform a user study to gain insights on how difficult predicting the most
replayed data is for humans. Our user study contains 30 videos randomly
selected from the test set. For the MR data prediction, we use a different
setup than for the DL model. We do this because the task performed by the DL
model, _i.e_., constructing a ranking of 100 video segments, is too complex
for human annotators. We simplify the task by subdividing each video in 10
shots rather than 100 and averaging the underlying 100 GTs into 10 bins.

We do not ask users to manually fill in the Most Replayed data, to prevent the
influence of biases, _e.g_., a bias towards continuity of the score across
segments. Instead, we show a series of side-by-side comparisons of two video
segments, to guide the users towards building a ranking. The user study is
composed of an introduction about the purpose of the Most Replayed data; the
full video, sped up to $30$s for convenience; 19 pairwise comparisons, with
the addition of an attention check. Each comparison presents participants with
two video shots, sped up to $10$s, along with the instructions: “Guess which
of the two video shots has greater ‘Most replayed’ score.” followed by the
mutually exclusive options: “Left”, “Right”, and “CONTROL”. As part of the
attention check, in one extra comparison, we place a video with a text overlay
asking to choose the “CONTROL” option. Participants who fail this simple check
are rejected.

The indices for the binary comparison were derived from the execution of the
MergeSort algorithm (13) on 10 elements. The number of comparisons, 19,
corresponds to the number of operations that the MergeSort algorithm needs to
construct a total ordering. The indices of the segments involved in the
comparisons are randomly permuted for each user, so that any imbalance with
the MergeSort indices is not reflected in the outcome. Once we have obtained
the answers to the pairwise comparisons, we construct a graph of the ordering
and perform depth-first graph traversal to reconstruct a unique ranking of the
segments.

The user study was crowdsourced to approximately 300 paid workers on Amazon
MTurk (1). Our crowdworkers population corresponds to the average demographics
on Amazon MTurk, with a uniform distribution across genders, mainly comprising
residents from the US and India, born between 1990 and 2000, as reported by
mturk-tracker (5). The number of users assigned to each video was 10 to 11,
which is sufficient to obtain a statistically significant result, according to
Carvalho _et al_. (4).

##  3 Results

#### Model training

We use 5-fold cross validation, with a 80/20 training/test ratio. Therefore,
of the 500 videos, 400 are utilized for training, and 100 for testing. To
train our models we follow a similar procedure to Apostolidis _et al_. (3) and
Fajtl _et al_. (7). We use the Adam optimizer (12) with learning rate $lr=$
$5\text{\times}{10}^{-5}\text{\,}\mathrm{a}$nd L2 regularization $\lambda=$
$1\text{\times}{10}^{-5}\text{\,}$. Each batch contains only one sample, which
is an entire video. This explains the low learning rate. For the
MarginRankingLoss, we always use a margin of $0.01$, except for when we are
training on 10 video shots, in which case we use a margin of $0.05$. We train
for 300 epochs, because at that point the training set accuracy reaches a
plateau. Even though other research commonly picks the best epoch with respect
to the test set (3, 7), we refrain from doing so not to artificially boost our
results. Therefore, when reporting the scores we average over the last 50
epochs (250 to 299) and all 5 splits.

#### Evaluation metrics

To evaluate our model, a ranking correlation metric could be used, _e.g_.,
Kendall’s $\tau$ (11). However, this would penalize equally errors at the
bottom and at the top of the ranking. Furthermore, we prioritize the global
ordering rather than the exact position of each element. For instance,
permutations of adjacent segments in the predicted ranking should not be
heavily penalized.

Hence, we use precision@K, a metric inspired from information retrieval (18).
Precision@K measures how many of the top K results are true positives, divided
by K. Given that we do not work with binary labels, we classify the top K
video shots in the ground truth as positives and the rest as negatives. Using
these labels, the metric corresponds to the proportion of the top K video
shots of the predicted ranking that are among the top K video shots in the
ground truth. We report precision@K for K in $\\{15,30,50\\}$, after
interpolating the total number of video shots to 100, when required. The
selection of $K=15$ is inspired by the evaluation practices for video
summarization in the literature (2) which typically adhere to a portion of 15%
of the total duration. The values of $K=30$ and $K=50$ were chosen to assess
precision at varying ranking depths. In the context of the user study, given
that there are only 10 video shots, we use values of K in $\\{1,3,5\\}$. It is
worth noting that precision@1 corresponds to top-1 accuracy, a metric commonly
used in image classification (15).

###  3.1 DL models

All models are able to sufficiently fit the training set, obtaining
precision@50 above $80\%$ on the test set. However, the performance at test
time is only marginally better than random. Results at test time are shown at
the top of Table 2. It is surprising that our fully-connected baseline
exhibits a satisfactory performance on this task, and the gains of the more
complex PGL-SUM architecture are minimal.

We perform an ablation study on the full model, to understand the contribution
of each component. At the bottom of Table 2 we report the scores for our model
without local attention, without global attention and without the residual
connection. We only display Case 1 of the interpolation, since the two cases
are almost identical in performance. We discover that the removal of global or
local attention does not heavily impact performance, contrary to the removal
of the residual connection (shown in Supplementary Material, Figure 2).
Therefore, we deduce that the crucial part of the learning is occurring on the
input frame features, within the fully-connected layers at the end of the
pipeline.

###  3.2 User study

To measure inter-rater agreement, we compute the Krippendorff’s $\alpha$ (14)
among all the users, for each video. Since the average $\alpha$ is $-0.017\pm
0.009$, we conclude that the users’ answers are generally not coherent with
one another. In Table 1 we compare the precision@K of the users’ rankings and
those generated by the DL model, in the simplified scenario with 10 video
segments. The top section of the table shows the results computed on the 30
videos included in the user study, while the bottom section shows the results
on the complete test set, averaged on 5 splits. Note that for the YTMR500 test
set, the standard deviation is computed between the results of the 5 splits
only, not across all the videos in the test set.

We report scores for our attention-based model in two scenarios: firstly, when
it is trained on the ground truth interpolated to 10 data points (“trained on
10” in Table 1), to closely match the task given to the users; secondly, when
it is trained on the complete ground truth (“trained on 100” in Table 1), and
averaged into 10 bins afterward. Naturally, training on more data, in the
“trained on 100” case, yields better performance. Users are not able to
perform significantly better than random on this task. Note that users do not
undergo the same training as our DL models, which means they must base their
predictions on their prior knowledge. From the results of our user study, we
believe that predicting the Most Replayed data from video segments is a
difficult task for humans.

Model | prec.@1 (%) | prec.@3 (%) | prec.@5 (%)
---|---|---|---
Random | 10 | 30 | 50
User study test set (30 videos)
Users (avg.) | 9.6 $\pm$ 25.9 | 31.8 $\pm$ 20.4 | 51.3 $\pm$ 15.3
PGL-SUM trained on 10 | $\mathbf{18.5\pm 15.0}$ | 37.0 $\pm$ 10.4 | 53.0 $\pm$ 6.9
PGL-SUM trained on 100 | 17.5 $\pm$ 12.4 | $\mathbf{39.2\pm 12.6}$ | $\mathbf{58.5\pm 9.5}$
YTMR500 test set ($5$ splits $\times 100$ videos)
PGL-SUM trained on 10 | 14.3 $\pm$ 2.9 | 35.0 $\pm$ 1.5 | 54.7 $\pm$ 1.5
PGL-SUM trained on 100 | $\mathbf{17.5\pm 2.7}$ | $\mathbf{38.1\pm 2.2}$ | $\mathbf{56.5\pm 1.8}$
Table 1: Results of our user study compared to our best DL model. Users are not significantly better than random. The DL models are always superior, and perform better when trained on more data, with one exception. N.b. precision@$\\{1,3,5\\}$ are computed on rankings of 10 segments. The precision of the DL model is averaged over the last 50 epochs. Standard deviation is computed among the 30 videos for the user study test set and among the splits of a 5-fold cross validation for the YTMR500 test set. Model | prec.@15 | prec.@30 | prec.@50
---|---|---|---
| (%) | (%) | (%)
Random | 15 | 30 | 50
Fully-connected 1 | 21.5 $\pm$ 1.8 | 37.6 $\pm$ 0.9 | 56.3 $\pm$ 0.4
Fully-connected 2 | 21.3 $\pm$ 1.6 | 37.4 $\pm$ 1.1 | 56.2 $\pm$ 0.7
PGL-SUM 1 | $\mathbf{22.0\pm 1.6}$ | $\mathbf{37.9\pm 1.0}$ | $\mathbf{56.8\pm 0.6}$
PGL-SUM 2 | $22.0\pm 1.9$ | $37.7\pm 0.8$ | $56.4\pm 0.6$
PGL-SUM 1 w/o local attention | $20.6\pm 2.0$ | $36.4\pm 1.0$ | $55.6\pm 1.0$
PGL-SUM 1 w/o global attention | $21.5\pm 1.7$ | $37.5\pm 1.1$ | $56.6\pm 0.7$
PGL-SUM 1 w/o residual | $19.4\pm 1.2$ | $35.6\pm 1.5$ | $55.1\pm 0.9$
Table 2: Results on the test set for our models, followed by some ablations.
All DL models perform better than random. Surprisingly, the gains of the more
complex PGL-SUM architecture are minimal, suggesting that attention between
the segments is not fundamental.
N.b. precision@$\\{15,30,50\\}$ are computed on rankings of 100 segments. The
numbers 1 and 2 refer to the type of interpolation: Case 1 is when the ground
truth is interpolated and Case 2 is when the frame features are averaged.

###  3.3 Discussion

Based on our experiments in Section 3.1, we observe that using a more complex
architecture does not induce a significant performance gain over the fully-
connected baseline. Contrarily to our speculations, it seems that providing
each segment with context about the full video does not improve the accuracy.
We hypothesize that the pre-extracted video features alone provide sufficient
abstraction to the fully-connected network to generate a satisfactory output
from individual segments. As demonstrated by the ablation without a residual
connection, hiding the input features from the fully-connected layers hinders
performance. As shown by the users’ performance in our user study in Section
3.2, predicting the Most Replayed data is an arduous task. One plausible
explanation is that the ground truth is noisy and lacks any clear patterns
with respect to the input. Upon manual analysis of several videos, we found it
hard to justify the location of certain peaks in the Most Replayed data.
Another possible explanation is that video-only input does not provide enough
information to resolve the problem effectively. Some peaks may be caused by
interesting information in the speech, while others could result from dramatic
changes in loudness. We defer to further research to incorporate multimodal
inputs, particularly from audio channels and text transcripts.

##  4 Conclusion

The Most Replayed data presents a new source of insight on users’ interests in
online video streaming. In this work, we focus on predicting this data using
Deep Learning and compare the results against human performance, measured
through a user study. For our experiments, we use YTMR500, a novel dataset
comprising 500 vlog videos and their corresponding Most Replayed data. All the
DL models evaluated on on YTMR500 perform significantly better than random,
whereas the human participants are not able to accurately predict the Most
Replayed data. We believe future research can further enhance the results, for
instance, by incorporating multimodal inputs. We encourage the community to
deploy our dataset in follow-up work.

Supplementary Material

##  1 The YTMR500 dataset

Given a video, we investigate whether it is possible to predict which specific
parts users will watch and replay. Since we are the first to tackle this
problem, we cannot use pre-existing datasets. Therefore, we introduce a novel
dataset of videos and annotations collected from YouTube, _YTMR500_ (“YouTube
Most Replayed 500”). The dataset consists of 500 videos, in the form of with
pre-computed spatio-temporal features, and the corresponding Most Replayed
data. The videos have average duration of 11.9$\pm$4.1 minutes. The dataset
creation process can be outlined in three main steps: (1) Data collection, (2)
Feature extraction and (3) Cleanup.

#### Step 1a: Video data collection.

We retrieve videos from YouTube matching the following criteria:  i) under the
Creative Commons license,  ii) duration from 3 to 20 minutes, and  iii) at
least 30 thousand views.  A high view count is necessary in order for YouTube
to make the Most Replayed data publicly visible. We use the search queries
“vlog”, “trip”, “travel”, “visiting” to obtain a list of videos, which are
then selected to exclude those with static backgrounds or bad recording
quality. Some thumbnails of the videos in the dataset can be seen in Figure
S2.

#### Step 1b: Retrieval of the Most Replayed data.

For each of the videos in Step 1a, we download 222https://github.com/Benjamin-
Loison/YouTube-operational-API the Most Replayed data, discarding those for
which the data is missing. Concretely, the Most Replayed data consists of 100
scalars in the $[0,1]$ range, for each video. Hence, for videos of varying
duration, each data point covers a different time duration.

#### Step 2: Feature extraction

We use a pre-trained model to extract features from the videos. The model
takes as input a segment of 32 frames, which corresponds to $\sim 1.1$s of
video, and outputs a feature vector of 1024 dimensions. This helps reduce the
complexity of the input to our trained model upfront and makes the
architecture compatible with any resolution and video format. It also reduces
the dataset size, with our settings, by a factor of 2.7 (from 7GB to 2.6GB).
Multiple models were taken into consideration for this step, either image-
based or video-based. Image features, common in video summarization works (3,
7, 19), cannot capture any temporal relationship between the frames of the
segment. For this reason, we opt to use video features in our preprocessing.
We choose _I3D_ as it is pre-trained on the extensive Kinetics-400 (10) and is
a popular choice in the literature (6, 9, 16, 17). Specifically, we obtain RGB
features from the “Mixed 5c” layer of _I3D_ , _i.e_., the second-to-the-last
layer, which are 1024-dimensional vectors
333https://github.com/v-iashin/video_features. Note that, for uniformity, all
videos are first downsampled to 30 fps before feature extraction.

#### Step 3: Cleanup

To reach the number of 500, a few excess videos are removed. The Most Replayed
data annotations are transformed into a vector of size $100$, removing
unnecessary metadata. The annotations are packaged together with the video
features, having size $1024\times T$, with $T$ proportional to video duration.

##  2 Predicting the Most Replayed data in a video

###  2.1 Deep Learning models

#### Fully connected model

We deploy as baseline a fully-connected model, shown in Figure S1. The model
maps each input feature vector to a scalar in the range $[0,1]$. This
architecture does not capture any temporal relationships between different
segments of the video.

#### Attention-based model

We investigate whether considering the temporal relationships across segments
improves the MR prediction accuracy beyond our fully-connected baseline. For
this, we use an attention-based model inspired by the architecture of PGL-SUM
(Apostolidis _et al_. (3)). The model is shown in Figure S3.

$\dots$I3D features$\dots$I3D featuresInputsLinear Layerwith ReLUDropout
0.5Linear Layerwith
Sigmoid${\hat{y}_{1}}$${\hat{y}_{2}}$${\dots}$${\hat{y}_{I}}$$\left[\vbox{\hrule
height=11.47713pt,depth=11.47713pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=11.47713pt,depth=11.47713pt,width=0.0pt}\right]$Output for each
feature vector

Figure S1: Our fully-connected baseline. We use a $50\%$ Dropout to prevent
the model from overfitting the training set. Figure S2: We introduce the
_YTMR500_ dataset, which contains 500 vlog and travel videos and the
corresponding Most Replayed data.

$\dots$I3D features$\dots$Inputs $\dots$ Time windows Local Attention $\dots$
Local Attention $+$$+$$+$GlobalAttentionLocal attention moduleDropout
0.5LayerNormLinear Layerwith ReLUDropout 0.5LayerNormLinear Layerwith
Sigmoid${\hat{y}_{1}}$${\hat{y}_{2}}$${\dots}$${\hat{y}_{I}}$$\left[\vbox{\hrule
height=11.47713pt,depth=11.47713pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=11.47713pt,depth=11.47713pt,width=0.0pt}\right]$OutputFully-connected
model (+ LayerNorm)Residual connection

Figure S3: Our attention-based model architecture is inspired by PGL-SUM of
Apostolidis _et al_. (3). The Global Attention module can capture
relationships between each of the segments of the video, while the Local
Attention modules focus on relationships inside a section. Ultimately, two
linear layers map the vector output of the attention modules into a scalar,
for each segment.

## Acknowledgements

This work is part of the research program Efficient Deep Learning (EDL), which
is (partly) financed by the Dutch Research Council (NWO).

## References

  * (1) Amazon mechanical turk.  https://www.mturk.com/.  Accessed: 25 June 2023.
  * (2) Evlampios Apostolidis, Eleni Adamantidou, Alexandros I Metsai, Vasileios Mezaris, and Ioannis Patras.  Video summarization using deep neural networks: A survey.  Proceedings of the IEEE, 109(11):1838–1863, 2021.
  * (3) Evlampios Apostolidis, Georgios Balaouras, Vasileios Mezaris, and Ioannis Patras.  Combining global and local attention with positional encoding for video summarization.  In 2021 IEEE International Symposium on Multimedia (ISM), pages 226–234, December 2021.
  * (4) Arthur Carvalho, Stanko Dimitrov, and Kate Larson.  How many crowdsourced workers should a requester hire?  Annals of Mathematics and Artificial Intelligence, 78(1):45–72, 2016.
  * (5) Djellel Difallah, Elena Filatova, and Panos Ipeirotis.  Demographics and dynamics of mechanical turk workers.  In Proceedings of the eleventh ACM international conference on web search and data mining, pages 135–143, 2018.
  * (6) Keval Doshi and Yasin Yilmaz.  End-to-end semantic video transformer for zero-shot action recognition, 2022.
  * (7) Jiri Fajtl, Hajar Sadeghi Sokeh, Vasileios Argyriou, Dorothy Monekosso, and Paolo Remagnino.  Summarizing videos with attention.  In Gustavo Carneiro and Shaodi You, editors, Computer Vision - ACCV 2018 Workshops - 14th Asian Conference on Computer Vision, Perth, Australia, December 2-6, 2018, Revised Selected Papers, volume 11367 of Lecture Notes in Computer Science, pages 39–54. Springer, 2018.
  * (8) Cisco VNI Forecast.  Cisco predicts more ip traffic in the next five years than in the history of the internet.  https://newsroom.cisco.com/press-release-content?articleId=1955935, 2017-2022.  Accessed: 22 August 2023.
  * (9) Rohit Girdhar, Joao Joao Carreira, Carl Doersch, and Andrew Zisserman.  Video Action Transformer Network.  In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 244–253, Long Beach, CA, USA, June 2019. IEEE.
  * (10) Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, Mustafa Suleyman, and Andrew Zisserman.  The kinetics human action video dataset, 2017.
  * (11) M. G. Kendall.  A new measure of rank correlation.  Biometrika, 30(1-2):81–93, 06 1938.
  * (12) Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2017.
  * (13) Donald Knuth.  Sorting and Searching, volume 3 of The Art of Computer Programming.  Addison-Wesley, 2nd edition, 1998.
  * (14) Klaus Krippendorff.  Content analysis: An introduction to its methodology.  Sage Publications, 2004.
  * (15) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
  * (16) Zekang Li, Zongjia Li, Jinchao Zhang, Yang Feng, and Jie Zhou.  Bridging text and video: A universal multimodal transformer for audio-visual scene-aware dialog.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 29:2476–2483, 2021.
  * (17) Devraj Mandal, Sanath Narayan, Saikumar Dwivedi, Vikram Gupta, Shuaib Ahmed, Fahad Shahbaz Khan, and Ling Shao.  Out-of-distribution detection for generalized zero-shot action recognition, 2019.
  * (18) Hinrich Schütze, Christopher D Manning, and Prabhakar Raghavan.  Introduction to information retrieval, volume 39.  Cambridge University Press Cambridge, 2008.
  * (19) Yale Song, Jordi Vallmitjana, Amanda Stent, and Alejandro Jaimes.  Tvsum: Summarizing web videos using titles.  In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5179–5187, 2015.
  * (20) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.