Quantum Genetic Algorithms, Applications and Convergence Analysis
Author: Rubén Ibarrondo López
Advisor(s): Mikel Sanz
Master in Mathematical Modeling and Reseach, Statistics and Computing
Publication year: 2021
Abstract: The ability to control quantum phenomena, such as quantum superposition and interference, has led to a new computational paradigm known as quantum computation, which allows us to design algorithms with dramatic advantages over classical computers. However, whether quantum computation can provide any advantage to evolutionary algorithms, and more precisely, to genetic algorithms (GAs), remains as an open question. Mainly, the development of a fully-quantum GA is hampered by both theoretical constraints, such as the impossibility of perfectly cloning or erasing quantum information, and technical limitations due to the difficulty of the analysis of a huge heuristic quantum algorithm without access to a quantum computer. In this work, we propose a new completelyquantum genetic algorithm (QGA) and we thoroughly analyze its components and performance by means of numerical simulations and quantum-channel techniques. These methods allow us to extract valuable conclusions about the behavior of the algorithm, including its convergence, without the requirement to execute it in a quantum computer. Besides, they make possible to compare the performance of different subroutines in the replication procedure. This proposal paves the way for a new bioinspired optimization quantum algorithm which, additionally, can be straightforwardly parallelized among different processors.