Quantum Information Processing manuscript No.
(will be inserted by the editor)

A quantum genetic algorithm with quantum
crossover and mutation operations

arXiv:1202.2026v5 [] 22 Nov 2013

Akira SaiToh · Robabeh Rahimi · Mikio
Nakahara

Received: date / Accepted: date

Abstract In the context of evolutionary quantum computing in the literal
meaning, a quantum crossover operation has not been introduced so far.
Here, we introduce a novel quantum genetic algorithm which has a quantum
crossover procedure performing crossovers among all chromosomes in parallel
for each generation. A complexity analysis shows that a quadratic speedup is
achieved over its classical counterpart in the dominant factor of the run time
to handle each generation.
Keywords Genetic algorithm · Quantum computing · Computational
complexity
PACS 03.67.Ac · 87.23.-n · 89.70.Eg
A. SaiToh
Quantum Information Science Theory Group, National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda, Tokyo 101-8430, Japan
R. Rahimi
Institute for Quantum Computing, University of Waterloo, 200 University Avenue West,
Waterloo, Ontario N2L 3G1, Canada
M. Nakahara
Department of Physics, Kinki University, 3-4-1 Kowakae, Higashi-Osaka, Osaka 577-8502,
Japan
A. SaiToh · M. Nakahara
Research Center for Quantum Computing, Interdisciplinary Graduate School of Science and
Engineering, Kinki University, 3-4-1 Kowakae, Higashi-Osaka, Osaka 577-8502, Japan
Present Address:
A. SaiToh
Department of Computer Science and Engineering, Toyohashi University of Technology, 1-1
Hibarigaoka, Tenpaku-cho, Toyohashi, Aichi 441-8580, Japan
E-mail: saitoh@sqcs.org

2

Akira SaiToh et al.

1 Introduction
Continuous development has been performed on genetic algorithms [19,11,32].
Along with the development of quantum computing [15,37], quantum-inspired
classical algorithms for evolutionary computing have been developed [36,16,
17,18,35,34,6,24,33] (see also a review [54] and references therein). In addition, classical genetic algorithms to evolve quantum circuits have also been
studied by several authors [52,44,2,45,53,38,25,22,43,23,29,26,30,7,46] (see
also review articles [10,9]). These algorithms are, however, designed to work
on classical computers. Quantum genetic algorithms (QGAs), in its literal
meaning, nonetheless, have gathered comparably little attention and a few
works [40,49,27,50,28] have been performed so far. Evolutionary computing
on quantum architectures will achieve more attention if there is a scenario
to establish significant improvement over classical counterparts. Indeed, Malossini et al. [27,28] claimed that the computational complexity of an evolutionary step between generations is exponentially fast in their quantum algorithm
in comparison to a classical one. It seems, however, that they overlooked the
complexity of index-to-string conversion circuits or, otherwise, overlooked the
circuit complexity of a variant of the inversion-about-average operation. Their
claim is thus misleading as we will discuss in Sect. 2. Recently, Johannsen et
al. [20] applied quantum search algorithms to several optimization problems
in a certain context of evolutionary computing. Nevertheless, it is obscure
how much cost is spent for the internal quantum circuit of a variant of the
inversion-about-average operation used for amplitude amplification (namely,
the operation denoted as ASφ0 A−1 in the convention of Ref. [4]) in their approach.
Let us briefly summarize the conventional approach of QGAs and its problem. Here, we omit discussions on incomplete or physically unfeasible works
on QGAs, which were summarized by Sofge in Ref. [41]. The aim of a genetic
algorithm is, in most cases, to find an individual (typically, an input string)
with a very high fitness value for a given problem. It starts with O(|A|w ) initial
individuals where |A| is the size of the alphabet A and w is the length of a
schema expected to be a building block for a given problem. Let us restrict the
problem by representing each individual as a chromosome encoded as a binary
string with the length n. We need ∼ N = 2n initial chromosomes for the worst
case. With a quantum register, one may use n qubits to make a superposition
of N chromosomes. We regard the probability to find a chromosome on the
computational basis as its (normalized) population.
First we briefly overview the selection strategies in conventional QGAs. In
short, a selection is an operation to enhance populations of individuals with
high fitness values and to decrease those with low fitness values. In quantum
computing, it is natural to utilize variants of Grover’s algorithm [12] for this
purpose. In fact, a variant of the Grover search for a priori unknown number r
of solutions (the Grover-BBHT search) [3] and that for finding the maximum
[8,1] are the essential parts
p of the QGAs developed in Refs. [49,27,50,28].
The query complexity O( N/r) for a variant of the Grover search dominates

A quantum genetic algorithm with quantum crossover and mutation operations

3

the total complexity in the QGA of Udrescu et al. [49,50]. For the QGA
of Malossini et al. [27,28], there is a different factor to consume time. As
mentioned, this will be discussed in detail in Sect. 2.
Second we overview the strategies for crossovers and mutations in conventional QGAs. In a short explanation of these terms, a crossover is an operation
to exchange substrings of two chromosomes and a mutation is an operation
to flip certain bits of a chromosome. These are effective operations to enlarge the search space. So far, quantum crossover operations have not been
developed. Malossini et al. [27,28] used classical crossover and mutation operations; Udrescu et al. [49,50] did not use crossover and mutation operations.
Johannsen et al. [20] introduced quantum mutation operations in an application of quantum amplitude amplification [4] to some optimization problems;
nevertheless, crossovers were not used. It is, in fact, in general difficult to manipulate populations of quantum states for handling crossovers if we imitate
the classical way in a straightforward manner (See also Ref. [10] which explained the difficulty in a slightly different manner). Picking-up two particular
individuals and making a crossover costs O(n) quantum gates if we use O(n)
ancillary qubits. Since there are many possible pairs for a crossover at each
generation, there is no speedup over a classical crossover. More specifically
speaking, this approach needs to look up classical data of chromosomes to
specify a pair of chromosomes. Thus there cannot be any speedup. In addition, this requires an exponentially large classical memory in comparison to
the size of a quantum register. We will show a different approach to handle
crossovers in our algorithm in Sect. 3.
As another direction for developing quantum evolutionary computing, which
we do not pursue in this contribution, one may use so-called quantum fixedpoint search algorithms [14,48]. They increase the population of a superposition of target chromosomes by iterative applications of unitary amplitudeamplification operations. Unlike the original Grover search, there is no drawback in an excessive iteration; the probability of finding a target grows monotonically as 1 − ǫ2t+1 where ǫ is the probability of finding a non-target chromosome and t is the number of queries. The query complexity of this approach
is, however, as large as that of the exhaustive search: When the number r of
targets is very small in comparison to N , we have ǫ2t+1 = (1 − r/N )2t+1 ≃
1 − (2t + 1)r/N , which implies that O(N/r) queries are required to achieve
a sufficiently small error probability, say 1/2. Thus for r ≪ N , Grover’s algorithm should be chosen instead of fixed-point quantum search algorithms.
In addition, the asymptotic optimality of ǫ2t+1 as an error reduction speed
was proved [5] for fixed-point quantum search methods. It is also known that
the query complexity of the Grover search is optimal [3] in general as a unitary process for unsorted search. Therefore, it is unlikely1 that a fixed-point
1 There is another drawback in the use of a quantum fixed-point search. It requires
es = 1 − (1 − eiπ/3 ) P |ςl ihςl | and U
et = 1 − (1 − eiπ/3 )|τm ihτm |
phase shift operations U
l
with source states |ςl i and target states |τm i (l and m are labels) in addition to another
appropriate unitary operation [14]. One may alternatively use Ûs = 1−(1−eiπ/3 )|SihS| and
Ût = 1 − (1 − eiπ/3 )|T ihT | where |Si is an equally-weighted superposition of |ςl i and |T i is

4

Akira SaiToh et al.

quantum search is effectively used in an evolutionary computing instead of the
standard Grover search and its variants.
In this contribution, we propose a quantum genetic algorithm that involves
a quantum crossover and a quantum mutation. It uses the quantum search for
finding the maximum [8,1] for the selection procedure. Although this selection
strategy looks similar to those of conventional QGAs [49,27,50,28], it is different in the point that we use tailored inversion operations for the quantum
search. Our algorithm achieves a quadratic speedup over its classical counterpart in the dominant factor of the run time to update each generation as an
algorithm involving all possible crossovers for a chosen crossing site.
This paper is organized in the following way. Section 2 discusses on the
algorithm of Malossini et al. [27,28]. Section 3 describes our algorithm. The
procedures of the crossover, the mutation and the selection are developed in the
standard quantum circuit model. Computational complexities of the algorithm
are evaluated in Sect. 4. The obtained results are discussed in Sect. 5 and
summarized in Sect. 6.

2 A conventional quantum genetic algorithm
Here we discuss the conventional quantum genetic algorithm proposed by Malossini et al. [27,28]. There is another conventional algorithm proposed by
Udrescu et al. [49,50], which is not introduced here. The main difference is
that Udrescu et al. did not employ crossovers and mutations while Malossini
et al. employed them as classical operations.
The problem we consider is given as follows.
Problem: Suppose there are N individuals with indices 0, . . . , N − 1. There is
a fitness function f : {0, . . . , N − 1} → [0, 1]. Find one of the individuals with
sufficiently large fitness values.
The algorithm of Malossini et al. is described in Fig. 1 (Algorithm 1).
They analyzed their algorithm and claimed [27,28] that the selection procedure
e log N
e)
internally requires a very small number of oracle calls in contrast to O(N
e is the number
oracle calls required by a classical selection procedure, where N
of individuals in a generation. In short, their claim was that the number of the
Grover iterations in step (b) (of Fig. 1) was O(1).
Their complexity analysis was, however, misleading. A more accurate description of the complexity is given in the following way. There are two possible
e is approximately equal to N ; (B) N
e ≨ N.
cases we should consider: (A) N
Let us consider the case (A). We can preset the index x to represent the xth
e ≃ N . Then the given fitness
individual in a good approximation thanks to N
function can be used as it is, without index conversion. This indicates that we
an equally-weighted superposition of |τm i. (This kind of alternative operation for a quantum
search was used in Ref. [47].) The problem is that ςl ’s are highly-random nonconsecutive
chromosomes in the context of evolutionary computing. There is no known way to construct
es or Ûs within poly(log N
e ) cost in such a case, where N
e is the number of ςl ’s.
U

A quantum genetic algorithm with quantum crossover and mutation operations

5

Algorithm 1 (Malossini et al. [27, 28])
Main Procedure:
e ≤ N individuals.
Start from a generation consisting of N
Repeat:
1. Use the Quantum Selection Procedure to get one index. Do the same procedure
to get another.
2. Classically make a crossover for the two individuals corresponding to the indices
obtained in 1. Classically make a proper mutation.
3. Classically replace randomly chosen two individuals with the two offsprings
obtained in 2.
Quantum Selection Procedure:
e possible ones in the present generation
(i) Choose randomly an index y among N
and compute its fitness f (y). Set the threshold Fy ←− f (y).
(ii) Perform τ times:
P
(a) Initialize the quantum registers to √1
x |xi|yi, where x’s are the indices
e
N

of the present generation.
(b) Apply the Grover-BBHT search [3], where we internally use an oracle
that inverts the signs of the marked states, namely states |xi such that
f (x) ≥ Fy . This enhances the amplitudes of marked states after its Grover
iteration.
(c) Measure the left register in the computational basis and get the new index
y ′ . If f (y ′ ) > Fy , then y ← y ′ and Fy ← f (y ′ ).
(iii) Return the index y.

Fig. 1 Description of Malossini et al.’s algorithm.

e ≃ N,
use nothing but the standard Grover-BBHT search for N indices. As N
the quantum selection procedure is called only once or a very small number of
times. Suppose there are r nearly-optimal individuals that are acceptable as
solutions for a given problem. Inside the quantum selection procedure, as the
selection goes on in (ii), the oracle used in step (b) has less marked states. The
number of marked states converges to r. Therefore,
the query complexity of a
q
p
e
single step in a very later selection stage is O( N /r) = O( N/r). This is the
accurate description of the query complexity for the present case and it is the
same as that Udrescu et al. gave for their algorithm [49,50]. On average, each
time of the repetition in (ii) virtually extinguishes a half of the individuals by
increasing
the threshold. Thus, by considering the sum of the geometric series
p
i r) (i = 0, 1, 2, . . .), the average total query complexity is found to be
N/(2
p
O( N/r).
Let us now consider the case (B). In this case, the quantum selection procedure is called several (or more) times. The important fact is that the chromosomes of individuals in a generation are not consecutive binary strings. The
e binary strings out of N possible ones. There are two
generation contains N
options to handle them: (B-1) consecutive integers are assigned as pointers to
nonconsecutive chromosomes; (B-2) nonconsecutive chromosomes are used as
they are.
(B-1): In this case, the index x is a pointer to the chromosome κx for which
the fitness function works appropriately. (In short, this is a workaround for
the fact that the original Grover-BBHT search should start from a uniform
superposition of consecutive indices while the generation consists of noncon-

6

Akira SaiToh et al.

secutive chromosomes.) Therefore, for the superposition |ψ0 i = √1

e
N

P

x |xi|yi,

the fitness function cannot be applied directly. We need a conversion circuit
to interpret x as κx . Then the fitness function is applied and it returns f (κx ).
Each conversion should involve O(log N ) CCNOT gates. Thus, the total circuit
e log N ). As a result, a single oracle call
depth for the index conversions is O(N
e log N ). Indeed, the query
accompanies the additional time complexity O(N
e is much smaller than N . However, the cost of index
complexity is small if N
conversions hinders speedup over a classical selection procedure.
P
(B-2): In this case, the state |xi in the superposition |ψ0 i = √1
x |xi|yi
e
N

keeps the actual chromosome x as an index. One should use the Grover-search
routine somehow without index conversions by choosing |ψ0 i as its initial state.
Indeed, this is possible [4] in the case where one can provide the operation
L = I − 2|ψ0 ihψ0 | as the inversion-about-average operation instead of the
standard one for the original Grover search. Nevertheless, L should be gen†
erated by sandwiching I − 2|0ih0| with U(a) and U(a)
in the present context,
where the unitary operation U(a) corresponds to the initialization step (a).
e log N ) (see, e.g., Ref. [51]). (There is
Thus the circuit complexity of L is O(N
a little confusing result by Soklakov and Schack [42]; they showed that a state
preparation, namely an initialization, is possibly performed within polynomial
cost in log N for some cases. Nevertheless, considering the internal cost of the
e poly(log N )) time for general
special oracle they use, their method spends O(N
cases including the present case where the parent set consists of random indices.) As a consequence, an expensive circuit for L should be used subsequent
to every query. Obviously, the time complexity in this case is as large as the
one in case (B-1).
One may also think of replacing the Grover-search routine with the generalized Grover search for nonconsecutive integer sets [13]. Nevertheless, it is
required to find an appropriate unitary transformation replacing the standard
Hadamard transformation H ⊗ · · · ⊗ H. There is no known way to find it efficiently when a random integer set is given and target integers are unknown
in advance.
There is, in fact, a way to reduce the circuit complexity of L introduced in
(B-2) if the algorithm is modified so that it uses an efficient pseudo-randomizer
(or, pseudo-scrambler) circuit instead of directly using a random number generator. Our algorithm introduced in the next section takes this approach.
In addition to the above discussions, we should mention that Algorithm 1
e log N ) space to keep a generation in a
has another problem: it takes O(N
classical memory. This is usually quite larger than the O(log N ) space that is
enough for quantum search (neglecting the space internally used by an oracle
circuit). Our algorithm is designed not to face this problem.

A quantum genetic algorithm with quantum crossover and mutation operations

7

3 Algorithm with quantum crossover and quantum mutation
As we have seen in the previous sections, conventional quantum genetic algorithms were not designed to achieve quantum speedup in their selection
procedures in case a generation consists of nonconsecutive chromosomes. In
addition, a quantum crossover operation has not been developed so far. Here,
we propose an algorithm using a quantum crossover and a quantum mutation.
We use a variant of the Grover search with tailored subroutines for the selection procedure, whose query complexity is the main factor of the total time
complexity. We achieve a quadratic speedup over a classical counterpart in
a dominant factor of time complexity as a genetic algorithm with crossovers
among all parents. It is novel in the sense that a simultaneous crossover using a superposition is achieved. The speedup partly relies on an efficient internal structure of a pseudo-randomizer circuit, which will be explained in
Appendix A.

3.1 Algorithm flow
We introduce our algorithm in Fig. 2 (Algorithm 2). In this algorithm, the
quantum register is accessible from its subroutines as a kind of global variables.
The procedures called inside the algorithm are described in corresponding
subsections 3.2-3.5.

3.2 Preparing the initial state of a quantum register
In this subsection, we define the procedure init_reg(R, z).
This procedure is intended to prepare a superposition corresponding to the
generation given as a set X = {R(q)}q ∪{z} with q = 00 · · · 0c−2 1c−1 , . . . , 10 · · · 1c−1
⊗n
e = 2c ). The procedure starts with the quantum state |0i⊗c
(thus ♯X = N
.
a |0i
P
1
√
The desired superposition is |ϕi =
x∈X |ax ia |xi with ax the address
e
N

pointing x. We opt to use consecutive addresses 0, . . . , 2c − 1. The procedure
is now defined in Fig. 3. The order of time complexity of this procedure equals
to the internal circuit complexity poly(cn) of the pseudo-randomizer R. An
explicit example to construct R as a quantum circuit is given in Appendix A.

3.3 Crossover
Here, we construct a quantum crossover procedure quantum_crossover(l). It
is a 1-point crossover acting on the chromosomes simultaneously.
Recall that the original generation is given as a set X of n-bit integers x
e . Each x has its left side xleft and its right side xright separated
with ♯X = N
by the crossing site. The crossing site is placed between the (l − 1)th and the
lth qubits as specified by the parameter. Hence, the bit length of xleft is l.

8

Akira SaiToh et al.

Algorithm 2
Consider a threshold fth for fitness values, which is considered to be sufficiently large.
t ←− 0.
REPEAT 1.-9.:
1. Construct a pseudo-randomizer R that maps a c-bit string to a pseudo-random
n-bit string. It should be implemented as a circuit whose input and output are
integer couples (a, 0) and (a, R(a)), respectively, where a is a c-bit integer. The
circuit should consist of poly(cn) elementary reversible logic gates. We require R
to regard 00 · · · 0c−1 as an exception and map it to 00 · · · 0n−1 . We also require
e = 2c ≨ N = 2n . Once constructed, R is fixed until next t. An explicit example
N
to construct R is given in Appendix A.
2. IF t = 0 THEN generate a random c-bit string γ and set z ←− R(γ) (otherwise,
z is the best chromosome found in the (t − 1)th trial) ENDIF
3. Generate a random c-bit string γ ′ and set u ←− R(γ ′ ).
4. CALL init_reg(R, z) defined in Sect. 3.2 twice to make two identical quantum
P
states that are both |ϕi = √1
x∈X |ax ia |xi where ax is the address pointing
e
N

5.

6.
7.
8.
9.

to x ∈ X; X = {R(q)}q ∪{z} with q = 00 · · · 0c−2 1c−1 , . . . , 10 · · · 1c−1 ; subscript
“a” stands for the address portion. We write the entire unitary operation of this
procedure as Uinit . That is, |ϕi⊗2 = Uinit (|0ia |0i)⊗2 .
CALL quantum_crossover(l) defined in Sect. 3.3 for the current quantum register, which is a 1-point crossover with the crossing site, chosen at one’s convenience, placed between the (l − 1)th and the lth bits of a chromosome. All
possible crossovers for this crossing site are performed simultaneously. This procedure is an identity map as a quantum operation acting on |ϕi⊗2 .
Apply the quantum mutation (Sect. 3.4) to the current quantum register. We
write the entire unitary operation of this procedure as Umut . Apply the same
mutation classically to u.
CALL quantum_selection(Uinit , Umut , u) defined in Sect. 3.5 for the current
quantum register and obtain the output chromosome z.
IF f (z) ≥ fth THEN RETURN z and EXIT ENDIF
t ←− t + 1. Refresh the quantum register.

Fig. 2 Description of our algorithm.
PROCEDURE init_reg(R, z):
P2c −1
⊗c ⊗ I ⊗n to
(i) Make a superposition √1♯X
j=0 |jia |0 · · · 0i by applying H

⊗n .
|0i⊗c
a |0i
(ii) Apply the pseudo-randomizer R implemented as a unitary operation mapping
|jia |0i to |jia |xj i with xj an n-bit pseudo-random number for j = 1, . . . , 2c − 1.
By assumption, |0ia |0i is mapped to |0ia |0i.
(iii) Apply a 00 · · · 0c−1 -controlled X z0 ⊗· · ·⊗X zn−1 to map |0ia |0i to |0ia |zi, where
zk is the kth bit of z (k = 0, . . . , n − 1).
(iv) RETURN the current state, namely |ϕi.

Fig. 3 Description of procedure init reg(R, z).

With the procedure, we generate a superposition of all the children that are
combinations of xleft ’s and xright ’s together with their parents with the same
weight as children.
The state of the quantum register in the beginning of this procedure is

⊗2

|ϕi

=

!
1 X
left
right
√
|ax ia |x i|x
i ⊗
♯X x∈X

!
1 X
′ left
′ right
√
i .
|ax′ ia |x i|x
♯X x′ ∈X

A quantum genetic algorithm with quantum crossover and mutation operations

9

This state has the components |xleft i|xright i|x′ left i|x′ right i besides the addresses.
left
We relabel the qubits so that the middle portion |xright i|x′ i is put aside from
our minds. Let us conceal them by denoting as |∗xx′ i. In addition, we denote
right
the main portion |xleft x′
i with the subscript “main”. The state |ϕi⊗2 with
the new qubit labels is written as
1 X X
right
imain |∗xx′ i.
|ax ax′ ia |xleft x′
♯X
′
x∈X x ∈X

We have at most (♯X)2 distinct chromosomes in this state. In this way, all
possible crossovers are performed at once by the relabelling. The resultant
state is a superposition of all of the children together with their parents. (The
parents are involved because the values of x and x′ may coincide.) This is
desirable as a crossover because sometimes some parents have higher fitness
values than any child.
The procedure described above is formally written as shown in Fig. 4.

PROCEDURE quantum_crossover(l):
(i) We have the quantum register in the state |ϕi⊗2 . The original labels of its
qubits are 0, . . . , 2c + 2n − 1. We relabel them as 0, . . . , c − 1, 2c, . . . , 2c + l − 1,
{z
} |
{z
}
|
c

2c + n, . . . , 2c + 2n − l − 1,
|
{z
}
n−l

2c + l, . . . , 2c + n − 1.
|
{z
}

c, . . . , 2c − 1,
|
{z
}
c

l

2c + 2n − l, . . . , 2c + 2n − 1,
{z
}
|
l

n−l

(ii) RETURN
Fig. 4 Description of procedure quantum crossover(l).

As is obvious, this procedure is an identity map as a quantum operation.
Once the crossover process is completed, one may use a mutation as an option.
This is going to be explained in the next subsection.

3.4 Mutation
In classical genetic algorithms, randomly selected chromosomes are affected
by a mutation, which is typically certain bit flips acting on randomly-chosen
places. Here, we consider the mutation procedure described in Fig. 5. Although
it is written as a classical routine, it can be trivially interpreted as a quantum
circuit. As a quantum circuit, this mutation procedure tmp_mut is realized
by a multiple-bit controlled multiple-bit NOT gate. (In the example mentioned in Fig. 5, the gate is “0-controlled 1-controlled 1-controlled
0-controlled 1-controlled NOT NOT” with control bits specified by the
first template and the target bits specified by the second template.) The gate

10

Akira SaiToh et al.

PROCEDURE tmp_mut:
(i) Let us randomly generate the first template like ***0*1***1**0****1*, which
specifies a schema to mutate. Using this template, we pick up chromosomes with
specified bits like 0,1,1,0,1 in the specified places.
(ii) We also use the second template like *X*************X*** in which X’s can be
placed only on the places where *’s (namely, “don’t care” symbols) are placed
in the first template. Using this template, we apply the bit flip X to the specified
places of the chromosomes picked up in (i).
(iii) RETURN
Note: Technically, we often wish to avoid a mutation for the best chromosome z found
so far by the present time step. This is realized by choosing the first template
so that this does not happen.
Fig. 5 Description of procedure tmp mut.
right

acts on the portion |xleft x′
imain ; the addresses ax and ax′ are untouched.
Therefore, the resultant state can be written as
|ϕi
e =

right
1 X X
xleft xe′
imain |∗xx′ i,
|ax ax′ ia |e
♯X
′

(1)

x∈X x ∈X

right
where (e
xleft xe′
)’s are the chromosomes after the mutation process.
The next step is to apply a natural selection to the chromosomes living in
the superposition |ϕi.
e

3.5 Selection

In this subsection, we introduce our selection procedure. It is intended to find
right
a chromosome having the maximum fitness among (e
xleft xe′
)’s. It utilizes
the quantum search for finding the maximum [8,1]. As we have mentioned,
conventional QGAs [49,27,50,28] have similar selection strategies. The difference from them is that we use tailored inversion operations for the quantum
search.
Our selection procedure is called with three arguments: Uinit , Umut and u.
We have the state (1) at the beginning of this procedure. The procedure is now
defined in Fig. 6. Here in the text, we do not repeat its description. It should be
e + (28/5)(log2 N
e )2 ⌉
noted that, in the procedure, we set kterm = η × ⌈(45/2)N
with integer constant η ≥ 1.
Let us give an explanation about kterm , namely, the number of iterations.
The defined procedure is the same as the well-known quantum search algorithm for finding the maximum [8,1] except for the definitions of the inversion operation for targets and the inversion-about-average operation. In other
words, we perform the quantum search for finding the maximum in the subright
xleft xe′
imain |∗xx′ i}. As proved by Dürr and Høyer [8],
space span{|ax ax′ ia |e
the probability for the output
to
be the maximum is at least 1/2 if the number
√
of iterations is ⌈(45/2) M + (7/5)(log2 M )2 ⌉ with M the number of indices.
e 2 since there are N
e 2 distinct addresses.
In the present context, we have M = N

A quantum genetic algorithm with quantum crossover and mutation operations

11

PROCEDURE quantum_selection(Uinit , Umut , u):
FOR k ←− 0 TO kterm − 1:
(i) Set
X
U1 = I ⊗ I ⊗ I − 2
I ⊗ |yihy| ⊗ I
f (y)≥f (u)

where the left and the right I’s act on the address states |ax ax′ i and the states
|∗xx′ i, respectively. This is the oracle function that can be implemented as
follows. First, we attach ancillary qubits as blocks (I) and (II) in the state
√
right
xleft xe′
) is set
|0 · · · 0i(I) |−i(II) with |−i = (|0i − |1i)/ 2. For each xx′ , f (e
as a value of the block (I) by using f implemented as a quantum circuit. Let
us write this operation as Uf . Then we compare the block (I) with f (u); we
right
flip the qubit (II) if f (e
xleft xe′
) ≥ f (u). We apply Uf † (this disentangles the
ancillary qubits from the main register) and remove the ancillary qubits.
(ii) Set
U2 = I ⊗ I ⊗ I − 2|ϕih
e ϕ|.
e
This operation is composed in the following way.

†
†
,
Umut
U2 = Umut Uinit [I − 2(|0i⊗c |0i⊗n h0|⊗c h0|⊗n )⊗2 ]Uinit

where we also relabel qubits according to quantum_crossover(l).
(iii) Apply the Grover-BBHT search [3] for which we use U1 and U2 instead of
the standard operations, namely, the inversion operation for targets and the
inversion-about-average operation, respectively. As for the starting state of the
search, we use |ϕi.
e
(iv) Measure the main register and obtain the chromosome u′ .
IF f (u′ ) > f (u) THEN u ←− u′ ENDIF
END FOR
RETURN u.
Fig. 6 Description of procedure quantum selection(Uinit , Umut , u).

Therefore, after kterm iterations, we find the output chromosome having the
right
maximum fitness among (e
xleft xe′
)’s, with the probability at least 1−(1/2)η .
By setting η sufficiently large, say, around 16 to 24, we have the desired output
with almost certainty.
4 Computational cost
We are going to evaluate the computational cost of each process of Algorithm
2 (Fig. 2) in Sect. 4.1. The total computational cost to handle a generation
will be derived in Sect. 4.2 and compared with that of classical counterpart in
Sect. 4.3.
4.1 Costs of each procedure
For a single call of each procedure, the costs are evaluated as follows.
Cost of the initialization The procedure to prepare the initial state, described
e log N ) elementary quantum gates.
in Sect. 3.2, uses poly(cn) = poly(log N

12

Akira SaiToh et al.

Cost of the crossover The crossover described in Sect. 3.3 makes use of two
identical (c + n)-qubit states. This procedure does not use any quantum operation but relabels qubits. This takes O(log N ) time.
Cost of the mutation The mutation described in Sect. 3.4 involves a single
gate that looks like, say,
∗ − NOT − ∗ − C0 − ∗ − C1 − ∗ − ∗ − ∗ − C1 − ∗ − ∗
−C0 − ∗ − ∗ − NOT − ∗ − C1 − ∗
with multiple control bits (0-control C0 ’s and 1-control C1 ’s) and multiple
NOT gates placed according to the corresponding templates, where symbol
∗ stands for an untouched qubit. Such a gate can be realized by O(log N )
elementary quantum gates with O(log N ) ancillary qubits.
e)
Cost of the selection The selection described in Sect. 3.5 consumes O(N
2
e chromosomes.
queries to find the best chromosome in the set of at most N
Each query accompanies the operation U2 that invokes Uinit and Umut , and
also their inverse operations. It is easy to find that the internal cost of U2 is
poly(cn) according to the costs for Uinit and Umut . In addition, the cost to
prepare the starting state is poly(cn). We may also mention that, the internal
cost of the fitness function is a certain small factor, typically poly(n), as conventionally assumed [11]. Therefore, the circuit complexity of the procedure
e poly(log N
e log N )). (We assume that the circuit depth is on the order
is O(N
of the circuit size, namely, the number of elementary quantum gates.) As for
space, we use poly(log N ) qubits in total, considering a typical fitness function
consuming poly(n) space. When the fitness function is designed to use O(n)
space, O(log N ) qubits are enough, although we do not assume this case for
evaluating the space complexity.

4.2 Total cost
Comparing the costs of the four procedures, the dominant cost is the circuit
complexity for the selection procedure. Therefore, we find that our algorithm
uses
e poly(log N
e log N ))
O(N
(2)

elementary quantum gates for each t. This is the time complexity of our algorithm for handling each generation. It is quadratically faster than classically
expected amount considering the fact that the number of combinations is
e 2 ) in our crossover procedure (see the next subsection for the details). As
O(N
for the space complexity, we spend poly(log N ) qubits and O(log N ) classical
bits as is easily evaluated from the description of Algorithm 2 (Fig. 2).

A quantum genetic algorithm with quantum crossover and mutation operations

13

4.3 Comparison with a classical counterpart
The classical counterpart of our algorithm is the one described in Fig. 7 (Algorithm 3). As is obvious from its structure, it should have the same output
and the same number of iterations as our algorithm with almost certainty as
long as the same random seed is used for step 1 to construct R for each value
of t. The computational costs of individual procedures in Algorithm 3 are as

Algorithm 3
Consider a threshold fth for fitness values, which is considered to be sufficiently
large.
t ←− 0.
REPEAT 1.-7.:
1. Construct the pseudo-randomizer R found in Algorithm 2 (Fig. 2) as a classical
function. Fix R until next t. Using R, we generate a generation X = {R(q)}
e = 2c ≨ N = 2n .
with q = 00 · · · 0c−2 1c−1 , . . . , 10 · · · 1c−1 . We require N
e − 1 n-bit-length chromosomes in X presently.)
(Thus, we have N
2. IF t 6= 0 THEN put z into X (z is the best chromosome found in the (t − 1)th
trial) ELSE generate a random c-bit string γ and put R(γ) into X ENDIF
e chromosomes in X.)
(Now we have N
3. Split all x ∈ X between the (l − 1)th bit and the lth bit. This makes l-bit strings
xleft ’s and (n − l)-bit strings xright ’s. Generate the set X̂ consisting of all x’s
and all of their children that are all the combinations of xleft ’s and xright ’s.
4. Apply the template-based mutation tmp_mut, introduced in Sect. 3.4, as a classical procedure to all chromosomes in X̂.
5. Find the chromosome z having the best fitness value among those in X̂.
6. IF f (z) ≥ fth THEN RETURN z and EXIT ENDIF
7. t ←− t + 1.
Fig. 7 Description of a classical counterpart of our algorithm.

follows.
e poly(cn)) basic operations.
– Generating X in the steps 1.-2. takes O(N
2
2
e
e
– We need to use O(nN ) space and O(nN ) basic operations to perform all
e parents.
the crossovers among N
e 2 ) basic operations.
– Mutations acting on the individuals of X̂ take O(nN
e 2 poly(n)) basic
– The selection to find the best individual from X̂ takes O(N
operations considering the cost poly(n) of calculating a fitness value.

e , the time and space complexities are O(N
e 2 poly(log N ))
As n = log2 N and c = log2 N
2
e log N ), respectively, for each t, i.e., for handling each generation.
and O(N
In contrast, as we have seen in Sect. 4.2, the time and space complexities of
e poly(log N
e log N ))
our quantum genetic algorithm (described in Fig. 2) are O(N
and poly(log N ), respectively, for each t. Therefore, neglecting the difference
e log N ) and poly(log N ), we have achieved a quadratic
between poly(log N
speedup over its classical counterpart together with an exponential reduction
in space.
The classical counterpart has been constructed by keeping the one-byone correspondence with the quantum algorithm. Thus there is a possibility

14

Akira SaiToh et al.

that a better classical algorithm with the same behavior exists. This is in
fact the case for Algorithm 3. For a fairer comparison, now we reform Algorithm 3 and reduce its space complexity. The algorithm described in Fig. 8
(Algorithm 4) has the same output and the same number of repetitions as
Algorithm 3 while its space complexity is exponentially reduced. We use the
same pseudo-randomizer construction and the same mutation procedure as
e = 2c and N = 2n for integers c and n satisfying
before. Of course, we set N
e 2 ) times for each value of t. We
1 ≤ c < n. In this algorithm, R is called O(N
Algorithm 4
Consider a threshold fth for fitness values, which is considered to be sufficiently
large.
t ←− 0.
REPEAT 1.-8.:
1. Construct the pseudo-randomizer R : {0, 1}c → {0, 1}n as a classical operation.
2. Construct the mutation process as a map M as a classical operation.
e − 1}, z ←− R(γ) (otherwise, z is
3. IF t = 0 THEN for a random γ ∈ {1, . . . , N
the best chromosome found in the (t − 1)th step) ENDIF
e − 1}, j ←− R(γ ′ ).
4. For a random γ ′ ∈ {1, . . . , N
e
5. FOR a ←− 0 TO N − 1:
IF a = 0 THEN x ←− z ELSE x ←− R(a) ENDIF
e − 1:
FOR b ←− 0 TO N
IF b = 0 THEN y ←− z ELSE y ←− R(b) ENDIF
Crossover x and y and obtain children v and w.
Find the best chromosome g among the chromosomes M (x),
M (y), M (v) and M (w).
IF f (g) > f (j) THEN j ←− g ENDIF
END FOR
END FOR
6. z ←− j.
7. IF f (z) ≥ fth THEN RETURN z and EXIT ENDIF
8. t ←− t + 1.
Fig. 8 Description of an improved classical counterpart of our algorithm.

know that R internally takes poly(cn) time. Therefore, this algorithm spends
e 2 poly(log N
e log N )) time for handling each generation. As for the space
O(N
complexity, it spends only poly(log N ) space, which is clear from the algorithm
structure.
In comparison to this enhanced classical algorithm, our quantum algorithm
still has a quadratically small time complexity as shown in Eq. (2).

5 Discussion
How to perform crossovers in a quantum manner was a pending problem in
conventional quantum genetic algorithms [49,27,50,28]. In fact, a selective
crossover for specific two chromosomes is expensive when they are component
states of a superposition. Even if we attach address states pointing to the
component states, we need to look up the classical data of the chromosomes
to construct a quantum circuit realizing the unitary operation for this purpose,

A quantum genetic algorithm with quantum crossover and mutation operations

15

or more specifically, for placing address-controlled bit-flip gates appropriately.
In our algorithm (Algorithm 2 shown in Fig. 2), we have avoided to mimic a
classical way and chosen a different approach. We use two identical copies of a
superposition corresponding to a generation and utilize relabelling of qubits so
as to handle all possible combinations of substrings simultaneously. Obviously,
the classical counterpart of our algorithm is the one that seeks for the best
chromosome (after a mutation) among all possible crossovers for a chosen
crossing site for each generation. Comparing our algorithm with the classical
counterpart, we concluded that we have achieved a considerable reduction in
the computational cost.
One may, however, claim that usually at most several crossovers are performed for a single generation in a classical genetic algorithm. Indeed, our
algorithm is not aimed to be a quantum counterpart of a common classical
genetic algorithm. As we discussed in Sect. 2, a straightforward conversion
of a common classical algorithm into quantum one by simply incorporating
a quantum search into the selection procedure has a problem: we need to either interpret nonconsecutive integers to consecutive ones or use an expensive
construction for the inversion-about-average operation in order to perform
the Grover-BBHT search, which causes a significant loss of performance. This
problem should be resolved so as to find a meaningful quantum counterpart for
the common case. Seemingly, the following workaround looks fine: (i) Use the
pseudo-randomizer R used in Algorithm 2 instead of a random number generator to generate initial chromosomes of a generation. (ii) Apply a small number
of crossovers. (iii) Use a selection procedure similar to that of Algorithm 2.
Nevertheless, as we have discussed, it is not known how to construct the procedure (ii) as a unitary operation without the expensive process of looking
up classical data of chromosomes. Therefore, it is the fact that a meaningful quantum counterpart is not easily found for a common classical genetic
algorithm.
In view of the search space covered by each generation, a simultaneous
crossover is, of course, desirable. Use of a superposition for this purpose was
discussed [49,50] but not developed previously. In this sense, we have made a
meaningful improvement by introducing Algorithm 2.
Besides the crossover, let us discuss on the selection procedure. Our algorithm uses a variant of the Grover-BBHT search to achieve a quadratic
speedup over its classical counterpart. The internal cost for each query is kept
polynomial in the length of a chromosome because of the polynomial cost of
our pseudo-randomizer, as described in Sect. 4. Apart from the complexity,
there is some room to find a different design for the selection. Our algorithm
is designed to carry over only the best chromosome z to the next generation,
among the chromosomes existing after the quantum crossover and mutation
procedures. Since projective measurements are used in the quantum selection,
it is inevitable to demolish other chromosomes. This can be a drawback because some of them may possess good fitness values albeit not the best. To
mitigate this severe selection, one may keep the values of z obtained in several elder generations as classical data. These values can be put into a later

16

Akira SaiToh et al.

generation by modifying the register-initialization procedure slightly: one can
modify the pseudo-randomizer so that it does not touch several input strings;
then one can map them to the kept values of z. In this way, one may maintain
a better diversity for high-fitness chromosomes. This is one possible extension
of our algorithm.
There have not been many studies on quantum genetic algorithms so far.
It is hoped that several or more different designs of genetic procedures will be
developed for quantum computers.
6 Summary
We have proposed a genetic algorithm whose crossover, mutation and selection procedures have been all constructed as quantum routines so that quantum parallelism is effectively used. Its crossover procedure performs crossovers
among all chromosomes of a generation. The run time of our algorithm to
update each generation is quadratically faster than that of its classical counterpart, apart from negligible factors.
Acknowledgements A.S. is thankful to Shigeru Yamashita for his comment. A.S. and
M.N. were supported by the “Open Research Center” Project for Private Universities:
matching fund subsidy from MEXT. R.R. is supported by Industry Canada and CIFAR.

A An example of constructing the pseudo-randomizer R
In this appendix, we show an example to construct the pseudo-randomizer R used in Algorithms 2, 3 and 4. It should map a c-bit string to a pseudo-random n-bit string except for
00 · · · 0c−1 that is mapped to 00 · · · 0n−1 . Its internal circuit complexity should be poly(cn).
As we use a quantum circuit to realize it in Algorithm 2, it is desirable to employ a circuit
structure that is originally unitary.
Consider inputs a ∈ {0, 1}c . We design a circuit that maps a0 · · · ac−1 00 · · · 0n−1 to
a0 · · · ac−1 κ0 · · · κn−1 with κ = R(a), an n-bit pseudo-random number (here, a0 · · · ac−1
and κ0 · · · κn−1 are the binary representations of a and κ). By the definition of R, the
circuit preserves 00 · · · 0c−1 00 · · · 0n−1 . This circuit is generated by function gen_r_circ()
described in Fig. 9. As is clear from the description, the circuit output from this function

FUNCTION gen_r_circ():
Comment: We use wires v0 , . . . , vc−1 , w0 , . . . , wn−1 .
FOR i ←− 0 TO c − 1:
(1) Use a random number generator to generate an n-bit integer γ. Write its binary
representation as γ0 · · · γn−1 .
(2) Using the wire vi as the control wire (namely, the control bit), output the gate
controlled-(X0 )γ0 ⊗· · ·⊗(Xn−1 )γn−1 with Xk the bit flip gate acting on the wire
wk (k = 0, . . . , n − 1). In this gate, the bit flips are active under the condition
that vi = 1.
END FOR
Fig. 9 Description of function gen r circ().

can be directly used as a quantum circuit. Using the circuit C = gen_r_circ(), we have

A quantum genetic algorithm with quantum crossover and mutation operations

17

C

|ai|0i 7→ |ai|R(a)i ∀a ∈ {0, 1}c . The circuit complexity of C is O(cn) because, for each i,
at most n CNOT gates are used to decompose the gate output from step (2). In addition,
gen_r_circ() spends O(c poly(n)) time when a common random number generator [21, 31]
is used in step (1).
Note that the function gen_r_circ() is called only once for each t, in the beginning of
step 1 in Algorithms 2, 3 and 4. We have only to reuse the circuit C for the use of the
pseudo-randomizer until t is incremented.
It is expected that outputs from the circuit C possess good uniformity if we use a good
random number generator in step (1) of gen_r_circ() for generating C. Let us write γ as
γ(i) to emphasize
its dependence on i. For a nonzero input a0 · · · ac−1 , the kth bit of the
Pc−1
output R(a) is
i=0 ai · γk (i) mod 2. This indicates that, for two different inputs a and
a′ , the kth bits of R(a) and R(a′ ) differ with probability 1/2 in the ideal case where γ(i)’s
are generated from a true random number generator. This is because a and a′ differ by at
least a single bit. It also indicates that two different bits, the kth and the k ′ th bits, of R(a)
for a nonzero input a differ with the probability 1/2 in the ideal case. This is because γk (i)
and γk′ (i) differ with the probability 1/2.
Now we show the result of our numerical test of C. We tried statistical tests of randomness [21, 39] to test pseudo-random numbers output from C, using NIST’s Statistical
Test Suite (STS) (version 2.1.1) [39]. We set c = 10 and n = 32. Mersenne Twister (MT)
(version mt19937ar) [31] was used to generate γ in step (1) of gen_r_circ(). We used the
seed value 121212 and did not reset MT during the circuit generation. The circuit C output
from gen_r_circ(), of course, consisted of 10 outputs from step (2). For this C, we used the
inputs a ∈ {0, 1}c \{00 · · · 0c−1 } from smaller to larger and obtained corresponding outputs
R(a) by numerical computation. We obtained 1023 × 32 bits in total in the outputs, since
210 − 1 = 1023. We regarded them as a serial bit string from left to right and used STS in
its default setting to test the string. In the execution of STS, we used 25 binary sequences
with length 1200 as samples from the string. The following tests were tried with the default
parameter values in STS: the Frequency Test, the Block Frequency Test, the Cumulative
Sums Test, the Runs Test, the Longest-Run-of-Ones Test, the Binary Matrix Rank Test, the
Spectral DFT Test and the Serial Test. The string passed the tests except for the Binary
Matrix Rank Test. It should be noted that the input length was too small for the binary
matrix rank test [39]. In addition, randomness is not very strictly required for the use in
evolutionary computing. Therefore, considering the tests that the string passed, we may
claim that gen_r_circ() generates a usable pseudo-randomizer circuit for our algorithm.
We conducted another test: We generated ten circuits by calling gen_r_circ() ten times
without resetting MT, using the seed value 676767. For each circuit, we performed the
same process as above to obtain the serial bit string. We obtained ten serial bit strings in
total and tested the concatenated string using STS. As samples input to STS, we used 25
binary sequences with length 12000. The concatenated string passed the tests except for the
Binary Matrix Rank Test and the Spectral DFT Test. It was unexpected that it did not
pass the spectral DFT test. It requires a further investigation to reveal the reason of this
phenomenon.
The results of the first and the second tests are summarized in Table 1. In summary for this appendix, we found that a pseudo-randomizer circuit whose outputs possess
enough randomness for the use in evolutionary computing can be generated by the function gen_r_circ(). It is hoped that the function will be improved so as to achieve better
randomness for the sake of general use.

References
1. Ahuja, A., Kapoor, S.: A quantum algorithm for finding the maximum (1999).
arXiv:quant-ph/9911082
2. Barnum, H., Bernstein, H.J., Spector, L.: A quantum circuit for OR (1999). arXiv:quantph/9907056
3. Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching.
Fortschr. Phys. 46, 493–505 (1998)

18

Akira SaiToh et al.

Table 1 List of test results for the first and the second tests we performed (see the text
for the details of the tests). Each value is a P -value (see Ref. [39] for its meaning for each
test). The asterisk ∗ indicates a failure to pass the test. We should mention that the values
for the Longest-Run-of-Ones Test accidentally coincided, while the internally-used results
for sample sequences were different.
Frequency Test
Block Frequency Test
Cumulative Sums Test (Forward)
Cumulative Sums Test (Reverse)
Runs Test
Longest-Run-of-Ones Test
Binary Matrix Rank Test
Spectral DFT Test
Serial Test

1st Test
0.021262
0.105618
0.105618
0.001691
0.141256
0.875539
0.000000 ∗
0.000533
0.041438

2nd Test
0.186566
0.001156
0.029796
0.057146
0.010606
0.875539
0.000000 ∗
0.000000 ∗
0.186566

4. Brassard, G., Høyer, P., Tapp, A.: Quantum counting. In: K.G. Larsen, S. Skyum,
G. Winskel (eds.) Proceedings of Automata, Languages and Programming, 25th International Colloquium (ICALP’98) (LNCS 1443), pp. 820–831. Aalborg, Denmark, 13-17
July 1998, Springer-Verlag, Berlin (1998). arXiv:quant-ph/9805082
5. Chakraborty, S., Radhakrishnan, J., Raghunathan, N.: Bounds for error reduction with
few quantum queries. In: C. Chekuri, K. Jansen, J. Rolim, L. Trevisan (eds.) Proceedings
of the 9th International Workshop on Randomization and Computation (RANDOM
2005) (LNCS 3624), pp. 245–256. Berkeley, CA, 22-24 August 2005, Springer-Verlag,
Berlin (2005)
6. Chen, M., Quan, H.: Quantum-inspired evolutionary algorithm based on estimation
of distribution. In: Proceedings of the 2nd International Conference on Bio-Inspired
Computing: Theories and Applications (BIC-TA 2007), pp. 17–19. Zhengzhou, China,
14-17 September 2007, IEEE Press, Piscataway, NJ (2007)
7. Ding, S., Jin, Z., Yang, Q.: Evolving quantum oracles with hybrid quantum-inspired
evolutionary algorithm (2006). arXiv:quant-ph/0610105
8. Dürr, C., Høyer, P.: A quantum algorithm for finding the minimum (1996). arXiv:quantph/9607014
9. Gepp, A., Stocks, P.: A review of procedures to evolve quantum algorithms (2007).
arXiv:0708.3278
10. Giraldi, G.A., Portugal, R., Thess, R.N.: Genetic algorithms and quantum computation
(2004). arXiv:cs/0403003
11. Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning.
Addison-Wesley, Reading, MA (1989)
12. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings
of the 28th Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 212–
219. Philadelphia, PA, 22-24 May 1996, ACM Press, New York, NY (1996)
13. Grover, L.K.: Quantum search on structured problems (1998). arXiv:quant-ph/9802035
14. Grover, L.K.: Fixed-point quantum search. Phys. Rev. Lett. 95, 150501–1–4 (2005)
15. Gruska, J.: Quantum Computing. McGraw-Hill, London (1999)
16. Han, K.H., Kim, J.H.: Genetic quantum algorithm and its application to combinatorial
optimization problem. In: Proceedings of the 2000 Congress on Evolutionary Computation (CEC2000), pp. 1354–1360. La Jolla, CA, 16-19 July 2000, IEEE Press, Piscataway,
NJ (2000)
17. Han, K.H., Kim, J.H.: Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Trans. Evol. Comput. 6(6), 580–593 (2002)
18. Han, K.H., Kim, J.H.: Quantum-inspired evolutionary algorithms with a new termination criterion, hǫ gate, and two-phase scheme. IEEE Trans. Evol. Comput. 8(2),
156–169 (2004)

A quantum genetic algorithm with quantum crossover and mutation operations

19

19. Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis
with Applications to Biology, Control and Artificial Intelligence. The University of
Michigan Press, Ann Arbor, MI (1975)
20. Johannsen, D., Kuru, P.P., Lengler, J.: Can quantum search accelerate evolutionary
algorithms? In: M. Pelikan, J. Branke (eds.) Proceedings of the 12th Annual Genetic
and Evolutionary Computation Conference (GECCO-2010), pp. 1433–1440. Portland,
OR, 7-11 July 2010, ACM, New York, NY (2010)
21. Knuth, D.E.: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms,
3rd Ed. Addison-Wesley, Reading, MA (1997). Chap. 3
22. Leier, A., Banzhaf, W.: Evolving Hogg’s quantum algorithm using linear-tree GP. In:
E. Cantú-Paz, J.A. Foster, K. Deb, L.D. Davis, R. Roy, U.M. O’Reilly, H.G. Beyer,
R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M.A. Potter,
A.C. Schultz, K.A. Dowsland, N. Jonoska, J. Miller (eds.) Proceedings of the Genetic
and Evolutionary Computation Conference 2003 (GECCO-2003), Part I (LNCS 2723),
pp. 390–400. Chicago, IL, 12-16 July 2003, Springer-Verlag, Berlin (2003)
23. Leier, A., Banzhaf, W.: Comparison of selection strategies for evolutionary quantum
circuit design. In: K. Deb (ed.) Proceedings of the Genetic and Evolutionary Computation Conference 2004 (GECCO-2004), Part II (LNCS 3103), pp. 557–568. Seattle, WA,
26-30 June 2004, Springer-Verlag, Berlin (2004)
24. Liao, R., Wang, X., Qin, Z.: A novel quantum-inspired genetic algorithm with expanded
solution space. In: Proceedings of the 2010 Second International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC 2010), pp. 192–195. Nanjing,
China, 26-28 August 2010, IEEE Computer Society, Los Alamitos, CA (2010)
25. Lukac, M., Perkowski, M.: Evolving quantum circuits using genetic algorithm. In:
A. Stoica, D. Keymeulen, J. Lohn (eds.) Proceedings of the 2002 NASA/DoD Conference on Evolvable Hardware, pp. 177–181. Alexandria, VA, 15-18 July 2002, IEEE
Computer Society, Los Alamitos, CA (2002)
26. Lukac, M., Perkowski, M., Goi, H., Pivtoraiko, M., Yu, C.H., Chung, K., Jee, H., Kim,
B.G., Kim, Y.D.: Evolutionary approach to quantum and reversible circuits synthesis.
In: S.N. Yanushkevich (ed.) Artificial Intelligence in Logic Design, pp. 201–257. Kluwer
Academic Publisher, Dordrecht (2004)
27. Malossini, A., Blanzieri, E., Calarco, T.: QGA: quantum genetic algorithm (2004). Technical Report: #DIT-04-105, Dec. 2004, Univ. Trento, http://www.dit.unitn.it
28. Malossini, A., Blanzieri, E., Calarco, T.: Quantum genetic optimization. IEEE Trans.
Evol. Comput. 12(2), 231–241 (2008)
29. Massey, P., Clark, J.A., Stepney, S.: Evolving quantum circuits and programs through
genetic programming. In: K. Deb (ed.) Proceedings of the Genetic and Evolutionary Computation Conference 2004 (GECCO-2004), Part II (LNCS 3103), pp. 569–580.
Seattle, WA, 26-30 June 2004, Springer-Verlag, Berlin (2004)
30. Massey, P., Clark, J.A., Stepney, S.: Human-competitive evolution of quantum computing artefacts by genetic programming. Evol. Comput. 14(1), 21–40 (2006)
31. Matsumoto, M., Nishimura, T.: Mersenne Twister: a 623-dimensionally equidistributed
uniform pseudorandom number generator. ACM Trans. Model. Comput. Sim. 8, 3–30
(1998). Http://www.math.sci.hiroshima-u.ac.jp/˜m-mat/MT/mt.html
32. Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA
(1996)
33. Mohammed, A.M., Elhefnawy, N.A., El-Sherbiny, M.M., Hadhoud, M.M.: Quantum
crossover based quantum genetic algorithm for solving non-linear programming. In:
Proceedings of the 8th International Conference on INFOrmatics and Systems (INFOS2012), pp. BIO–145–153. Cairo, Egypt, 14-16 May 2012, IEEE, Piscataway, NJ
(2012)
34. Nakayama, S., Imabeppu, T., Ono, S.: Pair swap strategy in quantum-inspired evolutionary algorithm (2006). In the Late-breaking papers of the 2006 Genetic and Evolutionary
Computation Conference (GECCO-2006), Seattle, WA, 8-12 July 2006
35. Nakayama, S., Imabeppu, T., Ono, S., Iimura, I.: Consideration on pair swap strategy in
quantum-inspired evolutionary algorithm. IEICE Trans. Inf. Sys. J89-D(9), 2134–2139
(2006). In Japanese

20

Akira SaiToh et al.

36. Narayanan, A., Moore, M.: Quantum-inspired genetic algorithms. In: Proceedings of
the IEEE 3rd International Conference on Evolutionary Computation (ICEC96), pp.
61–66. Nagoya, Japan, 20-22 May 1996, IEEE Press, Piscataway, NJ (1996)
37. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
38. Rubinstein, B.I.P.: Evolving quantum circuits using genetic programming. In: Proceedings of the 2001 Congress on Evolutionary Computation (CEC2001), pp. 144–151. Seoul,
Korea, 27-30 May 2001, IEEE Press, Piscataway, NJ (2001)
39. Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., Vo, S.: A statistical test suite for random and pseudorandom number generators for cryptographic applications (2010).
NIST Special Publication 800-22, Revision 1a,
http://csrc.nist.gov/groups/ST/toolkit/rng/index.html
40. Rylander, B., Soule, T., Foster, J., Alves-Foss, J.: Quantum evolutionary programming.
In: L. Spector, E.D. Goodman, A. Wu, W.B. Langdon, H.M. Voigt, M. Gen, S. Sen,
M. Dorigo, S. Pezeshk, M.H. Garzon, E. Burke (eds.) Proceedings of the Genetic and
Evolutionary Computation Conference (GECCO-2001), pp. 1005–1011. San Francisco,
CA, 7-11 July 2001, Morgan Kaufmann, San Francisco (2001)
41. Sofge, D.A.: Prospective algorithms for quantum evolutionary computation. In: P.D.
Bruza, W. Lawless, K. van Rijsbergen, D.A. Sofge, B. Coecke, S. Clark (eds.) Proceedings of the 2nd Quantum Interaction Symposium (QI-2008), pp. 98–105. Oxford, UK,
26-28 March 2008, College Publications, London (2008). arXiv:0804.1133
42. Soklakov, A.N., Schack, R.: Efficient state preparation for a register of quantum bits.
Phys. Rev. A 73, 012307–1–13 (2006)
43. Spector, L.: Automatic Quantum Computer Programming: A Genetic Programming
Approach. Springer, New York (2004, Paperback Ed. 2007)
44. Spector, L., Barnum, H., Bernstein, H.: Genetic programming for quantum computers.
In: J.R. Koza (ed.) Genetic Programming 1998: Proceedings of the Third Annual Conference (GP-98), pp. 365–374. Madison, WI, 22-25 July 1998, Morgan Kaufmann, San
Francisco (1998)
45. Spector, L., Barnum, H., Bernstein, H., Swamy, N.: Finding a better-than-classical
quantum AND/OR algorithm using genetic programming. In: Proceedings of the 1999
Congress on Evolutionary Computation (CEC1999), pp. 2239–2246. Washington, D.C.,
6-9 July 1999, IEEE Press, Piscataway, NJ (1999)
46. Spector, L., Klein, J.: Machine invention of quantum computing circuits by means of
genetic programming. AI EDAM 22, 275–283 (2008)
47. Tanaka, Y., Ichikawa, T., Tada-Umezaki, M., Ota, Y., Nakahara, M.: Quantum oracles
in terms of universal gate set. Int. J. Quant. Inf. 9, 1363–1381 (2011)
48. Tulsi, T., Grover, L.K., Patel, A.: A new algorithm for fixed point quantum search.
Quant. Inf. Comput. 6, 483–494 (2006)
49. Udrescu, M., Prodan, L., Vlăduţiu, M.: Grover’s algorithm and the evolutionary approach of quantum computation (2004). ACSA Report, ”Politehnica” University of
Timisoara, 15 Oct. 2004, http://www.acsa.upt.ro/publications/index.htm
50. Udrescu, M., Prodan, L., Vlăduţiu, M.: Implementing quantum genetic algorithms:
A solution based on Grover’s algorithm. In: Proceedings of the 3rd Conference on
Computing Frontiers, pp. 71–81. Ischia, Italy, 3-5 May 2006, ACM Press, New York
(2006)
51. Ventura, D., Martinez, T.: Initializing the amplitude distribution of a quantum state.
Found. Phys. Lett. 12, 547–559 (1999)
52. Williams, C.P., Gray, A.G.: Automated design of quantum circuits. In: C.P. Williams
(ed.) Quantum Computing and Quantum Communications: First NASA International
Conference (LNCS 1509), pp. 113–125. Palm Springs, CA, 17-20 February 1998,
Springer-Verlag, Berlin (1999)
53. Yabuki, T., Iba, H.: Genetic algorithms for quantum circuit design–evolving a simpler
teleportation circuit. In: L.D. Whitley, D.E. Goldberg, E. Cantú-Paz, L. Spector, I.C.
Parmee, H.G. Beyer (eds.) Proceedings of the 2000 Genetic and Evolutionary Computation Conference (GECCO-2000), pp. 425–430. Las Vegas, NV, 8-12 July 2000, Morgan
Kaufmann, San Francisco (2000)

A quantum genetic algorithm with quantum crossover and mutation operations

21

54. Zhang, G.: Quantum-inspired evolutionary algorithms: a survey and empirical study. J.
Heuristics 17, 303–351 (2011)

