Quantum Genetic Algorithms (QGA) are an emerging field of multivariate quantum optimization that emulate Darwinian evolution and natural selection, with vast applications in chemistry and engineering. The appropriate application of fitness functions and fitness selection is the problem-encoding step and the slowest step in designing QGAs for specific physical applications. In this paper, we provide a comprehensive review of these crucial steps. Our survey maps cases of quantum advantage, classifies and illustrates QGAs and their subroutines, and discusses the two main physical problems tackled by QGAs: potential energy minimization of particles on a sphere and molecular eigensolving. We conclude that the encoding used by the Thomson problem is a decisive step toward the use of QGAs in a variety of physical applications, while Grover’s search as a selection step in Reduced QGAs is the main driver of speedup. Although the small scale of simulations and the emergent nature of QGA optimizations make their complexity analyses difficult, recent studies are focusing on strategies to scale QGAs up.
Quantum Genetic Algorithms (QGA) are an emerging field of multivariate quantum optimization that emulate Darwinian evolution and natural selection, with vast applications in chemistry and engineering. The appropriate application of fitness functions and fitness selection is the problem-encoding step and the slowest step in designing QGAs for specific physical applications. In this paper, we provide a comprehensive review of these crucial steps. Our survey maps cases of quantum advantage, classifies and illustrates QGAs and their subroutines, and discusses the two main physical problems tackled by QGAs: potential energy minimization of particles on a sphere and molecular eigensolving. We conclude that the encoding used by the Thomson problem is a decisive step toward the use of QGAs in a variety of physical applications, while Grover’s search as a selection step in Reduced QGAs is the main driver of speedup. Although the small scale of simulations and the emergent nature of QGA optimizations make their complexity analyses difficult, recent studies are focusing on strategies to scale QGAs up.
Genetic algorithms (GAs) are a class of evolutionary algorithms inspired by Darwinian natural selection. They are popular heuristic optimisation methods based on simulated genetic mechanisms, i.e., mutation, crossover, etc. and population dynamical processes such as reproduction, selection, etc. Over the last decade, the possibility to emulate a quantum computer (a computer using quantum-mechanical phenomena to perform operations on data) has led to a new class of GAs known as “Quantum Genetic Algorithms” (QGAs). In this review, we present a discussion, future potential, pros and cons of this new class of GAs. The review will be oriented towards computer scientists interested in QGAs “avoiding” the possible difficulties of quantum-mechanical phenomena.
This survey presents a comprehensive analysis of the Improved Quantum Genetic Algorithm (IQGA), an interesting way of applying quantum computing to genetic algorithms (GAs). The study begins with an introduction to the several variants of Quantum Genetic Algorithm (QGA), which are widely used in different applications of GAs. The article introduces the IQGA as a quantum version of the classical GA, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the genetic operations, and highlighting its crucial role in quantum algorithms. The analysis also addresses the mathematical foundations of the IQGA, and the key advantages and challenges associated with its use in several applications. Finally, it concludes with an exploration of the current and potential applications of IQGA and common characteristics of several implementations of IQGAs.
Abstract Quantum Genetic Algorithms (QGAs) integrate genetic programming and quantum computing to address search and optimization problems. Most QGA approaches add quantum features to genetic algorithm operators, such as selection, crossover, or mutation. Oppositely, the Reduced Quantum Genetic Algorithm (RQGA) is a fully quantum algorithm that encodes the entire search space (i.e., population) as a superposition of all possible solutions (chromosomes) using the individuals’ quantum register; the fitness function takes the individuals’ quantum register as input to generate corresponding fitness values within the chromosomes’ superposition. RQGA finds the best fitness value and its corresponding chromosome (i.e., the solution or one of the solutions) using Grover’s algorithm. The complexity of Grover’s algorithm is O(2N⁄2), where N is the number of superposed individual chromosomes. However, RQGA operates on an exponentially-big search space (N = 2n, where n is the number of qubits in the individuals’ quantum register), which entails an exponential runtime of O(2n⁄2). This paper introduces an optimization solution for RQGA that controls the algorithm complexity by selecting a limited number of qubits in the individuals’ register and fixing the remaining ones as classical values of ’0’ and ’1’ with a genetic algorithm. We also improve the performance of the RQGA by discarding unfit solutions and bounding the search only in the valid individuals’ area. Putting it all together, we introduce a novel quantum genetic algorithm—Hybrid Quantum Algorithm with Genetic Optimization (HQAGO)—that solves search problems in O(2(n-k)⁄2) oracle queries, where k is the number of fixed classical bits in the individuals’ register. We illustrate instantiations of HQAGO that solve the NP-hard knapsack and graph coloring problems, analyze the complexity of the new algorithm, and study the convergence of its heuristic part.
This paper presents a novel approach to optimization design leveraging the principles of quantum mechanics, specifically superposition and entanglement, through a Quantum Genetic Algorithm (QGA). Traditional Genetic Algorithms (GAs) face challenges in complex, high-dimensional optimization problems due to the exponential growth of the search space. The QGA aims to mitigate these limitations by encoding genetic information into quantum states and utilizing quantum operations for selection, crossover, and mutation. This approach theoretically utilizes quantum superposition to explore multiple solution possibilities simultaneously and quantum entanglement to correlate solutions, potentially leading to faster convergence and improved optimization performance. The paper outlines the theoretical framework, the algorithmic steps of the QGA, and discusses potential applications. The primary contribution is the conceptual framework and the proposed method, recognizing the nascent stage of QGA research and presenting a novel exploration of its potential.
This survey presents a comprehensive analysis of the Improved Quantum Genetic Algorithm (IQGA), an interesting way of applying quantum computing to genetic algorithms (GAs). The study begins with an introduction to the several variants of Quantum Genetic Algorithm (QGA), which are widely used in different applications of GAs. The article introduces the IQGA as a quantum version of the classical GA, detailing how it leverages quantum parallelism and superposition to reduce the time complexity of the genetic operations, and highlighting its crucial role in quantum algorithms. The analysis also addresses the mathematical foundations of the IQGA, and the key advantages and challenges associated with its use in several applications. Finally, it concludes with an exploration of the current and potential applications of IQGA and common characteristics of several implementations of IQGAs. Keywords: QGA, IQGA, GA.
Recently, researchers have applied genetic algorithms (GAs) to address some problems in quantum computation. Also, there has been some works in the designing of genetic algorithms based on quantum theoretical concepts and techniques. The so called Quantum Evolutionary Programming has two major sub-areas: Quantum Inspired Genetic Algorithms (QIGAs) and Quantum Genetic Algorithms (QGAs). The former adopts qubit chromosomes as representations and employs quantum gates for the search of the best solution. The later tries to solve a key question in this field: what GAs will look like as an implementation on quantum hardware? As we shall see, there is not a complete answer for this question. An important point for QGAs is to build a quantum algorithm that takes advantage of both the GA and quantum computing parallelism as well as true randomness provided by quantum computers. In the first part of this paper we present a survey of the main works in GAs plus quantum computing including also our works in this area. Henceforth, we review some basic concepts in quantum computation and GAs and emphasize their inherent parallelism. Next, we review the application of GAs for learning quantum operators and circuit design. Then, quantum evolutionary programming is considered. Finally, we present our current research in this field and some perspectives.