Journal of Combinatorial Optimization

A quantum genetic algorithm for a parallel machine scheduling problem

Tilmann Schwenzow, Annika Lehnert, Christoph Liebrecht, Jörg E. Franke, Sebastian Reitelshöfer

Published Oct 18, 2025• 1 citation

Abstract

Abstract Scheduling problems are a common challenge across various industries. This paper addresses a specific problem arising in printed circuit board (PCB) assembly: the parallel machines scheduling problem with sequence-dependent setup times. To address this challenge, we propose a hybrid quantum genetic algorithm (QGA) designed to solve this problem on an error-free quantum computer. The development focuses on three key aspects: efficient adaptability of the quantum circuit to different problem instances, feasibility of the measured circuit outputs, and efficient utilization of qubits. To compare the quantum algorithm with its purely classical counterpart, we introduce a novel key performance indicator to quantify a potential quantum speedup. Furthermore, we evaluate the convergence behavior of the solver across various problem instances. Our results demonstrate that the QGA exhibits strong convergence behavior, resulting in near-optimal solutions. Additionally, we identify a potential quantum advantage for solving this practical problem. The advantage increases as the population size grows.

DOI: 10.1007/s10878-025-01347-7

Related papers

Investigating the Variational Quantum Eigensolver to solve scheduling for identical parallel machines with sequence-dependent setup-times

Tilmann Schwenzow, Karen Wintersperger, Hila Safi +5 more

Abstract Scheduling jobs on parallel identical machines with sequence-dependent setup times is a well-known NP-hard problem, which can be found in various industries such as the printed circuit board industry. We compare the performance of a classical exact solver and a hybrid quantum algorithm for solving this problem. As the classical exact solver, we introduce a Branch and Bound algorithm tailored to the problem. As for the quantum algorithm, we employ the Variational Quantum Eigensolver (VQE) and develop a dense encoding scheme that efficiently uses the limited number of qubits in a noise-free quantum computer simulation. For small problem instances, our results reveal that VQE shows a convergence behavior regarding the time to solution which is comparable to classical solvers. This initial approach for VQE solving the specific scheduling problem and its critical reflection lay the groundwork for identifying areas of inquiry for future research. Moreover, this work underscores the potential of quantum computing for solving complex optimization problems, which cannot be solved with classical solvers.

Sep 11, 20240 citations

Hybrid quantum search with genetic algorithm optimization

Sebastian Mihai Ardelean, Mihai Udrescu

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.

PeerJ Computer ScienceAug 5, 202414 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, 20260 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, 20260 citations

Two-Dimensional Quantum Genetic Algorithm: Application to Task Allocation Problem

Sabyasachi Mondal, Antonios Tsourdos

This paper presents a Two-Dimensional Quantum Genetic Algorithm (2D-QGA), which is a new variety of QGA. This variety will allow the user to take the advantages of quantum computation while solving the problems which are suitable for two-dimensional (2D) representation or can be represented in tabular form. The performance of 2D-QGA is compared to two-dimensional GA (2D-GA), which is used to solve two-dimensional problems as well. The comparison study is performed by applying both the algorithm to the task allocation problem. The performance of 2D-QGA is better than 2D-GA while comparing execution time, convergence iteration, minimum cost generated, and population size.

SensorsFeb 10, 20217 citations

Incorporating Quantum Advantage in Quantum Circuit Generation through Genetic Programming

Stein, Christoph, Michael Färber

Designing efficient quantum circuits that leverage quantum advantage compared to classical computing has become increasingly critical. Genetic algorithms have shown potential in generating such circuits through artificial evolution. However, integrating quantum advantage into the fitness function of these algorithms remains unexplored. In this paper, we aim to enhance the efficiency of quantum circuit design by proposing two novel approaches for incorporating quantum advantage metrics into the fitness function of genetic algorithms.1 We evaluate our approaches based on the Bernstein-Vazirani Problem and the Unstructured Database Search Problem as test cases. The results demonstrate that our approaches not only improve the convergence speed of the genetic algorithm but also produce circuits comparable to expert-designed solutions. Our findings suggest that automated quantum circuit design using genetic algorithms that incorporate a measure of quantum advantage is a promising approach to accelerating the development of quantum algorithms.

arXiv:2501.09682Jan 16, 20251 citation