A genetic algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. We present an algorithm which enhances the classical GA with input from quantum annealers. As in a classical GA, the algorithm works by breeding a population of possible solutions based on their fitness. However, the population of individuals is defined by the continuous couplings on the quantum annealer, which then give rise via quantum annealing to the set of corresponding phenotypes that represent attempted solutions. This introduces a form of directed mutation into the algorithm that can enhance its performance in various ways. Two crucial enhancements come from the continuous couplings having strengths that are inherited from the fitness of the parents (so-called nepotism) and from the annealer couplings allowing the entire population to be influenced by the fittest individuals (so-called quantum-polyandry). We find our algorithm to be significantly more powerful on several simple problems than a classical GA.
A genetic algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. We present an algorithm which enhances the classical GA with input from quantum annealers. As in a classical GA, the algorithm works by breeding a population of possible solutions based on their fitness. However, the population of individuals is defined by the continuous couplings on the quantum annealer, which then give rise via quantum annealing to the set of corresponding phenotypes that represent attempted solutions. This introduces a form of directed mutation into the algorithm that can enhance its performance in various ways. Two crucial enhancements come from the continuous couplings having strengths that are inherited from the fitness of the parents (so-called nepotism) and from the annealer couplings allowing the entire population to be influenced by the fittest individuals (so-called quantum-polyandry). We find our algorithm to be significantly more powerful on several simple problems than a classical GA.
Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Reverse annealing enables the development of genetic algorithms that use quantum fluctuation for mutations and classical mechanisms for the crossovers -- we refer to these as Quantum-Assisted Genetic Algorithms (QAGAs). We describe a QAGA and present experimental results using a D-Wave 2000Q quantum annealing processor. On a set of spin-glass inputs, standard (forward) quantum annealing finds good solutions very quickly but struggles to find global optima. In contrast, our QAGA proves effective at finding global optima for these inputs. This successful interplay of non-local classical and quantum fluctuations could provide a promising step toward practical applications of Noisy Intermediate-Scale Quantum (NISQ) devices for heuristic discrete optimization.
Genetic Algorithms (GAs) are optimization methods that search near-optimal solutions by applying well-known operations such as selection, crossover and mutation. In particular, crossover and mutation are aimed at creating new solutions from selected parents with the goal of discovering better and better solutions in the search space. In literature, several approaches have been defined to create new solutions from the mating pool to try to improve the performance of genetic optimization. In this paper, the literature is enriched by introducing a new mating operator that harnesses the stochastic nature of quantum computation to evolve individuals in a classical genetic workflow. This new approach, named Quantum Mating Operator, acts as a multi-parent operator that identifies alleles' frequency patterns from a collection of individuals selected by means of conventional selection operators, and encodes them through a quantum state. This state is successively mutated and measured to generate a new classical chromosome. As shown by experimental results, GAs equipped with the proposed operator outperform those equipped with traditional crossover and mutation operators when used to solve well-known benchmark functions.
Due to the non- intuitive nature of Quantum algorithms, it becomes difficult for a classically trained person to efficiently construct new ones. So rather than designing new algorithms manually, lately, Genetic algorithms (GA) are being implemented for this purpose. GA is a technique to automatically solve a problem using principles of Darwinian evolution. This has been implemented to explore the possibility of evolving an n-qubit circuit when the circuit matrix has been provided using a set of single, two and three qubit gates. Using a variable length population and universal stochastic selection procedure, a number of possible solution circuits, with different number of gates can be obtained for the same input matrix during different runs of GA. The given algorithm has also been successfully implemented to obtain two and three qubit Boolean circuits using Quantum gates. The results demonstrate the effectiveness of the GA procedure even when the search spaces are large.
This paper explores the application of genetic algorithms (GAs) to optimize quantum circuits. The core claim is that GA can effectively improve the efficiency and accuracy of quantum computation by strategically modifying the topology and control parameters of quantum circuits. The proposed mechanism treats a quantum circuit as a genetic individual, leveraging the principles of genetic algorithms – including crossover, mutation, and selection – to iteratively enhance circuit performance. This approach represents a novel method for quantum circuit optimization, offering a potentially robust and adaptable solution compared to traditional optimization techniques. We present a framework for implementing this approach, focusing on the algorithmic steps and considerations for successful application. The exploration will cover the challenges and potential benefits of integrating evolutionary algorithms with the unique characteristics of quantum computation. ---
Quantum genetic algorithms (QGA) integrate genetic programming and quantum computing to address search and optimization problems. The standard strategy of the hybrid QGA approach is to add quantum resources to classical genetic algorithms (GA), thus improving their efficacy (i.e., quantum optimization of a classical algorithm). However, the extent of such improvements is still unclear. Conversely, Reduced Quantum Genetic Algorithm (RQGA) is a fully quantum algorithm that reduces the GA search for the best fitness in a population of potential solutions to running Grover’s algorithm. Unfortunately, RQGA finds the best fitness value and its corresponding chromosome (i.e., the solution or one of the solutions of the problem) in exponential runtime, O(2n/2), where n is the number of qubits in the individuals’ quantum register. This article introduces a novel QGA optimization strategy, namely a classical optimization of a fully quantum algorithm, to address the RQGA complexity problem. Accordingly, we control the complexity of the RQGA algorithm 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 RQGA by discarding unfit solutions and bounding the search only in the area of valid individuals. As a result, our Hybrid Quantum Algorithm with Genetic Optimization (HQAGO) solves search problems in O(2(n−k)/2) oracle queries, where k is the number of fixed classical bits in the individuals’ register.
This paper presents a novel approach to complex optimization problems utilizing a hybrid Genetic Algorithm (GA) enhanced with quantum computing techniques. Classical GAs often struggle with slow convergence rates in high-dimensional search spaces. This research addresses this limitation by integrating quantum superposition and interference into the core operations of the GA, specifically crossover and mutation. The proposed method, termed Quantum-Enhanced Genetic Algorithm (Q-GA), aims to significantly accelerate the optimization process by exploring the solution space more efficiently. The core idea is to represent potential solutions within a quantum state, allowing for parallel exploration facilitated by superposition. We detail the architecture of the Q-GA, outlining the integration of classical GA components with quantum algorithms. The performance of the Q-GA is theoretically analyzed, focusing on the potential speedup achievable through quantum computation. The results presented demonstrate the promise of this hybrid approach for tackling computationally intensive optimization problems where classical GAs fall short.