# Evolving Quantum Circuits

Daniel Tandeitnik<EMAIL_ADDRESS>Department of Physics,
Pontifical Catholic University of Rio de Janeiro, Rio de Janeiro 22451-900,
Brazil  Thiago Guerreiro<EMAIL_ADDRESS>Department of Physics, Pontifical
Catholic University of Rio de Janeiro, Rio de Janeiro 22451-900, Brazil

###### Abstract

We develop genetic algorithms for searching quantum circuits, in particular
stabilizer quantum error correction codes. Quantum codes equivalent to notable
examples such as the 5-qubit perfect code, Shor’s code, and the 7-qubit color
code are evolved out of initially random quantum circuits. We anticipate
evolution as a promising tool in the NISQ era, with applications such as the
search for novel topological ordered states, quantum compiling, and hardware
optimization.

##  I Introduction

Natural selection is a unifying idea in biology [1]. Through evolution and
competition, systems can navigate the complexity landscape [2] from small-
sized molecules and molecule sets [3] to complex molecular machines [4] to
living organisms [5]. Through natural selection, complex designs such as eyes
and brains can come into existence in the universe [6], and artificial
evolution has been employed in the laboratory to produce molecules with
desired optical response properties [7]. In view of that, an interesting
engineering question is whether one can exploit evolution as a design tool for
complex technology where human intuition and the standard deductive method
might encounter difficulties or perhaps even fail.

A natural field in which human intuition often encounters difficulties is
quantum information science. Devising innovative means of producing complex
quantum states and algorithms [8] outside the scope of known quantum
information primitives [9] is a challenging task [10], especially under the
limitations imposed by present-day quantum hardware [11]. This motivates the
main question of this work: Can artificial selection be employed as an
effective tool to design useful quantum circuits?

Computer-assisted searches for new physical phenomena [12] and laws of nature
[13, 14, 15] comprise a very timely research topic, with notable examples
including the search for new quantum optics experiments [16, 17, 18],
resourceful states in quantum metrology [19, 20, 21], ground states in
condensed matter systems [22], the study of nonlocality [23], entanglement and
Bell inequalities [24, 25] and the automated discovery of autonomous quantum
error correction systems [26] . Closely related to these developments, tools
from artificial intelligence, genetic algorithms and competition have also
been employed in chemistry, on the search for new pathways to organic
molecules and closed autocatalytic reaction sets [27], the efficient training
of neural networks for image classification [28] and the evolution of deep
learning algorithms through competition [29]. Here, we propose harvesting some
of these tools and ideas within the context of quantum computing and quantum
algorithms.

Hilbert space is large [30, 31, 32] and – similarly to the vast and complex
landscape of the biosphere – evolution may offer an efficient path to navigate
its complexity. To test this idea, we apply genetic algorithms (GA) to the
search for quantum circuits. As much as these ideas could benefit from a full
scale quantum computer, there are not many such devices readily available for
use at the present time [33, 34, 35, 36]. We therefore focus on stabilizer
circuits [37], which are efficiently simulable on classical computers [38,
39]. The stabilizer formalism is the natural language of quantum error
correction [37], leading us to evolve quantum error correction codes (QECCs)
[40].

Within the framework of stabilizer QECCs, we will demonstrate that evolution,
given the appropriate fitness landscape, can successfully produce known
examples of error correcting codes, notably the Perfect 5-qubit code [41],
Shor’s 9-qubit code [42], the 7-qubit color code [43, 44] and novel examples
of QECCs. These are arguably simple textbook examples but, as we will point
out, the sample space (modulo equivalences) of circuits in which such codes
live is so large that random search becomes prohibitive, thus proving the
principle that evolution efficiently drives the search.

Artificial selection might offer valuable opportunities in the current era of
NISQ devices [45] in which elementary quantum gates are costly and noisy.
Generically, random stabilizer circuits are capable of generating good
codewords for QECCs [46], but evolution can go beyond typicality in guiding
the search for simple, low-depth circuits more amenable to noisy devices.
Device specificity can also be taken into account by devising fitness
landscapes in terms of the complexity geometry metric [47], which penalizes
gates according to hardware characteristics [48].

At present, our artificial selection algorithm can be compared to the
evolution of simple bacteria in controlled laboratory conditions where the
fitness landscape is simple and well understood [49]. With more complex
fitness functions and the addition of quantum hardware we anticipate
improvements and systematic means of devising complex quantum circuits in
various applications beyond stabilizer circuits and QECCs including but not
limited to learning unitaries [50], quantum compiling [51, 52, 53], and
hardware specific tailor-made circuits [48, 33]. We highlight that while
evolution may be complementary to known circuit optimisation schemes [52], its
main strength relies on the possibility of creating novel and creative quantum
circuits. All scripts used in this work are available in the GitHub repository
[54].

This paper is organized as follows. In Section II we introduce the GA applied
to quantum circuits. Section III is dedicated to a simple application of the
GA, demonstrating its capabilities within a well-understood context. Next, we
apply the tools of evolution to the search for QECCs in Section IV. We
conclude with a brief discussion and outlook.

##  II Genetic Algorithm

For about 4.28 billion years [55], millions of living species go through a
continuous optimization process, what Darwin termed the evolution of species
[56]. The evolutionary process occurs through the interaction of populations
of species with their habitat, whose function is to select individuals with a
greater aptitude to grow, thrive, and reproduce. Mathematically, one can
allude to the environment as a fitness function whose domain and codomain are
individuals of a population and a measurement of how well an individual is
adapted to its habitat, respectively. The fitness function then becomes a cost
function of the natural selection optimization problem.

A key point of evolution is its robustness to noise, an often missing feature
in standard optimization methods [57]. The environment is not static: through
natural unpredictable events, it transforms in a chaotic fashion leading to an
ever-changing fitness landscape. Inspired by the evident success of life in
thriving through evolution in dynamic, noisy environments, researchers have
been using algorithms simulating natural selection to solve mathematical
optimization problems as early as 1957 [58, 59, 60, 61, 62, 63, 64], broadly
termed evolutionary algorithms [65].

In this section we make a brief introduction to the biological evolutionary
process emphasizing its genetic point of view. Next, GAs to evolve Clifford
quantum circuits are introduced.

###  II.1 The evolutionary process

Given a population of individuals belonging to the same species, one may
divide its evolution process into four stages [57]: reproduction, mutation,
competition, and selection. In broad terms, reproduction is the transmission
of genetic material from parents to their offspring. Mutations are minute
stochastic errors that occur during the transmission of genes. Competition and
selection drift the population towards individuals better adapted to the
environment, where the fittest individuals reproduce passing along their genes
to future generations, while the unfitted perish removing their genes from the
gene pool. An evolutionary algorithm aims at emulating, to some extent, this
cycle for a population of potential solutions to an optimization problem until
a threshold is reached.

The evolution process hinges on the representation of individuals as their
genetic material, commonly referred to as the genotype, and a screening method
that favors certain genotypes over others. Further, the genotype is a
collection of DNA strands made of elementary building blocks from a finite set
of possibilities, namely the four nucleotides adenine, thymine, guanine, and
cytosine [66]. Considering sexual reproduction, the genotype design naturally
leads to the genetic operations of crossover and mutation. Crossover is a
recombination of the parent’s DNA, where whole segments of DNA are
interpolated to form the offspring’s DNA at conception. Crossover promotes the
dispersion of good DNA blocks among the population, as natural selection
gradually removes bad blocks, and mutation enables the search for new
solutions not reachable through recombination.

Given the genetic operators, we have only an aimless, random walk through the
genotype sample space due to their stochastic nature. Natural selection is
responsible for drifting the walk in the direction of genotypes that beget
fitter individuals. Natural selection results from the interplay between the
environment’s restrictions on the individuals and the phenotype each one
displays. The phenotype is the genetic expression of the genotype, i.e., the
set of physical attributes displayed by the individual [67] — this set
determines the individual’s probability of reproduction.

A helpful way of visualizing the evolutionary optimization process is with a
fitness landscape [68, 69]. The fitness landscape is a mathematical construct
that maps genotypes to reproduction rates. The environment defines a function
in which the domain is the space of all possible genotypes and whose codomain
is the reproduction rate. Distances on the landscape are defined as the
closeness of two genotypes, i.e., how similar are the phenotypes they spawn.
Figure 1 exemplifies a representation of an arbitrary fitness landscape. The
rationale is that, at an initial time, the population genotype set is centered
at some point in the landscape. As the generations go by, the population
stochastically drifts towards the surface peaks due to natural selection and
the genetic operators. Naturally, the fitness landscape in Figure 1 is a
schematic representation, as actually producing such a graph may be impossible
due to the complex nature of the problem at hand.

Figure 1: Illustration of three distinct populations climbing a hypothetical
fitness landscape. At an initial time, each population starts at some low
point of the landscape (colored circles) and stochastically rises towards the
peaks. The mutation rate regulates the size of each step. The height of the
surface represents the reproduction rate of a given genotype.

###  II.2 Genetic algorithms applied to Clifford circuits

We now describe how we mimic nature’s evolutionary process in a GA applied to
Clifford quantum circuits. We note three main aspects we need to cover to
build a GA that simulates nature: (1) a genetic representation of the
tentative solutions, (2) a method to implement the genetic operators of
crossover and mutation, (3) a selection mechanism that distinguishes between
solutions regarding the optimization problem.

To illustrate how we genetically represent quantum circuits in this work,
consider the random circuit depicted in Figure 2(a) and its genetic expression
in Figure 2(b). We genetically represent a circuit composed of $t$ gates as a
$t\times 3$ array whose rows are gates in ascending order of application. The
first column stores the operator, and the second and third the indices of the
affected qubits. If the gate is a $\rm{CNOT}$, the second (third) column is
the control (target) qubit index. For single-qubit gates the third column is
ignored.

Figure 2: A random quantum circuit and its genotype. Each row of the genotype
is a gate in ascending order (from top to bottom) of application, with the
columns storing the operator and the indices of the target qubits. The
$\rm{CNOT}$ is abbreviated as $\rm{C}$.

Crossovers and mutations naturally become row operations by expressing quantum
circuits as a matrix. There is a freedom of choice in defining how each
genetic operator works. The most appropriate option often arises from
experimentation since the efficiency of a GA is strongly dependent on the
optimization problem itself [65]. For instance, the crossover can be performed
at one-point or at multiple points [57, 65, 70]. Additionally, we may use more
than two parents at the reproduction step, thus having more than two genotypes
to crossover [71, 72]. For simplicity, we worked solely with one-point
crossovers between the genotypes of two parents. Hence, given two arbitrary
parents A and B, their genotypes are divided at split points randomly selected
according to a uniform probability distribution. Offspring A(B) is formed by
stacking the top portion of parent A(B) on top of the bottom portion of parent
B(A). Figure 3 shows an example of the crossover operation.

Figure 3: Example of a crossover between two genotypes. The parents’ genotypes
are divided at randomly chosen points and their offspring are built by
stacking the pieces.

Mutations happen to the offspring’s genotype after a crossover procedure. With
equal probabilities, it is chosen whether (a) the mutation modifies an
existing gate or (b) it inserts a new gate into the circuit. Then,

  * •

If (a): a random row of the genotype is uniformly selected to be altered. The
row contents are overwritten by a new gate uniformly selected between
$\\{I,H,P,\rm{CNOT}\\}$. If the identity is picked, the entire row is deleted;

  * •

If (b): a random insertion point on the genotype is uniformly selected. A new
row with a new uniformly selected gate chosen between $\\{H,P,\rm{CNOT}\\}$ is
inserted at the chosen point.

Figure 4 shows an example displaying the three kinds of mutations that can
happen to an offspring genotype.

Figure 4: Illustration of the three types of mutation that may occur to a
circuit. From top to bottom: the first gate is replaced by a Hadamard gate on
qubit 2, a new row in inserted between the second and third rows, and an
identity replaces the fifth gate, hence deleting it.

Just as in nature, we also consider that each genotype gives rise to a
phenotype in GAs. We regard the phenotype of a given circuit as a set of real-
valued numbers that quantify its properties. For instance, we extensively
consider the depth (the length of the longest path from the beginning of a
circuit to its end) as an essential parameter since it is a measure of how
long it takes to execute a circuit. Thus, from a population of circuits, one
can sort the individuals by their depth and use it as a selection bias, e.g.,
considering circuits with lower depth as better suited. Hence, the selection
mechanism for quantum circuits works in the following way:

  1. 1.

The phenotype of each individual is evaluated, where the optimization problem
determines the list of assessed parameters;

  2. 2.

Each individual’s fitness is evaluated via a fitness function $\mathcal{F}$
whose arguments are the phenotypes. By convention, we define $\mathcal{F}$
such that higher fitness individuals are considered better solutions;

  3. 3.

For breeding selection, a probability of reproduction is associated to each
individual proportional to its relative fitness with respect to the rest of
the population. A roulette wheel selection system [57] is employed to pick two
individuals to mate, i.e., to go through the process of crossover/mutation.

The most computationally expensive part of the GA is calculating the
phenotype. Moreover, coming up with a proper set of phenotype parameters might
be challenging. Clear understanding of the optimization problem is hence key
in devising the defining parameters which capture an optimal solution, as well
as methods to calculate these phenotypes.

Finally, after the size of the population reaches an established maximum limit
– recall reproduction adds two new individuals at each iteration – we may
purge the worst circuits. We regard this process as the competition aspect of
the GA since it emulates the limited growth of biological populations and the
death of ill-adapted individuals.

With all the fundamental elements of the GA defined, we build the basic scheme
of the simulated evolutionary cycle. At the start, an initial population of
random circuits is initialized with each individual’s fitness evaluated and
stored. The GA then works via the iteration of a cycle of selective breeding,
crossover, mutation, and population purge until a termination criterion is
met. Termination criteria can be a maximum number of iterations or a target
fitness value. Each cycle marks a generation. Putting it all together, Figure
5 displays the complete decision tree of the GA.

Figure 5: Decision tree for the genetic algorithm. The halt decision gate
evaluates when a termination condition is met.

##  III Toy model

As a first test of the capability of the GA as a searching tool for quantum
circuits we introduce a simple toy problem. A circuit $U$ acts on a 1D lattice
of qubits, which we now label by the indices $x\in\\{1,...,n\\}$, initially in
the state $\ket{\psi_{0}}=\ket{0}^{\otimes n}$. The resulting state after
application of the circuit is $\ket{\psi}=U\ket{\psi_{0}}$. Define the density
matrix $\rho_{x}$ as the state obtained by splitting the chain at $x$ and
tracing out all qubits to the left of $x$ in the final state $\ket{\psi}$. The
von Neumann entropy of $\rho_{x}$ is denoted $S(x)$, and we define the mean
entropy generated by a circuit as

$\langle S\rangle=\dfrac{1}{n}\sum_{x}S(x).$ (1)

Consider then the following problem: find quantum circuits that generate the
largest possible $\langle S\rangle$ with the least possible circuit depth $D$.
We propose the fitness function

$\mathcal{F}=\langle S\rangle/D\ .$ (2)

Circuits that maximize (2) solve the problem. Note that solutions can be found
by deductive reasoning as follows. Subadditivity of the von Neumann entropy
implies that $S(x)$ can change by at most one from one qubit to the next [73],

$|S(x+1)-S(x)|\leq 1.$ (3)

The maximum mean entropy of a circuit is therefore given by

$\langle
S\rangle_{\mathrm{max}}=\dfrac{1}{n}\left(\sum_{M=1}^{n/2}M+\sum_{M=1}^{n/2-1}M\right)=\dfrac{n}{4}.$
(4)

The minimum value of depth for a circuit generating non-vanishing entropy is
$D_{\mathrm{min}}=2$. Hence, the highest possible value for $\mathcal{F}$ is
$\mathcal{F}_{\mathrm{max}}=n/8$. There are multiple solutions that maximize
$\mathcal{F}$, one example of which is shown in Figure 6 for $n=6$ qubits.
Note that the circuit produces a tensor product of Bell pairs organized in a
specific way within the 1D lattice.

Figure 6: A $6$-qubit circuit solving the toy problem. Permutations of the
$\rm{CNOT}$s along the time direction, as well as of the target qubits yields
the same solution.

To determine whether a GA provides advantage in the search for the solution,
we compare its performance to a purely random search (RS). The decision tree
used for RS is shown in Figure 7. Since the bottleneck of both algorithms is
the fitness evaluation, their time performance per iteration is nearly
identical, i.e., a generation for each method takes almost the same time to
execute. Hence, we chose to compare the methods by how fast each can converge
to a solution within a given number of generations.

Figure 7: Decision tree for the RS. The algorithm generates random circuits
and saves the best circuit ever generated until a termination condition –
maximum number of generations or maximum fitness value – is reached.

The total number of solutions to the problem is very small in comparison to
all possible $n$-qubit circuits composed of $t$ gates. We expect further that
the ratio of solutions to possible circuits decreases significantly with the
number of qubits $n$. If the GA is to have an advantage over RS, we should
expect this edge to grow as we increase $n$. Figure 8 shows the fitness values
of the best circuit in the population as a function of generation number for
three cases with increasing number of qubits given by $n=4,8$ and $16$. We
note that each curve is the average over $100$ runs, and that over all runs
the optimal circuits are generated many times by the GA. For $n=4$ we can see
that RS is able to find solutions. Nevertheless, the GA has an increasing
advantage over RS as we increase the number of qubits, as expected. This can
be seen by the widening gap between the GA and RS traces in Figures 8(a), (b)
and (c). The red dashed lines show the maximum attainable fitness values, for
reference.

Figure 8: Evolutionary search using a genetic algorithm (green line) versus
random search (blue line) for $n=4,8,16$ qubits in the search for a circuit
maximizing Eq. (2). Each curve is the average over $100$ runs. The dashed red
line represents the maximum fitness given by $n/8$; see Eq. (4) and the main
text. Figure 9: Evolution of the topology of the fittest circuit in an
evolutionary search simulation for $n=8$ qubits. The edges represent the
qubits indexed by lattice position, and the vertices correspond to CNOT gates.

We can visualize the topology of a quantum circuit as a graph, where each node
corresponds to a qubit and vertices represent qubit interactions, implemented
here as $\rm{CNOT}$ gates. This graph representation highlights the necessary
hardware architecture a quantum computer needs to have to execute the circuit,
i.e. which qubits need to be coupled. Figure 9 shows the typical example of an
initial randomly generated circuit topology, and its subsequent evolution
towards the topology of the optimal solution, as depicted in Figure 6
corresponding to Bell pairings of the qubits. We see that starting from
complicated random circuits artificial selection can perform a directed search
towards high fitness individuals in a much shorter time than RS.

##  IV Evolutionary search for QECCs

Given the appropriate fitness function, can a GA evolve quantum error
correction codes such as the 5-qubit perfect code [41], the 7-qubit color code
[43, 44], and Shor’s 9-qubit code [42]? These are examples of stabilizer
codes, meaning they are generated by Clifford gates. As in the toy example,
efficient simulation in classical computers is therefore granted by the
Gottesman-Kill theorem [37].

Defining the appropriate fitness function that will efficiently direct the
search for the desired QECCs is crucial, and not a straightforward task. The
crux of the matter involves defining a phenotype set that captures the
expected features of a good error correction code. For the toy example in the
previous section, the definition of the problem itself contained the relevant
phenotype leading to the form of the fitness function. Backed by the content
developed in Appendix A, we now present metrics capable of measuring the
effectiveness of a circuit in correcting quantum errors and a method for
evaluating such metrics.

###  IV.1 QECC fitness function

One can represent a given QECC by a set of two or more mutually orthogonal
codewords $\\{\ket{c_{i}}\\}$. The codewords define a group of syndrome
operators $\\{S_{i}\\}$ employed to detect and correct errors up to weight $t$
following the scheme shown in Figure 16 of Appendix A. With the syndrome
operators and a subset of errors $\mathcal{E}$ we require our code to detect
and correct, one builds the syndrome table. The table can then be used to
decide if the set of codewords forms a functional QECC by checking if there
are undetectable and uncorrectable errors. We reiterate how undetectable and
uncorrectable errors are classifieds:

  * •

Syndromes represented by bit strings of $0$-s correspond to undetectable
errors. Thus, given the syndrome table, the number of undetectable errors is
obtained by counting how many errors return $0$-stringed syndromes;

  * •

If more than one error is associated with distinctive syndromes, all 2-on-2
combinations are cross-checked with the shared stabilizers of all codewords.
If one combination fails, we classify the errors associated to the syndrome as
uncorrectable.

Let $e_{\mathrm{und}}$ and $e_{\mathrm{unc}}$ be the number of undetectable
and uncorrectable errors associated to a set of codewords, respectively. Then,
define the corrigibility degree $\mathcal{C}$ as

$\mathcal{C}\equiv(|\mathcal{E}|-e_{\mathrm{und}}-e_{\mathrm{unc}})/|\mathcal{E}|$
(5)

We use the corrigibility degree as our main phenotype to evolve QECCs, however
its evaluation assumes the possession of a tentative set of codewords. To
employ the GA, we must relate codewords to Clifford circuits, as we now
explain. Consider Shor’s code as an illustrative example. The code can be
represented by its codewords or by an encoding circuit (EC) as depicted in
Figure 10(a). Note, however, the EC in itself is insufficient to determine the
codewords; one must determine which initial states are acted upon by the EC.
For the particular circuit portrayed in Figure 10(a), the $\ket{\psi}$ ket in
the first register implicitly informs that the initial states are taken to be
$\\{\ket{00\dots 0}$ or $\ket{10\dots 0}\\}$. Furthermore, different circuits
may generate equivalent codewords for Shor’s code in the sense that both sets
of codewords form a $[[9,1,3]]$ QECC. For example, consider the circuit shown
in Figure 10(b): if it acts on the initial states $\\{\ket{0\dots
000},\ket{0\dots 010}\\}$ it effectively generates equivalent codewords.

The main takeaway is that if we are going to evolve ECs, we need an algorithm
capable of producing different sets of tentative codewords from various
combinations of initial states. For instance, if the GA evolved the circuit
from Figure 10(b) and only tried to use $\\{\ket{00\dots 0},\ket{10\dots
0}\\}$ as the initial states to form the codewords, it would erroneously
conclude that the circuit does not constitute a good QECC.

Figure 10: Standard Shor’s $[[9,1,3]]$ EC and an example of an equivalent
circuit.

In Appendix B, we describe the procedure to evaluate different sets of
tentative codewords given a Clifford circuit regarded as an EC for a QECC.
Given this procedure, we are ready to introduce the fitness function.

Consider a tentative EC with circuit depth $D$. Let $V_{\perp}$ be the set of
all codewords $\\{\ket{c_{0}},\ket{c_{i}}\\}$ with associated corrigibility
degree $\mathcal{C}_{i}$. The fitness associated to the EC is then given by

$\mathcal{F}=\max_{V_{\perp}}\ F$ (6)

where

$F=w\times\mathcal{C}_{i}-D.$ (7)

where $w$ is a predefined weight.

Given a specific problem, there is generally no unique definition for the
fitness function. Specifically in the search for QECCs, the form (7) is the
result of intuitive reasoning and empirical tinkering. For instance, we tested
and excluded functional forms containing terms proportional to $\mathcal{C}/D$
as we observed these to enforce a tendency of evolving low depths in detriment
of corrigibility $\mathcal{C}$, while we imperatively wish the highest
possible value for $\mathcal{C}$. A simple solution is to give greater weight
to phenotypes that maximize $\mathcal{C}$, implemented by multiplying it by a
factor of $w$. We find $w=1000$ to yield satisfactory results.

###  IV.2 Results

We have applied the GA to the problem of searching QECCs capable of correcting
up to single-qubit errors using the fitness function as defined in Eqs. (6)
and (7). We tested the GA performance against RS for a range of qubit
overheads, from $n=5$ to $n=11$. Figure 11 displays the results. In all seven
cases, the GA showed a clear advantage over RS by being able to evolve
functional, low-depth QECCs in just a few hundred generations. Indeed, the GA
was capable of finding multiple examples of circuits equivalent – in terms of
distance – to the perfect 5-qubit and Shor’s 9-qubit code starting from random
circuits and with no built-in specific insights referring to the quantum
codes.

Figure 11: Evolutionary search using the genetic algorithm (green line) versus
random search (blue line) for QECCs with $n=5,6,7,8,9,10,11$ qubits. Each
curve is the average over $100$ runs of the population’s best fitness. The
fitness values are normalized.

An unanticipated result was that finding QECCs either by GA or RS seems to
become easier as the number of physical qubits increases, up until $n=8$.
Recall that the number of pure stabilizer states scales as $O(2^{n^{2}})$
[38]. We therefore expected it would be easier to find codes with fewer
physical qubits, while plots in Figure 11 show the opposite behavior from
$n=5$ to $8$. We conjecture that the number of possible QECCs rapidly grows
with $n$, making it easier to find codes for $n$ between $5$ to $8$. For
instance, inequality (22), demonstrated in Appendix C, indicates that the
number of single-qubit errors grows linearly. In contrast, the number of
potential syndrome codes grows exponentially with $n$, thus allowing a wider
range of codes to exist. Moreover, the issue of equivalent ECs enlarges the
number of solutions in the sample space. Figure 12 illustrates this point
where any register permutation creates a new equivalent circuit. Therefore,
the freedom to exchange registers makes a single solution appear $n!$ times.
Given these considerations, it is conceivable that for $n$ equals 5 to 8, the
number of solutions grows faster than the sample space of solutions.

Figure 12: Generation of an equivalent EC for Shor’s code by permutation of
two qubit registers. Any permutation of the register produces equivalent ECs.

Nevertheless, while RS indeed found solutions within the given limit of
$2,000$ generations, it rarely found low depth examples. In contrast, the GA
consistently evolved QECCs with depth lower than $6$, as shown in Table 1.
Even though it appears from the graphs in Figure 11 that RS becomes more
efficient as $n$ increases, the data in Table 1 suggests otherwise. The GA had
a success rate above $70\%$ in all cases in finding QECCs with $D\leq 6$. On
the other hand, RS varied between $4\%$ and $52\%$ success rates showing an
abrupt downward trend starting from $n=9$. Finally, the GA was able to evolve
circuits with depth as low as $4$, while RS was not capable. We expect that
for larger values of $n$, RS becomes increasingly inefficient. Furthermore,
the difference in the speed at which each method converges to a solution is
substantial. Note the speed of convergence becomes increasingly important for
large $n$ since computational costs scales accordingly.

Table 1:  Percentage of solutions found by the GA and RS with depth less than or equal to 6, 5 and 4 within the maximum limit of 2,000 generations for qubit overhead $n$. | GA | RS
---|---|---
$n$ | $D\leq 6$ | $D\leq 5$ | $D\leq 4$ | $D\leq 6$ | $D\leq 5$ | $D\leq 4$
5 | $81\%$ | $48\%$ | $19\%$ | $12\%$ | $2\%$ | $0\%$
6 | $70\%$ | $27\%$ | $6\%$ | $15\%$ | $2\%$ | $0\%$
7 | $93\%$ | $82\%$ | $56\%$ | $52\%$ | $9\%$ | $0\%$
8 | $92\%$ | $72\%$ | $33\%$ | $46\%$ | $5\%$ | $0\%$
9 | $90\%$ | $70\%$ | $32\%$ | $38\%$ | $2\%$ | $0\%$
10 | $82\%$ | $58\%$ | $14\%$ | $4\%$ | $0\%$ | $0\%$
11 | $72\%$ | $44\%$ | $12\%$ | $9\%$ | $0\%$ | $0\%$

To further demonstrate the applicability of GAs in finding specific codes, we
modified the fitness landscape to specialize in the search for color codes
[44]. Color codes are a particular class of error correction codes contained
in the broader family of topological QECCs [44, 74]. An important feature of
topological codes is their modularity, i.e., the main code is assembled by
patching elementary repeated pieces. Modularity enables the scalability of
code circuits with each module requiring only nearest-neighbor interactions,
relieving a major hardware constraint. These, including other reasons, place
topological codes among the leading prospects for actual hardware
implementation [75, 76, 77].

We set out to evolve color codes in two-dimensional (2D) lattice
configurations with nearest-neighbor qubit interactions. As we will see, a
simple modification of the previous fitness function suffices to guide
evolution. As a defining phenotype, we note 2D color codes are members of the
CSS class [78, 43]. This means that, given a set of codewords, if their common
stabilizer set can be generated by stabilizers constructed only from $X$s or
$Z$s independently – that is, each generator is made only by $X$s or $Z$s –
then the code is of the CSS type [79, 80, 44]. We can then build a metric
quantifying how close to this requirement a code is, similarly to the
corrigibility degree introduced previously.

Given a set of codewords, we measure its CSS degree ‘$\mathcal{CSS}$’ by
constructing a generator set, for their joint stabilizers, with the maximum
number of operators made only by $X$s or $Z$s possible. We define
$\mathcal{CSS}_{i}$ of a tentative pair of codewords $i$ as the ratio of
operators that satisfies the CSS criterion by the total number of elements in
the generator set. Hence, to drive the GA towards two-dimensional color codes,
we modify Eq. (7) according to

$F=w\times\mathcal{C}_{i}+w^{\prime}\times\mathcal{CSS}_{i}-D.$ (8)

Again, the weight $w^{\prime}$ is used to enforce codes that satisfy the CSS
criterion. We use $w^{\prime}=1000$.

The simplest 2D color code is the triangular $7$-qubit code [44] with topology
as illustrated in Figure 13 [81]. While searching for color codes using the
GA, we have used the 7-qubit code as a benchmark. Figure 14 shows the
performance of the GA versus RS. The fitness values are normalized by a
target-fitness for a color code circuit taken from [36]. Noting the greater
difficulty in evolving color codes, we have increased the generation limit to
$10,000$. Despite the appearance that RS performs comparably well, in reality
the GA had a success rate of $54\%$ while RS never found any color code.

Figure 13: Lattice arrangement of the $7$-qubit color code. Figure 14:
Evolutionary search using a genetic algorithm versus random search for the
$7$-qubit color code. Each curve is the average over $100$ runs of the
population’s best fitness. The fitness values are normalized according to the
standard fitness of the circuit from [36] .

As a final remark we highlight that calculating phenotypes can be a difficult
task. For instance, it is generally expected that computing the code distance
is exponentially hard in the number of physical qubits $N$ [82]. This
difficulty can be overcome, for example, by noting that the error-correcting
capacity of a code is related to the entanglement structure between regions in
the code lattice quantified by the mutual information between the region and
its complement [46]. Computing the mutual information of partitions of a
stabilizer state is polynomial in $N$ [38], and thus a suitable fitness
function for large numbers of qubits may be devised based on this method. This
reinforces that despite evolution being blind, its proper application relies
on mathematical knowledge and creativity in the fitness definition, especially
in the limit of large systems.

##  V Conclusion

In conclusion, we have employed genetic algorithms to the search for quantum
error correction codes starting from an initially random population of quantum
circuits. Through the introduction of suitable fitness functions, the genetic
algorithm was capable of repeatedly outperforming random search and evolving
examples of QECCs equivalent to Shor’s $9$-qubit code, as well as the
$5$-qubit perfect code. We have also employed the genetic algorithm in the
search for topological codes, notably the 2D 7-qubit code, successfully
demonstrating that the genetic method can be used in the targeted search for
quantum circuits with specific properties, notably the evolution of
topological order.

We anticipate at least three directions of future research in which ideas
closely related to the ones introduced here might lead to interesting
developments within the broader field of quantum information and computing.

First, evolution might offer valuable means to search for novel topological
codes. It might be possible to encode topological features of quantum states
into an appropriate fitness function thus enabling the automated search for
new topologically ordered states characterized by distinct values of the
topological entanglement entropy [83, 84].

Second, quantum algorithm compilation [85] is a challenging problem that will
become increasingly important as noisy intermediate-scale quantum (NISQ)
computers emerge [45, 86]. Hence, the development of quantum compiling methods
is an active field [86, 87, 88, 89, 90, 91, 92, 93, 94]. In principle, GAs
could provide a promising tool for the automation of quantum compiling and
depth reduction.

Figure 15: IBM quantum lattices, adapted from [95]: (a) $20$-qubits systems
Johannesburg and Poughkeepsie; (b) $20$-qubits systems Almaden, Boeblingen,
and Singapor; (c) $5$-qubits systems Ourense, Valencia, and Vigo; (d)
$14$-qubits system Melbourne; (e) $5$-qubits system Yorktown; (f) $53$-qubits
system Rochester. GAs can be used to devise tailor circuits for each specific
hardware topology.

Third, one may translate quantum hardware specifications into metrics
incorporated in the fitness function to produce tailor-made algorithms. As an
illustration, Figure 15 shows the available lattices of the quantum system
devices IBM offers on their Quantum service [95]. Note that each device
geometry imposes interaction restrictions on two-qubit gates. Given a device
with a particular lattice, we could incorporate penalty factors for circuits
that disobey the topology restrictions of the quantum device under
consideration. Additionally, some gates may be harder to implement due to
details of the experimental implementation. Brown and Susskind [48] introduce
the concept of unitary complexity, quantifying the difficulty in implementing
a given unitary provided physical properties and constraints of the setup. The
unitary complexity can also be used as a penalty factor in the fitness
function, driving the search for simple circuits for a given hardware
implementation.

Finally, we conclude by highlighting how remarkable it is that an unsupervised
genetic algorithm with a few hundred lines of code can evolve in minutes
celebrated results that required the insightful minds of Ray Laflamme, Peter
Shor and Robert Calderbank to come about. As quantum computers improve in
number of qubits and more complex topologies, genetic algorithms may yet prove
to be an invaluable optimization method in the quantum computing engineer’s
toolbox.

## Acknowledgements

We thank Bruno Suassuna, Igor Brandão, Lucianno Defaveri, George Svetlichny,
Stuart Kauffman, Ernesto Galvão and Guilherme Temporão for useful discussions.
This study was financed in part by Conselho Nacional de Desenvolvimento
Científico e Tecnológico (CNPq), and by the Fundação de Amparo à Pesquisa do
Estado do Rio de Janeiro (FAPERJ). This study was financed in part by the
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) -
Finance Code 001. We would like to thank the support received by CNPq
Scholarship No. 132606/2020-8, FAPERJ Scholarship No. 2021.01394.9, and CNPq
Scholarship No. 140197/2022-2.

## References

  * Bialek [2012] W. Bialek,  _Biophysics: Searching for Principles_ (Princeton University Press, 2012).
  * Kauffman [2019] S. A. Kauffman,  _World Beyond Physics: The Emergence and Evolution of Life_ (Oxford University Press, USA, 2019).
  * et al. [2020a] J. C. X. et al., Autocatalytic chemical networks at theorigin of metabolism, Proc. R. Soc. B 287, 20192377. (2020a).
  * et al. [2017] B. L. et al., An introduction to ratchets in chemistry and biology, Materials Horizons (2017).
  * Alberts  _et al._ [2015] B. Alberts, D. Bray, K. Hopkin, A. D. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter,  _Essential cell biology_ (Garland Science, 2015).
  * Kauffman and Roli [2021] S. Kauffman and A. Roli, The world is not a theorem, Entropy 23, 10.3390/e23111467 (2021).
  * et al. [2018] K. D. P. et al., A robotic multidimensional directed evolution approach applied to fluorescent voltage reporters, Nat Chem Biol. 14, 352 (2018).
  * Shor [2003] P. W. Shor, Why haven’t more quantum algorithms been found?, Journal of the ACM 50, 87 (2003).
  * Martyn  _et al._ [2021] J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand unification of quantum algorithms, PRX Quantum 2, 040203 (2021).
  * Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang,  _Quantum computation and quantum information_ (American Association of Physics Teachers, 2002).
  * Bravyi  _et al._ [2018] S. Bravyi, D. Gosset, and R. König, Quantum advantage with shallow circuits, Science 362, 308 (2018).
  * Iten  _et al._ [2020] R. Iten, T. Metger, H. Wilming, L. del Rio, and R. Renner, Discovering physical concepts with neural networks, Phys. Rev. Lett. 124, 010508 (2020).
  * et al. [2020b] M. C. et al., Discovering symbolic models from deep learning with inductive biases, arXiv:2006.11287 (2020b).
  * et al. [2020c] M. C. et al., Lagrangian neural networks, arXiv:2003.04630 (2020c).
  * Jared O’Leary [2021] A. M. Jared O’Leary, Joel A. Paulson, Stochastic physics-informed neural networks (spinn): A moment-matching framework for learning hidden physics within stochastic differential equations, arXiv:2109.01621 (2021).
  * Krenn  _et al._ [2016] M. Krenn, M. Malik, R. Fickler, R. Lapkiewicz, and A. Zeilinger, Automated search for new quantum experiments, Phys. Rev. Lett. 116, 090405 (2016).
  * et al. [2019a] J. M. A. et al., Machine learning method for state preparation and gate synthesis on photonic quantum computers, Quantum Science and Technology 4, 024004 (2019a).
  * Mario Krenn [2020] A. Z. Mario Krenn, Manuel Erhard, Computer-inspired quantum experiments, Nature Reviews Physics 2, 649 (2020).
  * Knott [2016] P. A. Knott, A search algorithm for quantum state engineering and metrology, New Journal of Physics 18, 073033 (2016).
  * et al. [2019b] R. N. et al., Designing quantum experiments with a genetic algorithm, Quantum Sci. Technol. 4, 045012 (2019b).
  * Rambhatla  _et al._ [2020] K. Rambhatla, S. E. D’Aurelio, M. Valeri, E. Polino, N. Spagnolo, and F. Sciarrino, Adaptive phase estimation through a genetic algorithm, Phys. Rev. Research 2, 033078 (2020).
  * Carleo and Troyer [2017] G. Carleo and M. Troyer, Solving the quantum many-body problem with artificial neural networks, Science 355 (2017).
  * Gao  _et al._ [2018] J. Gao, L.-F. Qiao, Z.-Q. Jiao, Y.-C. Ma, C.-Q. Hu, R.-J. Ren, A.-L. Yang, H. Tang, M.-H. Yung, and X.-M. Jin, Experimental machine learning of quantum states, Phys. Rev. Lett. 120, 240501 (2018).
  * Canabarro  _et al._ [2019] A. Canabarro, S. Brito, and R. Chaves, Machine learning nonlocal correlations, Phys. Rev. Lett. 122, 200401 (2019).
  * Kriváchy  _et al._ [2020] T. Kriváchy, Y. Cai, D. Cavalcanti, A. Tavakoli, N. Gisin, and N. Brunner, A neural network oracle for quantum nonlocality problems in networks, npj Quantum Information 6, 1 (2020).
  * Wang  _et al._ [2022] Z. Wang, T. Rajabzadeh, N. Lee, and A. H. Safavi-Naeini, Automated discovery of autonomous quantum error correction schemes, PRX Quantum 3, 020302 (2022).
  * et al. [2020d] A. W. et al., Synthetic connectivity, emergence, and self-regeneration in the network of prebiotic chemistry, Science 369, 1584 (2020d).
  * Real  _et al._ [2019] E. Real, A. Aggarwal, Y. Huang, and Q. V. Le, Regularized evolution for image classifier architecture search, in  _Proceedings of the aaai conference on artificial intelligence_ , Vol. 33 (2019) pp. 4780–4789.
  * Olsson  _et al._ [2018] C. Olsson, S. Bhupatiraju, T. Brown, A. Odena, and I. Goodfellow, Skill rating for generative models, arXiv preprint arXiv:1808.04888 (2018).
  * Poulin  _et al._ [2011] D. Poulin, A. Qarry, R. Somma, and F. Verstraete, Quantum simulation of time-dependent hamiltonians and the convenient illusion of hilbert space, Phys. Rev. Lett. 106, 170501 (2011).
  * Susskind [2018] L. Susskind, Three lectures on complexity and black holes, arXiv:1810.11563 (2018).
  * Brandão  _et al._ [2021] F. G. Brandão, W. Chemissany, N. Hunter-Jones, R. Kueng, and J. Preskill, Models of quantum complexity growth, PRX Quantum 2, 030316 (2021).
  * et al. [2019c] F. A. et al., Quantum supremacy using a programmable superconducting processor, Nature 574, pages505 (2019c).
  * Wu  _et al._ [2021] Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, H.-L. Huang, Y.-H. Huo, L. Li, N. Li, S. Li, Y. Li, F. Liang, C. Lin, J. Lin, H. Qian, D. Qiao, H. Rong, H. Su, L. Sun, L. Wang, S. Wang, D. Wu, Y. Xu, K. Yan, W. Yang, Y. Yang, Y. Ye, J. Yin, C. Ying, J. Yu, C. Zha, C. Zhang, H. Zhang, K. Zhang, Y. Zhang, H. Zhao, Y. Zhao, L. Zhou, Q. Zhu, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.-W. Pan, Strong quantum computational advantage using a superconducting quantum processor, Phys. Rev. Lett. 127, 180501 (2021).
  * Jerry Chow [2021] J. G. Jerry Chow, Oliver Dial,  _IBM Quantum breaks the 100 qubit barrier_ , Tech. Rep. (IBM, https://research.ibm.com/blog/127-qubit-quantum-processor-eagle, 2021).
  * et al. [2021] L. P. et al., Demonstration of fault-tolerant universal quantum gate operations, arXiv:2111.12654 (2021).
  * Gottesman [1997] D. Gottesman,  _Stabilizer codes and quantum error correction_ , Ph.D. thesis, California Institute of Technology (1997).
  * Aaronson and Gottesman [2004] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A 70, 052328 (2004).
  * Gidney [2021] C. Gidney, Stim: a fast stabilizer circuit simulator, Quantum 5, 497 (2021).
  * Roffe [2019a] J. Roffe, Quantum error correction: An introductory guide, Contemporary Physics (2019a).
  * Laflamme  _et al._ [1996] R. Laflamme, C. Miquel, J. P. Paz, and W. H. Zurek, Perfect quantum error correcting code, Physical Review Letters 77, 198 (1996).
  * Shor [1995] P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical review A 52, 10.1103/PhysRevA.52.R2493 (1995).
  * Calderbank  _et al._ [1997] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. Sloane, Quantum error correction and orthogonal geometry, Physical Review Letters 78, 405 (1997).
  * Kubica [2018] A. M. Kubica,  _The ABCs of the color code: A study of topological quantum codes as toy models for fault-tolerant quantum computation and quantum phases of matter_ , Ph.D. thesis, California Institute of Technology (2018).
  * Preskill [2018] J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2, 79 (2018).
  * Li and Fisher [2021] Y. Li and M. P. Fisher, Statistical mechanics of quantum error correcting codes, Physical Review B 103, 104306 (2021).
  * Nielsen [2005] M. A. Nielsen, A geometric approach to quantum circuit lower bounds, arXiv preprint quant-ph/0502070 (2005).
  * Brown and Susskind [2019] A. R. Brown and L. Susskind, Complexity geometry of a single qubit, Physical Review D 100, 046020 (2019).
  * Dekel and Alon [2005] E. Dekel and U. Alon, Optimality and evolutionary tuning of the expression level of a protein, Nature 436, 588 (2005).
  * Kiani  _et al._ [2020] B. T. Kiani, S. Lloyd, and R. Maity, Learning unitaries by gradient descent, arXiv preprint arXiv:2001.11897 (2020).
  * Heyfron and Campbell [2018a] L. E. Heyfron and E. T. Campbell, An efficient quantum compiler that reduces t count, Quantum Science and Technology 4, 015004 (2018a).
  * Nam  _et al._ [2018] Y. Nam, N. J. Ross, Y. Su, A. M. Childs, and D. Maslov, Automated optimization of large quantum circuits with continuous parameters, npj Quantum Information 4, 1 (2018).
  * Jones and Benjamin [2022] T. Jones and S. C. Benjamin, Robust quantum compilation and circuit optimisation via energy minimisation, Quantum 6, 628 (2022).
  * Tandeitnik [2022] D. Tandeitnik, Evolving quantum circuits, https://github.com/tandeitnik/Evolving_Quantum_Circuits (2022).
  * Dodd  _et al._ [2017] M. S. Dodd, D. Papineau, T. Grenne, J. F. Slack, M. Rittner, F. Pirajno, J. O’Neil, and C. T. Little, Evidence for early life in earth’s oldest hydrothermal vent precipitates, Nature 543, 60 (2017).
  * Darwin [2004] C. Darwin,  _On the origin of species, 1859_ (Routledge, 2004).
  * Fogel [1994] D. B. Fogel, An introduction to simulated evolutionary optimization, IEEE transactions on neural networks 5, 3 (1994).
  * Fraser [1957] A. S. Fraser, Simulation of genetic systems by automatic digital computers i. introduction, Australian journal of biological sciences 10, 484 (1957).
  * Barker [1958] J. Barker, Simulation of genetic systems by automatic digital computers, Australian Journal of Biological Sciences 11, 603 (1958).
  * Bremermann  _et al._ [1962] H. J. Bremermann _et al._ , Optimization through evolution and recombination, Self-organizing systems 93, 106 (1962).
  * Bremermann [1968] H. J. Bremermann, Numerical optimization procedures derived from biological evolution processes, Cybernetic problems in bionics , 597 (1968).
  * Bremermann and Rogson [1964] H. J. Bremermann and M. Rogson,  _AN EVOLUTION-TYPE SEARCH METHOD FOR CONVEX SETS._ , Tech. Rep. (CALIFORNIA UNIV BERKELEY, 1964).
  * Reed  _et al._ [1967] J. Reed, R. Toombs, and N. A. Barricelli, Simulation of biological evolution and machine learning: I. selection of self-reproducing numeric patterns by data processing machines, effects of hereditary control, mutation type and crossing, Journal of theoretical biology 17, 319 (1967).
  * Sampson [1976] J. R. Sampson, Adaptation in natural and artificial systems (john h. holland) (1976).
  * Bartz-Beielstein  _et al._ [2014] T. Bartz-Beielstein, J. Branke, J. Mehnen, and O. Mersmann, Evolutionary algorithms, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 4, 178 (2014).
  * Roth [2019] S. C. Roth, What is genomic medicine?, Journal of the Medical Library Association: JMLA 107, 442 (2019).
  * Pierce [2012] B. A. Pierce,  _Genetics: a conceptual approach_ (Macmillan, 2012).
  * Gavrilets [2004] S. Gavrilets,  _Fitness landscapes and the origin of species (MPB-41)_ (Princeton University Press, 2004).
  * Kauffman and Levin [1987] S. Kauffman and S. Levin, Towards a general theory of adaptive walks on rugged landscapes, Journal of theoretical Biology 128, 11 (1987).
  * Holland [1992] J. H. Holland,  _Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence_ (MIT press, 1992).
  * Eiben  _et al._ [1994] A. E. Eiben, P.-E. Raue, and Z. Ruttkay, Genetic algorithms with multi-parent recombination, in  _International conference on parallel problem solving from nature_ (Springer, 1994) pp. 78–87.
  * Ting [2005] C.-K. Ting, On the mean convergence time of multi-parent genetic algorithms without selection, in  _European Conference on Artificial Life_ (Springer, 2005) pp. 403–412.
  * Nahum  _et al._ [2017] A. Nahum, J. Ruhman, S. Vijay, and J. Haah, Quantum entanglement growth under random unitary dynamics, Phys. Rev. X 7, 031016 (2017).
  * Kitaev [2003] A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics 303, 2 (2003).
  * Nickerson  _et al._ [2014] N. H. Nickerson, J. F. Fitzsimons, and S. C. Benjamin, Freely scalable quantum technologies using cells of 5-to-50 qubits with very lossy and noisy photonic links, Physical Review X 4, 041041 (2014).
  * Sete  _et al._ [2016] E. A. Sete, W. J. Zeng, and C. T. Rigetti, A functional architecture for scalable quantum computing, in  _2016 IEEE International Conference on Rebooting Computing (ICRC)_ (IEEE, 2016) pp. 1–6.
  * O’Gorman  _et al._ [2016] J. O’Gorman, N. H. Nickerson, P. Ross, J. J. Morton, and S. C. Benjamin, A silicon-based surface code quantum computer, npj Quantum Information 2, 1 (2016).
  * Gottesman [1996] D. Gottesman, Class of quantum error-correcting codes saturating the quantum hamming bound, Physical Review A 54, 1862 (1996).
  * Calderbank and Shor [1996] A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Physical Review A 54, 1098 (1996).
  * Steane [1996] A. Steane, Multiple-particle interference and quantum error correction, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551 (1996).
  * Bermudez  _et al._ [2017] A. Bermudez, X. Xu, R. Nigmatullin, J. O’Gorman, V. Negnevitsky, P. Schindler, T. Monz, U. Poschinger, C. Hempel, J. Home, _et al._ , Assessing the progress of trapped-ion processors towards fault-tolerant quantum computation, Physical Review X 7, 041061 (2017).
  * Gullans and Huse [2020] M. J. Gullans and D. A. Huse, Dynamical purification phase transition induced by quantum measurements, Physical Review X 10, 041020 (2020).
  * Kitaev and Preskill [2006] A. Kitaev and J. Preskill, Topological entanglement entropy, Physical review letters 96, 110404 (2006).
  * Levin and Wen [2006] M. Levin and X.-G. Wen, Detecting topological order in a ground state wave function, Physical review letters 96, 110405 (2006).
  * Harrow [2001] A. Harrow,  _Quantum compiling_ , Ph.D. thesis, Citeseer (2001).
  * Khatri  _et al._ [2019] S. Khatri, R. LaRose, A. Poremba, L. Cincio, A. T. Sornborger, and P. J. Coles, Quantum-assisted quantum compiling, Quantum 3, 140 (2019).
  * Venturelli  _et al._ [2018] D. Venturelli, M. Do, E. Rieffel, and J. Frank, Compiling quantum circuits to realistic hardware architectures using temporal planners, Quantum Science and Technology 3, 025004 (2018).
  * Booth  _et al._ [2018] K. E. Booth, M. Do, J. C. Beck, E. Rieffel, D. Venturelli, and J. Frank, Comparing and integrating constraint programming and temporal planning for quantum circuit compilation, in  _Twenty-Eighth international conference on automated planning and scheduling_ (2018).
  * Cincio  _et al._ [2018] L. Cincio, Y. Subaşı, A. T. Sornborger, and P. J. Coles, Learning the quantum algorithm for state overlap, New Journal of Physics 20, 113022 (2018).
  * Maslov  _et al._ [2008] D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne, Quantum circuit simplification and level compaction, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 436 (2008).
  * Booth Jr [2012] J. Booth Jr, Quantum compiler optimizations, arXiv preprint arXiv:1206.3348 (2012).
  * Chong  _et al._ [2017] F. T. Chong, D. Franklin, and M. Martonosi, Programming languages and compiler design for realistic quantum hardware, Nature 549, 180 (2017).
  * Heyfron and Campbell [2018b] L. E. Heyfron and E. T. Campbell, An efficient quantum compiler that reduces t count, Quantum Science and Technology 4, 015004 (2018b).
  * Häner  _et al._ [2018] T. Häner, D. S. Steiger, K. Svore, and M. Troyer, A software methodology for compiling quantum programs, Quantum Science and Technology 3, 020501 (2018).
  * McClure and Gambetta [2019] D. McClure and J. Gambetta, Quantum computation center opens, https://www.ibm.com/blogs/research/2019/09/quantum-computation-center/ (2019), [Online; accessed 9-April-2022].
  * Roffe [2019b] J. Roffe, Quantum error correction: an introductory guide, Contemporary Physics 60, 226 (2019b).

##  Appendix A Brief review of QECC stabilizer codes

Figure 16: The generic circuit of a $[[n,k,d]]$ stabilizer error correction
code. (a) A data register $\ket{\psi}_{D}$ is entangled with $n-k$ redundancy
qubits via an EC to form the logical-state $\ket{\psi}_{L}$. (b) After a
potential error $E$ occurs, ancilla qubits are attached to $\ket{\psi}_{L}$
and $m$ syndrome measurements $P_{i}$ are performed. The result of the
measurements produces the syndrome. (c) With the syndrome, one queries the
syndrome table, and the appropriate correction $R$ is appointed and applied.
This process is represented by the Decoder gate. The double-line channels
symbolizes classical communication.

The main objective of a QECC is to protect $k$ data-qubit registers from a set
of errors $\mathcal{E}$. By protection, it is meant that the code must be able
to detect and correct any error in $\mathcal{E}$. Figure 16 summarizes the
general structure of a $[[n,k,d]]$ stabilizer error correction code. It is
divided into three stages: encoding, syndrome extraction and correction. We
now describe each stage in detail.

On the encoding stage, Figure 16(a), a $k$-qubit data-state $\ket{\psi}_{D}$
is entangled with $m=n-k$ auxiliary qubits via an EC forming a $n$-qubit
logical state $\ket{\psi}_{L}$. The EC defines the set of codewords
$\mathcal{C}=\\{\ket{c_{i}}_{L}\\}_{i}$ which specify how the other stages of
the code function. In general, $|\mathcal{C}|=2^{k}$. For example, for $k=2$,
the encoding stage maps $\\{\ket{00},\ket{01},\ket{10},\ket{11}\\}$ into four
mutually orthogonal codewords in an expanded Hilbert space.

During syndrome extraction, errors are detected by performing $m$ syndrome
measurements as shown in Figure 16(b). The codewords define a group of common
stabilizers spanned by $m$ generators [37]. Let $\mathcal{P}=\\{P_{i}\\}$ be a
set of generators for the common stabilizer group of $\mathcal{C}$. We refer
to the elements of $\mathcal{P}$ as syndrome operators. It follows that
syndrome operators satisfy the following properties [96]:

  1. 1.

$\mathcal{P}\subseteq\mathcal{G}_{n}$;

  2. 2.

$P_{i}\ket{\psi}_{L,j}=+1\ket{\psi}_{L,j}\,\forall\,i,j$;

  3. 3.

$[P_{i},P_{j}]=0\,\forall\,i,j$,

where $\mathcal{G}_{n}$ is the general $n$-qubit Pauli group defined as the
set composed of all tensor product combinations of the elements of
$\mathcal{G}_{1}=\\{\pm I,\pm iI,\pm X,\pm iX,\pm Y,\pm iY,\pm Z,\pm iZ\\}$.
Property 2 ensures that the syndrome measurements do not further disturb the
damaged logical state, and property 3 allows one to perform measurements in
any order.

Let $E\in\mathcal{E}$ be an error that occurred between the encoding and
syndrome extraction stages. The effect of each syndrome measurement is to map
$E\ket{\psi}_{L}$ into the superposition

$\displaystyle E$ $\displaystyle\ket{\psi}_{L}\ket{0}_{A_{i}}\rightarrow$
$\displaystyle\frac{1}{2}\left[(I+P_{i})E\ket{\psi}_{L}\ket{0}_{A_{i}}+(I-P_{i})E\ket{\psi}_{L}\ket{1}_{A_{i}}\right].$
(9)

Note that $E$ necessarily either commutes or anti-commutes with $S_{i}$ since
$E,P_{i}\in\mathcal{G}_{n}$. If $E$ and $P_{i}$ commutes (anti-commutes), the
final state is unequivocally $E\ket{\psi}_{L}\ket{0}_{A_{i}}$
($E\ket{\psi}_{L}\ket{1}_{A_{i}}$). Therefore, each syndrome measurement can
be understood as a deterministic measurement of the state with the outcome
revealing whether the error commutes or anti-commutes with the syndrome
operator. At the end of the syndrome extraction stage, one is left with a
binary syndrome string of length $m$ whose $i$-th entry encodes whether
$P_{i}$ and $E$ commutes or not.

Given $\mathcal{E}$ and $\mathcal{P}$, one builds the so-called syndrome table
relating each error to the corresponding syndrome string it generates. As an
illustration, Table 2 shows the syndrome table for the $3$-qubit code with
$\mathcal{P}=\\{Z_{1}Z_{2},Z_{2}Z_{3}\\}$, and considering errors with weight
one on three qubits. Note that the syndromes for $Z_{i}$ are composed only of
zeros, which is the same syndrome for $E=I$ since the identity commutes with
any operator. These errors are classified as undetectable [37] as they are not
distinguishable from $I$.

Table 2: $3$-qubit code syndrome table for single-qubit errors. Error | Syndrome | Error | Syndrome
---|---|---|---
$X_{1}$ | $10$ | $Z_{1}$ | $00$
$X_{2}$ | $11$ | $Z_{2}$ | $00$
$X_{3}$ | $01$ | $Z_{3}$ | $00$

Finally, in the correction stage one prescribes an operator $R$ for which

$RE\ket{\psi}_{L}=\ket{\psi}_{L}.$ (10)

Since Pauli operators square to the identity, $R$ is in principle identical to
the appointed error guided by the syndrome table. The decoder gate of Figure
16(c) is a crosscheck, performed in a classical computer, between the
extracted syndrome and its related error on the syndrome table. This scheme
functions perfectly for non-degenerate codes, where a one-to-one
correspondence between errors and syndromes exists. On the other hand, for
degenerate codes multiple errors can produce the same syndrome. For a
successful correction, all two-on-two combinations of errors with the same
syndrome must stabilize all codewords. Consider an arbitrary correction code
with codewords $\\{\ket{c_{i}}_{L}\\}$, and let $\\{E_{i}\\}$ be a set of
errors with the same syndrome. One requires,

$E_{i}E_{j}\ket{c_{k}}_{L}=+\ket{c_{k}}_{L}\,\forall i,j,k$ (11)

for $\\{E_{i}\\}$ to be correctable. If the above condition is met, applying
any element of $\\{E_{i}\\}$ will restore the logical state even though it is
impossible to single out which error actually took place. If for some pairing
$E_{i}E_{j}$ Equation (11) is not satisfied, the set $\\{E_{i}\\}$ is
classified as uncorrectable, since it is impossible to decide the proper
correction operation.

##  Appendix B Generating sets of codewords

Given an EC, applying it to the $\ket{0}^{\otimes n}$ state generates a first
possible codeword $\ket{c_{0}}$. Recollecting that codewords form a set of
mutually orthogonal states, we create a method to build $2^{n}-1$ mutually
orthogonal states to $\ket{c_{0}}$ which will give us a set of $2^{n}$
potential codewords (since we work with qubits, a $n$-dimensional Hilbert
space is spawned by $2^{n}$ states) $\\{\ket{c_{i}}\\}$. In possession of
$\\{\ket{c_{i}}\\}$, it remains to evaluate the corrigibility degree
$\mathcal{C}$ of subsets. To generate states orthogonal to $\ket{c_{0}}$, we
find a set of logical $\mathcal{X}\equiv\\{\bar{X}_{i}\\}$ operators such that

$\displaystyle\bar{X}_{i}\ket{c_{0}}$ $\displaystyle=\ket{c_{i}}$ (12)
$\displaystyle\bra{c_{i}}\ket{c_{j}}$ $\displaystyle=\delta_{ij}$ (13)

$\forall i\in\\{1,\dots,2^{n-1}\\}$.

There is a systematic method to build a particular (non-unique) set
$\mathcal{X}$ that satisfies the above equations starting from the
computational basis. Consider the $n$-qubit computational basis. Starting from
$\ket{\psi_{0,I}}=\ket{0}^{\otimes n}\,$ (the first subscript $0$ refers to
$\ket{0}^{\otimes n}$ and the $I$ subscript stands for the identity), it is
straightforward to verify that the logical $\\{\bar{X}_{i,I}\\}$ operators
that take $\ket{\psi_{0,I}}$ to the other states of the basis
$\ket{\psi_{i,I}}$ – which are mutually orthogonal by definition – are all the
$2^{n}-1$ tensor product combinations of Pauli letters $X$ and $I$ possessing
at least one $X$. Define $[\bar{X}_{I}]$ as a $2^{n}-1\times n$ matrix whose
rows are $\\{\bar{X}_{i,I}\\}$:

$[\bar{X}_{I}]=\begin{bmatrix}X&I&I&\dots&I&I\\\ I&X&I&\dots&I&I\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\ I&I&I&\dots&I&X\\\
X&X&I&\dots&I&I\\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
X&X&X&\dots&X&X\end{bmatrix}.$ (14)

Notice that $\\{\bar{X}_{i,I}\\}$ satisfies Equations (12) and (13). Let
$\ket{\psi_{0,U}}=U\ket{\psi_{0,I}}$, where $U$ is some unitary computation.
The operator $U$ transforms each $\bar{X}_{i,I}$ into $\bar{X}_{i,U}\equiv
U\bar{X}_{i,I}U^{\dagger}$ such that

$\displaystyle\bra{\psi_{0,U}}\bar{X}_{i,U}\ket{\psi_{0,U}}$
$\displaystyle=\bra{\psi_{0,I}}U^{\dagger}U\bar{X}_{i,I}U^{\dagger}U\ket{\psi_{0,I}}$
$\displaystyle=\bra{\psi_{0,I}}\bar{X}_{i,I}\ket{\psi_{0,I}}$
$\displaystyle=0$ (15)

$\forall i$. Each $\bar{X}_{i,U}$ is distinct since if
$\bar{X}_{i,U}=\bar{X}_{j,U}$ for some $i,j$ , then

$U\left(\bar{X}_{i,I}-\bar{X}_{j,I}\right)U^{\dagger}=0.$ (16)

Since $U\neq 0$ and $\\{\bar{X}_{i,I}\\}$ are different by construction, then
forcibly $i=j$. We conclude that $\\{\bar{X}_{i,U}\\}$ forms a set of logical
operators whose elements take $\ket{\psi_{0,U}}$ into $2^{n}-1$ unique
mutually orthogonal states $\ket{\psi_{i,U}}$. Taking the particular case of
$U$ as an EC, $\mathcal{X}=\\{\bar{X}_{i,\rm{EC}}\\}$ is the set we seek.

There is a significant computational cost in evaluating the corrigibility
degree $\mathcal{C}$ for each subset of $\\{\ket{c_{i}}\\}$ due to the large
number of subsets. To overcome this, we simplify our approach by considering a
limited number of subsets. First, we limited ourselves to evolving QECCs with
two-dimensional code spaces which leads to an $O\left(2^{2n-1}\right)$ number
of subsets to consider for each tentative EC (a significant but not sufficient
reduction). Second, by appealing to symmetry, we make the heuristic argument
that we can fix one of the codewords, as $\ket{c_{0}}$ without loss, and only
consider subsets of the form $\\{\ket{c_{0}},\ket{c_{i}}\\}$ for
$i=1,\dots,2^{n}-1$.

##  Appendix C Qubit overhead

Let $n$ be the Hilbert space dimension of a QECC. Considering errors as a
product of Pauli operators, we express a general error by assigning a Pauli
letter for each entry of a vector of the form
$\bm{E}=(a_{1},a_{2},\dots,a_{n})$. Define $n_{e}(n,t)$ as the number of
errors with weight $t$. For $t=1$, each possible error can be constructed by
choosing one of the $n$ entries of $\bm{E}$ and assigning one of three Pauli
letters $\\{X,Y,Z\\}$. Therefore,

$n_{e}(n,1)={n\choose 1}\times 3.$ (17)

For $t=2$ the reasoning is similar: we choose two entries in $n$ to allocate
the errors and, for each entry, we choose one of three Pauli letters. Thus,

$n_{e}(n,2)={n\choose 2}\times 3^{2}.$ (18)

This reasoning holds true for any $t\leq n$. Therefore, the general formula
for $n_{e}(n,t)$ is given by

$n_{e}(n,t)={n\choose t}\times 3^{t}.$ (19)

For error-correction we are interested in detecting and correcting errors with
weight up to $t$. Let $s(n,t)$ denote all possible errors up to weight $t$,
i.e., the number of errors with weight less or equal to $t$. It follows that

$s(n,t)=\sum_{i=1}^{t}n_{e}(n,i)=\sum_{i=1}^{t}{n\choose i}\times 3^{i}.$ (20)

With $s(n,t)$ we can derive the minimum number of qubits necessary for
constructing a non-degenerate quantum error-correction code capable of
handling errors up to a weight $t$.

The argument goes as follows: if the codewords are made by $n$ qubits, then at
most $n-1$ auxiliary ancilla qubits are employed in the syndrome measurement
stage. Therefore, the syndrome is a vector with at most $n-1$ binary entries.
Since there exist $2^{n-1}$ binary vectors with $n-1$ entries and at least one
distinct vector must be assigned to each particular error, there must exist at
least as many binary vectors as the number of possible errors for a non-
degenerate error correction code to be able to correct all errors up to weight
$t$:

$s(n,t)+1\leq 2^{n-1}$ (21)

To account for the case in which no errors occurred, $1$ is added to the LHS
of Equation (21).

For $t=1$, it follows

${n\choose 1}\times 3+1=3n+1\leq 2^{n-1}.$ (22)

Note that $n=5$ saturates the inequality (22), therefore it is of no use to
try to build a QECC with less then $5$ qubits; non-degenerate $5$-qubits codes
that correct single-qubit errors are called perfect codes [37, 41] since they
have the property of using every available syndrome for $5$ qubits.


# Yet Another Format of Universal Dependencies for Korean

Yige Chen† Eunkyul Leah Jo‡∗ Yundong Yao‡∗
KyungTae Lim¶ Miikka Silfverberg‡ Francis M. Tyers§ Jungyeul Park‡
†The Chinese University of Hong Kong, Hong Kong ‡The University of British
Columbia, Canada
¶Hanbat National University & TeddySum, South Korea §Indiana University, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Yige Chen, Eunkyul Leah Jo, and Yundong Yao contributed equally.

###### Abstract

In this study, we propose a morpheme-based scheme for Korean dependency
parsing and adopt the proposed scheme to Universal Dependencies. We present
the linguistic rationale that illustrates the motivation and the necessity of
adopting the morpheme-based format, and develop scripts that convert between
the original format used by Universal Dependencies and the proposed morpheme-
based format automatically. The effectiveness of the proposed format for
Korean dependency parsing is then testified by both statistical and neural
models, including UDPipe and Stanza, with our carefully constructed morpheme-
based word embedding for Korean. morphUD outperforms parsing results for all
Korean UD treebanks, and we also present detailed error analyses.

Yet Another Format of Universal Dependencies for Korean

Yige Chen†††thanks:  Yige Chen, Eunkyul Leah Jo, and Yundong Yao contributed
equally. Eunkyul Leah Jo‡∗ Yundong Yao‡∗ KyungTae Lim¶ Miikka Silfverberg‡
Francis M. Tyers§ Jungyeul Park‡ †The Chinese University of Hong Kong, Hong
Kong ‡The University of British Columbia, Canada ¶Hanbat National University &
TeddySum, South Korea §Indiana University, USA<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

##  1 Introduction

Dependency parsing is one of the tasks in natural language processing that
have been investigated extensively. Using the dependency grammar, it finds the
relations between the words in a sentence, and forms an acyclic dependency
graph that explains the grammatical structure of the sentence. With various
machine learning techniques, the current dependency parsers are able to
approach human performances given English
corpora.111https://ai.googleblog.com/2016/05/announcing-syntaxnet-worlds-
most.html Previous studies trying to probe or improve Korean dependency
parsers are lacking, especially for those considering the underlying reason
and rationale based on the linguistic properties of Korean. The parsers do not
perform as well as their English counterparts, partly due to the fact that
Korean is a language that has more complicated linguistic features that make
parsing on the word level difficult.

There have been previous studies trying to cope with the word-level
representation issues of Korean (Choi and Palmer, 2011; Park et al., 2013;
Kanayama et al., 2014). Given that Korean is an agglutinative language that
heavily relies on morphemes, and the natural segmentation does not correctly
reflect either the words or the morphemes of Korean texts, Park and Tyers
(2019) suggested an annotation scheme that decomposes Korean texts into the
morpheme level, and applied the morpheme-based format to POS tagging.

In this study, we propose a morpheme-based scheme for Korean dependency
parsing that is developed based on Park and Tyers (2019), and adopt the
proposed scheme to Universal Dependencies (Nivre et al., 2016, 2020), which
contains two Korean dependency parsing treebanks, namely the GSD treebank
(McDonald et al., 2013) and the Kaist treebank (Choi et al., 1994; Chun et
al., 2018). While the two Korean treebanks meet the standards of Universal
Dependencies and have been studied for dependency parsing tasks extensively
(Kondratyuk and Straka, 2019; Qi et al., 2020), the treebanks are formatted in
a way that the natural segmentations of Korean texts are preserved, and even
with some morpheme-level information, only the language-specific part-of-
speech tags on the morpheme level are included in the treebanks, and both
treebanks do not have any morpheme-level parsing tags. Different from the
traditional scheme based on natural segmentation, this scheme utilizes the
inherent morphological and typological features of the Korean language, and
the morpheme-level parsing tags can therefore be derived using a set of
linguistically motivated rules, which are further used to produce the
morpheme-level dependency parsing results and automatic conversions between
the morpheme-based format and the traditional format.

The proposed morpheme-based representation is examined using several
dependency parsing models, including UDPipe (Straka et al., 2016; Straka and
Straková, 2017) and Stanza (Qi et al., 2020). Compared to the baseline models
trained using the two treebanks without modification, our proposed format
makes statistically significant improvements in the performances of the
parsing models for the Korean language as reported in the error analysis.

##  2 Representation of morphUD

프랑스 &의 & 세계 &적 &이 &ㄴ & 의상 &디자이너 &엠마누엘 &웅가로 &가 & 실내 & 장식 &용 & 직물 & 디자이너 &로 & 나서
&었 &다 &.
peurangseu & -ui & segye & -jeok & -i & -n & uisang & dijaineo & emmanuel &
unggaro & -ga & silnae & jangsik & -yong & jikmul & dijaineo & -ro & naseo &
-eoss & -da & .
France & -gen & world & -suf & -cop& -rel & fashion & designer & Emanuel &
Ungaro & -nom & interior & decoration & usage & textile & designer & -ajt &
become & -past & -ind & .
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18
& 19 & 20 & 21
[edge unit distance=1.7ex]18nmod [edge below]21case [edge unit
distance=1.5ex]38acl [edge below]43aux [edge below]53aux [edge below]63aux
78compound810compound910compound[edge unit distance=0.96ex]1018nsubj [edge
below]1110case 1213compound [edge unit distance=2.6ex]1315compound [edge
below]1413aux 1516compound [edge unit distance=1.9ex]1618advcl [edge
below]1716case 18root [edge below]1918aux [edge below]2018aux [edge unit
distance=1.3ex]2118punct

Figure 1: Example of morpheme-based universal dependencies for Korean: while
dependencies in top-side are the original dependencies between words,
dependencies in bottom-side are newly added dependencies for between
morphemes.

In this study, we adopt a morpheme-based format that captures the linguistic
properties of the Korean language proposed by Park and Tyers (2019). The
natural segmentation of Korean is based on eojeol, which does not necessarily
reflect the actual word or morpheme boundaries of the language. For example,
an eojeol of Korean may contain both a noun and its postposition, or both a
verb and its particles marking tense, aspect, honorifics, etc. While this is
typical for Korean as an agglutinative language, it creates difficulties and
challenges for NLP tasks regarding the Korean language, including dependency
parsing. It is not ideal that the tokens dependency relations are annotated on
are sometimes words, and sometimes phrases as an eojeol may consist of more
than a word. Furthermore, Korean as an agglutinative language has very regular
conjugations, which makes it easy and natural to split those words and phrases
into morphemes when analyzing the language since nearly every piece of an
eojeol can be identified to be of a certain meaning or function.

The morpheme-based format aims at decomposing the Korean sentences further
into morphemes, which means that dependency relations are no longer marked on
the eojeol level. Instead, they are marked on morphemes such that within each
eojeol that is not monomorphemic, a head of that eojeol will be found and all
other morphemes will be attached directly to the head. As a result, the head
of a non-monomorphemic eojeol carries the dependency relation this eojeol
originally has, and all other morphemes will be attached to it. In order to
find the head, we develop a script and apply some heuristics which include
that the head of an eojeol is usually a noun, a proper noun, or a verb, and
while there is no noun or verb in an eojeol, the script we implemented
continues to find other morphemes such as pronouns, adjectives, adverbs,
numerals, etc. The script also excludes the use of adpositions, conjunctions,
and particles as heads in most cases, unless these are the only part-of-
speeches in an eojeol except for punctuations. While there are multiple
morphemes that can be heads in an eojeol, the script will decide which one to
take based on the part-of-speeches of the morphemes. For instance, when there
are multiple nouns, the last one will carry the dependency relation of the
eojeol, whereas when there are multiple verbs, the first verb will carry the
dependency relation as Korean is a head-final language. Once the head of a
non-monomorphemic eojeol is found, the other morphemes will be dependent on
the head and be assigned with other dependency relations such as compound,
case, auxiliary depending on their UPOS and XPOS.

##  3 Experiments and results

###  3.1 Data and systems

In this study, we deploy two parsers to evaluate our proposed format, namely
UDPipe (Straka et al., 2016) as a baseline system and Stanza (Qi et al., 2020)
as one of the state-of-the-art dependency parsers. UDPipe is a pipeline
designed for processing CoNLL-U formatted files, which performs tokenization
using Bi-LSTM, morphological analysis, part-of-speech tagging, lemmatization
using MorphoDiTa (Straková et al., 2014), and dependency parsing using
slightly modified Parsito (Straka et al., 2015). Since the whole pipeline
needs no language-specific knowledge, which means that it can be trained using
corpora in a different scheme, we choose UDPipe as our baseline. Stanza is
another natural language processing toolkit that includes Dozat’s biaffine
attention dependency parser (Dozat and Manning, 2017). Dozat’s dependency
parser uses the minimum spanning tree algorithm that can deal with non-
projectivity dependency relations, and more importantly it excelled all of
dependency parsers during CoNLL 2017 and 2018 Shared Task (Zeman et al., 2017,
2018) In this study, the two dependency parsing pipelines take both the
original word-based form222While words and eojeols are not the same in Korean
based on their definitions, in this study, the terms “word-based” and “eojeol-
based” are interchangeable.  (the current scheme adopted by Universal
Dependencies), which we denote as wordUD, and the morpheme-based form, which
we denote as morphUD, of the GSD and KAIST treebanks as the input.

We develop the script to convert between the wordUD format and our proposed
morphUD format. The script consists of two major components, which are wordUD
to morphUD (Word2Morph) and morphUD to wordUD (Morph2Word). The Word2Morph
component splits the word tokens in the CoNLL-U treebank of Korean into
morphemes using the lemmas already provided, and assigns dependency relations
on the resegmented tokens based on the original dependency relations annotated
on the word tokens. The Morph2Word component, on the other hand, firstly pairs
the tokens in the wordUD dataset and the morphUD dataset, and then assigns the
dependency relations from morpheme tokens in morphUD to word tokens in wordUD.
Within both components, a root detector for the word is implemented in order
to find the root (or stem) of a word when the word is multimorphemic (i.e.,
needs to be split into morphemes and attach dependency relations on it
correspondingly). Evaluations of the conversion scripts are not conducted in
this study, since the morphemes are inherited from the lemmas in the
treebanks, and the part-of-speech tags, roots, and dependency relations are
predicted and assigned to the morphemes based on the linguistic features and
the grammar of Korean that are regular, as presented in Section 2.

###  3.2 Results

We report the labeled attachment score (LAS), which is a standard evaluation
metric in dependency parsing, using the evaluation script (2018 version)
provided by CoNLL 2018 Shared
Task.333https://universaldependencies.org/conll18/conll18_ud_eval.py Table 1
shows results of udpipe as a baseline system and stanza as one of the state-
of-the-art systems. All results are reported in the wordUD format. That is,
all experiments are trained and predicted in the proposed morphUD format, and
then the result is converted back to the wordUD format for comparison
purposes. We train udpipe once because it can produce the same parsing model
if we train it on the same machine. For stanza, we provide average LAS and its
standard deviation after five training and evaluation. Both systems use the
finely crafted 300d embedding file by fastText (Bojanowski et al., 2017):
wordUD and morphUD use words and morphemes as their embedding entries,
respectively to make sure that their input representation would be correctly
matched. For embeddings, there are 9.6M sentences and 157M words (tokenized)
based on wordUD. The set of documents for embeddings includes all articles
published in The Hankyoreh during 2016 (1.2M sentences), Sejong
morphologically analyzed corpus (3M), and Korean Wikipedia articles (20201101)
(5.3M). As expected, all results of morphUD outperform wordUD in Table 1.

| ko_gsd | ko_kaist
---|---|---
| wordUD | +morphUD | wordUD | +morphUD
udpipe | 70.90 | 77.01 | 77.01 | 81.80
stanza | 84.63 ($\pm 0.18$) | 84.98 ($\pm 0.20$) | 86.67 ($\pm 0.17$) | 88.46 ($\pm 0.14$)
Table 1: Dependency parsing results: for the comparison purpose all morphUD
results are converted back to wordUD after training and predicting with the
format of morphUD

###  3.3 Error analysis and discussion

Figure 2 shows the confusion matrix between wordUD and morphUD, in which the
column and the row represent the arc direction of gold and system,
respectively. morphUD outperforms wordUD in predicting all directions except
for right (gold) / left (system). The system predicts the left arc instead of
the correct right arc (212 arc direction errors in wordUD vs. 240 in morphUD).
This is because we spuriously added left arcs for functional morphemes in
morphUD where the system learned more left arc instances during training.

| l | r | o
---|---|---|---
l |  |  |
r |  |  |
o |  |  |
(a) b

| l | r | o
---|---|---|---
l |  |  |
r |  |  |
o |  |  |
(b) b

Figure 2: Confusion matrix for the direction of arcs where the column
represents gold, and the row system: left, right, and o for to root.

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
0 |  |  |  |  |  |  |  |  |  |  |
1 |  |  |  |  |  |  |  |  |  |  |
2 |  |  |  |  |  |  |  |  |  |  |
3 |  |  |  |  |  |  |  |  |  |  |
4 |  |  |  |  |  |  |  |  |  |  |
5 |  |  |  |  |  |  |  |  |  |  |
6 |  |  |  |  |  |  |  |  |  |  |
7 |  |  |  |  |  |  |  |  |  |  |
8 |  |  |  |  |  |  |  |  |  |  |
9 |  |  |  |  |  |  |  |  |  |  |
10 |  |  |  |  |  |  |  |  |  |  |

(a) b

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
0 |  |  |  |  |  |  |  |  |  |  |
1 |  |  |  |  |  |  |  |  |  |  |
2 |  |  |  |  |  |  |  |  |  |  |
3 |  |  |  |  |  |  |  |  |  |  |
4 |  |  |  |  |  |  |  |  |  |  |
5 |  |  |  |  |  |  |  |  |  |  |
6 |  |  |  |  |  |  |  |  |  |  |
7 |  |  |  |  |  |  |  |  |  |  |
8 |  |  |  |  |  |  |  |  |  |  |
9 |  |  |  |  |  |  |  |  |  |  |
10 |  |  |  |  |  |  |  |  |  |  |

(b) b

Figure 3: Confusion matrix for the depth of arcs where the column represents
gold, and the row system.

Figure 4: Example of the 2/1 error by MaltEval where the gold’s arc depth is 2
and the system’s depth is 1. Note that morphUD results are converted back to
wordUD: geuligo wang-ui chinjog-i byeoseul-eul hal su issdolog jongchin gwageo
jedo-leul silsihayeossda ‘And they introduced a clan system to make sure that
the king’s relatives can obtain the government position’

where n children=0tier=word [NP-AJT [NP [NP [NP [실내
silnae
(‘interior’),name=silnae]] [NP [장식용
jangsik-yong
(‘ornamental’),name=jangsik-yong]]] [NP [직물
jikmul
(‘textile’),name=jikmul]]] [NP [디자이너로
dijaineo-ro
(‘designer-ajt’),name=dijaineo-ro]]] [-¿] (silnae) to[out=south east,in=south]
(jangsik-yong); [-¿] (jangsik-yong) to[out=south east,in=south] (jikmul); [-¿]
(jikmul) to[out=south east,in=south] (dijaineo-ro);

Figure 5: Compound noun with a left-skewed tree for NP modifiers in the Korean
treebank

Figure 3 presents the confusion matrix for the arc depth. The most frequent
arc depth error is 2 (gold) / 1 (system) (901 arc depth errors in wordUD vs.
855 in morphUD). Figure 4 shows an example of parsing errors generated by
MaltEval (Nilsson and Nivre, 2008). The parsing error shows that whereas the
gold’s arc requires the depth 2, the system predicts the depth 1. This is
mainly because the analysis of compound nouns for the NP modifier in the
Korean treebank prefers a left skewed tree as shown in Figure 5 where some
nouns are a verbal noun, and it plays a role as a predicate of the precedent
NP modifier. This is a quite different from the English treebank where the
right skewed tree dominates: $[_{\textsc{np}}$ $[_{\textsc{prps}}$ its$]$
$[_{\textsc{n}}$ $[_{\textsc{nn}}$ Micronite$]$ $[_{\textsc{n}}$
$[_{\textsc{nn}}$ cigarette$]$ $[_{\textsc{nns}}$ filters$]]]]]$. This is a
well-known problem when parsing the Korean treebank because it requires the
semantics of the noun to distinguish between the right and the left skewed
trees. One possible remedy for this problem was to build a fully lexicalized
parsing system (Park et al., 2013).

##  4 Conclusion

We proposed a new annotation scheme for Universal Dependencies for Korean. We
have already worked on NER, in which we outperformed the word-level
representation dataset by using the morphologically enhanced dataset, and we
are planning to extend our idea to the semantic role labeling task. We are
also trying to create a consortium to develop the morphologically enhanced
Universal Dependencies for other morphologically rich languages such as
Basque, Finnish, French, German, Hungarian, Polish, and Swedish. All
conversion scripts (wordUD to morphUD, and vice versa), and morphUD datasets
for ko_gsd and ko_kaist will be available through author’s github at
https://github.com/jungyeul/morphUD-korean.

## References

  * Bojanowski et al. (2017) Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017.  Enriching Word Vectors with Subword Information.  _Transactions of the Association for Computational Linguistics_ , 5:135–146.
  * Choi and Palmer (2011) Jinho D. Choi and Martha Palmer. 2011.  Statistical Dependency Parsing in Korean: From Corpus Generation To Automatic Parsing.  In _Proceedings of the Second Workshop on Statistical Parsing of Morphologically Rich Languages_ , pages 1–11, Dublin, Ireland. Association for Computational Linguistics.
  * Choi et al. (1994) Key-Sun Choi, Young S. Han, Young G. Han, and Oh W. Kwon. 1994.  KAIST Tree Bank Project for Korean: Present and Future Development.  In _Proceedings of the International Workshop on Sharable Natural Language Resources_ , pages 7–14, Nara Institute of Science and Technology. Nara Institute of Science and Technology.
  * Chun et al. (2018) Jayeol Chun, Na-Rae Han, Jena D. Hwang, and Jinho D. Choi. 2018.  Building Universal Dependency Treebanks in Korean.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Dozat and Manning (2017) Timothy Dozat and Christopher D. Manning. 2017.  Deep Biaffine Attention for Neural Dependency Parsing.  In _Proceedings of the 5th International Conference on Learning Representations (ICLR 2017)_ , Toulon, France. The International Conference on Learning Representations (ICLR).
  * Kanayama et al. (2014) Hiroshi Kanayama, Youngja Park, Yuta Tsuboi, and Dongmook Yi. 2014.  Learning from a Neighbor: Adapting a Japanese Parser for Korean Through Feature Transfer Learning.  In _Proceedings of the EMNLP’2014 Workshop on Language Technology for Closely Related Languages and Language Variants_ , pages 2–12, Doha, Qatar. Association for Computational Linguistics.
  * Kondratyuk and Straka (2019) Dan Kondratyuk and Milan Straka. 2019.  75 languages, 1 model: Parsing universal dependencies universally.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2779–2795, Hong Kong, China. Association for Computational Linguistics.
  * McDonald et al. (2013) Ryan McDonald, Joakim Nivre, Yvonne Quirmbach-Brundage, Yoav Goldberg, Dipanjan Das, Kuzman Ganchev, Keith Hall, Slav Petrov, Hao Zhang, Oscar Täckström, Claudia Bedini, Núria Bertomeu Castelló, and Jungmee Lee. 2013.  Universal Dependency Annotation for Multilingual Parsing.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 92–97, Sofia, Bulgaria. Association for Computational Linguistics.
  * Nilsson and Nivre (2008) Jens Nilsson and Joakim Nivre. 2008.  MaltEval: an Evaluation and Visualization Tool for Dependency Parsing.  In _Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC’08)_ , Marrakech, Morocco. European Language Resources Association (ELRA).
  * Nivre et al. (2016) Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman. 2016.  Universal Dependencies v1: A Multilingual Treebank Collection.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016)_ , page 1659–1666, Portorož, Slovenia. European Language Resources Association (ELRA).
  * Nivre et al. (2020) Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Jan Hajič, Christopher D. Manning, Sampo Pyysalo, Sebastian Schuster, Francis Tyers, and Daniel Zeman. 2020.  Universal Dependencies v2: An Evergrowing Multilingual Treebank Collection.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 4034–4043, Marseille, France. European Language Resources Association.
  * Park et al. (2013) Jungyeul Park, Daisuke Kawahara, Sadao Kurohashi, and Key-Sun Choi. 2013.  Towards Fully Lexicalized Dependency Parsing for Korean.  In _Proceedings of the 13th International Conference on Parsing Technologies (IWPT 2013)_ , pages 120–126, Nara, Japan. Assocation for Computational Linguistics.
  * Park and Tyers (2019) Jungyeul Park and Francis Tyers. 2019.  A New Annotation Scheme for the Sejong Part-of-speech Tagged Corpus.  In _Proceedings of the 13th Linguistic Annotation Workshop_ , pages 195–202, Florence, Italy. Association for Computational Linguistics.
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020\.  Stanza: A Python Natural Language Processing Toolkit for Many Human Languages.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 101–108, Online. Association for Computational Linguistics.
  * Straka et al. (2016) Milan Straka, Jan Hajic, and Jana Straková. 2016.  UDPipe: Trainable Pipeline for Processing CoNLL-U Files Performing Tokenization, Morphological Analysis, POS Tagging and Parsing.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016)_ , pages 4290–4297, Paris, France. European Language Resources Association (ELRA).
  * Straka et al. (2015) Milan Straka, Jan Hajič, Jana Straková, and Jan Hajič Jr. 2015.  Parsing Universal Dependency Treebanks using Neural Networks and Search-Based Oracle.  In _14th International Workshop on Treebanks and Linguistic Theories (TLT 2015)_ , pages 208–220, Warszawa, Poland. IPIPAN.
  * Straka and Straková (2017) Milan Straka and Jana Straková. 2017.  Tokenizing, POS Tagging, Lemmatizing and Parsing UD 2.0 with UDPipe.  In _Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 88–99, Vancouver, Canada. Association for Computational Linguistics.
  * Straková et al. (2014) Jana Straková, Milan Straka, and Jan Hajič. 2014.  Open-source tools for morphology, lemmatization, POS tagging and named entity recognition.  In _Proceedings of 52nd Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 13–18, Baltimore, Maryland. Association for Computational Linguistics.
  * Zeman et al. (2018) Daniel Zeman, Jan Hajič, Martin Popel, Martin Potthast, Milan Straka, Filip Ginter, Joakim Nivre, and Slav Petrov. 2018.  CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies.  In _Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 1–21, Brussels, Belgium. Association for Computational Linguistics.
  * Zeman et al. (2017) Daniel Zeman, Martin Popel, Milan Straka, Jan Hajič, Joakim Nivre, Filip Ginter, Juhani Luotolahti, Sampo Pyysalo, Slav Petrov, Martin Potthast, Francis Tyers, Elena Badmaeva, Memduh Gokirmak, Anna Nedoluzhko, Silvie Cinková, Jan Hajič jr., Jaroslava Hlaváčová, Václava Kettnerová, Zdeňka Urešová, Jenna Kanerva, Stina Ojala, Anna Missilä, Christopher D. Manning, Sebastian Schuster, Siva Reddy, Dima Taji, Nizar Habash, Herman Leung, Marie-Catherine de Marneffe, Manuela Sanguinetti, Maria Simi, Hiroshi Kanayama, Valeria de Paiva, Kira Droganova, Héctor Martínez Alonso, Çagrı Çöltekin, Umut Sulubacak, Hans Uszkoreit, Vivien Macketanz, Aljoscha Burchardt, Kim Harris, Katrin Marheinecke, Georg Rehm, Tolga Kayadelen, Mohammed Attia, Ali Elkahky, Zhuoran Yu, Emily Pitler, Saran Lertpradit, Michael Mandl, Jesse Kirchner, Hector Fernandez Alcalde, Jana Strnadová, Esha Banerjee, Ruli Manurung, Antonio Stella, Atsuko Shimada, Sookyoung Kwak, Gustavo Mendonça, Tatiana Lando, Rattima Nitisaroj, and Josie Li. 2017.  CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies.  In _Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 1–19, Vancouver, Canada. Association for Computational Linguistics.