# QNEAT: Natural Evolution of Variational Quantum Circuit Architecture

Alessandro Giovagnoli 1 Yunpu Ma 2 Volker Tresp 3

###### Abstract

Quantum Machine Learning (QML) is a recent and rapidly evolving field where
the theoretical framework and logic of quantum mechanics are employed to solve
machine learning tasks. Various techniques with different levels of quantum-
classical hybridization have been proposed. Here we focus on variational
quantum circuits (VQC), which emerged as the most promising candidates for the
quantum counterpart of neural networks in the noisy intermediate-scale quantum
(NISQ) era. Although showing promising results, VQCs can be hard to train
because of different issues, e.g., barren plateau, periodicity of the weights,
or choice of architecture. This paper focuses on this last problem for finding
optimal architectures of variational quantum circuits for various tasks. To
address it, we propose a gradient-free algorithm inspired by natural evolution
to optimize both the weights and the architecture of the VQC. In particular,
we present a version of the well-known neuroevolution of augmenting topologies
(NEAT) algorithm and adapt it to the case of variational quantum circuits. We
refer to the proposed architecture search algorithm for VQC as QNEAT. We test
the algorithm with different benchmark problems of classical fields of machine
learning i.e. reinforcement learning and combinatorial optimization.

##  1 Introduction

The field of quantum computing has, in the last decades, attracted much
attention due to the promise of enabling us to solve problems that
classically, altaugh they be solved, are practically not feasible [1], [2],
[3], [4]. These problems range from quantum metrology [5], [6], mathematics
[7], [8], chemistry [9] to optimization in general [10], [11], [12]. The
possibility of using intrinsic quantum algorithms that proved to have a
speedup like the Deutsch–Jozsa, Grover search, quantum Fourier transform, or a
hybrid of classical and quantum techniques [13] is pushing the academy and
industry into exploring the extent of the capabilities of this field.

At this stage, the theoretical methods and algorithms related to the field of
quantum information theory are limited by the current state of the art in
quantum hardware production, which is developing at a slower pace.

In the current noisy intermediate-scale quantum (NISQ) era, quantum computers
contain qubits ranging from 50 to 100, which are not fault-tolerant. They are
still affected by decoherence, meaning that the qubits cannot be kept for a
long time in the desired quantum state, and are not able to continuously
implement quantum error correction, features needed to achieve the so-called
quantum supremacy [14], [15], [15].

In the current NISQ era emerged the field of quantum machine learning (QML),
which exploits and mixes classical and quantum techniques to solve classical
or pure quantum machine learning problems [16]. Some algorithms and techniques
have already proved to give a quantum speedup over their classical
counterparts once the hardware allows managing a higher number of qubits with
higher stability. Other methods are instead being still explored.

A promising class of algorithms is the variational quantum algorithms that use
variational quantum circuits (VQCs) as the building block. In these
parametrized quantum circuits, the physical gates, usually rotations and
controlled-nots, depend on adjustable parameters that can be adapted to make
the circuit perform better on various tasks.

Similar to classical machine learning, we use neural networks as function
approximators that rely on the theory of the well-known Universal
Approximation Theorem [17]. Analogously we assume here the existence of a
function mapping the quantum state containing the features of the problem of
interest into the quantum state containing the labels. According to the laws
of quantum mechanics, this function is a unitary evolution mapping an initial
state into the final one. It can be shown that any unitary operator acting on
multiple qubits can be expressed through ROTs and CNOTs, which justifies the
interest in using VQCs and exploring their capabilities to solve machine-
learning tasks.

Due to the low amount of qubits needed to encode the information and the low
amount of parameters necessary to approximate the function of interest
adequately, VQCs are promising candidates for quantum neural networks in the
NISQ era. They are already employed in several machine learning tasks. In
these tasks, VQCs are set in a classical neural network pipeline, and their
weights are trained to minimize a selected loss function once a fixed
architecture has been chosen.

Nonetheless, they present issues that may limit their usage. One major problem
is the classical barren plateau phenomenon [18], [19], [20], [21], [22], which
is linked to the expressibility of VQCs and not only to the optimizer. Another
issue is that the depth of the circuit increases the noise, leading to the
loss of entanglement or coherence between qubits. A key factor in the study of
the VQCs is thus choosing an appropriate architecture, or ansatz, that can
adequately approximate the function of interest. However, simultaneously, it
doesn’t compromise the stability of the circuit by making it too deep, i.e.,
with an unnecessary amount of quantum gates. This motivates the interest in
studying variable architecture algorithms that evolve, finding the most
suitable architecture and weights rather than starting from a fixed
architecture and only updating its weights.

In Section 2 we will first briefly review some of the techniques already shown
in the literature to perform such tasks. In Section 3 and 4 we present our
algorithm, in Section 5 the experiments setting on which it has been tested on
and in Section 6 we present the results. In conclusion, in Section 7 we show a
variation of the QNEAT algorithm for multiple objective optimization purposes.

##  2 Related work

The classical machine learning pipeline, which has also been applied to VQCs,
is based on the traditional gradient-based approach. In this approach, a
selected loss function is evaluated, gradients are computed through the
backpropagation, and the weights of the function approximator are updated.

One of the main problems in applying the classical gradient-based methods is
the barren plateau of gradients during the training of VQCs. It has been shown
[23] that with the increasing depth of the circuit, the probability of finding
a non-zero entry in the gradient becomes exponentially small. This issue is
related to the intrinsic expressibility of variational quantum circuits and
not simply to the selected optimizer. Therefore, gradient-free methods have
been proposed to overcome problems, such as barren plateaus or the risk of
being stuck in local minima. Some examples are particle swarm optimization
[24], evolution strategies [25], or genetic algorithms [26].

These gradient-free techniques have also been applied to the case of quantum
circuit optimization. Some start from a fixed ansatz and only focus on
optimizing the weights [27]. The chosen fixed initial architecture can be
problem inspired, meaning that the way the gates are placed in the circuit
depends on the given problem, which is optimal for its solution. Some examples
are Ansätze derived from the field of quantum chemistry [28], [29] or
combinatorial optimization, as the famous quantum approximate optimization
algorithm (QAOA) [30], [31]. In alternative, they could be problem agnostic,
meaning that the architecture is independent of the problem as the hardware
efficient ansatz [32], often used because of its ease in physical hardware
implementation.

Other techniques instead attempt to find the optimal architecture for the task
of interest, which means heuristically trying to place new gates to make the
circuit perform better according to some carefully designed metrics. Inspired
by the field of quantum chemistry and designed to gradually evolve a
variational quantum eigensolver are the ADAPT-VQE algorithm [33], one of the
first algorithms of this type to be proposed, or EVQE [34] where new gates are
added smoothly, and an informed removal of redundant gates is performed.

Various algorithms have been proposed to try to optimise the architecture of a
quantum circuit in order to match a target matrix [35], [36], [37], [38],
[39]. The techniques here proposed are not easily generalisable though to the
task of optimising VQCs also because they make use of non-parametrised gates.

In this paper we propose a genetic algorithm which takes inspiration from the
classical neuroevolution of augmenting topologies (NEAT) [40] proposed in 2002
by Stanley and Miikkulainen, which is categorized as a sexual algorithm since
it employs the crossover technique. As it will be shown, here the architecture
of the circuit as well as the weights are otpimized at the same time, and
trough the speciation diversity is preserved, meaning that different areas of
the search space are explored.

An adaptation of the NEAT algorithm to the quantum case is proposed, having a
generic multi-purpose and NISQ-friendly algorithm for solving a variety of
tasks in the field of quantum machine learning: from the tasks closely
inspired by quantum problems to the classical machine learning tasks. In the
following sections we will explore in detail the quantum neat algorithm and
show some of the settings where it has been tested and the results.

##  3 NEAT for Variational Quantum Circuits

In this chapter, we present our algorithm, which consists of an adapted
version of the Neuroevolution for Augmented Topologies for the case of quantum
variational architectures. We will first consider the case of a free or a pre-
defined structure in the architecture and then explain how the genome,
crossover, mutation, and speciation process have been adapted.

### The architecture

To adapt the architecture to the quantum case, we first distinguish between a
constrained and a free architecture. We define a variational quantum circuit
with a free architecture as a VQC where there is no constraint on the
placements of rotation gates (ROTs) and controlled-not gates (CNOTs). In other
words, ROTs gates are allowed to concatenate one after the other, and CNOTs
can connect any two wires. In such a case, no regularity is encountered, and
thus no concept of a layer is defined.

A VQC with a constrained architecture is instead a circuit where, after the
initial encoding layer, the ROTs and CNOTs follow a regular pattern. There are
many architectures, namely architecture Ansätze, that can be used. Some common
examples are the hardware efficient architecture or the strongly entangling
architecture. We will take the last one as a reference and describe it in more
detail since it’s often used in literature when dealing with the type of
problems we will test our algorithm.

After the usual encoding layer, the architecture consists of repeating layers
of first a set of ROTs, one for each wire, and then a sequence of CNOTs, where
each one of them goes from wire $i$ to wire $i+1$, $\mod(n)$, with $n$ the
number of wires, as showed in Figure 1. The gates grouped into the dotted
lines constitute one layer, which can be repeated for an arbitrary amount of
time. In our case, the algorithm will determine how deep the circuit will be
and, thus, how many layers it will be made of.

[column sep=10pt, row sep=0.7cm,between origins] $\ket{0}$& [4,disable auto
height, style=inner xsep=-4pt]U R[4,steps=5,style=dashed,rounded corners,
inner xsep=2pt, background] 1 1-11-3

$\ket{0}$ R 1 2-12-3

$\ket{0}$ R 1 3-13-3

$\ket{0}$ R -3 4-14-3

Figure 1: Quantum circuit with the Strongly Entangling Layers architecture

To give e deeper insight into the resulting architecture once the algorithm
made it evolve and added gates respecting the constraints, we look at one
example in Figure 2, where the encoding part has been left out for simplicity.
The dotted lines identify the layers previously discussed. According to the
constraints, these layers are not entirely filled but only partially. Layer
number 1 is completely filled; layer 2 only has two ROTs and two CNOTs, while
layer 3 is filled with two ROTs and one CNOT. In any case, we can see that the
constraints are respected inside each layer: no more than one ROT for each
wire is placed, and the CNOTs always connect wires $i$ and $i+1,\mod(n)$.
Inside each layer, we can thus identify a sublayer of ROTs and a sublayer of
CNOTs.

[column sep=8pt, row sep=0.7cm,between origins] &
R[4,steps=5,style=dashed,rounded corners, inner xsep=0pt, background]1 1
[4,steps=4,style=dashed,rounded corners, inner xsep=-1.5pt, background]2
R[4,steps=2,style=dashed,rounded corners, inner xsep=0pt, background]3 1

R 1 R 1 2-12-3

R 1 R R 3-13-3

R -3 -3 4-14-3

Figure 2: Example of a quantum constrained variational quantum circuit. Each
layer is encircled with dotted lines. In each layer first the rotation gates
and than the cnot gates are placed.

Clearly, the set of all possible architectures compatible with the constraints
we posed is a subset of the ones that a free search could find. Nonetheless,
the task would be computationally much more expensive. For example, only the
number of CNOTs that could be placed in a layer grows with the number $n$ of
wires as $\frac{n!}{2(n-2)!}$, while it grows linearly with $n$ in the
constrained case. Also, no better performance on a practical level is
guaranteed. For these reasons, from now on, we will only consider the case of
a constrained architecture and leave the free case as a possible future
research.

### Genome

Each agent of the population is endowed with genetic information that encodes
which gates are present at a given moment of the evolution and where they are
placed. Through the genes of the agent, its architecture can be reconstructed.

If we consider a VQC with $n$ layers and $m$ wires, then each gate is uniquely
identified by a tuple $(t,l,w)$ containing information about the type, layer,
and wire of the gate. More specifically

$t\in\\{\text{ROT},\text{CNOT}\\},\ l\in\\{1,\dots,n\\},and\
w\in\\{1,\dots,m\\}.$

This information is enough to identify any gate because in the constrained
architecture, once a layer $l$ is specified, we also know to which sublayer
the gate belongs, meaning that all the ROTs must be placed before the CNOTs.
Parameter $w$ indicates which wire it belongs to, and if we are dealing with a
ROT gate, then it can already be placed without any other ambiguity.
Otherwise, if it’s a CNOT gate, we know that it will go from $w\to
w+1,\mod(m)$, which also determines uniquely where to place it.

The genes also contain the innovation numbers, which, analogously to the
classical NEAT algorithm, keep track of the chronological time step in which
the mutation happened and are later used to compare mutations that occurred at
the same time for the crossover. Each innovation number uniquely identifies a
tuple $(l,w)$. Since the architecture is constrained, ROTs and CNOTs are
always placed in their respective sublayers, which means that a mutation
producing a CNOT could not have produced a ROT in the same place. Thus the
innovation numbers of CNOTs and ROTs should be compared separately. On this
basis, we divide the genome lists depending on the type of gate.

Every ROT gate also contains information about the rotation angles. As an
explicit example we show the genome of the architecture in Figure 2 in Table 1
and 2.

Layer | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3
---|---|---|---|---|---|---|---|---
Wire | 1 | 2 | 3 | 4 | 2 | 3 | 1 | 3
Angles | $\vec{\theta}_{11}$ | $\vec{\theta}_{12}$ | $\vec{\theta}_{13}$ | $\vec{\theta}_{14}$ | $\vec{\theta}_{22}$ | $\vec{\theta}_{23}$ | $\vec{\theta}_{31}$ | $\vec{\theta}_{33}$
Innov. n. | 1 | 2 | 3 | 4 | 6 | 7 | 9 | 10

Table 1: Genome of ROTs for architecture in Figure 2. The rotation angles
$(\theta_{x},\theta_{y},\theta_{z})$ are encoded in a vector
$\vec{\theta}_{l,w}$ where $l,w$ stand for the layer and wire.

Layer | 1 | 1 | 1 | 1 | 2 | 2 | 3
---|---|---|---|---|---|---|---
Wire (from) | 1 | 2 | 3 | 4 | 2 | 4 | 1
(Wire to) | 2 | 3 | 4 | 1 | 3 | 1 | 2
Innov. n. | 1 | 2 | 3 | 4 | 6 | 8 | 9

Table 2: Genome of CNOTs for architecture in Figure 2. The genome of each CNOT
contains the information of the wire on which the control depends on, here
called Wire (from). The information about the wire it is acting on (Wire to)
is redundant because of the constrains on the architecture. Here is shown
anyway for completeness.

### Crossover

Crossover is the process through which the genome of two members of the
population gets mixed during the reproduction of the fittest members to
produce the offspring’s genome. Given two genomes, we define matching genes
the ones that, given a type $t\in\\{\text{ROT},\text{CNOT}\\}$ have the same
tuple $(l,w)$. In the case of ROTs, this means that two rotation gates, even
though they may have different angles, are considered matching genes if placed
at the same point of the circuit’s architecture. In the case of CNOTs,
instead, the above definition corresponds to saying that two CNOTs are
matching if they connect identical qubits. We then define disjoint genes as
those that differ for one of the values in the tuple $(l,w)$.

When two members reproduce, we want the fittest member’s genome to be the
basis for the future offspring, with some modifications deriving from the less
fit one. The crossover method works by aligning the genomes with respect to
the innovation numbers so that the chronology of mutations allows us to
compare and see which are the matching or disjoint genes. Then we select the
genes for the offspring with the following rules:

  1. 1.

Matching genes are inherited randomly.

  2. 2.

Disjoint genes are inherited from the fittest parent. If the two parents have
the same fitness, disjoint genes will also be chosen randomly.

The crossover process is performed separately for CNOTs and ROTs since so are
the genome lists. In Figure 3, we give an explicit example of crossover for
two simple architectures. We assume that two architectures have the same
fitness, and we highlight the layers with the dotted boxes.

[column sep=8pt, row sep=0.7cm,between origins] &
R[4,steps=3,style=dashed,rounded corners, inner xsep=-0.5pt, background]1 1
[4,steps=2,style=dashed,rounded corners, inner xsep=-0.5pt, background]2
R
1
-3 $\;\;\;\;\;\;\varprod\;\;\;\;\;\;$ [column sep=8pt, row sep=0.7cm,between origins] & R[4,steps=5,style=dashed,rounded corners, inner xsep=-0.5pt, background]1 1
1
R 1 1
-3 pt CNOTs Layer: 1
---
$1->2$
Layer: 1
---
$3->4$
Layer: 2
---
$4->1$
Layer: 1
---
$1->2$
Layer: 1
---
$2->3$
Layer: 1
---
$3->4$
Layer: 1
---
$4->1$
pt Layer: 1
---
$1->2$
Layer: 1
---
$2->3$
Layer: 1
---
$3->4$
Layer: 2
---
$4->1$
ROTs Layer: 1
---
Wire: 1
Layer: 2
---
Wire: 2
Layer: 1
---
Wire: 1
Layer: 1
---
Wire: 3
pt Layer: 1
---
Wire: 1
Layer: 2
---
Wire: 2
pt[column sep=8pt, row sep=0.7cm,between origins] &
R[4,steps=4,style=dashed,rounded corners, inner xsep=-0.5pt, background]1 1
[4,steps=2,style=dashed,rounded corners, inner xsep=-0.5pt, background]2
1 R
1
-3  Figure 3: Crossover process for two simple VQCs where the encoding layer has been omitted. The crossover process takes place separetly for CNOTs and ROTs. In each box the genes are aligned with respect to the innovation number. The fist line lists the genome of the left VQC; the second line the genome of the right VQC; the third line the genome of the offspring, where the gates have been selected according to the rules explained. Here the two VQC are supposed to have the same fitness, thus the choice of matching or disjoint genes is made randomly.

### Mutation

After the crossover has been performed, a mutation can take place. In the
mutation process, there are three possible features that we can modify: The
weights of the rotations can be adjusted (adding, for example, a small value
sampled from a normal distribution); A new gate (ROT or CNOT) can be added
respecting the rules of the constrained architecture. All the recent changes
are then encoded into the genome.

### Speciation

Furthermore, just like in the original idea of the NEAT algorithm, species are
introduced to diversify the different evolutions and preserve the diversity
for some time. This is because a new architecture may perform well only once
the weights have been appropriately adapted, which may take some evolution
steps.

We thus divide the population into species, and, in order to understand if a
generic agent is a member of a given species, we use the following metric to
compare the agent with the best-performing member of the species.

$\delta=c_{1}\frac{E}{N}+c_{2}\frac{D}{N}+c_{3}\overline{W},$ (1)

where $c_{1},c_{2},c_{3}$ are linear coefficients that can be chosen
arbitrarily, $E$ is the number of genes in excess, so the ones whose invention
number is not reached by the other agent, $D$ is the number of disjoint genes,
as defined before. $\overline{W}$ is the average distance between the rotation
angles of matching genes. $N$ is the number of genes of the architecture
containing the longest genome.

The reproduction process is thus performed inside a single species. If a
species is performing poorly, we want to penalize it by reducing its members,
and the opposite if, on average, it’s producing fit members. To do so, we
consider species $j$ containing in a given moment $N_{j}$ members. The number
of members of that species after the reproduction process will be

$N^{\prime}_{j}=\sum\limits_{i=0}^{N_{j}}\frac{f_{ij}}{\bar{f}},$ (2)

where $\bar{f}$ is the average fitness of the whole population.

##  4 The algorithm

We present the complete algorithm of QNEAT. The algorithm is explicitly
described in Algorithm 1. The primary hyperparameters of the algorithm are the
followings: the number of generations we want to run it for $N_{g}$, the
population size $N$, the weights mutation coefficient, e.g., the standard
deviation of the normal distribution $\mathcal{N}(0,\sigma)$ from which we
will sample to change the rotation weights. Moreover, we define the
probability that the weights of a gate will be changed as $p_{w}$, that a ROT
gate will be added as $p_{ROT}$, and that a CNOT gate will be added as
$p_{CNOT}$, the compatibility threshold $\delta_{0}$ to determine if a member
is or is not part of a species.

One last crucial hyperparameter given in input is the number of initial total
layers $i_{L}$. While we could start from an empty circuit and let QNEAT
evolve it, as we will do in the experiments, another option is to start from a
circuit with an initial number of layers filled in the sense of Figure 1.
Initial layers may lead to a faster convergence from observation of
experimental results, even though it’s not guaranteed.

Input: $N_{g},N,\sigma,p_{w},p_{ROT},p_{CNOT},\delta_{0},i_{L}$

begin

Create random population of size $N$

for  _every generation_ do

/* Evaluate fitness */

for  _every agent of the population_ do

Evaluate the fitness of the agent

end for

end for

/* Speciation */

for  _every agent of the population_ do

for  _every species_ do

Select best agent of species

$\delta\leftarrow d(agent,\text{best agent})$

if  _$\delta <\delta_{0}$_ then

Add agent to the current species

end if

else

Add a new species with current agent

end if

end for

end for

/* Crossover */

for  _every species_ do

Select the best performing agents and kill the others

Calculate the number of necessary spawns $N^{\prime}$

for  _$N^{\prime}$ times_ do

Select random agent1 and agent2 between the most performing ones

Child $\leftarrow$ $\text{ }crossover(agent1,agent2)$

/* Mutation */

Child $\leftarrow mutate(child)$

Add child to the species

end for

end for

end

Algorithm 1 QNEAT Algorithm

##  5 Experiments settings

To explore the range of tasks the algorithm can be applied to, we test it on a
variety of benchmark problems. Namely, the algorithm has been tried on
reinforcement learning and optimization tasks. In each task of benchmarks, the
algorithm remains the same apart from the function we use to evaluate the
fitness of population members.

### Reinforcement Learning

The field of quantum reinforcement learning is rapidly evolving [41].
Different techniques are being employed, each one with a different degree of
quantum-classical hybridization. As a reference we take the case of deep
reinforcement learning, where the well known Q-value method is solved with a
function approximator: a classical neural network is used to learn the $Q$
function, so the expected future total reward, by an update rule that comes
from the Bellman equation. This leads the function $Q$ to its desired value:

$Q(s,a)=\mathbb{E}\left[r+\gamma\max\limits_{a\in\mathcal{A}}Q(s^{\prime},a)\right]$
(3)

where $a\in\mathcal{A}$ is an action in the action space,
$s,s^{\prime}\in\mathcal{S}$ are the current and next observation in the
observation space, $r$ the reward of the action taken and $\gamma$ the
discount factor.

Different attempts have been made to reproduce the same algorithm using a VQC
as a function approximator for the $Q$ function [42], [43], [44]. Starting
from this framework, we also want the QNEAT algorithm to learn the $Q$ value
function. Since no gradient-update is employed here, in no point of the
algorithm the constraint of the Bellman equation is applied, and thus the
policy found may not respect it. We can conclude thus that in this context the
QNEAT algorithm behaves like an informed random search for a good (supposedly
optimal) policy.

We test the algorithm on the Cart Pole and Frozen Lake benchmarks. In the
first case we encode the observation space information in the qubits by a
simple angle rotation with respect to the $x$ axis: for the $i$-th
observation, whose value we call $\theta$, a rotation $R_{x}(\theta)$ is
applied to the gate $i$. We measure as many qubits as the dimension of the
action space. In the Cart Pole problem the dimensions of the observation and
action space are, respectively, four and two.

In the Frozen Lake benchmark we have an 8x8 grid for a total of 64 squares. We
identify each square with a number from 1 to 64 and convert the number into a
bit string of length $6=\log_{2}(64)$. We thus use 6 qubits to encode the
information applying to the $i$-th qubit a rotation of angle

$\theta_{i}=\pi x_{i},\ \ \text{with}\;\;x_{i}\in\\{0,1\\}.$ (4)

### Optimization

As an example of optimization, we consider combinatorial optimization
problems. In particular, we study the MaxCut problem, which is particularly
important since many quadratic unconstrained binary optimization problems can
be mapped into the MaxCut problem. Being able to solve it means thus the
ability to solve a broader class of combinatorial optimization problems.

One traditional approach to solving combinatorial optimization problems is the
Quantum Approximate Optimization Algorithm (QAOA) [30]. The QAOA can be seen
as a particular case of Variational Quantum Eigensolvers (VQEs), a class of
VQCs used to approximate the Schrödinger equation to evolve an initial state
into a final one under an evolving Hamiltonian.

More specifically, given an initial Hamiltonian $H_{i}$ with a known ground
state $\psi_{i,0}$, and a final Hamiltonian $H_{f}$ encoding our optimization
problem with ground state $\psi_{f,0}$ encoding the optimal solution, then we
can start from the state $\psi_{i,0}$ and make it evolve with an appropriate
unitary operation into the final one

$\ket{\psi_{f,0}}=U\ket{\psi_{i,0}},$ (5)

where the action of the unitary operator $U$ is performed by the VQC. We can
thus map this problem into a VQC by encoding the initial ground state
$\ket{\psi_{i,0}}$ into the qubits and find an appropriate architecture to
simulate a unitary time evolution $U$ to the final state encoding the optimal
solution.

To give a concrete example, one possible choice of $U$ is the one given by the
Schrödinger equation. Namely, we can choose an evolving Hamiltonian
$H(t)=tH_{f}+(1-t)H_{i}$, with $H_{f}$ the one encoding our problem. Then we
can exponentiate it to obtain the Schrödinger equation

$\ket{\psi_{f,0}}=\exp{\frac{-iH(t)t}{\hbar}}\ket{\psi_{i,0}},$ (6)

where the exponential can be decomposed analytically into physical gates, and
a precise architecture can be found. This is only one possible choice of
architecture, and many have been proposed [45]. Here we use the QNEAT
algorithm to evolve the circuit and evolutionarily find the optimal
architecture.

In this class of problems, we aim to find the state that encodes the lowest
energy of the problem Hamiltonian $H_{f}$. In other words, we want to minimize
the following expectation value

$\expectationvalue{H_{f}}{\psi_{f}}.$ (7)

The MaxCut problem we took into account consists of dividing the nodes on a
graph into two separate sets so that the imaginary line drawn to encircle one,
or the other set goes through the maximum number of edges in the graph. We can
label the nodes $0$ or $1$ depending on the set they belong to, and these
values can be encoded into the qubits. With an appropriate Hamiltonian, we can
encode the information of the edge between the two being cut or not.

Random $1$$2$$3$$4$$5$$6$$7$$8$ Ladder $1$$2$$8$$3$$7$$4$$6$$5$ Barbell
$1$$2$$4$$3$$5$$7$$6$$8$ Barbell $1$$2$$4$$3$$5$$7$$6$$8$ Caveman
$1$$3$$2$$4$$5$$6$$7$$8$ Figure 4: Benchmark graphs used for testing the
performance of QNEAT on combinatorial optimization tasks.

The benchmark graphs used are shown in Figure 4 and have been taken as example
benchmarks from [46]. For fitness we use the average value of the Hamiltonian
of MaxCut, namely:

$H=\sum\limits_{(i,j)\in G}\frac{1}{2}\left(1-Z_{i}\otimes Z_{j}\right),$ (8)

considering $Z_{k}$ the spin measured on the $k-$th qubit and $G$ being the
set of the edges of the graph. Considering the output of the measure on the
qubit to be in $\\{-1,1\\}$, then if two nodes $(i,j)$ belong to the same set,
so they have values $(1,1)$ or $(-1,-1)$, then the edge contributes with a
factor of 0 to the Hamiltonian, which corresponds to the fact that no cut goes
through the edge. If instead they have different values, $(-1,1)$ or $(1,-1)$,
then the edge contributes with a factor 1. We thus aim at maximizing the
Hamiltonian.

At the end of the evolution process, we select the best member and sample 100
times to see the distribution on the outcome results, so how many times the
circuit gives a measured bit-string corresponding to one of the optimal
solutions of the MaxCut problem for the given graph.

##  6 Results

We present in Table 3 the hyperparameters used to solve the different
problems. With Reinforcement learning we include both CartPole and
FrozenLake8x8. With MaxCut we refer to all four graphs. The parameters have
been chosen by doing a grid search.

Param. | Reinforcement learning | MaxCut
---|---|---
$N$ | 150 | 200
$\sigma$ | 0.01 | 0.01
$p_{w}$ | 0.3 | 0.6
$p_{ROT}$ | 0.5 | 0.3
$p_{CNOT}$ | 0.5 | 0.3
$\delta_{0}$ | 1.0 | 0.45
$i_{L}$ | 0/1/2 | 2
Table 3: Hyperparameters used to initialise the QNEAT algorithm to solve the
various tasks: Reinforcement Learning (Cartpole and FrozenLake) and MaxCut
(the four graphs)

### Reinforcement Learning

The results of Cart Pole and Frozen Lake are presented in Figure 5 and 6
respectively. We study the score of the VQE evolved by the QNEAT algorithm
starting with $0,1,2$ initial layers. We present separately the results of:
the top 5 member, the top member averaged an extra 100 times and the whole
population. The maximum score is 500. During the evolution, we also keep track
of the number of ROTs and CNOTs that contribute to the architecture. We can
see how the top 5 agents rapidly reach the maximum score, converging faster
when the number of initial layers increases. The population instead converges.

Figure 5: Results of the QNEAT algorithm for the Cart Pole environment. The
performances of the top 5 agents, the best agent, and the whole population
have been tracked. The best-performing agent has been tested 100 times. In the
last column, the number of gates has been plotted to keep track of the
complexity of the circuit. Figure 6: Results for the FrozenLake environment
arranged in the same way described in the above plots. Figure 7: Results for
the MaxCut problem. Each row describes one of the four graphs showed in Figure
4. The first column shows the accuracy while the other three show,
respectively, the number of total gates, CNOTs and ROTs used for the
architecture.

### Combinatorial Optimization

We solve the MaxCut problem on the four different graphs that we have shown
before. For each one of them, we evaluate the QAOA algorithm with 1, 2, 3, and
4 layers. Higher numbers of layers have also been tested, but they show the
same behavior as the case with 4, and have thus been omitted. We compare it
then with the QNEAT. In figure 6, the results can be seen. The four rows refer
to the different graphs. In each row, we study the performance of the best
member: the first column shows the accuracy of measuring an optimal solution
obtained by the QNEAT and QAOA algorithm. The last three rows show separately
the number of total gates, CNOTs, and ROTs used in the architecture of each
algorithm. Each epoch represents a generation of 200 members in the case of
QNEAT, while only one gradient update in the case of the QAOA algorithm. From
the graph, it can be easily seen how the QAOA improves with the number of
layers used. This comes with a linear increase of gates used. Also, it can be
seen how the QNEAT algorithm reaches good accuracies, comparable with the case
of QAOA with four layers but with a much lower amount of gates. This makes the
implementation more compatible with the current NISQ-era architectures.

### Evolution

We also show visually the evolution of one VQC starting from an empty
configuration in the case of the Cart Pole benchmark. The parameters used for
the next evolution are shown in Table 3 for the Reinforcement Learning tasks.
At the end of the evolution of the population, the best agent has been tracked
backward and its architecture visualized generation by generation. Figure 8
shows the evolution process. Only some of the 50 generations have been shown,
namely the ones where new gates have been added. In the others, either nothing
happened, or only the weights have been changed. It can be seen that, starting
from an empty architecture, apart from the encoding part, gates are slowly
added until reaching slightly more than 20 gates, in accordance with the
results shown in Figure 5. In the case of the Cart Pole problem such a small
architecture is capable of solving the benchmark and perform the top scores.

Figure 8: Evolution of an empty VQC with the QNEAT algorithm for the Cart Pole
environment with parameters on Table 3. From top to bottom, each row is a
different generation. Not all of the generations have been shown: of a total
of 50 generations, only the ones where anew gate has been added. In the
others, either no mutation happened or only the weights changed.

##  7 Multiple Objective Optimization

So far we have tested the QNEAT algorithm on the classical machine learning
benchmark problems and we kept track of the number of gates that were added
during the evolution.

In doing so we always relied on the fact that, because of how the QNEAT
algorithm works, new gates are added only if the resulting performance is
better, so only if it is necessary. We never explicitly requested, in any
point of the algorithm, that the number of gates should be minimized.

Obviously, we want the number of gates to be as low as possible, provided that
the agent is performing the top score of whatever the problem is considered.
QNEAT algorithm, as it is, deals with this problem by only letting species
with bigger architectures if they are performing better. Nonetheless, no
penalty is added to deep, complex architectures. In order to enforce the
algorithm to prioritize short architectures, we apply a technique known as
Multi Objective Optimization (MOO).

In particular, here we studied the NSGA-II algorithm [47], an algorithm
proposed to deal with optimization problems when having multiple scores or
fitnesses to take account at the same time.

NSGA-II is a genetic algorithm based on the idea of finding the Pareto fronts
in the space of the fitness functions, and then evolving the members of the
Pareto fronts closer to the highest values of the scores.

The algorithm works as follows: we start with a set of fitnesses
$\\{f_{1},\dots,f_{n}\\}$, which we suppose we want to minimize. This
assumption can always be made true by simply inverting any eventual $f_{i}$
that should be maximized as $1/f_{i}$. Given a population of $N$ members, the
algorithm starts with reproduction and mutation of the original population $P$
to generate the new set of members $Q$. The population will have thus $2N$
members, where half of them are the mutation of the initial ones.

After all of them have been let perform the tasks, we can plot each one as a
point $(f_{1},\dots,f_{n})\in\mathbb{R}^{n}$ in the fitnesses space.

Here the set of points, representing the members, are divided in Pareto
fronts, or nondomination fronts. A member $A$ is said to dominate another
member $B$ if all the fitnesses of $A$ are equal to the fitness of $B$, and at
least one is strictly better. Once the different members have been compared,
they can be divided into fronts, where each front has a rank. Each member of
the front does not dominate and is not dominated by any of the other members;
it dominates all the members of every other front with a lower rank, and is
dominated by the members of higher-rank fronts. In different words, a
domination front is the set of all those members that are roughly at the same
distance with respect to the fitness axis, compared to the other members.

Once the population, now still counting $2N$ members, has been divided into
Pareto fronts, we then order all the members according to the overall
performance and select the first half of them to make the new population. The
way the members are ordered in the end depends on two factors: the rank and
the crowding distance.

  1. 1.

Rank. Once the members are divided into Pareto fronts, each receives a rank,
simply an integer number, corresponding to the Pareto front it belongs to.
Once this has been done, all the members with a higher rank are considered to
be better than those with a lower rank, and starting from these ones the
mutation and crossover processes will take place.

  2. 2.

Crowding distance. Inside a nondomination front, where the rank is the same
for every member, another metric is used to classify the members, the crowding
distance. Given one element $i$, we define its crowding distance as the
distance in the fitnesses space of the nearest members to him in the same
front, averaged on all the fitnesses directions. The memebers who are in an
area of the space that is more crowded are considered to be better.

More exactly, the condition to establish if a member $i$ is better than a
member $j$ is

$\begin{split}i<j\text{ if }(i_{\text{rank}}<j_{\text{rank}})\\\ \text{ or
}((i_{\text{rank}}=j_{\text{rank}})\text{ and
}(i_{\text{distance}}>j_{\text{distance}}))\end{split}$ (9)

According to the condition in equation 9, all the $2N$ members are ordered and
then the first $N$ of them are selected to be part of the next generation.

The algorithm’s main loop is shown in Algorithm 2, while the other algorithms
mentioned inside can be consulted in the original work.

begin

$R_{t}=P_{t}\cup Q_{t}$

$\mathcal{F}=$ fast-non-dominated-sort($R_{t}$)

$P_{t+1}=$

while  _ $|P_{t+1}|+|\mathcal{F}_{i}|\leq N$ _ do

crowding-distance-sort($\mathcal{F}_{i}$)

$P_{t+1}=P_{t+1}\cup\mathcal{F}_{i}$

$i\leftarrow i+1$

end while

Sort ($\mathcal{F}_{i}$)

$P_{t+1}\leftarrow P_{t+1}\cup\mathcal{F}_{i}\left[1:(N-|P_{t_{1}}|)\right]$

$Q_{t+1}=\text{make-new-pop}(P_{t+1})$

end

Algorithm 2 Multi Objective Optimization - NSGA-II

In our case, we merged the QNEAT and MMO algorithms. More specifically, we
kept the species structure of the first algorithms, and, inside each species,
the MMO was applied, looking for the Pareto fronts separately for each
species. This is done to keep the different species evolve independetly, so
that the members inside each species don’t need to compete with members from
other species.

The mutation and crossover to generate new offsprings are instead drawn from
the QNEAT algorithm.

The hyperparameters used to run the algorithm are the same as in Table 3.

We show and compare the results of the QNEAT algorithm with and without the
MOO variation. We evolve a VQC, both with and without MOO, starting from 0, 1
and 2 layers. The results are shown in Figure 9. It can be seen how the
version with MOO performs worse both in terms of average and variance when it
comes to the fitness of the environment. Nonetheless, it can be seen how the
number of gates is actually lower. In the case of $2$ initial layers though,
the difference between the two versions in not that sharp neither in the
fitness nor in the number of gates, even though the QNEAT without any
variation converges faster.

This behavior can be explained by the fact that the MOO algorithm looks for
Pareto fronts in the space of fitnesses, where a front could be constituted of
members that perform well but have a high number of gates, as well as members
that have a small number of gates but perform poorly. Finding a good threshold
to decide which part of the Pareto front to decide is essential to balance
this possible trade-off.

Figure 9: Comparison between QNEAT without the MOO alteration, and with the
MOO. Each row represents an experiment performed with, respectively, 0, 1 and
2 initial layers, starting form the top row. In the first column, the average
score of the top 5 members are shown, while in the right column the total
gates are tracked. It can be seen how, as the number of initial layers
increases, the averages of the top 5 members converge. Nonetheless, the number
of gates is lower.

##  8 Conclusions

In this paper, we explored the Quantum NeuroEvolution of Augmenting Topologies
(QNEAT) algorithm. We defined how we adapted the genome and the process of
crossover and mutation from the classical NEAT in order to be able to evolve
the architectures of Variational Quantum Circuits. We then tested the
algorithm of classical machine learning tasks, such as Reinforcement Learning
and Combinatorial Optimization problems, and kept track during the evolution
of the growth and depth of the architecture. In conclusion, we merged the
QNEAT algorithm with the NSGA-2 algorithm for multi objective optimization.

One topic that should be studied in future works is the difference between the
constrained and free architecture, in order to see how the last one would
perform in terms of generations necessary to evolve a circuit up to the
desired fitness, and also to see if an architecture can be found that will
improve the score. Also, the QNEAT algorithm should be tested on harder and
bigger problems, to see how effective it is on more complex reinforcement
learning environments as well as bigger graphs for the case of the Max Cut
problem.

## References

  * [1] Aram W. Harrow and Ashley Montanaro  “Quantum computational supremacy”  Nature, 2017
  * [2] Isaac L. Michael A.  “Quantum Computation and Quantum Information”  Cambridge, 2010
  * [3] Peter W. Shor  “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”  Siam, 1999
  * [4] Lov K. Grover  “Quantum Mechanics Helps in Searching for a Needle in a Haystack”  American Physical Society, 1997
  * [5] Jacob L. Beckey  “Variational quantum algorithm for estimating the quantum Fisher information”  APS, 2022
  * [6] Bálint Koczor  “Variational-state quantum metrology”  IOP, 2020
  * [7] Carlos Bravo-Prieto  “Variational Quantum Linear Solver”, 2019
  * [8] Hsin-Yuan Huang  “Near-term quantum algorithms for linear systems of equations”, 2019
  * [9] Yudong Cao  “Quantum Chemistry in the Age of Quantum Computing”, 2019
  * [10] Akshay Ajagekar and Fengqi You  “Quantum computing for energy systems optimization: Challenges and opportunities”, 2019
  * [11] Daniel J. Egger  “Quantum Computing for Finance: State-of-the-Art and Future Prospects”, 2020
  * [12] Yangyang Li  “Quantum Optimization and Quantum Learning: A Survey”, 2020
  * [13] Suguru Endo  “Hybrid quantum-classical algorithms and quantum error mitigation”, 2020
  * [14] Jan Benhelm  “Towards fault-tolerant quantum computing with trapped ions”, 2008
  * [15] Samson Wang  “Noise-induced barren plateaus in variational quantum algorithms”, 2021
  * [16] Jacob Biamonte  “Quantum machine learning”, 2017
  * [17] G. Cybenko  “Approximation by superpositions of a sigmoidal function”  Springen, 1989
  * [18] Jarrod R. McClean  “Barren plateaus in quantum neural network training landscapes”, 2018
  * [19] M. Cerezo  “Cost function dependent barren plateaus in shallow parametrized quantum circuits”, 2021
  * [20] Arthur Pesah  “Absence of Barren Plateaus in Quantum Convolutional Neural Networks”, 2021
  * [21] Zoë Holmes  “Barren Plateaus Preclude Learning Scramblers”, 2021
  * [22] Chen Zhao  “Analyzing the barren plateau phenomenon in training quantum neural networks with the ZX-calculus”, 2021
  * [23] Jarrod R. McClean  “Barren plateaus in quantum neural network training landscapes”, 2018
  * [24] Mudita Juneja  “BParticle swarm optimization algorithm and its parameters: A review”, 2016
  * [25] Daan Wierstra  “Natural Evolution Strategies”, 2014
  * [26] Sourabh Katoch  “A review on genetic algorithm: past, present, and future”, 2020
  * [27] Abhinav Anand  “Natural Evolutionary Strategies for Variational Quantum Computation”, 2021
  * [28] Yudong Cao  “Quantum Chemistry in the Age of Quantum Computing”, 2018
  * [29] Rodney J. Bartlett  “Coupled-cluster theory in quantum chemistry”, 2007
  * [30] Edward Farhi  “A Quantum Approximate Optimization Algorithm”, 2014
  * [31] Stuart Hadfield  “From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz”, 2019
  * [32] Abhinav Kandala  “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets”, 2017
  * [33] Harper R. Grimsley  “An adaptive variational algorithm for exact molecular simulations on a quantum computer”, 2019
  * [34] Arthur G. Rattew  “A Domain-agnostic, Noise-resistant, Hardware-efficient Evolutionary Variational Quantum Eigensolver”, 2020
  * [35] Colin P. Williams  “Automated Design of Quantum Circuits”, 1999
  * [36] Prashant  “Evolving Quantum Circuits using Genetic Algorithms”, 2007
  * [37] Martin Lukac  “Evolutionary Approach to Quantum and Reversible Circuits Synthesis”, 2003
  * [38] Shengchao Ding  “Evolving quantum circuits at the gate level with a hybrid quantum-inspired evolutionary algorithm”, 2008
  * [39] Xiaoxiao Wang  “Synthesis of reversible logic circuit using a species conservation method”, 2014
  * [40] Kenneth O. Stanley  “Evolving Neural Networks through Augmenting Topologies”, 2002
  * [41] Nico Meyer  “A Survey on Quantum Reinforcement Learning”, 2022
  * [42] Samuel Yen-Chi Chen  “Variational Quantum Circuits for Deep Reinforcement Learning”, 2020
  * [43] Owen Lockwood  “Reinforcement Learning with Quantum Variational Circuits”, 2020
  * [44] Andrea Skolik  “Quantum agents in the Gym: a variational quantum algorithm for deep Q-learning”, 2022
  * [45] Jules Tillya  “The Variational Quantum Eigensolver: a review of methods and best practices”, 2022
  * [46] Sami Khairy  “Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems”, 2019
  * [47] K. Deb  “A fast and elitist multiobjective genetic algorithm: NSGA-II”, 2002