# Quantum Genetic Algorithm Based on Qutrits and Its Application

Authors: Valerii Tkachuk
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Typical approaches to designing quantum genetic algorithms are based on a concept of a qubit, a two-level quantum system. But many-valued quantum logic is more perspective from the point of view of the computational power. This paper proposes a quantum genetic algorithm based on a three-level quantum system in order to accelerate evolutionary process. Simulation using a set of standard test functions proves that the given algorithm is more effective and precise than the conventional quantum genetic algorithm.


---

## Body

## 1. Introduction

Evolutionary algorithms are one of the most widely used methods for solving the global optimization or search problem [1]. In its classical implementation, the smallest unit of information is a bit, a structure which may be in one of the following states: 0 and 1. It is important that a classical bit does not allow any intermediate states.Quantum genetic algorithm (QGA) is a new evolutionary algorithm based on a combination of quantum computation and conventional genetic algorithms technology [2, 3]. This algorithm can be applied to the same set of problems the conventional genetic algorithm is used for, but it allows significantly accelerating the evolutionary process through quantum parallelization and entanglement of the quantum state. Probabilistic mechanism of the quantum computations combined with the evolutionary algorithm provides a global search for a solution with a rapid convergence and a small value of population. These algorithms have demonstrated their effectiveness for solving combinatorial and functional optimization problems, mechanical engineering optimization problems, image processing, and many others [4–8].QGA main concepts were first proposed by Narayanan and Moore [9]. The basic unit of information used in a quantum computations is a qubit, a quantum system, which may be in the 0 basis state or the 1 basis state. Quantum nature of the qubit lies in the superposition principle, under which the qubit may be in any state which is a linear combination of basis states:(1)q=α00+α11with a normalization constraint: (2)α02+α12=1.As a consequence of the superposition principle, qubit state space is incomparably greater than state space of a classical bit. Information, stored inα02 and α12 amplitudes, is the quantum part of the information. Practically, α02  та  α12 are numbers that specify the probability amplitudes of a qubit being in the states 0 and 1, respectively.The outcome of quantum measurement is a qubit in one of the basis states. However, it is important that the result of the measurement is not deterministic, like it is in the classical calculation, but probabilistic.QGA uses a matrix representation for practical implementation:(3)0=10,1=01.Qubit (1) state in this representation can be defined as (4)q=α0α1.A structured set containingN qubits represents a quantum chromosome. State vector of such chromosome is a superposition state of 2N basis states of the register i1,i2,…,iN,  i1,i2,…,iN=0,1:(5)ψ=∑k=0Nαi1,i2,…,iNi1,i2,…,iN.All the information about a qubits system is represented by state vectorψ. The only thing that can be done to such a system is transforming the initial state vector ψinto a new state |ψ′〉 by applying a quantum gate. So quantum genetic algorithm is a state transition process from some starting state to an ending state using a quantum gate algorithm. The information about the problem solution is only contained by the vector of the system ending state |ψ′〉.The main disadvantage appearing during quantum state rotation is the need to use a table to look up the rotating angle, which limits the universality of the search. Fixed rotating angle has a negative impact on the search speed, which is the reason for QGA sometimes being implemented as an adaptive process for determining the rotating angle. To enhance the local searching ability and to get out of the local optimal solutions, GDA can be extended with conventional operators traditionally used in the classical genetic algorithm, such as quantum mutation operation and quantum disaster operation [10].


## 2. Quantum Genetic Algorithm Based on Qutrits (QGA_3)

Qudit is a structure with several, more than two, states, which can also be used to encode a chromosome. A qudit is basically a unit of quantum information, which may be in any ofn states or in any superposition of those.Ternary quantum logic is the simplest type of the many-valued logic. The basic unit of memory is called a qutrit. It has three basis states,0, 1, and 2. The state of the qutrit can be represented as a superposition in the form of a linear combination:(6)q=α0+β1+γ2with a normalization constraint: (7)α2+β2+γ2=1.Matrix representation:(8)0=100,1=010,2=001.For the practical implementation, qutrit (6) state can be represented as(9)q=αβγ.A system containingN qutrits has 3N basis states (as opposed to 2Nstates for binary logic). When switching from binary to many-valued logic, we get an exponential increase in the number of basis states, which leads to an increase in the algorithm performance for the same search accuracy.Quantum chromosome length is determined by the desired search accuracyε, search area xmin,xmax, and the number of quantum system basis states:(10)N=lognxmax-xminε+1,where n is a number of quantum system basis states.Withn=2, search accuracy ε=10-6, and search area -1,1, the length of the quantum chromosome has to be at least 21 qubits, while with n=3 only 14 qutrits are required.


### 2.1. Qutrit Encoding

Matrix representation of a quantum chromosome is a structure which consists ofN qutrits.α1α2α3α4α5⋯⋯⋯αNβ1β2β3β4β5⋯⋯⋯βNγ1γ2γ3γ4γ5⋯⋯⋯γNHereαi,βi,γi determine the state of ith qutrit, аnd N qutrits determine one individual in the population. The initial state of the qutrits holds no information about the system state, so the easiest way to initialize the base population is by setting all probability state amplitudes to be equal to one another [2]. This means that at the end of the initialization each qutrit is in the state(11)q=130+131+132.


### 2.2. Observation of Genes

Classical information about the problem’s solution is located in the ending state vector|ψ〉′and can be retrieved as a result of quantum observation. Qutrit in one of the basis states, which is obtained as a result of quantum observation, is a classical representation of a quantum chromosome.Based on the approach described in [11], the following pseudocode for quantum N-qutrit chromosome state observation can be suggested (Algorithm 1). The product of its work provides the ground state p (0, 1 or 2) with a probability of αi2, βi2 and γi2, respectively.Algorithm 1:Qutrit state observation.
( 1 ) for i in 1,…,Ndo ( 2 )  r← random number in range [0,1] ( 3 )  ifr<ai2then ( 4 )   p←0 ( 5 )  else ifr<ai2+βi2then ( 6 )   p←1 ( 7 )  else ( 8 )   p←2 ( 9 )  end if ( 10 ) end forThe algorithm leads to the quantum chromosome being transformed into its classical representation in the ternary numbering system.α1α2α3α4α5⋯⋯⋯αNβ1β2β3β4β5⋯⋯⋯βNγ1γ2γ3γ4γ5⋯⋯⋯γNObservation↓↓↓↓↓↓↓↓↓020112100


### 2.3. Quantum Rotating Gates

All information about the problem and the algorithm for solving it is contained in the quantum gate, so its algorithm is the key issue of any quantum genetic algorithm construction.The pseudocode for the genetic operator updating the qutrit state (quantum gate of the system evolution) as a result of probability amplitudesαi, βi, and γi modification is presented in Algorithm 2.Algorithm 2:Update of quantum states.
( 1 ) for i in 1,…,Ndo ( 2 )  bestamp←ith gene of the population’s best individual ( 3 )  sum←0 ( 4 )  foramp in {0,1,2}do ( 5 )   ifamp≠bestampthen ( 6 )    q′[amp]=μ⋅q ( 7 )    sum←sum+q′[amp]2 ( 8 )   end if ( 9 )  end for ( 10 )  q′[bestamp]←1-sum ( 11 ) end forThe algorithm’s concept can be illustrated by the image given below. The vertical lines set the probability amplitudesα, β, and γ. If the classical representation of the population best individual has, for example, a 2 on the position i, all the amplitudes, except for γ, are multiplied by the factor μ. Its value lies in a range between 0 and 1 and is determined empirically. As a result, only the probability amplitude γ, which corresponds to the population best individual on the previous evolution stage, will increase. At the same time, probability amplitudes α and β will decrease.It is important, that the described quantum gate algorithm eliminates the necessity to use a lookup table, which exists in the traditional QGA.Initialized population (t=0) includes all the possible solutions with the same probability. This means that the QGA process starts with a random search. As the evolution progresses in time, the distribution undergoes changes (Figure 1).Figure 1
Average distribution of the population individualsn over the search area on different stages of the evolution using an example of F4 function optimization for 100 runs.The mechanisms for the local search witht>100 are illustrated in Figure 2. They demonstrate the role of μ parameter. Its fixed value has a bad impact on the convergence speed. So, it is desirable to use an adaptive quantum gate operator. The listed data shows that it can influence the individual a in three possible ways:(1)
The fitness of the individual is improved, but it does not become the best;(2)
The fitness of the individual is improved, and it becomes the best;(3)
The fitness of the individual is worsened.Figure 2
Possible outcomes of applying a quantum gate operator. Here (b) is the best individual of the population; (a) current individual of the population.This means that the bigger the number of individuals located in the area of the best individualb, the more effective the process of the local convergence.To sum up, QGA starts with the global search and switches to the local search automatically due to the change in the structural characteristics of the population individuals’ distribution.


### 2.4. Quantum Disaster Operation

Quantum population evolution may cause its falling into local optimal solution. This question is particularly important when the search area is large (big number of parameters) or when the fitness function has a complex topology around the global optimum.Taking into consideration the small number of the quantum population, which is usually not bigger thans=10 individuals, getting out of the local optimal solution can be achieved by a quantum disaster operation [12]. It can be summarized as initialization of some population individuals, except for the best, with an initial state. Such operation “virtually” enlarges the size of the population and extends the area for optimal value search.In the simplest case, quantum disaster operation can be implemented as Algorithm3.Algorithm 3:Quantum disaster.
( 1 ) for i in 1,…,sdo ( 2 )  if the chromosome is not the bestthen ( 3 )   if disaster conditionthen ( 4 )    fori in 1,…,Ndo ( 5 )     αi=βi=γi=13 ( 6 )    end for ( 7 )   end if ( 8 )  end if ( 9 ) end for


## 2.1. Qutrit Encoding

Matrix representation of a quantum chromosome is a structure which consists ofN qutrits.α1α2α3α4α5⋯⋯⋯αNβ1β2β3β4β5⋯⋯⋯βNγ1γ2γ3γ4γ5⋯⋯⋯γNHereαi,βi,γi determine the state of ith qutrit, аnd N qutrits determine one individual in the population. The initial state of the qutrits holds no information about the system state, so the easiest way to initialize the base population is by setting all probability state amplitudes to be equal to one another [2]. This means that at the end of the initialization each qutrit is in the state(11)q=130+131+132.


## 2.2. Observation of Genes

Classical information about the problem’s solution is located in the ending state vector|ψ〉′and can be retrieved as a result of quantum observation. Qutrit in one of the basis states, which is obtained as a result of quantum observation, is a classical representation of a quantum chromosome.Based on the approach described in [11], the following pseudocode for quantum N-qutrit chromosome state observation can be suggested (Algorithm 1). The product of its work provides the ground state p (0, 1 or 2) with a probability of αi2, βi2 and γi2, respectively.Algorithm 1:Qutrit state observation.
( 1 ) for i in 1,…,Ndo ( 2 )  r← random number in range [0,1] ( 3 )  ifr<ai2then ( 4 )   p←0 ( 5 )  else ifr<ai2+βi2then ( 6 )   p←1 ( 7 )  else ( 8 )   p←2 ( 9 )  end if ( 10 ) end forThe algorithm leads to the quantum chromosome being transformed into its classical representation in the ternary numbering system.α1α2α3α4α5⋯⋯⋯αNβ1β2β3β4β5⋯⋯⋯βNγ1γ2γ3γ4γ5⋯⋯⋯γNObservation↓↓↓↓↓↓↓↓↓020112100


## 2.3. Quantum Rotating Gates

All information about the problem and the algorithm for solving it is contained in the quantum gate, so its algorithm is the key issue of any quantum genetic algorithm construction.The pseudocode for the genetic operator updating the qutrit state (quantum gate of the system evolution) as a result of probability amplitudesαi, βi, and γi modification is presented in Algorithm 2.Algorithm 2:Update of quantum states.
( 1 ) for i in 1,…,Ndo ( 2 )  bestamp←ith gene of the population’s best individual ( 3 )  sum←0 ( 4 )  foramp in {0,1,2}do ( 5 )   ifamp≠bestampthen ( 6 )    q′[amp]=μ⋅q ( 7 )    sum←sum+q′[amp]2 ( 8 )   end if ( 9 )  end for ( 10 )  q′[bestamp]←1-sum ( 11 ) end forThe algorithm’s concept can be illustrated by the image given below. The vertical lines set the probability amplitudesα, β, and γ. If the classical representation of the population best individual has, for example, a 2 on the position i, all the amplitudes, except for γ, are multiplied by the factor μ. Its value lies in a range between 0 and 1 and is determined empirically. As a result, only the probability amplitude γ, which corresponds to the population best individual on the previous evolution stage, will increase. At the same time, probability amplitudes α and β will decrease.It is important, that the described quantum gate algorithm eliminates the necessity to use a lookup table, which exists in the traditional QGA.Initialized population (t=0) includes all the possible solutions with the same probability. This means that the QGA process starts with a random search. As the evolution progresses in time, the distribution undergoes changes (Figure 1).Figure 1
Average distribution of the population individualsn over the search area on different stages of the evolution using an example of F4 function optimization for 100 runs.The mechanisms for the local search witht>100 are illustrated in Figure 2. They demonstrate the role of μ parameter. Its fixed value has a bad impact on the convergence speed. So, it is desirable to use an adaptive quantum gate operator. The listed data shows that it can influence the individual a in three possible ways:(1)
The fitness of the individual is improved, but it does not become the best;(2)
The fitness of the individual is improved, and it becomes the best;(3)
The fitness of the individual is worsened.Figure 2
Possible outcomes of applying a quantum gate operator. Here (b) is the best individual of the population; (a) current individual of the population.This means that the bigger the number of individuals located in the area of the best individualb, the more effective the process of the local convergence.To sum up, QGA starts with the global search and switches to the local search automatically due to the change in the structural characteristics of the population individuals’ distribution.


## 2.4. Quantum Disaster Operation

Quantum population evolution may cause its falling into local optimal solution. This question is particularly important when the search area is large (big number of parameters) or when the fitness function has a complex topology around the global optimum.Taking into consideration the small number of the quantum population, which is usually not bigger thans=10 individuals, getting out of the local optimal solution can be achieved by a quantum disaster operation [12]. It can be summarized as initialization of some population individuals, except for the best, with an initial state. Such operation “virtually” enlarges the size of the population and extends the area for optimal value search.In the simplest case, quantum disaster operation can be implemented as Algorithm3.Algorithm 3:Quantum disaster.
( 1 ) for i in 1,…,sdo ( 2 )  if the chromosome is not the bestthen ( 3 )   if disaster conditionthen ( 4 )    fori in 1,…,Ndo ( 5 )     αi=βi=γi=13 ( 6 )    end for ( 7 )   end if ( 8 )  end if ( 9 ) end for


## 3. Simulation Test

QGA_3 based on a qutrits system is implemented using C++ programming language. The tests have been performed on the Intel Celeron CPU G1840 2.80 GHz, 4.0 GB RAM, Windows 7 Professional environment.The majority of the quantum algorithms use similar primary ideas and approaches, which are based on the qubit representation of the population. For example, some algorithms based on the quantum computation ideas are presented in [13]. The studies of the quantum algorithms and the possibilities of their modification and improvement are carried out in [14, 15]. Other potential approaches also include the option of the transition to qutrits representation of the population and can be considered as directions for further research. Considering this, the only algorithms compared by effectiveness and performance were QGA and the suggested QGA_3.The analysis and performance evaluation have been performed on a number of test functions [16]:De Jong Function (12) F 1 = 100 x 1 2 - x 2 2 + 1 - x 1 2 ,  - 2.048 ≤ x i ≤ 2.048 ,   i = 1,2 .The function has one global minimum solution:(13)F11,1=0.Coldstein Price Function (14) F 2 = 1 + x 1 + x 2 + 1 2 19 - 14 x 1 + 3 x 1 2 - 14 x 2 + 6 x 1 x 2 + 3 x 2 2 · 30 + 2 x 1 - 3 x 2 2 18 - 32 x 1 + 12 x 1 2 + 48 x 2 - 36 x 1 x 2 + 27 x 2 2 ,  - 2 ≤ x i ≤ 2 ,   i = 1,2 .The function has one global minimum solution:(15)F20,-1=3.Schaffer Function (16) F 3 = 0.5 + s i n 2 x 1 2 + x 2 2 - 0.5 1.0 + 0.001 x 1 2 + x 2 2 2 ,  - 100 ≤ x i ≤ 100 ,   i = 1,2The function has one global minimum solution:(17)F30,0=0.Monopole and Six-Peak Camelback Function (18) F 4 = 10 + sin ⁡ 1 / x 0.1 + x - 0.16 2 ,  0 ≤ x ≤ 1 .The function has one global maximum solution:(19)F40.1275=19.8949.Dual-Pole and Six-Peak Camelback Function (20) F 5 = 4 - 21 x 1 2 + 1 3 x 1 4 x 1 2 + x 1 x 2 + - 4 + 4 x 2 2 x 2 2 ,  - 3 ≤ x i ≤ 3 ,   i = 1,2 .The function has two global minimum solutions:(21)F5-0.0898,0.7126=F50.0898,-0.7126=-1.031628.Multipeak Positive Function (22)
F
6
=
e
-
0.001
x
c
o
s
2
0.8
x
,
-
2
≤
x
≤
5
.The function has one global maximum solution:(23)F60=1.Ackley Function (24) F 7 = - 20 e - 0.2 1 / n ∑ i = 1 n x i 2 - e 1 / n ∑ i = 1 n cos ⁡ 2 π x i ⁡ + 22.71828 ,  - 5 ≤ x i ≤ 5 ,   i = 1,2 .The function has one global minimum solution:(25)F70,0=0.Rastrigin Function (26) F 8 = 10 n + ∑ i = 1 n x 1 2 - 10 cos ⁡ 2 π x i ,  - 5.12 ≤ x i ≤ 5.12 ,   i = 1,2 .The function has one global minimum solution:(27)F80,0=0.Optimization and Results. For QGA and QGA_3 simulation testing the following typical parameters were used: population size s=10, total generations of iteration t=500, and precision ε=1·10-6.The Choice of μ Parameter.The value of parameter μ determines the evolution of the quantum system and has a key role in the algorithm. It determines the balance between the global (quantum observation operation) and local (quantum gate) search for the found solution specification.To choose the optimalμ value we have investigated its influence on the behavior of the main parameters which characterize the quantum system evolution, such as the average fitness of the best individual and the standard deviation of function value over 1000 algorithm runs. Its characteristic behavior for the example of F8 function optimization is presented in Figures 3 and 4. The quantum disaster operation was not applied in this case.Figure 3
Average population fitness as a function ofμ parameter. Evolution time t=500.Figure 4
Standard deviation of the population fitness as a function ofμ parameter. Evolution time t=500.The research shows that ifμ<0.95, the determinative operation in the population evolution is the quantum observation. Global search and the best individual’s approximation to the optimal value take place because of its probabilistic nature. At the same time, the quantum rotation angle is greater than 15° and is too big to perform a local search.Asμ value increases, the rotation angle approaches its optimal value ~4°. It corresponds to μ~0.996÷0.998: with this parameter value the fitness function and standard deviation reach the minimum value (see Figures 3 and 4).Quantum system behavior forμ>0.998 is critically dependent on its evolution time (see Figure 5). Indeed, with t=250 system simply does not have enough time to relax to the ending state, which corresponds to the fitness function optimal value. Enlarging the value of evolution time parameter t=1000 practically simply causes the algorithm running time to increase, with no optimal value improvement.Figure 5
Average fitness of the best individual as a function ofμ parameter for different evolution time parameter values.The role of the quantum disaster operation can be illustrated by Figure6. The results of the F8 function optimization are given for parameters count i=6. Taking into consideration the F8 complex topology around the optimum, the size of the population s=50.Figure 6
Quantum disaster operation influence on the average population fitness as a function ofμ parameter: ∆ –QGA_3 without the disaster operation; × – QGA_3 with the disaster operation.Based on the given analysis it has been established that for QGA_3 without the quantum disaster operationμ≈0.998 is the optimal value. Adding the quantum disaster operation to the QGA_3 algorithm allows producing the best result with μ≈0.975.The optimization results of theF1–F8 test functions with a standard set of input parameters are listed in Table 1.Table 1
Experimental results forF1–F8 test functions optimization.
Function QGA QGA_3 f o p t f - sd t -  (sec) f o p t f - sd t -  (sec) F 1 0.000 0.011 0.011 0.035 0.000 0.005 0.012 0.024 F 2 3.000 3.050 0.132 0.034 3.000 3.000 0.001 0.022 F 3 0.000 0.004 0.012 0.041 0.000 0.001 0.002 0.029 F 4 19.895 19.894 0.001 0.014 19.895 19.895 0.000 0.011 F 5 −1.031 −1.021 0.008 0.034 −1.031 −1.031 0.000 0.024 F 6 1.000 1.000 0.000 0.018 1.000 1.000 0.000 0.012 F 7 0.008 0.035 0.071 0.038 0.000 0.001 0.003 0.022 F 8 0.013 0.051 0.152 0.037 0.000 0.002 0.032 0.024In Table1, fopt denotes the function value of optimum; f- is the average value of the best individual fitness function; sd is standard deviation of fitness function; t- is average elapsed time need for the algorithm to run.A search forF7 and F8 functions global minimum has been carried out separately, using parameter count i=6 and a standard set of other algorithm parameters (see Table 2). The results reveal that QGA_3 is more, but not enough, effective, especially in regard to function F8.Table 2
Experimental results for test functionsF7 and F8, parameters count i=6.
Function QGA QGA_3 f o p t f - sd t -   ( s e c ) f o p t f - sd t -   ( s e c ) F 7 2.648 4.167 0.507 0.117 0.018 0.186 0.170 0.075 F 8 12.117 23.171 5.050 0.107 0.408 6.872 3.621 0.073The result can be significantly improved by enlarging the population size at least tos=50 and adding a quantum disaster operation, with the other parameters remaining unchanged. The results of experiments after the described improvements to the algorithm are listed in Table 3.Table 3
The influence of the quantum disaster operation on QGA_3 efficacy.
Function QGA_3 QGA_3 added disaster operation f o p t f - s d t -   ( s e c ) f o p t f - sd t -   ( s e c ) F 7 0.001 0.095 0.118 0.384 0.000 0.001 0.001 0.399 F 8 0.019 3.135 2.353 0.369 0.000 2.025 1.889 0.375


## 4. Conclusions

In this paper a new quantum genetic algorithm QGA_3 has been proposed. The algorithm is based on the idea of using qutrits for the representation of the population individuals. A simple algorithm, which does not require a lookup table, has been used for constructing the evolution operator which is responsible for the quantum system state updates.The experiments have been performed using a typical set of test functions. On the basis of the experimental results we have concluded that QGA_3 allows decreasing the computational time while being more productive and having better convergence, compared to the conventional QGA.We have also obtained that, in a case with a lot of parameters to be optimized, the QGA_3 efficacy can be improved by adding a quantum disaster operation. In the same time, the increase in algorithm operating time does not exceed 4%.Further promising investigations include the research ofn-valued quantum logic units, qudits and their possible applications for representation of the population individuals. This is expected to be a subject of separate studies.



---

*Source: 8614073-2018-04-29.xml*