figurec

# Calibrating the role of entanglement in variational quantum circuits

Azar C. Nakhl<EMAIL_ADDRESS>School of Physics, The
University of Melbourne, Parkville, 3010, VIC, Australia  Thomas Quella
<EMAIL_ADDRESS>School of Mathematics and Statistics, The
University of Melbourne, Parkville, 3010, VIC, Australia  Muhammad Usman
<EMAIL_ADDRESS>School of Physics, The University of Melbourne,
Parkville, 3010, VIC, Australia  Data61, CSIRO, Clayton, 3168, VIC, Australia

Entanglement is a key property of quantum computing that separates it from its
classical counterpart, however, its exact role in the performance of quantum
algorithms, especially variational quantum algorithms, is not well understood.
In this work, we utilise tensor network methods to systematically probe the
role of entanglement in the working of two variational quantum algorithms, the
Quantum Approximate Optimisation Algorithm (QAOA) and Quantum Neural Networks
(QNNs), on prototypical problems under controlled entanglement environments.
We find that for the MAX-CUT problem solved using QAOA, the fidelity as a
function of entanglement is highly dependent on the number of layers, layout
of edges in the graph, and edge density, generally exhibiting that a high
number of layers indicates a higher resilience to truncation of entanglement.
This is in contrast to previous studies based on no more than four QAOA layers
which show that the fidelity of QAOA follows a scaling law with respect to the
entanglement per qubit of the system. Contrarily, in the case of QNNs, trained
circuits with high test accuracies are underpinned by higher entanglement,
with any enforced limitation in entanglement resulting in a sharp decline in
test accuracy. This is corroborated by the entanglement entropy of these
circuits which is consistently high suggesting that, unlike QAOA, QNNs may
require quantum devices capable of generating highly entangled states. Overall
our work provides a deeper understanding of the role of entanglement in the
working of variational quantum algorithms which may help to implement these
algorithms on NISQ-era quantum hardware in a way that maximises their
accuracies.

##  I Introduction

The development and benchmarking of quantum algorithms have attracted
significant attention in recent years because their in-principle capability to
solve classically intractable problems[1] when coupled with advances in
quantum hardware is anticipated to provide a quantum advantage in a range of
real-world applications[2]. Among a variety of quantum algorithm classes that
are being developed, one particular class known as Variational Quantum
Algorithms (VQA) has been the subject of intense research due to the
possibility of combining the manipulation of quantum systems with classical
optimisation techniques[3], allowing one to take advantage of the high
dimensionality of the state space of quantum systems along with sophisticated
optimisation algorithms. In particular, these quantum algorithms with
classically optimised variational parameters have found applications in
chemistry[4, 5, 6], finance[7, 8], operations research[9, 10, 11, 12] and more
recently in quantum machine learning models[13, 14, 15, 16, 17, 18, 19, 20,
21].

However, unlike conventional quantum algorithms, such as those for dictionary
search[22], or semi-prime number factorisation[23], VQAs rely on heuristic
approaches. Importantly this means that even without quantum hardware noise
there is no guarantee of these algorithms’ performance on any given instance.
As a result, there is a significant amount of research on the performance
analysis of these algorithms[24, 25, 26, 27, 28]. Entanglement is one of the
key metrics that may be used to analyse the performance of VQAs, but as of yet
there has only been limited investigation of the role of entanglement with
regard to these algorithms[29, 30, 31, 32]. Our work aims to fill this
knowledge gap by providing a systematic and comprehensive calibration of the
role of entanglement in the functionality of two widely used variational
quantum algorithms: (1) the Quantum Approximate Optimisation Algorithm
(QAOA)[33] used for combinatorial optimisation tasks and; (2) Quantum Neural
Networks (QNNs)[14] used in a variety of machine learning applications
including in image classification[14, 16, 17], drug response prognosis[20] and
breast cancer prediction[21, 18, 19], among others. This work will use Matrix
Product State[34, 35] (MPS) simulations to analyse how these two algorithms
perform when their entanglement is restricted. We will also track the
entanglement entropy of these algorithms as the system size and depth of the
quantum circuit increase.

a) Full Circuit b) Linear Circuit

c) Periodic Circuit c) Single Control Circuit d) Alternating Circuit

Figure 1: The various QNN circuits considered in this work with labels above.
Each block may be repeated $p$ times with new parameter vectors
$\boldsymbol{\theta}_{i}^{j}$ each taking three real values. For an $n$ qubit
system, each layer has $n$ $U(\mathbf{\theta})$ arbitrary one-qubit gates as
defined in Ref. [1]. The number of entangling gates per layer is a)
$n(n-1)/2$, b) $n$, c) $n+1$, d)-e) $n$. All circuits have the first and last
layers shown, except for the full circuit for brevity. The different circuits
represent a different entanglement structure, except for the Linear and Full
circuits which can be shown to be identical as per Ref. [31].

For QAOA, in the context of the paradigmatic combinatorial optimisation
problem MAX-CUT, it has been shown that there is a volume law entanglement
barrier between the initial and final state of the algorithm[30], suggesting
that tensor network simulation methods[34, 35], whose memory and computational
resource requirements scale exponentially with the entanglement of the quantum
system are not able to simulate QAOA efficiently. This is corroborated by Ref.
[29] which shows that for complete graphs with random edge weights and
3-regular graphs with random edges, the fidelity of QAOA with few number of
layers follows a scaling law with respect to the entanglement per qubit such
that the fidelity is the same regardless of the size of the system. It remains
open as to whether such a scaling law holds for circuits with greater than
four QAOA layers or different classes of graphs, such as grid graphs or
$k$-regular graphs (where $k\neq 3$), a question that we will address in this
work. Similar studies of the fidelity with respect to entanglement per qubit
have also been conducted for Grover’s Algorithm, the Quantum Fourier Transform
and the quantum counting algorithm[36].

A second class of VQAs that has attracted significant attention in recent
years are Quantum Neural Networks (QNNs) used to perform machine learning
tasks. In general, Quantum Machine Learning (QML) models can range from
quantum subroutines of an overall classical process[14, 15, 17, 16, 18, 19,
21, 20] to completely quantum analogues of established machine learning
models[37, 38]. Contrary to other VQAs however there has only been limited
investigation as to how entanglement grows within these QML models. For
example, in the case of parameter optimisation-based methods such as QNNs, it
is recognised that entanglement-induced barren plateaus will arise for models
that satisfy volume-law growth in their entanglement entropy[39].
Additionally, there has also been investigation of the entanglement entropy of
QNN architectures with random parameters for up to 50 qubits[31]. However, we
are not aware of any previous work which has studied the entanglement of
trained QNNs. This will be the second focus of our work.

Tensor Networks provide an efficient method to quantitatively assess and
control the entanglement of a quantum state. In particular, MPS have found
significant application in the simulation of quantum algorithms on classical
computers in general[40, 41], and specifically for the study of entanglement
in quantum algorithms [29, 36, 31]. MPS are characterised by one freely
adjustable parameter, their bond dimension, which translates into an upper
bound on the entanglement entropy of the quantum system. Moreover, the
entanglement entropy can be efficiently determined from an MPS[42].

The bond dimension $\chi$ of an MPS is the primary driver of memory
utilisation, scaling as $O(N\chi^{2})$ for a system with $N$ sites. As a
result, states of high entanglement are difficult to represent, whereas
systems with relatively low entanglement may be represented in an efficient
manner. This may be compared to state-vector simulations which generally have
a memory requirement of $O(2^{N})$[1]. Unlike state-vector simulation methods,
quantum states represented as MPS may be approximated in such a way that their
bond dimension is reduced systematically, providing a way to control the
entanglement of the state at the cost of fidelity. This, along with the
ability to perform local operations on the state locally in memory, are the
key benefits of using MPS to study quantum systems and quantum algorithms.

In this work, we study the properties of QAOA when applied to the solution of
the MAX-CUT problem on 3-regular, 4-regular, complete and grid graphs for a
varying number of QAOA layers. We demonstrate that the entanglement of the
resulting QAOA circuits is highly dependent on both the type of graph and the
number of QAOA layers. As a result, we find that previously proposed scaling
laws for 3-regular and complete graphs[29] do not hold true for larger-depth
QAOA circuits or graphs with a structured edge layout such as the grid graph.
This observation has implications for the use of QAOA to solve tasks, such as
the vehicle routing problem[11] which has an underlying graph that is low
density and regular, and some spin-glass models[43] where the underlying graph
is a grid graph. We find that the entanglement per qubit required to achieve
high fidelity for such types of underlying graphs is low. This is contrasted
with tasks such as aircraft tail assignment[12] which have underlying graphs
which are of high density, where we conclude that the entanglement per qubit
required to achieve high fidelity is relatively high.

Importantly, our findings demonstrate that the entanglement scaling of QAOA on
average is not indicative of its scaling for specific tasks and furthermore
that the entanglement at low depth, where one is unlikely to find an
appropriate solution is fundamentally different to that at high depth, where
our work suggests that the entanglement per qubit required to achieve high
fidelity is significantly reduced.

We then consider QNNs which are a type of VQA that have a circuit structure
which is substantially different from that of QAOA. We show that various QNN
ansätze, each corresponding to a different entangling gate layout as per FIG.
1, have an entanglement entropy that depends on the dataset that is
considered. In general, we find that the QNNs are highly entangled, with
simpler datasets having a relatively lower entropy of entanglement throughout
the QNN. We show that the test accuracy scaling as a function of the
entanglement per qubit is strongly correlated with the accuracy of the
training, with poorly trained circuits being more resilient to a truncation in
the entanglement of the circuit. This indicates a high degree of entanglement
present in the trained circuits, suggesting that a pathway to demonstrating
quantum advantage for QNNs may be available.

##  II Methods

In this section, the theory underpinning the MPS representation of quantum
systems will be introduced, focusing on how its key characteristic, the bond
dimension is related to a quantum state and how it can be used as a metric for
entanglement. The bond dimension and control thereof will be central to our
analysis of QAOA and QNNs. QAOA will also be introduced, along with the
specific problems that will be considered, namely MAX-CUT on varying types of
regular, complete and grid graphs. Lastly QNNs, and specifically their
application to image classification will be considered, where different types
of circuits will be introduced, along with different datasets on which our
circuits will be trained. QAOA and QNNs have a wide variety of applications
and encapsulate two of the most common circuit architectures for VQAs, where
for QAOA the circuit structure is necessarily one that is dependent on the
problem instance, whereas for QNNs the circuit structure may be generic or
tailored to the quantum device which the algorithm will be executed on.

###  II.1 Matrix Product States

MPS are a tensor network representation of one-dimensional many-body quantum
states. We will assume that the total system consists of $N$ individual
$d$-level subsystems whose Hilbert space is spanned by orthonormal vectors
$|i_{s}\rangle$ with $i_{s}=0,\ldots,d-1$ and $s=1,\ldots,N$. For qubits, the
relevant unit in quantum computing applications, one has $d=2$. Each many-body
quantum state can then be represented in the form,

$|\psi\rangle=\sum_{i_{1},i_{2},\dots,i_{N}}A^{(1)}_{i_{1}}A^{(2)}_{i_{2}}\dots
A^{(N)}_{i_{N}}|i_{1}i_{2}\dots i_{N}\rangle,$ (1)

where the $A^{(s)}_{i_{s}}$ are suitably sized matrices that encode its
entanglement. It is custom to choose these matrices to be square matrices of
$s$-independent size $\chi\times\chi$, where $\chi$ is referred to as the bond
dimension. Only the matrices at the two ends of the matrix product are
$1\times\chi$ and $\chi\times 1$ matrices, respectively. This ensures that the
matrix product evaluates to a complex number in Eq. (1). Alternatively, for
fixed $s$ the set of matrices $A^{(s)}_{i_{s}}$ can be viewed as a rank-3
tensor, with one physical index $i_{s}$ and two auxiliary indices
corresponding to the matrix rows and columns. Using Penrose graphical
notation[42] MPS are then represented as,

$\ket{\psi}=\begin{array}[]{c}\@add@centering\centering\includegraphics[scale={1}]{mps.pdf}\;,\end{array}$
(2)

where $A^{(s)}=\sum_{i=0,1,\dots,d-1}\ket{i}\otimes A^{(s)}_{i}$ is a rank-3
tensor.

Given an MPS one may determine the entanglement entropy of a bipartition
between sites $s$ and $s+1$ by performing high-order singular value
decomposition (SVD)[44] on the $A^{(s)}$. Performing a high order SVD on all
the $A^{(s)}$ allows for the MPS to be put into a canonical form[45] in which
it is a simple process to determine the entanglement entropy of the state at
any given bipartition between adjacent sites. The singular values
$\Lambda_{i}^{(s)}$ may be used in the following equation to give the
entanglement entropy,

$S_{s}=-\sum_{i}\absolutevalue{\Lambda^{(s)}_{i}}^{2}\log(\absolutevalue{\Lambda^{(s)}_{i}}^{2}).$
(3)

By the principle of maximum entropy, $S_{s}$ is maximal when the
$(\Lambda^{(s)}_{i})^{2}=\frac{1}{\chi}$ for all $i$. When this is the case
one finds $S_{s}=\log\chi$, which is an upper bound for the entanglement
entropy of any bipartition. Hence any limitation in $\chi$ is effectively
enforcing a reduction in the entanglement entropy of the bipartition. We will
use this to our advantage to produce low entanglement approximations of
quantum states at the cost of a reduction in the fidelity of the state.

One can enforce a reduction in the bond dimension of an MPS via a process
known as truncation. As part of this process, the smaller singular values
resulting from the higher-order SVD on the $A^{(s)}$ are set to zero. In doing
so the bond dimension $\chi$ of the MPS is reduced. A more detailed outline of
the process of truncation can be found in Ref. [42]. The result of this
process is an MPS which only approximates the original state.

For our MPS-based circuit simulations, we utilise the open-source library
quimb[46] which has in-built quantum circuit simulation capability. Local
expectation values are computed analytically at the end of each circuit. Due
to performance constraints with the quimb library, the VQA minimisation
procedure is performed using a conventional state vector simulator,
specifically that packaged within IBM’s Qiskit SDK[47] for QAOA and Xanadu’s
Pennylane[48] for QML. This is equivalent to performing the minimisation using
an MPS-based circuit simulator without truncation. This procedural limitation
is noted in the results, with the implications of such limitations considered
for both VQAs studied. The optimised states are truncated by keeping only
$2^{i}$ singular values per internal bond for all $i=1,2,\dots,{N/2}$. As such
one has approximations ranging from low entanglement to high entanglement. It
is recognised that in general $2^{N/2}$ singular values are required to
represent an $N$ qubit system as an MPS exactly. For the truncated circuits,
we thus use the following metric to illustrate the entanglement of the
truncated circuit,

$\text{Entanglement per Qubit}=\frac{2\log_{2}(\chi)}{N}.$ (4)

This metric is the same as that used in Ref. [29], rescaled such that it is in
the interval $[0,1]$. This is done so that the value measured by this metric
is more intuitively understood without the need to consider the underlying MPS
representation. To quantify the performance of truncated MPS simulations, we
define a quantity that we call the simulation fidelity which is identical to
the “fidelity” metric used in Ref. [29] as,

$\text{Simulation Fidelity}=\frac{\text{Cost}(\chi)}{\text{Cost}(2^{N/2})}.$
(5)

We call the metric the simulation fidelity to avoid confusion with the
conventional definition of fidelity used for quantum states. The
$\text{Cost}(\chi)$ is the cost function associated with the VQA evaluated
using an MPS circuit simulation which has a maximum bond dimension of $\chi$.
This will be explicitly defined for the VQAs where this metric is used in the
sections below. A further discussion on the simulation fidelity, particularly
as it pertains to this work can be found in Appendix A.

###  II.2 Quantum Approximate Optimisation Algorithm

QAOA prepares a quantum circuit as a sequence of time-evolution operators of
some problem Hamiltonian $H_{P}$, representing some combinatorial optimisation
problem, and a mixer Hamiltonian $H_{M}$[33]. For an $n$-qubit system, a $p$
layered QAOA takes the following form,

$\ket{\psi(\alpha_{i},\beta_{i})}=\prod_{k=1}^{p}(e^{-i\alpha_{k}H_{P}}e^{-i\beta_{k}H_{M}})\ket{+}^{\otimes
n},$ (6)

where the product is ordered in the following way,
$\prod_{k=1}^{p}A_{k}=A_{p}A_{p-1}\dots A_{1}$. The initial state is defined
by $\ket{+}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$, and the mixer Hamiltonian is
defined as $H_{M}=\sum_{i=1}^{n}X_{i}$, where $X$ is the Pauli $X$ gate. Note
that the problem Hamiltonian $H_{P}$ is assumed to be diagonal in the
computational basis, and is, for the purposes of this work, quadratic at most.
As such the state described by Equation (6) may be prepared in a
straightforward manner using standard one and two-qubit operators. The
parameters $\alpha_{i}$, $\beta_{i}$ in Equation (6) may then be optimised
using the following cost function,

$\text{Cost}(\alpha_{i},\beta_{i},\chi)=\matrixelement{\psi_{\chi}(\alpha_{i},\beta_{i})}{H_{P}}{\psi_{\chi}(\alpha_{i},\beta_{i})},$
(7)

where $\ket{\psi_{\chi}}$ indicates an approximation of the state $\ket{\psi}$
with bond dimension of at most $\chi$ performed using truncation as per
Section II.1.

a) b) c) d)e)f)

g)  h)  $\rightarrow$

Figure 2: The various graph classes considered in this work are: a) Complete
graphs with random edge weights (not shown), b) 3-regular graphs with random
edge assignment and unit edge weights, c) 4-regular graphs with random edge
assignment and unit edge weights, d)-f) grids of d) two, e) three and f) four
columns with random edge weights, these are distinct from other 3 and
4-regular graphs as they have a specific edge structure. g) Beginning with a
two-row grid with random edge weights, evolve by randomly assigning new edges
with random weights selected from a uniform distribution over $[0,1]$ until a
complete graph with $L\times 2$ nodes is formed. h) A single layer QAOA
circuit for a four-node complete graph, with variational parameters
$\alpha_{1}$ and $\beta_{1}$ as per Equation (6). The QAOA circuit may be
executed using an MPS simulator.

One of the most common combinatorial optimisation tasks studied using QAOA is
the MAX-CUT problem[33, 27, 49, 50, 51] which seeks to partition a graph $G$
with vertices $V$ and edges $E$ into two non-overlapping sets with the maximal
number of edges between the two sets. The MAX-CUT problem can be represented
by the following problem Hamiltonian[52],

$H_{P}=\sum_{(i,j)\in E}w_{ij}Z_{i}Z_{j},$ (8)

where $w_{ij}$ is the weight of the edge between nodes $i$ and $j$, and $Z$ is
the Pauli $Z$ gate. This Hamiltonian may be solved using QAOA in a
straightforward manner[33]. It has been established that a number of common
optimisation problems may be formulated in terms of Hamiltonians of the form
in Equation (8) on specific graphs[52]. For example, spin-glass models such as
the Sherrington-Kirkpatrick model[53] and Edwards–Anderson model[43] can be
reduced to MAX-CUT problems on complete and grid graphs respectively, both
with edge weights $w_{ij}\in\\{1,-1\\}$. Additionally, MAX-CUT has
applications in circuit design[54] where the underlying graph is planar, as
well as machine scheduling[55] where the underlying graph is complete.

In this work, complete graphs with random uniform weights $w_{ij}\in[0,1]$ and
3-regular graphs with unit weights, i.e. graphs with nodes each of degree
three, will initially be considered similar to Ref. [29]. Examples of such
graphs can be seen in FIG. 2(a-b). We will be simulating these systems up to
$p=6$ QAOA layers for all graphs, which is greater than the $p\leq 2$ and
$p\leq 4$ simulations undertaken for complete and 3-regular graphs
respectively in previous works[29]. In doing so we seek to determine whether
higher-depth QAOA has similar characteristics to low-depth QAOA. Such a
distinction is important as in general one requires higher depth circuits in
order to determine the solution state to high accuracy[56]. The accuracy of
QAOA may be measured using a common metric known as the approximation ratio
which is introduced in Appendix B. This metric is used to track the
performance of the QAOA simulations for up to six layers for the types of
graph considered in the main body of this work in Appendix C.

Additionally, grid graph simulations will be performed, as unlike random
regular graphs this class has a structured edge layout and is planar making it
similar to the underlying graphs of the common applications of MAX-CUT
introduced above. Firstly, in order to draw comparisons between grid graphs
and other graphs of the same uniform degree, 4-regular graphs with random
uniform edge weights will also be simulated as per FIG. 2(c). Then, grids with
two, three and four columns and random uniform edge weights will be considered
as per FIG. 2(d-f). Simulation of all types of graphs considered in this work
will be undertaken for $1,\dots,6$ layers.

Another component of our study is to systematically explore the intermediate
regime between grid graphs of two rows and complete graphs at two QAOA layers
by starting with a grid graph and growing it by adding an edge with a randomly
assigned edge weight between two nodes chosen at random that are otherwise not
connected. This is repeated until the graph is complete. This process can be
visualised in FIG. 2(g). We anticipate that the characteristics of the
simulations, that is the entanglement entropy and simulation fidelity, will be
dependent on the fundamental properties of the graph, that is the number of
nodes, the number of edges and the layout of the edges. A metric that
encapsulates the number of edges relative to the number of nodes is called the
edge density and is defined on a graph $G=(V,E)$ as[57],

$\text{Density}=\frac{2|E|}{|V|(|V|-1)}.$ (9)

The density will be used as a point of comparison between different graphs
when analysing how QAOA performs on these instances.

For all optimisations the SLSQP optimiser[58] is utilised to minimise the QAOA
parameters $\alpha_{i}$, $\beta_{i}$ with the following hyperparameters;
maxiter=500, ftol=1e-13, tol=1e-13. The optimisation is repeated $10^{3}$
times with different initial $\alpha_{i}$, $\beta_{i}$ selected uniformly at
random from $[-\pi,\pi]$. IBM’s Qiskit aer simulator is used to find an
initial set of optimal parameters, feeding this result into the quimb MPS
simulator for the restricted entanglement simulations. Truncation of singular
values to adhere to bond dimensions $\chi<2^{N/2}$ is performed after each
QAOA layer. For each type of graph defined, an average of over 100 random
instances is taken.

###  II.3 Quantum Machine Learning

QNNs[31, 59], sometimes referred to as QVCs[16, 17] are machine learning
models characterised by multiple layers of parameterised unitary
transformations. They have found significant applications over recent years in
image classification[17, 14], drug response predictions[20], and breast cancer
prediction[21], amongst other tasks[59, 60, 61]. Unlike QAOA, QNNs have a
flexible circuit structure, allowing for circuits to be structured in such a
way that they may be efficiently executed on a quantum device[62]. In that
sense they are similar to the Variational Quantum Eigensolver (VQE)[4], with
the primary distinguishing feature being that QNNs must first receive an input
state which they will attempt to classify, as opposed to VQE and QAOA which
simply optimise a given ansatz according to some cost function which
completely defines the problem. One may also consider circuit ansätze which
have a specified entanglement layout as defined by their two-qubit operators
which is what will be considered in this work. In particular linear (both with
and without cyclic boundary conditions) complete, single-qubit control and
alternating-control layouts will be considered, each of which differs in their
structure of CNOT gates. The circuits are shown in FIG. 1. All ansätze have
arbitrary parameterised single qubit rotations on all qubits. These single
qubit rotations and entangling CNOT gates form a block that constitutes a
single layer of the QNN which may then be repeated many times. The total
number of gates for all the ansätze is primarily driven by the CNOT gates,
with all but the full circuit ansatz having a gate count scaling of $O(pn)$
where $p$ is the number of layers and $n$ is the number of qubits. The full
ansatz has a gate count scaling of $O(pn^{2})$. The precise number of CNOT
gates per layer is detailed in FIG. 1.

Figure 3: The simulation fidelity with restricted entanglement (top row), and
entanglement entropy at the end of the circuit (bottom row) of complete,
3-regular and 4-regular graphs for up to six QAOA layers and up to 14 nodes.
Note that after the peak entanglement entropy is reached for the regular
graphs, the simulation fidelity with respect to the entanglement per qubit no
longer follows a consistent scaling law as the number of graph nodes is
varied. Additionally one can observe that the entanglement per qubit required
to maintain high simulation fidelity decreases considerably.

We will be analysing QNNs which are trained to solve image classification
problems, a task that has garnered particular attention in the QML community
over recent years[63, 64, 16]. We will be using the MNIST[65], FMNIST[66] and
CIFAR[67] datasets. The MNIST and FMNIST datasets are $28\times 28$ greyscale
images with 10 labels (or classes). The images are amplitude encoded[68] onto
10 qubits. Additionally, a simple binary classification task over the $0$ and
$1$ classes of MNIST is performed. This is undertaken so that we have a model
that can achieve very high test accuracy, ideally $100\%$. We call this
modified dataset BMNIST. The CIFAR dataset contains $32\times 32$ RGB images
with 10 classes which are amplitude encoded onto 12 qubits with the three
colours encoded onto three separate channels. The task is reduced to a binary
classification problem over the cars and boats classes in order to simplify
training such that it can be performed on a classical simulator. For all
datasets, we utilise 32,000 training examples and 1,000 test examples.

Classification is performed by assigning a qubit to each class and measuring
the $Z$ expectation values of each qubit. The qubit with the largest $Z$
expectation value corresponds to the classification for the given input. In
order to perform optimisation over this classification we assign a conditional
probability that we find some class $c$ given some input $\mathbf{i}$ using
softmax normalisation,

$p(c|\mathbf{i})=\frac{\exp(\matrixelement{\psi(\mathbf{i})}{Z_{c}}{\psi(\mathbf{i})})}{\sum_{j}\exp(\matrixelement{\psi(\mathbf{i})}{Z_{j}}{\psi(\mathbf{i})})},$
(10)

which is fed into a cross entropy loss function which is minimised over. The
ADAM optimiser[69] with a learning rate of 5e-3 is utilised for training which
is undertaken for a single epoch with a batch size of $16$. As per the QAOA
simulations, truncation is performed after each layer, with normalisation of
the state performed once at the end of the circuit.

##  III Results and Discussion

In order to understand the role of entanglement in QAOA and QNNs, the
entanglement entropy of each VQA is analysed throughout the execution of the
algorithm with the untruncated ansatz. Additionally, an analysis of the
fidelity of the simulation upon truncation is undertaken. These metrics
provide an insight as to the role of entanglement in these algorithms and more
specifically provide a benchmark that can be used to determine whether or not
NISQ devices have sufficient capability to generate the entanglement
required[70, 71].

Figure 4: The simulation fidelity at two QAOA layers (top row), and the
entanglement entropy at the end of the circuit (bottom row) for grid graphs
with two (left column), three (middle column) and four columns (right column)
respectively. It is noted that despite the similarity to 4-regular graphs,
grids of three and four columns appear to behave qualitatively differently
from those of random 4-regular graphs. The simulation fidelity at four and six
QAOA layers is presented in Appendix D.

###  III.1 Quantum Approximate Optimisation Algorithm

QAOA on complete, 3-regular and 4-regular graphs as defined in Section II.2 is
evaluated for up to six QAOA layers ($p\leq 6$) with the number of nodes
varying between $8$ to $14$. The fidelity of the restricted entanglement
simulations and the entanglement entropy of the middle cut at the end of the
circuit are shown in FIG. 3. It is found that for complete graphs and for
3-regular graphs at $p\leq 2$, the simulation fidelity is consistent with the
$\mathcal{F}(\ln(\chi)/N)$ scaling law established in Ref. [29]. As the number
of QAOA layers increases however we find that for 3-regular graphs the
simulation fidelity remains consistently high as the entanglement per qubit is
decreased. It is observed that in this case the simulation fidelity no longer
follows a consistent scaling law as the number of nodes in the graph is
varied.

The entanglement entropy of the final state (that is at the end of the QAOA
circuit) is also tracked for circuits of varying depth where it is found that
entanglement entropy approaches a peak before starting to decrease for deeper
circuits. Recognising that the solution to combinatorial optimisation tasks
such as MAX-CUT are inherently product states, this can be interpreted as an
indication that the QAOA circuit is preparing a state that is close to that of
the desired ground state. Counter-intuitively this finding suggests that for
such problems increasing the number of QAOA layers may result in a greater
approximation ratio on devices incapable of creating high entanglement states.

Regarding 4-regular graphs, it is found that the entanglement entropy peaks at
a lower depth, two QAOA layers for all $N\leq 14$, compared to three layers
for $N=10$ and $N=14$ in the 3-regular case. Furthermore, the scaling law that
holds for two layers in the 3-regular case does not appear to be true for
4-regular graphs. This appears to be tied to the fact that the entanglement
entropy reaches a peak with fewer QAOA layers. At higher depth, a similar
trend to the 3-regular case is observed, where the state becomes more
resilient to truncation of entanglement, with the overall entanglement entropy
remaining low. Overall, the 4-regular case is found not to be significantly
different to the 3-regular case.

In the case of complete graphs, we find that the scaling law remains
consistent as the number of QAOA layers is increased. Note that unlike the
regular graphs considered above, there does not appear to be a peak in the
entanglement entropy. This is consistent with our observations that the
scaling law only holds below a certain number of QAOA layers where the
entanglement entropy has not yet reached a maximum. Given the relatively lower
approximation ratio for these states, as per Appendix C, the monotonic
increase in entanglement entropy is likely an indication that such graphs are
more difficult for QAOA to solve rather than necessarily being an indicator
that QAOA circuits for complete graphs exhibit inherently different
characteristics. This is especially the case given that the true ground state
is a product state, hence there must be a peak in entanglement entropy given
that in the limit that the number of QAOA layers approaches infinity then the
QAOA circuit can determine the ground state energy exactly[33]. Despite these
observations, it is still not clear why the scaling law observed holds and how
it is specifically related to the entanglement of the state. A more analytical
study would need to be conducted to determine the theoretical basis for the
behaviour of QAOA under these conditions.

a)

b)

c)

Figure 5: The simulation fidelity of graphs with density a) $40\%$, b) $60\%$
and c) $80\%$ at two QAOA layers. It is apparent that for less dense graphs
the resilience towards truncation is greater than that for graphs of higher
density. Also, note that the scaling of the fidelity becomes more regular as
the density of the graph increases and the edges become less structured.

Investigating if imposing structure on the graphs has an effect on the
simulation fidelity of QAOA, grid graphs are simulated using QAOA with results
presented in FIG. 4. Results are split by number of columns in the grid graph.
For the two-column case, our results closely resemble that of the 3-regular
graph, noting that two-column (or equivalently two-row) grids are 3-regular.
The primary distinction found is that the entanglement entropy remains low
compared to similarly sized 3-regular graphs. We hypothesise that this is due
to the fact that the edge layout in grid graphs is such that nodes that are
situated far away from each other are in general less likely to be connected
via an edge, given a node layout as per FIG. 4, which is the case for the
simulations performed. This is compared to the random edges of random
3-regular graphs. Increasing the size to three and four-column grid graphs,
which are now 4-regular, the results again appear similar to their random
regular graph counterparts. The primary distinctions being as above, a
decrease in entanglement entropy resulting from a node layout where nearby
nodes are more likely to have edges compared to distant nodes.

These grid graph results highlight the importance of the mapping of nodes to
qubits. Recognising in particular that by arranging nodes in such a way that
their edges are preferentially between nodes that are near adjacent one can
achieve a far lower entanglement entropy. This is of course not always
possible. Continuing to consider grids whose nodes are labelled counting from
left to right across each row, then top to bottom down each row, it is found
that the exchange between rows and columns, in particular in the $3\times 4$
case compared to the $4\times 3$ case, appears to result in a significant
difference in entanglement entropy along the middle cut. This is an indication
that the entanglement is not evenly distributed for grid graphs, and hence
node ordering may affect the optimisation step of QAOA, in particular in cases
where entanglement is limited. Ultimately however for a given circuit with
optimised parameters, this appears to only have a minimal effect on the
simulation fidelity upon truncation.

In addition to graph topology, graph density is another key characteristic of
graphs that has an effect on the performance of QAOA circuits, with denser
graphs resulting in circuits with a greater number of two-qubit gates and an
overall greater depth. In order to investigate the effect of graph density,
and specifically the transition from low-density graphs with structured edge
layouts to high-density graphs, the procedure described in Section II.2 is
followed to build a spectrum of graphs with varying density. The simulation
fidelity for various graphs with approximately $40\%$ density, $60\%$ density
and $80\%$ density at two QAOA layers is reported in FIG. 5. It is found that
the simulation fidelity decreases with the overall graph density, a result
that appears consistent with that for the random regular and complete graphs.
Likewise, there does not appear to be a universal scaling law for the
simulation fidelity of the low-density graphs, with the scaling law only
becoming more apparent as the density increases and one approaches a complete
graph.

Note in particular that the QAOA circuits are not trained using truncated MPS.
This is because any further optimisation at a given maximal entanglement per
qubit would simply exacerbate the observations of high simulation fidelity at
lower entanglements per qubit which fundamentally does not alter the principal
result of this work. Furthermore, it has been found that for one QAOA layer,
the parameters corresponding to the minimum of an exact QAOA simulation are
unchanged upon truncation [29].

###  III.2 Quantum Machine Learning

The QNNs are trained on all datasets introduced in Section II.3 using the 5
different ansätze on a full state-vector simulator for up to 100 layers. The
test accuracy and entanglement entropy of the final state for the various-
sized QNNs trained on the MNIST dataset are shown in FIG. 6. Similar to QAOA
it is found that the entanglement entropy at the end of the circuit increases
as the number of QNN layers increases until a threshold entropy is reached,
$<20$ layers for all but the alternating ansatz, after which the entanglement
entropy appears to slightly decline with the test accuracy continuing to
increase. We consider the structure of the alternating ansatz in Appendix E
and conclude that the Hilbert Space in which the state, prepared using one
layer of the ansatz, lives is greatly reduced compared to the other ansätze
considered in this work. As a result, it takes many more layers for the
alternating ansatz to be able to produce near-maximally entangled states.

a) Full Circuit b) Linear Circuit c) Periodic Circuit d) Single Control
Circuit e) Alternating Circuit Figure 6: The test accuracy (blue dots) and
average entanglement entropy (red crosses) at the end of the circuit for the
circuits as per FIG. 1. Each circuit is a $10$ qubit QNN with varying layers
trained on the MNIST dataset. Note a rapid increase in test accuracy as the
QNNs approach the maximum Haar entanglement entropy at $\approx 4.5$ (red
dashed line)[31]. As the number of QNN layers increases beyond what is needed
to reach the maximum entanglement entropy, a decrease in the entropy as the
test accuracy steadily increases is observed. Note that the alternating ansatz
in e) takes longer to reach the maximum entanglement entropy and performs
worse than all other ansätze, which perform comparably.

We note that a perfectly classified input would result in the final state of
the circuit being a product state corresponding to the classification. This
state would be of low entanglement. As a result, one can conclude that
increasing the number of layers of the QNN results in a classification that is
reproducible given the same input. This outcome is highly desirable. However,
it is important to recognise that for systems where the number of qubits
required for the input is equal to that required for the classification such a
perfect outcome is not possible. This is because such an outcome would break
the unitarity of the circuit, with in general many inputs leading to the same
output. It is recognised that this is the case for the MNIST and FMNIST
datasets which require $10$ qubits to be amplitude encoded and under a one-hot
encoding scheme[72] for classes will also require all of the same $10$ qubits
for classification. Possible workarounds, if such a perfect classification is
needed, are to separate the encoding and classification qubits or otherwise
utilise another class encoding strategy that requires fewer qubits than is
required for embedding the input.

a)b) Figure 7: The evolution of entanglement throughout the circuit for 20, 60
and 100 layer periodic ansatz QNNs trained on a) the binary MNIST dataset and
b) the $10$ class MNIST dataset. Test accuracies for a) are $0.998$, $0.998$
and $0.999$ respectively and $0.728$, $0.774$ and $0.807$ for b). Note that
the entanglement entropy drops off towards the end of the circuit, with larger
circuits showing a more significant drop in entanglement entropy towards the
end of the circuit. The results for all other ansätze are provided in Appendix
F.

FIG. 6 reveals a decrease in the entanglement entropy at the end of the
circuit as the number of QNN layers is increased past a certain threshold. In
order to hypothesise whether the QNNs will be resilient towards truncation,
one must also consider the entanglement entropy throughout the evolution of
the state. As such, the entanglement entropy throughout the execution of
various-sized QNNs is tracked for the MNIST and binary MNIST datasets. The
entropy at the end of each QNN layer for the periodic ansatz is shown in FIG.
7, with the remaining ansätze shown in Appendix F. It is observed that the
decline in entanglement entropy occurs sharply at the end of the circuit and
is not a gradual decrease similar to that seen in the analysis above. Hence,
despite a decrease in the entanglement entropy of the final state, it is
likely not the case that deeper circuits result in a greater resilience
towards truncation similar to that which was observed for QAOA on regular
graphs. This observation would also suggest that training a QNN layer by layer
is unlikely to be successful as the final state of some QNN with $a$ layers
appears to be substantially different to a QNN with $b>a$ layers at layer $a$.
This is in contrast to QAOA, where it is possible to see improvement in the
cost by training a system layer by layer up until $N$ total layers where $N$
is the number of qubits[73].

To test this hypothesis, MPS simulations with truncation are run across the
entire test set with test accuracy for each entanglement per qubit shown in
FIG. 8. For the monochromatic $28\times 28$ pixel MNIST and FMNIST datasets,
it is found that all but the alternating ansatz appear to not be resilient to
any truncation at $20$, $60$ or $100$ QNN layers. This is in agreement with
the observation made above that resilience towards truncation is unlikely even
when the final state is of relatively lower entanglement. Counter-intuitively
this means that provided a trained QNN and a quantum device or simulator
incapable of achieving high entanglement, it may be more beneficial to use the
alternating ansatz at low depth as it is capable of achieving higher test
accuracies with less entanglement compared to the other ansätze. As the number
of QNN layers is increased however this advantage disappears with all ansätze
not showing any resilience towards truncation. Additionally, factoring in the
gate requirements of each ansatz as per TABLE 1, it is noted that despite the
vastly greater number of gates the full circuit ansatz does not appear to
perform substantially better than the ansätze which only have a CNOT gate
count which scales linearly with the number of qubits per layer.

$p$ | Circuit | Accuracy | #Gates | $S$
---|---|---|---|---
20 | Full | 0.731 | 1,100 | 2.254
| Linear | 0.724 | 400 | 4.242
| Periodic | 0.728 | 420 | 4.256
| Single Control | 0.738 | 400 | 4.251
| Alternating | 0.583 | 400 | 2.673
60 | Full | 0.778 | 3,300 | 4.182
| Linear | 0.749 | 1,200 | 4.182
| Periodic | 0.774 | 1,260 | 4.165
| Single Control | 0.751 | 1,200 | 4.222
| Alternating | 0.760 | 1,200 | 4.209
100 | Full | 0.791 | 5,500 | 4.086
| Linear | 0.785 | 2,000 | 4.089
| Periodic | 0.807 | 2,100 | 4.077
| Single Control | 0.786 | 2,000 | 4.140
| Alternating | 0.777 | 2,000 | 4.173
Table 1: The test accuracy, number of gates and entanglement entropy, $S$, of
the different QNN circuit ansätze trained on the MNIST dataset at $p=20$, $60$
and $100$ layers. Despite requiring substantially more gates, the fully
connected ansatz does not result in any substantial improvement in the test
accuracy nor is the entanglement entropy substantially different to the other
ansätze, except the alternating ansatz. Figure 8: Test accuracy for various
datasets under limited entanglement simulations. Note that deeper QNNs are
more able to utilise entanglement in a useful manner. We recognise that this
is not necessarily a result of shallower circuits being less entangled as
shallower circuits are found to have as high an entanglement entropy for QNN
above $20$ layers. In general, for the MNSIT binary classification task, there
appears to be no reason that one needs to extend beyond a shallow, low
entanglement circuit. For the binary CIFAR classification task it is observed
that there is a notable decrease in the test accuracy for deeper QNNs, this is
possibly a result of entanglement-induced barren plateaus.

For the simple binary MNIST dataset, it is found that the alternating and
single control ansätze show a significant resilience towards truncation at
$20$ QNN layers, and to a lesser extent at $60$ QNN layers. All other ansätze
show some resilience at $20$ layers and $60$ layers, but in general, appear to
have a lower test accuracy for a given entanglement per qubit compared to the
single control and alternating circuits. It is noted however that the
entanglement entropy in FIG. 7(a) continues to decrease for QNNs with a
greater number of layers. This is not inconsistent with the findings here of
high test accuracy at low depth, noting in particular that classification is
performed by taking the largest $Z$ expectation value taken over many shots.
Hence very high test accuracy does not necessarily correspond to a very high
probability of measuring the output corresponding to the correct
classification. Despite this, as the primary goal of QNNs is accurate
classification it remains beneficial to use circuits of low depth that are
resilient towards truncation which are able to achieve high classification
accuracy. For simple datasets such as binary MNIST, this can be achieved with
$<20$ layers with the alternating ansatz.

Analysing the more complex $32\times 32$ RGB CIFAR dataset, it is found that
the resilience towards truncation as circuit depth increases follows a similar
pattern to the greyscale datasets. Interestingly, however, it is found that
for the $20$ layer QNN, the alternating ansatz maintains a complete resilience
towards truncation. We believe this is a result of the imbalanced nature of
the CIFAR dataset, with some classes being represented more frequently than
others. As a result, one may simply guess the more frequent class for all
inputs and get a test accuracy $>0.5$. It is apparent that the alternating
ansatz is capable of encoding this simple classification model at low depth in
such a way that is completely resilient to truncation. As the depth increases
however a more sophisticated classification is performed and this resilience
is lost. At this high depth there also appears to be a slight decrease in the
overall test accuracy for all but the alternating circuit. It is possible this
is a result of entanglement-induced barren plateaus[74, 75], however, one
would need to determine whether the entanglement entropy of the ansätze
satisfies a volume law for this to be the case.

Additionally, at high depth, there is a minor increase in the test accuracy as
we perform moderate truncation for the alternating ansatz. Further
investigation is required to determine the underlying mechanism here, but we
hypothesise that the act of truncation, which is inherently a non-unitary
evolution of the state, is such that the system has access to a part of the
Hilbert space that was not available to it with just the standard unitary
operations of the circuit ansatz. A similar phenomenon is observed for QAOA on
grid graphs at higher depths as discussed in in Appendix D. Additionally, an
overall decrease in the test accuracy across all ansätze for high-depth
circuits is observed, which is likely due to entanglement-induced barren
plateaus.

Like QAOA, the QNNs are not trained using truncated MPS simulations. However,
training the QNNs with a truncated MPS simulation may result in a marked
improvement in the overall test accuracy. This hypothesis follows from Ref.
[76] where the authors found that training QNNs with noisy inputs results in a
notable improvement in test accuracy when tested on similarly noisy inputs.
This is compared to QNNs that are trained using exact inputs but tested with
noisy inputs where they found that the test accuracy was reduced. As the
truncated MPS simulations are significantly slower than training using
pennylane this hypothesis was not tested as it was not feasible to perform
adequate training with the computational resources available to us.

###  III.3 Summary of comparison between QAOA and QNN

Our work has revealed that the entanglement of VQAs is highly dependent on the
structure of the problem. In general, we find that for combinatorial
optimisation problems solved using QAOA, high-depth circuits do not
necessarily result in higher entanglement in circuits, with many problem
instances showing some resilience towards truncation. This is compared to
image classification tasks solved using QNNs, where we find that those
circuits are much more entangled at high depth, and are far less resilient to
any truncation of entanglement. Our results suggest that compared to QNN,
generally QAOA is more likely to be within the capability of NISQ devices due
to lower demand on the entanglement in the circuits. However, for some simple
datasets such as binary MNIST, QNN models using alternating ansatz may also be
within the reach of near-term devices due to relatively low-depth circuits
requiring low entanglement. For sufficiently complex datasets, however, it is
found that higher-depth and highly entangled QNNs are required to maintain
high test accuracies.

##  IV Conclusion And Discussion

Variational quantum algorithms show significant promise in the NISQ era of
quantum computing as a result of their ability to perform classically
difficult tasks using relatively few qubits and circuits of shallow depth. In
this work, we find that two of the leading VQCs, QAOA and QNNs, show a varying
degree of resilience towards the truncation of entanglement. Importantly
though, we find that the resilience of any given circuit is highly dependent
on the depth of the circuit and the variational ansatz, recognising that
different problems have inherently different requirements regarding circuit
depth and structure. As a result, a previously observed scaling law[29] does
not necessarily hold when considering specific problem instances.

For QAOA, we relate the simulation fidelity to the entanglement entropy of the
final states produced, finding that monotonic scaling laws with respect to the
size of the system for each type of graph being solved are more likely to hold
in the regime where the entanglement entropy has not yet reached a peak. We
also find that structured regular graphs, such as the grid graph appear to
exhibit scaling relations that are inherently distinct from random regular
graphs, ultimately finding that the scaling relation approaches that of the
complete graph upon increasing the density when interpolating from an initial
grid graph. This has implications for problems such as the vehicle routing
problem map onto low-density graphs of a given structure.

It still remains an open question as to the underlying mechanics behind the
scaling relations observed. However one can relate the eventual increase in
resilience to truncation to the simple nature of the final solution state of
combinatorial optimisation problems being a product state. We recognise that
any of the combinatorial optimisation problems considered can be solved
exactly with a trivial product ansatz with $3N$ parameters, where $N$ is the
number of qubits, but it remains open as to how efficiently such an
optimisation is compared to a QAOA ansatz with fewer variational parameters.

For QNNs, we find that all but the simplest datasets require highly entangled
ansätze in order to achieve high test accuracy, with high-depth circuits
exhibiting higher test accuracies and low resilience towards truncation of
entanglement. We find that, unlike QAOA, despite a decrease in entanglement
entropy for higher-depth models, resilience towards truncation decreases. For
more complicated datasets such as the RGB CIFAR dataset, we sometimes observe
a slight increase in test accuracy upon truncation, which is similar to an
observation made for QAOA on certain problems at high depths. It is not clear
what the underlying cause of this is, and as such this remains an open
question. Given the relatively low test accuracies at which this phenomenon
occurred, however, it is not clear whether or not this would continue to hold
for models of interest that achieve a high test accuracy.

Overall, our results based on a systematic set of simulations have provided
important new insights into the role of entanglement in the performance of two
widely used variational quantum algorithms. In the current NISQ era of quantum
computing where noise or errors in quantum devices limit the entanglement that
can be generated in quantum circuits, our work will enable their
implementations with optimal accuracy within the constraint of affordable
entanglement.

## Acknowledgements

The authors acknowledge useful discussions with Charles D. Hill in the early
stages of the project, and with Maxwell T West on the QNN part of the work.
ACN acknowledges the support of the Australian Government Research Training
Program Scholarship. The authors acknowledge the support from IBM Quantum Hub
at the University of Melbourne. The computational resources were provided by
the National Computing Infrastructure (NCI) and Pawsey Supercomputing Center
through the National Computational Merit Allocation Scheme (NCMAS).

## Code Availability

The code used to generate all results in this paper is available upon
reasonable request.

## References

  * [1] Nielsen, M. A. & Chuang, I. L.  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2012), 1 edn.  URL https://www.cambridge.org/core/product/identifier/9780511976667/type/book.
  * [2] Preskill, J.  Quantum Computing in the NISQ era and beyond.  _Quantum_ 2, 79 (2018).  URL https://quantum-journal.org/papers/q-2018-08-06-79/.
  * [3] Peruzzo, A. _et al._ A variational eigenvalue solver on a photonic quantum processor.  _Nature Communications_ 5, 4213 (2014).  URL https://www.nature.com/articles/ncomms5213.
  * [4] Kandala, A. _et al._ Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  _Nature_ 549, 242–246 (2017).  URL https://www.nature.com/articles/nature23879.
  * [5] Fedorov, D. A., Peng, B., Govind, N. & Alexeev, Y.  VQE method: a short survey and recent developments.  _Materials Theory_ 6, 2 (2022).  URL https://materialstheory.springeropen.com/articles/10.1186/s41313-021-00032-6.
  * [6] Jones, M. A., Vallury, H. J., Hill, C. D. & Hollenberg, L. C. L.  Chemistry beyond the Hartree–Fock energy via quantum computed moments.  _Scientific Reports_ 12, 8985 (2022).  URL https://www.nature.com/articles/s41598-022-12324-z.
  * [7] Egger, D. J. _et al._ Quantum Computing for Finance: State-of-the-Art and Future Prospects.  _IEEE Transactions on Quantum Engineering_ 1, 1–24 (2020).  URL https://ieeexplore.ieee.org/document/9222275/.
  * [8] Orús, R., Mugel, S. & Lizaso, E.  Quantum computing for finance: Overview and prospects.  _Reviews in Physics_ 4, 100028 (2019).  URL https://linkinghub.elsevier.com/retrieve/pii/S2405428318300571.
  * [9] Bentley, C. D. B., Marsh, S., Carvalho, A. R. R., Kilby, P. & Biercuk, M. J.  Quantum computing for transport optimization (2022).  URL http://arxiv.org/abs/2206.07313.  ArXiv:2206.07313 [quant-ph].
  * [10] Harwood, S. _et al._ Formulating and Solving Routing Problems on Quantum Computers.  _IEEE Transactions on Quantum Engineering_ 2, 1–17 (2021).  URL https://ieeexplore.ieee.org/document/9314905/.
  * [11] Azad, U., Behera, B. K., Ahmed, E. A., Panigrahi, P. K. & Farouk, A.  Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm.  _IEEE Transactions on Intelligent Transportation Systems_ 24, 7564–7573 (2023).  URL https://ieeexplore.ieee.org/document/9774961/.
  * [12] Vikstål, P. _et al._ Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem.  _Physical Review Applied_ 14, 034009 (2020).  URL https://link.aps.org/doi/10.1103/PhysRevApplied.14.034009.
  * [13] Cerezo, M., Verdon, G., Huang, H.-Y., Cincio, L. & Coles, P. J.  Challenges and opportunities in quantum machine learning.  _Nature Computational Science_ 2, 567–576 (2022).  URL https://www.nature.com/articles/s43588-022-00311-3.
  * [14] Farhi, E. & Neven, H.  Classification with Quantum Neural Networks on Near Term Processors (2018).  URL http://arxiv.org/abs/1802.06002.  ArXiv:1802.06002 [quant-ph].
  * [15] Romero, J., Olson, J. P. & Aspuru-Guzik, A.  Quantum autoencoders for efficient compression of quantum data.  _Quantum Science and Technology_ 2, 045001 (2017).  URL https://iopscience.iop.org/article/10.1088/2058-9565/aa8072.
  * [16] West, M. T. _et al._ Benchmarking adversarially robust quantum machine learning at scale.  _Physical Review Research_ 5, 023186 (2023).  URL https://link.aps.org/doi/10.1103/PhysRevResearch.5.023186.
  * [17] West, M. T. _et al._ Towards quantum enhanced adversarial robustness in machine learning.  _Nature Machine Intelligence_ 5, 581–589 (2023).  URL https://www.nature.com/articles/s42256-023-00661-1.
  * [18] Daskin, A.  A Simple Quantum Neural Net with a Periodic Activation Function.  In _2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)_ , 2887–2891 (IEEE, Miyazaki, Japan, 2018).  URL https://ieeexplore.ieee.org/document/8616487/.
  * [19] Bisarya, A. _et al._ Breast Cancer Detection Using Quantum Convolutional Neural Networks: A Demonstration on a Quantum Computer.  preprint, Oncology (2020).  URL http://medrxiv.org/lookup/doi/10.1101/2020.06.21.20136655.
  * [20] Sagingalieva, A. _et al._ Hybrid Quantum Neural Network for Drug Response Prediction.  _Cancers_ 15, 2705 (2023).  URL https://www.mdpi.com/2072-6694/15/10/2705.
  * [21] Li, P. & Xiao, H.  Model and algorithm of quantum-inspired neural network with sequence input based on controlled rotation gates.  _Applied Intelligence_ 40, 107–126 (2014).  URL http://link.springer.com/10.1007/s10489-013-0447-3.
  * [22] Grover, L. K.  A fast quantum mechanical algorithm for database search.  In _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96_ , 212–219 (ACM Press, Philadelphia, Pennsylvania, United States, 1996).  URL http://portal.acm.org/citation.cfm?doid=237814.237866.
  * [23] Shor, P. W.  Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.  _SIAM Journal on Computing_ 26, 1484–1509 (1997).  URL http://epubs.siam.org/doi/10.1137/S0097539795293172.
  * [24] Farhi, E., Gamarnik, D. & Gutmann, S.  The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case (2020).  URL http://arxiv.org/abs/2004.09002.  ArXiv:2004.09002 [quant-ph].
  * [25] Stilck França, D. & García-Patrón, R.  Limitations of optimization algorithms on noisy quantum devices.  _Nature Physics_ 17, 1221–1227 (2021).  URL https://www.nature.com/articles/s41567-021-01356-3.
  * [26] Gonthier, J. F. _et al._ Measurements as a roadblock to near-term practical quantum advantage in chemistry: Resource analysis.  _Physical Review Research_ 4, 033154 (2022).  URL https://link.aps.org/doi/10.1103/PhysRevResearch.4.033154.
  * [27] Wang, S. _et al._ Noise-induced barren plateaus in variational quantum algorithms.  _Nature Communications_ 12, 6961 (2021).  URL https://www.nature.com/articles/s41467-021-27045-6.
  * [28] De Palma, G., Marvian, M., Rouzé, C. & França, D. S.  Limitations of Variational Quantum Algorithms: A Quantum Optimal Transport Approach.  _PRX Quantum_ 4, 010309 (2023).  URL https://link.aps.org/doi/10.1103/PRXQuantum.4.010309.
  * [29] Dupont, M., Didier, N., Hodson, M. J., Moore, J. E. & Reagor, M. J.  Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm.  _PRX Quantum_ 3, 040339 (2022).  URL https://link.aps.org/doi/10.1103/PRXQuantum.3.040339.
  * [30] Dupont, M., Didier, N., Hodson, M. J., Moore, J. E. & Reagor, M. J.  Entanglement perspective on the quantum approximate optimization algorithm.  _Physical Review A_ 106, 022423 (2022).  URL https://link.aps.org/doi/10.1103/PhysRevA.106.022423.
  * [31] Ballarin, M., Mangini, S., Montangero, S., Macchiavello, C. & Mengoni, R.  Entanglement entropy production in Quantum Neural Networks.  _Quantum_ 7, 1023 (2023).  URL https://quantum-journal.org/papers/q-2023-05-31-1023/.
  * [32] Díez-Valle, P., Porras, D. & García-Ripoll, J. J.  Quantum variational optimization: The role of entanglement and problem hardness.  _Phys. Rev. A_ 104, 062426 (2021).  URL https://link.aps.org/doi/10.1103/PhysRevA.104.062426.
  * [33] Farhi, E., Goldstone, J. & Gutmann, S.  A Quantum Approximate Optimization Algorithm (2014).  URL http://arxiv.org/abs/1411.4028.  ArXiv:1411.4028 [quant-ph].
  * [34] Vidal, G.  Efficient Classical Simulation of Slightly Entangled Quantum Computations.  _Physical Review Letters_ 91, 147902 (2003).  URL https://link.aps.org/doi/10.1103/PhysRevLett.91.147902.
  * [35] Schollwöck, U.  The density-matrix renormalization group in the age of matrix product states.  _Annals of Physics_ 326, 96–192 (2011).  URL https://linkinghub.elsevier.com/retrieve/pii/S0003491610001752.
  * [36] Niedermeier, M., Lado, J. L. & Flindt, C.  Tensor-Network Simulations of Noisy Quantum Computers (2023).  URL http://arxiv.org/abs/2304.01751.  ArXiv:2304.01751 [cond-mat, physics:quant-ph].
  * [37] Havlíček, V. _et al._ Supervised learning with quantum-enhanced feature spaces.  _Nature_ 567, 209–212 (2019).  URL https://www.nature.com/articles/s41586-019-0980-2.
  * [38] Srikumar, M., Hill, C. D. & Hollenberg, L. C. L.  A kernel-based quantum random forest for improved classification (2023).  URL http://arxiv.org/abs/2210.02355.  ArXiv:2210.02355 [quant-ph].
  * [39] Ortiz Marrero, C., Kieferová, M. & Wiebe, N.  Entanglement-Induced Barren Plateaus.  _PRX Quantum_ 2, 040316 (2021).  URL https://link.aps.org/doi/10.1103/PRXQuantum.2.040316.
  * [40] Dang, A.  _Distributed Matrix Product State Simulationsof Large-Scale Quantum Circuits_.  Ph.D. thesis, The University of Melbourne (2017).
  * [41] Bañuls, M. C., Orús, R., Latorre, J. I., Pérez, A. & Ruiz-Femenía, P.  Simulation of many-qubit quantum computation with matrix product states.  _Physical Review A_ 73, 022344 (2006).  URL https://link.aps.org/doi/10.1103/PhysRevA.73.022344.
  * [42] Orús, R.  A practical introduction to tensor networks: Matrix product states and projected entangled pair states.  _Annals of Physics_ 349, 117–158 (2014).  URL https://linkinghub.elsevier.com/retrieve/pii/S0003491614001596.
  * [43] Edwards, S. F. & Anderson, P. W.  Theory of spin glasses.  _Journal of Physics F: Metal Physics_ 5, 965 (1975).  URL https://dx.doi.org/10.1088/0305-4608/5/5/017.
  * [44] Bergqvist, G. & Larsson, E.  The Higher-Order Singular Value Decomposition: Theory and an Application [Lecture Notes.  _IEEE Signal Processing Magazine_ 27, 151–154 (2010).  URL http://ieeexplore.ieee.org/document/5447070/.
  * [45] Perez-Garcia, D., Verstraete, F., Wolf, M. M. & Cirac, J. I.  Matrix Product State Representations (2007).  URL http://arxiv.org/abs/quant-ph/0608197.  ArXiv:quant-ph/0608197.
  * [46] Gray, J.  quimb: A python package for quantum information and many-body calculations.  _Journal of Open Source Software_ 3, 819 (2018).  URL http://joss.theoj.org/papers/10.21105/joss.00819.
  * [47] Treinish, M.  Qiskit/qiskit-metapackage: Qiskit 0.44.0 (2023).  URL https://zenodo.org/record/2573505.
  * [48] Bergholm, V. _et al._ PennyLane: Automatic differentiation of hybrid quantum-classical computations (2022).  URL http://arxiv.org/abs/1811.04968.  ArXiv:1811.04968 [physics, physics:quant-ph].
  * [49] Guerreschi, G. G. & Matsuura, A. Y.  QAOA for Max-Cut requires hundreds of qubits for quantum speed-up.  _Scientific reports_ 9, 6903 (2019).
  * [50] Wang, Z., Hadfield, S., Jiang, Z. & Rieffel, E. G.  Quantum approximate optimization algorithm for MaxCut: A fermionic view.  _Physical Review A_ 97, 022304 (2018).
  * [51] Zhou, L., Wang, S.-T., Choi, S., Pichler, H. & Lukin, M. D.  Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices.  _Physical Review X_ 10, 021067 (2020).
  * [52] Lucas, A.  Ising formulations of many NP problems.  _Frontiers in Physics_ 2 (2014).  URL http://journal.frontiersin.org/article/10.3389/fphy.2014.00005/abstract.
  * [53] Sherrington, D. & Kirkpatrick, S.  Solvable Model of a Spin-Glass.  _Physical Review Letters_ 35, 1792–1796 (1975).  URL https://link.aps.org/doi/10.1103/PhysRevLett.35.1792.
  * [54] Barahona, F., Grötschel, M., Jünger, M. & Reinelt, G.  An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design.  _Operations Research_ 36, 493–513 (1988).
  * [55] Alidaee, B., Kochenberger, G. A. & Ahmadian, A.  0-1 quadratic programming approach for optimum solutions of two scheduling problems.  _International Journal of Systems Science_ 25, 401–408 (1994).
  * [56] Herrman, R., Ostrowski, J., Humble, T. S. & Siopsis, G.  Lower bounds on circuit depth of the quantum approximate optimization algorithm.  _Quantum Information Processing_ 20, 59 (2021).  URL http://link.springer.com/10.1007/s11128-021-03001-7.
  * [57] West, D. B. _et al._ _Introduction to Graph Theory_ , vol. 2 (Prentice hall Upper Saddle River, 2001).
  * [58] Kraft, D.  Algorithm 733: TOMP–Fortran modules for optimal control calculations.  _ACM Transactions on Mathematical Software_ 20, 262–281 (1994).  URL https://dl.acm.org/doi/10.1145/192115.192124.
  * [59] Kwak, Y., Yun, W. J., Jung, S. & Kim, J.  Quantum Neural Networks: Concepts, Applications, and Challenges.  In _2021 Twelfth International Conference on Ubiquitous and Future Networks (ICUFN)_ , 413–416 (IEEE, Jeju Island, Korea, Republic of, 2021).  URL https://ieeexplore.ieee.org/document/9528698/.
  * [60] Glasser, I., Pancotti, N. & Cirac, J. I.  From Probabilistic Graphical Models to Generalized Tensor Networks for Supervised Learning.  _IEEE Access_ 8, 68169–68182 (2020).  URL https://ieeexplore.ieee.org/document/9058650/.
  * [61] Shi, J. _et al._ An Approach to Cryptography Based on Continuous-Variable Quantum Neural Network.  _Scientific Reports_ 10, 2107 (2020).  URL https://www.nature.com/articles/s41598-020-58928-1.
  * [62] Leone, L., Oliviero, S. F. E., Cincio, L. & Cerezo, M.  On the practical usefulness of the Hardware Efficient Ansatz (2022).  URL http://arxiv.org/abs/2211.01477.  ArXiv:2211.01477 [quant-ph].
  * [63] Das, M. & Bolisetti, T.  Variational Quantum Neural Networks (VQNNS) in Image Classification (2023).  URL http://arxiv.org/abs/2303.05860.  ArXiv:2303.05860 [quant-ph].
  * [64] Mathur, N. _et al._ Medical image classification via quantum neural networks (2022).  URL http://arxiv.org/abs/2109.01831.  ArXiv:2109.01831 [quant-ph].
  * [65] Li Deng.  The MNIST Database of Handwritten Digit Images for Machine Learning Research [Best of the Web].  _IEEE Signal Processing Magazine_ 29, 141–142 (2012).  URL http://ieeexplore.ieee.org/document/6296535/.
  * [66] Xiao, H., Rasul, K. & Vollgraf, R.  Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms (2017).  URL http://arxiv.org/abs/1708.07747.  ArXiv:1708.07747 [cs, stat].
  * [67] Krizhevsky, A. & Hinton, G.  Learning Multiple Layers of Features from Tiny Images (2009).  URL https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf.  Publisher: Toronto, ON, Canada.
  * [68] LaRose, R. & Coyle, B.  Robust data encodings for quantum classifiers.  _Physical Review A_ 102, 032420 (2020).  URL https://link.aps.org/doi/10.1103/PhysRevA.102.032420.
  * [69] Kingma, D. P. & Ba, J.  Adam: A Method for Stochastic Optimization (2014).  URL https://arxiv.org/abs/1412.6980.  Publisher: arXiv Version Number: 9.
  * [70] Mooney, G. J., White, G. A. L., Hill, C. D. & Hollenberg, L. C. L.  Whole‐Device Entanglement in a 65‐Qubit Superconducting Quantum Computer.  _Advanced Quantum Technologies_ 4, 2100061 (2021).  URL https://onlinelibrary.wiley.com/doi/10.1002/qute.202100061.
  * [71] Hamilton, K. E. _et al._ An entanglement-based volumetric benchmark for near-term quantum hardware (2022).  URL https://arxiv.org/abs/2209.00678.  Publisher: arXiv Version Number: 1.
  * [72] Sammut, C. & Webb, G. I.  _Encyclopedia of Machine Learning_ (Springer Science & Business Media, 2011).
  * [73] Campos, E., Rabinovich, D., Akshay, V. & Biamonte, J.  Training saturation in layerwise quantum approximate optimization.  _Phys. Rev. A_ 104, L030401 (2021).  URL https://link.aps.org/doi/10.1103/PhysRevA.104.L030401.
  * [74] McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R. & Neven, H.  Barren plateaus in quantum neural network training landscapes.  _Nature communications_ 9, 4812 (2018).
  * [75] Ortiz Marrero, C., Kieferová, M. & Wiebe, N.  Entanglement-Induced Barren Plateaus.  _PRX Quantum_ 2, 040316 (2021).  URL https://link.aps.org/doi/10.1103/PRXQuantum.2.040316.
  * [76] West, M. T. _et al._ Drastic Circuit Depth Reductions with Preserved Adversarial Robustness by Approximate Encoding for Quantum Machine Learning (2023).  URL http://arxiv.org/abs/2309.09424.  ArXiv:2309.09424 [quant-ph].
  * [77] Demange, M. & Paschos, V. T.  On an approximation measure founded on the links between optimization and polynomial approximation theory.  _Theoretical Computer Science_ 158, 117–141 (1996).  URL https://www.sciencedirect.com/science/article/pii/0304397595000607.

##  Appendix A A note on the Simulation Fidelity for QAOA

The simulation fidelity for QAOA may be explicitly written down as,

$\text{Simulation
Fidelity}=\frac{\matrixelement{\psi_{\chi}}{H_{P}}{\psi_{\chi}}}{\matrixelement{\psi}{H_{P}}{\psi}},$
(11)

where $\ket{\psi_{\chi}}$ is an approximation of state $\ket{\psi}$ with bond
dimension $\chi$. This definition, similar to that of the approximation ratio
suffers from a certain ambiguity. This is discussed in greater depth in
Appendix B. We note however that for all instances considered in this work we
have $\matrixelement{\psi}{H_{P}}{\psi}<0$. To illustrate this we provide the
average $\matrixelement{\psi}{H_{P}}{\psi}$ for the complete, 3-regular,
4-regular instance in this work in FIG. 9. Despite the issues with the
definition in Equation (11), we continue to use it so that our findings remain
directly comparable to previous works[29] which we compare our results
against.

a) b) c) Figure 9: The average cost over 100 graphs after the optimisation
step of QAOA for a) complete, b) 3-regular and c) 4-regular graphs
respectively for one to six QAOA layers. We find the cost after optimisation
is always less than zero.

##  Appendix B The QAOA Approximation Ratio

The performance of QAOA is commonly determined by the approximation ratio
defined as[33],

$\text{Approximation
Ratio}=\frac{\matrixelement{\psi}{H_{P}}{\psi}}{\matrixelement{\psi_{\text{Exact}}}{H_{P}}{\psi_{\text{Exact}}}},$
(12)

where $\ket{\psi_{\text{Exact}}}$ is the exact ground state solution of
$H_{P}$ defined in Section II.2 and $\ket{\psi}$ is the solution state found
using QAOA. It is recognised that the approximation ratio as stated is ill-
defined as (1) one may shift the energy spectrum by a constant which does not
materially change the problem but will result in a different approximation
ratio; (2) $\matrixelement{\psi}{H_{p}}{\psi}$ can be any real number and as
such the numerator and denominator may be of a different sign, resulting in a
negative approximation ratio and; (3)
$\matrixelement{\psi_{\text{Exact}}}{H_{P}}{\psi_{\text{Exact}}}$ may be zero
resulting in an undefined approximation ratio. A well-defined approximation
ratio has been established in Ref. [77] which introduces a third variable to
Equation (12) which corresponds to the worst case cost,
$\matrixelement{\psi_{\text{worst}}}{H_{P}}{\psi_{\text{worst}}}$. With this,
the approximation ratio will not vary under a constant shift in the energy
spectrum and will always be in $[0,1]$. It is recognised that for the MAX-CUT
problem Hamiltonian $H_{P}=\frac{1}{2}\sum_{(i,j)\in E}w_{ij}(Z_{i}Z_{j}-I)$
the worst case scenario is
$\matrixelement{\psi_{\text{worst}}}{H_{P}}{\psi_{\text{worst}}}=0$ and as
such one can continue to use the approximation ratio as defined in Equation
(12). However, in previous works studying the entanglement of QAOA suing the
MAX-CUT problem[29, 30] the Hamiltonian used is $H_{P}=\sum_{(i,j)\in
E}w_{ij}Z_{i}Z_{j}$ where the worst case cost is $\absolutevalue{E}$. As such
one must exercise caution when using the approximation ratio and MAX-CUT
Hamiltonian as defined in this work. Recognising that
$\matrixelement{\psi_{\text{Exact}}}{H_{P}}{\psi_{\text{Exact}}}<0$ for all
graph instances considered in this work and that
$\matrixelement{\psi}{H_{P}}{\psi}<0$, which we show in Appendix A, we do not
alter the approximation ratio or Hamiltonian given in order to maintain
comparability with previous works.

##  Appendix C QAOA Approximation Ratio Results

The approximation ratio is tracked for one to six QAOA layers for regular and
complete graphs in FIG. 10 as well as grid graphs in FIG. 11. These are the
same graphs considered in FIG. 3 and FIG. 4 respectively in the main body of
this work. We find that all graph types considered show a monotonic increase
in the approximation ratio as the number of QAOA layers is increased,
additionally noting that increasing the system size only has a negligible
negative effect on the performance of QAOA.

a) b) c) Figure 10: The approximation ratio for a) complete, b) 3-regular and
c) 4-regular graphs. It is recognised that complete graphs with random weights
appear to be harder for QAOA to solve with approximation ratios plateauing at
$>0.8$. This is contrasted by the random regular graphs with unit edge weights
which appear to have approximation ratios approaching one.

Additionally, it is recognised that the approximation ratios for the complete
graphs in FIG. 10(a) appear to be significantly lower than those of random
regular graphs of the same size in FIG. 10(b-c) with the complete graphs
plateauing at $0.8$ compared to close to one for the regular graphs. This is
generally an indication that the complete graphs are more difficult to solve
using QAOA compared to the less dense regular graphs. This is also consistent
with the results in the main body of this work which found that the
entanglement entropy of the complete graphs continued to increase up to six
QAOA layers, compared to regular graphs which had a maximum entanglement
entropy at two or three layers.

Regarding the grid graphs, it is found that the approximation ratio for two-
column grids in FIG. 11(a) are similar to the random regular graphs, whereas
three and four-column grids appear to have a lower approximation ratio
compared to random 4-regular graphs as well as the two-column grids. This is
consistent with the main body of this work which finds that the entanglement
entropy of the three and four-column grid graphs is higher compared to two-
column grids. However, we do note that the entanglement entropy of the random
4-regular graphs is similar to that of the three and four-column grids despite
the difference in approximation ratio.

Overall the approximation ratio serves as an adequate measure in determining
the performance of QAOA provided that one is careful with the formulation of
the problem Hamiltonian. In that regard, in its most commonly used form in the
study of QAOA and VQAs in general, one needs to be careful when using it to
perform fundamental analysis as it is ill-defined if considering various
problem Hamiltonians. For the types of problem considered in this work, the
approximation ratio primarily served as a tool in determining whether QAOA is
performing well or not, finding that the performance of QAOA as determined by
the approximation ratio appears to be loosely tied to the entropy of
entanglement of the final state.

a) b) c) Figure 11: The approximation ratio for grids with a) two, b) three
and c) four columns respectively for one to six QAOA layers. It is recognised
that the approximation ratio for three and four-column grids appears to
plateau at a lower value with two-column grids approaching an approximation
ratio of 1, indicating that QAOA is able to determine the ground state of the
Hamiltonian exactly.

##  Appendix D Simulation Fidelity for larger QAOA Simulations on Grid Graphs

We provide the simulation fidelity for the grid graphs discussed in the main
body of this work at four and six QAOA layers in FIG. 12. It is noted that the
scaling appears to be similar to that of the 3 and 4-regular graphs at the
same number of QAOA layers. The primary distinction is that there appears to
be a notable increase in the “simulation fidelity” upon truncation. Similar to
the QNNs trained on the CIFAR dataset, it is not apparent why this occurs, but
it is likely due to the act of truncation resulting in the state accessing a
part of the Hilbert Space that it previously could not with the unitary
operations which QAOA uses.

Figure 12: The simulation fidelity at four QAOA layers (top row) and six QAOA
layers (bottom row) for grid graphs with two (left column), three (middle
column) and four columns (right column) respectively. We find across all
graphs at both four and six layers that there is a strong resilience to
truncation of entanglement. It is also recognised that similar to the QNN
models trained on the CIFAR dataset, truncation sometimes results in an
improvement in the cost compared to the untruncated state, resulting in a
“simulation fidelity” of $>1$. Possible reasons for this are discussed in the
main body of this work.

##  Appendix E A note on the alternating ansatz

Consider the fundamental building blocks of the alternating ansatz, firstly,

$\quantikz[rowsep={2mm},columnsep=0.1cm]\ctrl{1}&\qw{}\\\ \targ{}\targ{}\\\
\qw{}\ctrl{-1}=(CNOT\otimes I)(I\otimes NOTC).$ (13)

It is apparent that the CNOT gates in this configuration commute as the Pauli
$X$ operation that may be conditionally applied to the second qubit commutes
with itself. Likewise for the second building block,

$\quantikz[rowsep={2mm},columnsep=0.1cm]\targ{}&\qw{}\\\ \ctrl{-1}\ctrl{1}\\\
\qw{}\targ{}=(NOTC\otimes I)(I\otimes CNOT),$ (14)

where it is recognised that the control operation likewise commutes with
itself. As such it becomes apparent that all the CNOT gates in the alternating
ansatz commute with each other. Given this, one can conclude that the state
resulting from this ansatz lives in a greatly restricted Hilbert space. This
may be compared to the other ansätze considered in this work where the CNOT
operations do not commute with each other to such an extent. An additional
consequence of this is that the entanglement that this ansatz can produce is
restricted at low depth as the only source of non-commutativity are the single
qubit rotations which sandwich the CNOT gates.

##  Appendix F Tracking Entanglement Entropy for all Ansätze

For completeness, we include the evolution of entanglement entropy throughout
the circuit for the QNNs trained on the MNIST and BMNIST which are not
included in the main body of this work in FIG. 13. There does not appear to be
a substantial difference between the evolution of the periodic ansatz and that
of the full, linear and single control ansätze. Regarding the alternating
ansatz, the only difference appears to be with the $20$ layer QNN where it is
recognised that the ansatz cannot generate very high entanglement and as such
QNN is in a different regime compared to other ansätze which can, or the
alternating ansatz at higher depth.

a) Full Circuit

b) Linear Circuit

c) Single Control Circuit

d) Alternating Circuit

Figure 13: The evolution of entanglement throughout the QNN circuit for the
remaining ansätze not shown in the main body of this work. The top sub-figures
are for circuits trained on the BMNIST dataset with the bottom sub-figures
corresponding to circuits trained on the MNIST dataset. We observe that there
is a minor plateau towards the end of the BMNIST circuits for all ansätze
shown, which was not observed in the periodic ansatz. As the $20$ layer
alternating ansatz circuit is not capable of generating maximal entanglement,
the entanglement entropy throughout the circuit appears to evolve differently
compared to the other ansätze.


of these weight distributions again has a closed-form solution.

$\displaystyle\operatorname*{KL}\left(\operatorname*{Dir}(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}},\overset{{\kappa}_{i}}{\ldots},\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\
}\operatorname*{Dir}(\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}},\overset{{\kappa}_{i}}{\ldots},\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}})\right)$
$\displaystyle=$
$\displaystyle\log\frac{\Gamma({\alpha}^{q}_{i})}{\Gamma(\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}})}-{\kappa}_{i}\log\frac{\Gamma(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})}{\Gamma(\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}})}+{\alpha}^{q}_{i}(1-\tfrac{\alpha^{p}_{0}}{\alpha^{q}_{0}})(\psi(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})-\psi({\alpha}^{q}_{i}))$

This term then needs to be summed across components $1\leq i\leq c{+}1$.

For the factors for generating vectors from each individual component of the
base distribution, because the different components have been factorised,
there is also a closed-form solution to computing these KL divergences. Each
Gaussian component of the posterior’s base distribution is compared
independently to the Gaussian of the prior’s base distribution. The
$\operatorname*{KL}$ divergence between two Gaussians (with diagonal
covariance with values ${\boldsymbol{\sigma}}$) is:

$\displaystyle\operatorname*{KL}({G}^{q}_{i}\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\ }G^{p}_{0})$ $\displaystyle=$
$\displaystyle\tfrac{1}{2}\sum_{h=1}^{d}(\frac{({\mu}^{q}_{ih}-{\mu}^{p}_{h})^{2}}{({\sigma}^{p}_{h})^{2}}+\frac{({\sigma}^{q}_{ih})^{2}}{({\sigma}^{p}_{h})^{2}}-1-\log(\frac{({\sigma}^{q}_{ih})^{2}}{({\sigma}^{p}_{h})^{2}}))$
$\displaystyle=$
$\displaystyle\tfrac{1}{2}\sum_{h=1}^{d}(({\mu}^{q}_{ih})^{2}+({\sigma}^{q}_{ih})^{2}-1-\log(({\sigma}^{q}_{ih})^{2}))$

where the last step assumes
${\boldsymbol{\mu}}^{p}={\boldsymbol{0}},\leavevmode\nobreak\
({\boldsymbol{\sigma}}^{p})^{2}={\boldsymbol{1}}$. This term then needs to be
multiplied by the number $\kappa_{i}$ of vectors for this component, and
summed across components $1\leq i\leq c{+}1$.

Given these exact closed-form solutions for each pair of factors, we can
compute the full KL divergence. We start by combining the formulas for the
weight factors, where some terms cancel:

$\displaystyle\operatorname*{KL}\left(\operatorname*{Dir}({\alpha}^{q}_{1},\overset{c+1}{\ldots},{\alpha}^{q}_{c+1})\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\
}\operatorname*{Dir}(\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{1}}{\alpha^{q}_{0}},\overset{c+1}{\ldots},\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{c+1}}{\alpha^{q}_{0}})\right)$
$\displaystyle+\sum_{i=1}^{c+1}\operatorname*{KL}\left(\operatorname*{Dir}(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}},\overset{{\kappa}_{i}}{\ldots},\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\
}\operatorname*{Dir}(\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}},\overset{{\kappa}_{i}}{\ldots},\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}})\right)$
$\displaystyle=$
$\displaystyle\log\frac{\Gamma(\alpha^{q}_{0})}{\Gamma(\alpha^{p}_{0})}-\sum_{i=1}^{c+1}{\kappa}_{i}\log\frac{\Gamma(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})}{\Gamma(\frac{\alpha^{p}_{0}{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}})}+(1-\tfrac{\alpha^{p}_{0}}{\alpha^{q}_{0}})\sum_{i=1}^{c+1}{\alpha}^{q}_{i}(\psi(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})-\psi(\alpha^{q}_{0}))$

Now we can put all these pieces together.

$\displaystyle\operatorname*{KL}(\operatorname*{BFDP}({\boldsymbol{G}}^{q},{\boldsymbol{\alpha}}^{q},{\boldsymbol{\kappa}})\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\
}\operatorname*{BFDP}({\boldsymbol{G}}^{p},{\boldsymbol{\alpha}}^{q}\tfrac{\alpha^{p}_{0}}{\alpha^{q}_{0}},{\boldsymbol{\kappa}}))$
$\displaystyle=$
$\displaystyle\int_{{\boldsymbol{\rho}}}\int_{{\boldsymbol{\pi}}^{\prime}}\int_{{\boldsymbol{v}}}d({\boldsymbol{\rho}}\hskip
0.86108pt;\leavevmode\nobreak\
{\alpha}^{q}_{1},\ldots,{\alpha}^{q}_{c+1})\left(\prod_{i=1}^{c+1}d({\boldsymbol{\pi}}^{\prime}_{i}\hskip
0.86108pt;\leavevmode\nobreak\
\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}},\overset{{\kappa}_{i}}{\ldots},\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})\prod_{i=1}^{c+1}\prod_{j=1}^{{\kappa}_{i}}{G}^{q}_{i}({\boldsymbol{z}}_{ij})\right)\leavevmode\nobreak\
\log\frac{\operatorname*{BFDP}({\boldsymbol{G}}^{p},{\boldsymbol{\alpha}}^{q}\tfrac{\alpha^{p}_{0}}{\alpha^{q}_{0}},{\boldsymbol{\kappa}})}{\operatorname*{BFDP}({\boldsymbol{G}}^{q},{\boldsymbol{\alpha}}^{q},{\boldsymbol{\kappa}})}\leavevmode\nobreak\
d\leavevmode\nobreak\ {{\boldsymbol{\rho}}}\leavevmode\nobreak\
d\leavevmode\nobreak\ {{\boldsymbol{\pi}}^{\prime}}\leavevmode\nobreak\
d\leavevmode\nobreak\ {{\boldsymbol{v}}}$ $\displaystyle=$
$\displaystyle\operatorname*{KL}\left(\operatorname*{Dir}({\alpha}^{q}_{1},\overset{c+1}{\ldots},{\alpha}^{q}_{c+1})\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\
}\operatorname*{Dir}(\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{1}}{\alpha^{q}_{0}},\overset{c+1}{\ldots},\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{c+1}}{\alpha^{q}_{0}})\right)$
$\displaystyle+\sum_{i=1}^{c+1}\leavevmode\nobreak\
\operatorname*{KL}\left(\operatorname*{Dir}(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}},\overset{{\kappa}_{i}}{\ldots},\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\
}\operatorname*{Dir}(\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}},\overset{{\kappa}_{i}}{\ldots},\alpha^{p}_{0}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}})\right)\leavevmode\nobreak\
+{\kappa}_{i}\operatorname*{KL}({G}^{q}_{i}\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\ }G^{p}_{0})$ $\displaystyle=$
$\displaystyle\log\Gamma(\alpha^{q}_{0})-\log\Gamma(\alpha^{p}_{0})+\sum_{i=1}^{c+1}{\kappa}_{i}(\log\Gamma(\frac{\alpha^{p}_{0}{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}})-\log\Gamma(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}}))+(\alpha^{q}_{0}-\alpha^{p}_{0})\left(-\psi(\alpha^{q}_{0})+\sum_{i=1}^{c+1}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}}\psi(\tfrac{{\alpha}^{q}_{i}}{{\kappa}_{i}})\right)$
$\displaystyle+\tfrac{1}{2}\sum_{i=1}^{c+1}{\kappa}_{i}\sum_{h=1}^{d}(\frac{({\mu}^{q}_{ih}-{\mu}^{p}_{h})^{2}}{({\sigma}^{p}_{h})^{2}}+\frac{({\sigma}^{q}_{ih})^{2}}{({\sigma}^{p}_{h})^{2}}-\log\frac{({\sigma}^{q}_{ih})^{2}}{({\sigma}^{p}_{h})^{2}}-1)$
$\displaystyle=$
$\displaystyle\log\Gamma(\alpha^{q}_{0})+\sum_{i=1}^{c+1}{\kappa}_{i}\left(\log\Gamma(\frac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}})-\log\Gamma(\frac{{\alpha}^{q}_{i}}{{\kappa}_{i}})\right)+(\alpha^{q}_{0}-1)\left(-\psi(\alpha^{q}_{0})+\sum_{i=1}^{c+1}\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}}\psi(\frac{{\alpha}^{q}_{i}}{{\kappa}_{i}})\right)$
$\displaystyle+\tfrac{1}{2}\sum_{i=1}^{c+1}{\kappa}_{i}\sum_{h=1}^{d}(({\mu}^{q}_{ih})^{2}+({\sigma}^{q}_{ih})^{2}-1-\log(({\sigma}^{q}_{ih})^{2}))$

where the last step assumes $\alpha^{p}_{0}=1,\leavevmode\nobreak\
{\boldsymbol{\mu}}^{p}={\boldsymbol{0}},\leavevmode\nobreak\
({\boldsymbol{\sigma}}^{p})^{2}={\boldsymbol{1}}$. Equation (B) gives the KL
portion of the loss when we are given the full set ${\boldsymbol{\kappa}}$ of
numbers of vectors ${\kappa}_{i}$ generated for each component $i$.

Equation (B) is approximately linear in ${\kappa}_{i}$, when the variation in
${\kappa}_{i}$ is fairly small relative to the values of ${\kappa}_{i}$. The
Gaussian term is exactly linear in ${\kappa}_{i}$, and the terms
$\psi(\frac{{\alpha}^{q}_{i}}{{\kappa}_{i}})$ and
${\kappa}_{i}\left(\log\Gamma(\frac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}{\kappa}_{i}})-\log\Gamma(\frac{{\alpha}^{q}_{i}}{{\kappa}_{i}})\right)$
are both approximately linear in ${\kappa}_{i}$. This allows us to approximate
the expectation over ${\kappa}_{i}$ of this loss as this loss of the
expectation over ${\kappa}_{i}$, as discussed in Section 3.2. In this case,
this approximation of the full KL divergence is:

$\displaystyle\operatorname*{KL}(\operatorname*{BFDP}({\boldsymbol{G}}^{q},{\boldsymbol{\alpha}}^{q},{\boldsymbol{\kappa}})\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\
}\operatorname*{BFDP}({\boldsymbol{G}}^{p},{\boldsymbol{\alpha}}^{q}\tfrac{\alpha^{p}_{0}}{\alpha^{q}_{0}},{\boldsymbol{\kappa}}))$
$\displaystyle\approx$
$\displaystyle\log\Gamma(\alpha^{q}_{0})+(\alpha^{q}_{0}-1)\left(\psi(\tfrac{\alpha^{q}_{0}}{\kappa_{0}})-\psi(\alpha^{q}_{0})\right)+\kappa_{0}\left(\log\Gamma(\frac{1}{\kappa_{0}})-\log\Gamma(\frac{\alpha^{q}_{0}}{\kappa_{0}})\right)$
$\displaystyle+\tfrac{1}{2}\kappa_{0}\sum_{i=1}^{c+1}\frac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}}\sum_{h=1}^{d}\left(({\mu}^{q}_{ih})^{2}+({\sigma}^{q}_{ih})^{2}-1-\log(({\sigma}^{q}_{ih})^{2})\right)$

In the case where ${\kappa}_{i}=1$ for all $1\leq i\leq c+1$, then each
Gaussian ${G}^{q}_{i}$ is only used once, and there is no Dirichlet KL term
for the individual components. This gives us a full KL divergence of:

$\displaystyle\operatorname*{KL}(\operatorname*{BFDP}({\boldsymbol{G}}^{q},{\boldsymbol{\alpha}}^{q},{\boldsymbol{1}})\operatorname*{\leavevmode\nobreak\
\|\leavevmode\nobreak\
}\operatorname*{BFDP}({\boldsymbol{G}}^{p},{\boldsymbol{\alpha}}^{q}\tfrac{\alpha^{p}_{0}}{\alpha^{q}_{0}},{\boldsymbol{1}}))$
$\displaystyle=$
$\displaystyle\log\Gamma(\alpha^{q}_{0})+\sum_{i=1}^{c+1}\left(\log\frac{\Gamma(\tfrac{{\alpha}^{q}_{i}}{\alpha^{q}_{0}})}{\Gamma({\alpha}^{q}_{i})}+{\alpha}^{q}_{i}(1-\tfrac{1}{\alpha^{q}_{0}})(\psi({\alpha}^{q}_{i})-\psi(\alpha^{q}_{0}))\right)$
$\displaystyle+\tfrac{1}{2}\sum_{i=1}^{c+1}\sum_{h=1}^{d}\left(({\mu}^{q}_{ih})^{2}+({\sigma}^{q}_{ih})^{2}-1-\log(({\sigma}^{q}_{ih})^{2})\right)$