Genetic algorithms are heuristic optimization techniques inspired by Darwinian evolution. Quantum computation is a new computational paradigm which exploits quantum resources to speed up information processing tasks. Therefore, it is sensible to explore the potential enhancement in the performance of genetic algorithms by introducing quantum degrees of freedom. Along this line, a modular quantum genetic algorithm has recently been proposed, with individuals encoded in independent registers comprising exchangeable quantum subroutines [1], which leads to different variants. Here, we address the numerical benchmarking of these algorithms against classical genetic algorithms, a comparison missing from previous literature. To overcome the severe limitations of simulating quantum algorithms, our approach focuses on measuring the effect of quantum resources on the performance. In order to isolate the effect of the quantum resources on the performance, we selected the classical variants to resemble the fundamental characteristics of the quantum genetic algorithms. Under these conditions, we encode an optimization problem in a two-qubit Hamiltonian and face the problem of finding its ground state. A numerical analysis based on a sample of 200 random cases shows that some quantum variants outperform all classical ones in convergence speed towards a near-optimal result. Additionally, we have considered a diagonal Hamiltonian and the Hamiltonian of the hydrogen molecule to complete the analysis with two relevant use-cases. If this advantage holds for larger systems, quantum genetic algorithms would provide a new tool to address optimization problems with quantum computers.
Genetic algorithms are heuristic optimization techniques inspired by Darwinian evolution. Quantum computation is a new computational paradigm which exploits quantum resources to speed up information processing tasks. Therefore, it is sensible to explore the potential enhancement in the performance of genetic algorithms by introducing quantum degrees of freedom. Along this line, a modular quantum genetic algorithm has recently been proposed, with individuals encoded in independent registers comprising exchangeable quantum subroutines [1], which leads to different variants. Here, we address the numerical benchmarking of these algorithms against classical genetic algorithms, a comparison missing from previous literature. To overcome the severe limitations of simulating quantum algorithms, our approach focuses on measuring the effect of quantum resources on the performance. In order to isolate the effect of the quantum resources on the performance, we selected the classical variants to resemble the fundamental characteristics of the quantum genetic algorithms. Under these conditions, we encode an optimization problem in a two-qubit Hamiltonian and face the problem of finding its ground state. A numerical analysis based on a sample of 200 random cases shows that some quantum variants outperform all classical ones in convergence speed towards a near-optimal result. Additionally, we have considered a diagonal Hamiltonian and the Hamiltonian of the hydrogen molecule to complete the analysis with two relevant use-cases. If this advantage holds for larger systems, quantum genetic algorithms would provide a new tool to address optimization problems with quantum computers.
Genetic algorithms are heuristic optimization techniques inspired by Darwinian evolution, which are characterized by successfully finding robust solutions for optimization problems. While quantum resources have allowed for the acceleration of many computational tasks, it remains an open question whether they can enhance the efficacy of evolutionary algorithms, particularly genetic algorithms. Here, we propose a subroutine-based quantum genetic algorithm with individuals codified in independent registers. This distinctive codification allows our proposal to depict all the fundamental elements characterizing genetic algorithms, i.e. population-based search with selection of many individuals, crossover, and mutation. Our subroutine-based construction permits us to consider several variants of the algorithm. For instance, we firstly analyze the performance of two different quantum cloning machines, a key component of the crossover subroutine. Indeed, we study two paradigmatic examples, namely, the biomimetic cloning of quantum observables and the Bužek-Hillery universal quantum cloning machine. We observed a faster average convergence of the former, but better final populations of the latter. Additionally, we analyzed the effect of introducing a mutation subroutine, concluding a minor impact on the average performance. Furthermore, we introduce a quantum channel analysis to prove the exponential convergence of our algorithm and even predict its convergence-ratio.
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.
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, [[EQUATION]], where [[EQUATION]] is the number of qubits in the individuals' quantum register. This paper introduces a novel QGA optimization strategy, namely a classical optimization of a fully quantum algorithm, to address the Reduced Quantum Genetic Algorithm (RQGA) complexity problem. Accordingly, we control the complexity of theReduced Quantum Genetic Algorithm (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 [[EQUATION]] oracle queries, where [[EQUATION]] is the number of fixed classical bits in the individuals' register.
Quantum computers are seen as the next generation computing technique with the processing power potential they have. However, currently, quantum computers are limited in terms of hardware and algorithmic capabilities. In this study, quantum-inspired methods which are formed by combining quantum computation techniques with classical algorithms are focused on. It has been emphasized in many studies that quantum-inspired methods provide advantages especially for metaheuristic methods. Different from them, in this study, the performance of population-based quantum-inspired methods are compared. The paper focuses on solving the same optimization problem by using quantum-inspired versions of the population-based optimization algorithms such as evolutionary algorithm, genetic algorithm, and differential evolution algorithm. The experimental results show that, while Quantum-inspired Evolutionary Algorithm is better at global search, Quantum-inspired Differential Evolution Algorithm is better at local search and more accurate results.
Recent development in quantum technology have shown that quantum computer can provide a dramatic advantage over classical computers for some algorithms. In particular, a polynomial-time algorithm for factoring, a problem which was previously thought to be hard for classical computers, has recently been developed [13]. Similarly, a quantum algorithm searching for unsorted database in square root of time it would take on a classical computer has also been described by Grover [4] - [3]. Both algorithms rely upon the inherent parallelism, superposition and entanglement property of quantum computing to achieve their improvements. Since most problems of real interest for genetic algorithms have a vast search space, it seems appropriate how quantum parallelism can be applied to Genetic Algorithms. In this paper we provide a brief background of quantum computers. We explain why and how quantum algorithms provides a fundamental improvements over classical ones for some problems. Further, we present here the Conventional Genetic Algorithm and the quantum approach of Genetical Algorithms(QGA) as well. The benefits and drawbacks of QGA are also analyzed. Moreover, this paper provides an improved version over the conventional QGA. This improvement originates from the best partial immigration technique applied to the quantum chromosomes. The main objective of the best partial immigration is to consider the string of qubits from the quantum chromosomes having best fitness and transfer the same randomly to the chromosomes of next generation for better mixing. The process is reiterated. To observe the performance the best partial immigration technique we have considered some popular optimization problems and performed the experiment on it. These problems are namely Travelling Salesman Problem(TSP), Binpacking Problem and Vertex Cover Problem. It has been observed that the obtained results outperforms the conventional QGA.
This paper presents a theory and an empirical evaluation of Higher-Order Quantum-Inspired Genetic Algorithms. Fundamental notions of the theory have been introduced, and a novel Order-2 Quantum-Inspired Genetic Algorithm (QIGA2) has been presented. Contrary to all QIGA algorithms which represent quantum genes as independent qubits, in higher-order QIGAs quantum registers are used to represent genes strings which allows modelling of genes relations using quantum phenomena. Performance comparison has been conducted on a benchmark of 20 deceptive combinatorial optimization problems. It has been presented that using higher quantum orders is beneficial for genetic algorithm efficiency, and the new QIGA2 algorithm outperforms the old QIGA algorithm which was tuned in highly compute intensive metaoptimization process.