Quantum computing proved good results and performance when applied to solving optimization problems. This paper proposes a quantum crossover-based quantum genetic algorithm (QXQGA) for solving non-linear programming. Due to the significant role of mutation function on the QXQGA's quality, a number of quantum crossover and quantum mutation operators are presented for improving the capabilities of searching, overcoming premature convergence, and keeping diversity of population. For calibrating the QXQGA, the quantum crossover and mutation operators are evaluated using relative percentage deviation for selecting the best combination. In addition, a set of non-linear problems is used as benchmark functions to illustrate the effectiveness of optimizing the complexities with different dimensions, and the performance of the proposed QXQGA algorithm is compared with the quantum inspired evolutionary algorithm to demonstrate its superiority.
Quantum computing proved good results and performance when applied to solving optimization problems. This paper proposes a quantum crossover-based quantum genetic algorithm (QXQGA) for solving non-linear programming. Due to the significant role of mutation function on the QXQGA's quality, a number of quantum crossover and quantum mutation operators are presented for improving the capabilities of searching, overcoming premature convergence, and keeping diversity of population. For calibrating the QXQGA, the quantum crossover and mutation operators are evaluated using relative percentage deviation for selecting the best combination. In addition, a set of non-linear problems is used as benchmark functions to illustrate the effectiveness of optimizing the complexities with different dimensions, and the performance of the proposed QXQGA algorithm is compared with the quantum inspired evolutionary algorithm to demonstrate its superiority.
In the literature, there are many Quantum Inspired Evolutionary Algorithms (QIEA) that proved good performance and results when applied to solving a myriad of problems. However, the real quantum representation increases precision for numerical optimisation problems and reduces the memory storage need, alternatively to the binary representation. On the other hand, evolutionary algorithms' performance mainly depends on the crossover and mutation operators, reaching equilibrium between the explorative and exploitative features of evolutionary algorithms. This paper proposes new quantum genetic operators for real quantum representation, instead of the 1/5 rule present in AEIQ-R, to improve the performance of the quantum genetic algorithm with real representation. Three crossover and two mutation operators are proposed and tested to optimise four functions with different dimensions. Friedman's test indicated a significant difference between the combinations, and that combination composed of quantum arithmetic crossover and quantum creep mutation have the best performance.
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.
We propose a gate-based Quantum Genetic Algorithm (QGA) for real-valued global optimization. In this model, individuals are represented by quantum circuits whose measurement outcomes are decoded into real-valued vectors through binary discretization. Evolutionary operators act directly on circuit structures, allowing mutation and crossover to explore the space of gate-based encodings. Both fixed-depth and variable-depth variants are introduced, enabling either uniform circuit complexity or adaptive structural evolution. Fitness is evaluated through quantum sampling, using the mean decoded output of measurement outcomes as the argument of the objective function. To isolate the impact of quantum resources, we compare gate sets with and without the Hadamard gate, showing that superposition consistently improves convergence and robustness across benchmark functions such as the Rastrigin function. Furthermore, we demonstrate that introducing pairwise inter-individual entanglement in the population accelerates early convergence, revealing that quantum correlations among individuals provide an additional optimization advantage. Together, these results show that both superposition and entanglement enhance the search dynamics of evolutionary quantum algorithms, establishing gate-based QGAs as a promising framework for quantum-enhanced global optimization.
This paper proposes a novel evolutionary computing method called a genetic quantum algorithm (GQA). GQA is based on the concept and principles of quantum computing such as qubits and superposition of states. Instead of binary, numeric, or symbolic representation, by adopting qubit chromosome as a representation GQA can represent a linear superposition of solutions due to its probabilistic representation. As genetic operators, quantum gates are employed for the search of the best solution. Rapid convergence and good global search capability characterize the performance of GQA. The effectiveness and the applicability of GQA are demonstrated by experimental results on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that GQA is superior to other genetic algorithms using penalty functions, repair methods and decoders.
This paper explores the application of a quantum-inspired genetic algorithm (QIGA) for solving complex optimization problems. Traditional genetic algorithms (GAs) can struggle with the intricacies of high-dimensional and non-linear problems, often encountering issues with premature convergence and local optima. This research proposes a novel approach where a standard GA is modified to incorporate principles inspired by quantum mechanics, specifically utilizing quantum-inspired concepts such as superposition and interference, to enhance the exploration and exploitation phases. The core claim is that QIGA can effectively tackle complex optimization scenarios. The mechanism involves mapping the original problem into the fitness function of the GA, and subsequently using the QIGA to perform the optimization. The results demonstrate the potential of this hybrid approach to improve solution quality and speed, particularly in problems with challenging characteristics. The research highlights a promising direction for combining classical optimization techniques with quantum-inspired ideas, offering a new tool for tackling computationally intensive optimization tasks. ---
Based on quantum genetic algorithm(QGA),a novel improved quantum genetic algorithm(NIQGA)to solve combinatorial optimization problem is proposed.To make full use of interference and entanglement characteristics of quantum state,dynamic step length in adjustment of angle of quantum gate,quantum crossover operation and quantum mutation operation are introduced,therefore high efficiency for optimization is achieved.Two typical combinatorial optimization problems—0/1 knapsack problem and route selection problem,are adopted to confirm the performance of NIQGA.Experimental results show that compared with GA and QGA,NIQGA is characterized by fast convergence rate and excellent capability on global optimization,especially better performance for combinatorial optimization problem with less correlation of genes.