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

A High Performance Algorithm for Solving Maximum Independent Set Problem

Hager Hussein

Published Jun 24, 2025• 0 citations
Publisher

Abstract

Abstract Software engineering plays an important role in computer science. Novel quantum algorithms can efficiently solve software-engineering problems. Not only software engineering but also many industries including logistics, finance, genomics, resource allocation, logistics, bioinformatics, mobile agents and more have optimization problems. Such problems may have long time solutions [15]. Research has been conducted to improve the performance of current solutions and to search for optimized solutions. Search-based software engineering (SBSE) uses computational techniques to determine optimized solutions in a large search space. There are SBSE problems such as Test Suite Minimization (TSM) and Maximum Independent Set (MIS) that require efficient solutions due to its important role. A quantum-inspired genetic algorithm had solved the TSM problem with higher performance than classical solutions [10]. The quantum-inspired genetic algorithm and quantum algorithm showed better performance results than classical solutions. This improvement motivated us to modify such algorithms in order to solve the MIS optimization problems [24, 25]. In addition, MIS has crucial applications in many domains. It can be applied in software engineering to separate related and unrelated requirements, which is of great support for project management. Resources, time, cost, and relevance can be updated accordingly. MIS can also be applied in network design, scheduling, resource allocation, logistics, bioinformatics, mobile agents, and more [17]. Quantum-inspired genetic algorithm combines quantum mechanics concepts and genetic algorithms which enhances search capability and provides efficient search mechanism [19]. In this study, a modified quantum-inspired genetic algorithm (QIGA) is proposed and implemented to find an optimized solution for the MIS problem. A classical genetic algorithm (GA) is implemented and has been tested. A Comparison is conducted to show the results of QIGA and GA to measure the performance improvement. Results and its analysis are displayed to show QIGA and GA convergence. The proposed algorithm has no prior assumptions.

DOI
10.21203/rs.3.rs-6951517/v1

Related papers

Quantum-Inspired Genetic Algorithm for Complex Optimization Problems

Jincheng Zhang

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. ---

•Sep 3, 2026•0 citations

Adaptive Quantum Inspired Genetic Algorithm for Combinatorial Optimization Problems

Jyoti Chaturvedi

The development in the field of quantum computing gives us a significant edge over classical computing in terms of time and efficiency.This is particularly useful for NP-hard problems such as graph layout problems.Since many real world problems are effectively solved by genetic algorithm (GA) and the performance of GA highly depends upon the setting of its parameters, therefore this paper focuses on a Quantum Inspired Genetic Algorithm (QIGA) and develops and evaluates adaptive strategies for the same.QIGA adapts ideas of Q-bits, superposition of Q-bits from quantum computing.The effectiveness and the applicability of adaptive QIGA is demonstrated by experimental results on the benchmark Knapsack, Maxcut and Onemax combinatorial optimization problems.The results show that adaptive QIGA is superior to QIGAs.

International Journal of Computer Applications•Dec 18, 2014•3 citations

Quantum-Inspired Genetic Algorithms for Large-Scale Optimization

Andrei Popescu

Large-scale optimization (LSO) problems—those with hundreds to thousands of decision variables—are prevalent in engineering design, logistics, telecommunications, and machine learning hyperparameter search. Classical evolutionary algorithms often struggle in this regime due to premature convergence and prohibitive search costs. This manuscript presents a Quantum-Inspired Genetic Algorithm (QIGA) that transfers three ideas from quantum computation into a purely classical algorithm: (i) Q-bit angle encoding that maintains a compact, uncertainty-aware distribution over decision values, (ii) rotation-gate adaptation that updates search probabilities toward promising regions while preserving exploration, and (iii) quantum observation that draws diverse candidate solutions from the encoded amplitudes at each generation. We further couple the core QIGA with (a) an island-model decomposition for ultra-high dimensionality, (b) surrogate-assisted local refinement for exploitation at low cost, and (c) a feasibility-aware penalty for constraints. We evaluate the approach on five canonical continuous benchmarks in 1,000 dimensions (Sphere, Rosenbrock, Rastrigin, Ackley, Griewank) under a fixed computational budget. Across 30 independent runs per function, QIGA achieves lower final objective values and higher success rates than classical GA, PSO, and DE baselines. A non-parametric Wilcoxon signed-rank test indicates statistically significant improvements for QIGA (adjusted p < 0.01) on all functions. We analyze the algorithm’s scaling behavior, the role of angle-space step control, and the contribution of island-level diversity. The results suggest that quantum-inspired probability evolution provides a robust inductive bias for LSO by decoupling representation capacity from point estimates and by enabling distribution-aware search moves. We conclude with practical guidelines for tuning and discuss extensions to constrained and mixed-variable problems.

International Journal of Advanced Research in Computer Science and Engineering•Apr 4, 2026•0 citations

Pengembangan Algoritma Kuantum Terinspirasi untuk Penyelesaian Masalah Optimasi Kompleks dalam Ilmu Komputasi

Yona Eka Pratiwi, Renatalia Fika

Quantum-Inspired Algorithms (QIAs) combine principles of quantum computing with classical evolutionary strategies to address complex optimization problems. This research explores the potential of QIAs in improving optimization processes, particularly in combinatorial and multi-objective optimization scenarios. The study focuses on the application of Quantum-Inspired Genetic Algorithms (QIGAs) and Quantum-Inspired Evolutionary Algorithms (QIEAs), assessing their effectiveness in solving classical problems like the Traveling Salesman Problem (TSP) and Minimum Spanning Tree (MST). Through computational simulations, the research compares the time convergence and solution accuracy of QIAs against traditional classical algorithms. The findings demonstrate that QIAs achieve faster convergence rates and higher-quality solutions, with accuracy levels reaching 98-99% of the global optimal solutions, while significantly reducing computational time. These results underline the advantages of QIAs in solving large and complex optimization problems, making them a promising alternative to traditional algorithms. Additionally, QIAs excel in avoiding local minima, a common pitfall of classical methods, due to their ability to explore the solution space more efficiently through quantum principles like superposition and interference. The implications of this study suggest that QIAs can be a valuable tool for tackling real-world optimization challenges, with potential applications in fields such as finance, logistics, telecommunications, and energy management. The research also indicates the necessity for further improvements in quantum-inspired algorithms' scalability and hardware integration, particularly for larger, more intricate optimization problems, to fully realize their potential in practical industrial applications.

Journal of New Trends in Sciences•May 30, 2023•0 citations

Higher-Order Quantum-Inspired Genetic Algorithms

Robert Nowotniak, Jacek Kucharski

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.

arXiv:1407.0977•Jul 2, 2014•0 citations

Higher-Order Quantum-Inspired Genetic Algorithms

Robert Nowotniak, Jacek Kucharski

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 developed.Contrary to all QIGA algorithms which represent quantum genes as independent qubits, in higherorder 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 tuned in highly compute-intensive metaoptimization process.

Annals of Computer Science and Information Systems•Sep 29, 2014•15 citations
Abstract Software engineering plays an important role in computer science. Novel quantum algorithms can efficiently solve software-engineering problems. Not only software engineering but also many industries including logistics, finance, genomics, resource allocation, logistics, bioinformatics, mobile agents and more have optimization problems. Such problems may have long time solutions [15]. Research has been conducted to improve the performance of current solutions and to search for optimized solutions. Search-based software engineering (SBSE) uses computational techniques to determine optimized solutions in a large search space. There are SBSE problems such as Test Suite Minimization (TSM) and Maximum Independent Set (MIS) that require efficient solutions due to its important role. A quantum-inspired genetic algorithm had solved the TSM problem with higher performance than classical solutions [10]. The quantum-inspired genetic algorithm and quantum algorithm showed better performance results than classical solutions. This improvement motivated us to modify such algorithms in order to solve the MIS optimization problems [24, 25]. In addition, MIS has crucial applications in many domains. It can be applied in software engineering to separate related and unrelated requirements, which is of great support for project management. Resources, time, cost, and relevance can be updated accordingly. MIS can also be applied in network design, scheduling, resource allocation, logistics, bioinformatics, mobile agents, and more [17]. Quantum-inspired genetic algorithm combines quantum mechanics concepts and genetic algorithms which enhances search capability and provides efficient search mechanism [19]. In this study, a modified quantum-inspired genetic algorithm (QIGA) is proposed and implemented to find an optimized solution for the MIS problem. A classical genetic algorithm (GA) is implemented and has been tested. A Comparison is conducted to show the results of QIGA and GA to measure the performance improvement. Results and its analysis are displayed to show QIGA and GA convergence. The proposed algorithm has no prior assumptions.
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. ---
The development in the field of quantum computing gives us a significant edge over classical computing in terms of time and efficiency.This is particularly useful for NP-hard problems such as graph layout problems.Since many real world problems are effectively solved by genetic algorithm (GA) and the performance of GA highly depends upon the setting of its parameters, therefore this paper focuses on a Quantum Inspired Genetic Algorithm (QIGA) and develops and evaluates adaptive strategies for the same.QIGA adapts ideas of Q-bits, superposition of Q-bits from quantum computing.The effectiveness and the applicability of adaptive QIGA is demonstrated by experimental results on the benchmark Knapsack, Maxcut and Onemax combinatorial optimization problems.The results show that adaptive QIGA is superior to QIGAs.
Large-scale optimization (LSO) problems—those with hundreds to thousands of decision variables—are prevalent in engineering design, logistics, telecommunications, and machine learning hyperparameter search. Classical evolutionary algorithms often struggle in this regime due to premature convergence and prohibitive search costs. This manuscript presents a Quantum-Inspired Genetic Algorithm (QIGA) that transfers three ideas from quantum computation into a purely classical algorithm: (i) Q-bit angle encoding that maintains a compact, uncertainty-aware distribution over decision values, (ii) rotation-gate adaptation that updates search probabilities toward promising regions while preserving exploration, and (iii) quantum observation that draws diverse candidate solutions from the encoded amplitudes at each generation. We further couple the core QIGA with (a) an island-model decomposition for ultra-high dimensionality, (b) surrogate-assisted local refinement for exploitation at low cost, and (c) a feasibility-aware penalty for constraints. We evaluate the approach on five canonical continuous benchmarks in 1,000 dimensions (Sphere, Rosenbrock, Rastrigin, Ackley, Griewank) under a fixed computational budget. Across 30 independent runs per function, QIGA achieves lower final objective values and higher success rates than classical GA, PSO, and DE baselines. A non-parametric Wilcoxon signed-rank test indicates statistically significant improvements for QIGA (adjusted p < 0.01) on all functions. We analyze the algorithm’s scaling behavior, the role of angle-space step control, and the contribution of island-level diversity. The results suggest that quantum-inspired probability evolution provides a robust inductive bias for LSO by decoupling representation capacity from point estimates and by enabling distribution-aware search moves. We conclude with practical guidelines for tuning and discuss extensions to constrained and mixed-variable problems.
Quantum-Inspired Algorithms (QIAs) combine principles of quantum computing with classical evolutionary strategies to address complex optimization problems. This research explores the potential of QIAs in improving optimization processes, particularly in combinatorial and multi-objective optimization scenarios. The study focuses on the application of Quantum-Inspired Genetic Algorithms (QIGAs) and Quantum-Inspired Evolutionary Algorithms (QIEAs), assessing their effectiveness in solving classical problems like the Traveling Salesman Problem (TSP) and Minimum Spanning Tree (MST). Through computational simulations, the research compares the time convergence and solution accuracy of QIAs against traditional classical algorithms. The findings demonstrate that QIAs achieve faster convergence rates and higher-quality solutions, with accuracy levels reaching 98-99% of the global optimal solutions, while significantly reducing computational time. These results underline the advantages of QIAs in solving large and complex optimization problems, making them a promising alternative to traditional algorithms. Additionally, QIAs excel in avoiding local minima, a common pitfall of classical methods, due to their ability to explore the solution space more efficiently through quantum principles like superposition and interference. The implications of this study suggest that QIAs can be a valuable tool for tackling real-world optimization challenges, with potential applications in fields such as finance, logistics, telecommunications, and energy management. The research also indicates the necessity for further improvements in quantum-inspired algorithms' scalability and hardware integration, particularly for larger, more intricate optimization problems, to fully realize their potential in practical industrial applications.
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.
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 developed.Contrary to all QIGA algorithms which represent quantum genes as independent qubits, in higherorder 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 tuned in highly compute-intensive metaoptimization process.