Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

PeerJ Computer Science

Hybrid quantum search with genetic algorithm optimization

Mihai Udrescu, Mihai Udrescu

Published Aug 5, 2024• 18 citations
Publisher

Abstract

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.

DOI
10.7717/peerj-cs.2210

Related papers

Hybrid quantum genetic algorithms and performance analysis

Ling Wang

Quantum algorithm (QA) with updating of quantum gates and catastrophe of population is compared with quantum genetic algorithm (QGA) by including crossover and mutation for quantum bits. Furthermore, a framework of hybrid quantum GA is proposed which combines the quantum based search and classic genetic search, and hybrid QGA with binary encoding (BQGA) and hybrid QGA with real encoding (RQGA) are presented. Numerical simulation on typical problems show that the performances of RQGA are the best among all testing algorithms and it is much robust on parameters and initial conditions.

Kongzhi yu juece•Jan 1, 2005•14 citations

Implementing quantum genetic algorithms: a solution based on Grover's algorithm

Mihai Udrescu, Lucian Prodan, Mircea Vlăduţiu

This paper presents a new methodology for running Genetic Algorithms on a Quantum Computer. To the best of our knowledge and according to reference [6]there are no feasible solutions for the implementation of the Quantum Genetic Algorithms (QGAs). We present a new perspective on how to build the corresponding QGA architecture. It turns out that the genetic strategy is not particularly helpful in our quantum computation approach; therefore our solution consists of designing a special-purpose oracle that will work with a modified version of an already known algorithm (maximum finding [1]), in order to reduce the QGAs to a Grover search. Quantum computation offers incentives for this approach, due to the fact that the qubit representation of the chromosome can encode the entire population as a superposition of basis-state values.

ACM International Conference on Computing Frontiers (CF)•May 3, 2006•36 citations

Optimization with Quantum Genetic Algorithm

Bhaskar Das, Utpal Roy

Recent development in quantum technology have shown that quan-tum computer can provide a dramatic advantage over classical com-puters for some algorithms. In particular, a polynomial-time algo-rithm 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 ap-plied to Genetic Algorithms. In this paper we provide a brief back-ground of quantum computers. We explain why and how quan-tum algorithms provides a fundamental improvements over classi-cal ones for some problems. Further, we present here the Conven-tional 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 con-ventional 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 fit-ness 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 con-ventional QGA. 1.

International Journal of Computer Applications•Sep 18, 2014•18 citations

Quantum Entanglement Genetic Algorithm

Jincheng Zhang

This paper proposes a novel approach to optimization problems by integrating quantum entanglement with the Genetic Algorithm (GA). The core idea is to leverage the inherent parallelism and enhanced information transfer capabilities of quantum entanglement to significantly improve the search performance of the GA. We represent genetic algorithm chromosomes as quantum states and employ quantum entanglement to facilitate rapid information exchange and crossover operations across multiple qubits. This mechanism allows for parallel exploration of the search space, mitigating the limitations of traditional GA's tendency towards local optima. The theoretical framework and the underlying principles are presented, demonstrating the potential for the Quantum Entanglement Genetic Algorithm (QGA) to accelerate the solution of complex optimization problems. The algorithm's effectiveness is discussed through a mathematical formulation, focusing on the key components of the QGA and its advantages over conventional GA. The ultimate goal is to demonstrate a robust and efficient method for tackling challenging optimization tasks.

•Sep 7, 2026•0 citations

Advances in quantum genetic algorithms

Dennis Lima, Rakesh Kumar Saini, Saif M. Al-Kuwari

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.

arXiv:2510.15059•Computer Science Review•Apr 24, 2026•0 citations

Quantum-Enhanced Genetic Algorithms for Complex Optimization

Jincheng Zhang

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.

•Sep 6, 2026•0 citations
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.
Quantum algorithm (QA) with updating of quantum gates and catastrophe of population is compared with quantum genetic algorithm (QGA) by including crossover and mutation for quantum bits. Furthermore, a framework of hybrid quantum GA is proposed which combines the quantum based search and classic genetic search, and hybrid QGA with binary encoding (BQGA) and hybrid QGA with real encoding (RQGA) are presented. Numerical simulation on typical problems show that the performances of RQGA are the best among all testing algorithms and it is much robust on parameters and initial conditions.
This paper presents a new methodology for running Genetic Algorithms on a Quantum Computer. To the best of our knowledge and according to reference [6]there are no feasible solutions for the implementation of the Quantum Genetic Algorithms (QGAs). We present a new perspective on how to build the corresponding QGA architecture. It turns out that the genetic strategy is not particularly helpful in our quantum computation approach; therefore our solution consists of designing a special-purpose oracle that will work with a modified version of an already known algorithm (maximum finding [1]), in order to reduce the QGAs to a Grover search. Quantum computation offers incentives for this approach, due to the fact that the qubit representation of the chromosome can encode the entire population as a superposition of basis-state values.
Recent development in quantum technology have shown that quan-tum computer can provide a dramatic advantage over classical com-puters for some algorithms. In particular, a polynomial-time algo-rithm 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 ap-plied to Genetic Algorithms. In this paper we provide a brief back-ground of quantum computers. We explain why and how quan-tum algorithms provides a fundamental improvements over classi-cal ones for some problems. Further, we present here the Conven-tional 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 con-ventional 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 fit-ness 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 con-ventional QGA. 1.
This paper proposes a novel approach to optimization problems by integrating quantum entanglement with the Genetic Algorithm (GA). The core idea is to leverage the inherent parallelism and enhanced information transfer capabilities of quantum entanglement to significantly improve the search performance of the GA. We represent genetic algorithm chromosomes as quantum states and employ quantum entanglement to facilitate rapid information exchange and crossover operations across multiple qubits. This mechanism allows for parallel exploration of the search space, mitigating the limitations of traditional GA's tendency towards local optima. The theoretical framework and the underlying principles are presented, demonstrating the potential for the Quantum Entanglement Genetic Algorithm (QGA) to accelerate the solution of complex optimization problems. The algorithm's effectiveness is discussed through a mathematical formulation, focusing on the key components of the QGA and its advantages over conventional GA. The ultimate goal is to demonstrate a robust and efficient method for tackling challenging optimization tasks.
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.
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.