Genetic Quantum Algorithms
Introduction
Quantum computing has been shown to solve an array of algorithmic problems, but there is a distinct lack of research into practical applications of this emerging technology. However, the probabilistic distribution of a qubit gives rise to new ways of computing one classical class of evolutionary algorithms: genetic algorithms. The probabilistic nature of a qubit motivates new approaches to algorithms that deal with juggling multiple possibilities and require variation of input, and genetic algorithms exploit this precise phenomenon. As a result, this article will present a review of a genetic quantum algorithm (GQA) proposed by Han & Kim (2000).
Genetic Algorithms
Genetic algorithms are able to present solutions to optimization problems by using heuristics motivated by mimicking ideas of genetic natural selection found in the biological world. They involve a population of “chromosomes,” or potential solutions in the search space, each that contains variable components, or “genes.” Each individual is then assigned a fitness score based on how well it optimizes the solution, and based on the fitness score of each individual, the algorithm decides how likely it is to “mate,” or contribute its components to the next generation. This process repeats, including features like mutations and crossing over of “mating” chromosomes that are found in nature to increase the diversity of the resultant population, until little change is observed between the parent generation and the child generation. At this point, the algorithm is said to have converged to an optimal solution: yielding the solution of this optimization problem as the “fittest” individuals in the population.
Motivation for a Quantum Analog
The population set of a genetic algorithm involves different proportions of each potential “chromosome,” however using a qubit “chromosome,” we could take advantage of the principle of superposition to allow one qubit to represent different populations of many chromosomes that would take many classical “chromosomes” to represent. As a result, a quantum analog could much more efficiently represent the random diversity in a population: removing the need for additional mutation functionality entirely. In addition, as a qubit’s value approaches |0> or |1>, it becomes more likely to end up in that state progressively more over time: another crucial step that allows for convergence of solution and exploitation of advantages found by more “fit” individuals in the population. Consequently, there is motivation to create a quantum analog of this algorithm: to try to further optimize using these quantum techniques.
Genetic Quantum Algorithm
The genetic quantum algorithm is formed along similar lines to classical genetic algorithms, with a few key differences. In the diagram below, Q(t) represents the qubit chromosomes, while P(t) represents the binary solution set formed by applications of Q(t) to the problem. The variable t represents time, allowing for evolving populations and solution sets over each iteration. The procedure begins by initializing our population set and finding their corresponding solutions before updating the population. Updates happen using quantum gates, however, the key difference in procedure from a classical genetic algorithm. These updates are tailored to the problem being solved with the GQA and are designed to allow for both eventual convergence of the population as well as the “survival of the fittest” strategy outlined by Darwinian selection as a whole. Note that the mutation step is skipped by this algorithm: the randomness provided by a qubit already encapsulates enough diversity to make mutation steps virtually obsolete and even, as found by the authors of this paper, enough to impede the efficiency of the algorithm. GQA populations can even afford to be much smaller than their classical analogues as each qubit stores much more information than a classical bit as described earlier, fully encapsulating this new class of algorithm.
The Knapsack Problem
The efficiency of these genetic quantum algorithms can be tested on the knapsack problem: a classic optimization problem. The knapsack problem involves a knapsack of limited capacity which has to be filled in a way that optimizes value from a set of objects: each with different capacity and associated value. Classical solutions to this problem largely fall into three categories: penalty-based functions, repair-based algorithms, and decoder-based algorithms. Here we will construct a quantum analog to a repair-based algorithm: one where we “repair” overfilled knapsacks by attempting to remove and add ingredients to further optimize them, either by random or greedy selection.
GQA Knapsack Solution
The specific steps of the algorithm are outlined in the paper by Han & Kim, however here we will present a rough overview. We use a repair algorithm in the same format as our genetic quantum algorithms from before, adding steps to make P(t) from Q(t) by applying the solutions to the problem and repair the knapsack by removing overfilled elements and adding elements until it is filled again randomly. However, the key step is how we update the population: by using a quantum rotation gate U(θ)<Q(t)| with θ defined by the lookup table below. In this table, b and x represent collection of bits of the best and binary solutions to the problem. A greater θ leads to a faster convergence, but too fast might lead to premature convergence or even divergence of the function: justifying the small values used in this table. As a result, this update function appropriately moves the solutions to change the order of repair of the knapsack on each iteration, successfully generating new solutions.
Comparison
The authors implemented 2 versions of their GQA algorithm: GQA(1) with 1 qubit and GQA(10) with 10 qubits. Since each qubit chromosome can already represent an array of possible solutions, more were largely unnecessary, especially when compared to the additional size they would take up in a world of low-qubit computing. Nevertheless, both of their algorithms were able to substantially outperform classical genetic algorithms on both best solution and average solution profit.
Conclusions
The dramatic increase in performance of the GQA over classical genetic algorithms in the knapsack problem demonstrates the power of quantum computing in practical computing: the power to encapsulate the diversity of possibility in a vast, probabilistic world. Further work might involve finding quantum analogs of even more similar practical algorithmic techniques and exploring further implementations of GQA: taking advantage of its diversity of representation and exploitative search to find an optimal solution.
References:
Han, K. H., & Kim, J. H. (2000, July). Genetic quantum algorithm and its application to combinatorial optimization problem. In Proceedings of the 2000 congress on evolutionary computation. CEC00 (Cat. №00TH8512) (Vol. 2, pp. 1354–1360). IEEE.
Mirjalili, S. (2019). Genetic algorithm. In Evolutionary algorithms and neural networks (pp. 43–55). Springer, Cham.
