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

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

Tilmann Schwenzow, Karen Wintersperger, Hila Safi, Oliver von Sicard, Christoph A. Niedermeier, Christoph Liebrecht, Jörg E. Franke, Sebastian Reitelshoefer

Published Sep 11, 2024• 0 citations
Publisher

Abstract

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.

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

Related papers

A quantum genetic algorithm for a parallel machine scheduling problem

Tilmann Schwenzow, Annika Lehnert, Christoph Liebrecht +2 more

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.

Journal of Combinatorial Optimization•Oct 18, 2025•1 citation

A case study of variational quantum algorithms for a job shop scheduling problem

David Amaro, Matthias Rosenkranz, Nathan Fitzpatrick +2 more

Abstract Combinatorial optimization models a vast range of industrial processes aiming at improving their efficiency. In general, solving this type of problem exactly is computationally intractable. Therefore, practitioners rely on heuristic solution approaches. Variational quantum algorithms are optimization heuristics that can be demonstrated with available quantum hardware. In this case study, we apply four variational quantum heuristics running on IBM’s superconducting quantum processors to the job shop scheduling problem. Our problem optimizes a steel manufacturing process. A comparison on 5 qubits shows that the recent filtering variational quantum eigensolver (F-VQE) converges faster and samples the global optimum more frequently than the quantum approximate optimization algorithm (QAOA), the standard variational quantum eigensolver (VQE), and variational quantum imaginary time evolution (VarQITE). Furthermore, F-VQE readily solves problem sizes of up to 23 qubits on hardware without error mitigation post processing.

arXiv:2109.03745•EPJ Quantum Technology•Feb 10, 2022•82 citations

Exploring Quantum Computing Algorithms for Effective Task Scheduling in Computing Systems

Prathamesh Vijay Lahande, Akshay Lokare, Indrajeet Kedari

Task scheduling is a critical problem within the modern underlying computing infrastructure, where resource overload causes a direct impact on the cost and time performance metrics, leading to increased latency, excessive financial cost, and overall poor throughput. Traditional scheduling algorithms are normally fixed and lack the strong exploration and exploitation processes, hence limiting their effectiveness when faced with large problems in scheduling, which are NP-hard. The current work investigates Quantum Computing (QC)-algorithms including Grover, the Variational Quantum Eigensolver (VQE) and Quantum Annealing (QA). This research work includes an extensive experiment conducted in the WorkflowSim simulator with heterogeneous task-scheduling performed with diverse Virtual Machine (VM) configurations. The performance-metrics considered for their comparison include cost and time, along with Relative Performance Index (RPI). The experimental results indicate that QC-algorithm QA achieves higher cost-efficiency, with an average cost reduction of 4 % compared to Grover and 25% compared to VQE, with a corresponding average reduction in time of about 14 % compared to Grover. VQE provides competitive behavior with particular VM configurations but provides poor stability behavior with a wider range of parameters. Statistical evaluations using five regression provides the Grover algorithm to have a superior predictive stability and stronger goodness-of-fit concerning cost and time compared to QA and VQE. Future research will be directed towards the design of hybrid quantum-classical scheduling systems and inclusion of additional performance indicators (including energy efficiency and throughput) and testing the mentioned systems on real quantum equipment to evaluate scalability and real-world feasibility in computational environments.

World Conference on Computational Science and Technology (WcCST)•Mar 26, 2026•0 citations

Enhancing computational accuracy with parallel parameter optimization in variational quantum eigensolver

Daisuke Tsukayama, Jun‐ichi Shirakashi, Tetsuo Shibuya +1 more

Variational quantum algorithms have promising applications in noisy intermediate-scale quantum (NISQ) devices. These algorithms rely on a classical optimization outer loop that minimizes a parameterized quantum circuit function. The optimization in variational quantum eigensolver (VQE) is NP-hard, meaning that finding the optimal solution is infeasible in the worst-case scenario. One way to address this challenge is through parallel optimization of parameters using multiple-parameterized quantum circuits. However, this approach is unsuitable for cloud-based quantum processing unit utilization due to the increased number of quantum circuit executions. Although NISQ devices have limitations in terms of gate depth, their size has been growing in recent years. Therefore, implementing multiple-parameterized quantum circuits in NISQ devices can suppress the increase in the number of executions. In this study, we propose a parallel-VQE, which leverages the parallel execution of parameterized quantum circuits to perform parallel parameter optimization in VQE, achieving convergence to solutions closer to the ground state. We validate the effectiveness of parallel-VQE in solving the random weighted max-cut problem using numerical simulations and a real quantum device. We present the results of running up to six circuits in parallel (120 qubits) and demonstrate the advantages of using multiple units to improve computational accuracy. This study provides a potential method for solving eigenvalue problems and combinatorial optimization problems for future quantum devices.

AIP Advances•Jan 1, 2025•8 citations

Comparative studies of optimizer performance in a variational quantum eigensolver

Qing Lü

Quantum computation holds the seminal key to overcoming inherent limitations of classical computing, potentially unlocking profound advancements across every scientific and industrial frontier. Currently and in the near future, variational quantum eigensolver (VQE) is one of the most promising algorithms in solving multi-body problems. Under the VQE framework, the classical optimizer plays a critical role in estimating expectation values. However, it is not well studied how different optimizers perform in a quantum circuit. The answer to this question helps make VQE applicable to larger systems. In this work, we scrutinize 12 optimizers on their convergence performances in VQE calculations by varying the number of qubits, depths of the quantum circuit, initial guesses, and number of measurements. It is found that gradient-based methods generally outperform the derivative-free methods. The optimizers involving stochastic processes usually fail to locate the minimum. The step length is far from trivial to reach the convergence. In addition, the Powell method is the most promising to alleviate the barren plateau problem.

The Journal of Chemical Physics•Dec 15, 2025•1 citation

A hybrid column generation-based heuristic for solving the parallel machine scheduling problem with sequence-dependent set-up times

Luis Fernando Pérez Armas, Samuel Deleplanque, Riad Aggoune +1 more

This study explores the application of a hybrid quantum-classical algorithm for solving the parallel machine scheduling problem (PMSP) with sequence-dependent set-up times, a pivotal scheduling problem that has applications in multiple industries. Using a column generation-based approach, we propose a heuristic that combines a classical linear relaxation for the master problem with quantum annealing (QA) for solving the pricing subproblem (PSP). Whereas the PSP generates columns (i.e. a sequence of jobs that are assigned to a machine), the master problem selects which columns to use in order to minimize the makespan of the schedule. To generate columns, the PSP solves a travelling salesman problem (TSP) that is formulated as a quadratic unconstrained binary optimization (QUBO) problem. The big advantage thereof is that subtours can be eliminated by use of quadratic terms in the objective function. In addition, our approach also leverages the quantum annealer's capability to generate many high-quality solutions (i.e. columns) in a very short time. To assess the performance of our hybrid column generation-based heuristic, we perform a computational experiment. The results of this experiment demonstrate the synergy of hybrid methods for tackling complex decision-making problems, achieving competitive high-quality solutions and computational advantages when compared with classical solution methods. This article is part of the theme issue 'Quantum theory and topology in models of decision making (Part 2)'.

Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Dec 11, 2025•2 citations
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.
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.
Abstract Combinatorial optimization models a vast range of industrial processes aiming at improving their efficiency. In general, solving this type of problem exactly is computationally intractable. Therefore, practitioners rely on heuristic solution approaches. Variational quantum algorithms are optimization heuristics that can be demonstrated with available quantum hardware. In this case study, we apply four variational quantum heuristics running on IBM’s superconducting quantum processors to the job shop scheduling problem. Our problem optimizes a steel manufacturing process. A comparison on 5 qubits shows that the recent filtering variational quantum eigensolver (F-VQE) converges faster and samples the global optimum more frequently than the quantum approximate optimization algorithm (QAOA), the standard variational quantum eigensolver (VQE), and variational quantum imaginary time evolution (VarQITE). Furthermore, F-VQE readily solves problem sizes of up to 23 qubits on hardware without error mitigation post processing.
Task scheduling is a critical problem within the modern underlying computing infrastructure, where resource overload causes a direct impact on the cost and time performance metrics, leading to increased latency, excessive financial cost, and overall poor throughput. Traditional scheduling algorithms are normally fixed and lack the strong exploration and exploitation processes, hence limiting their effectiveness when faced with large problems in scheduling, which are NP-hard. The current work investigates Quantum Computing (QC)-algorithms including Grover, the Variational Quantum Eigensolver (VQE) and Quantum Annealing (QA). This research work includes an extensive experiment conducted in the WorkflowSim simulator with heterogeneous task-scheduling performed with diverse Virtual Machine (VM) configurations. The performance-metrics considered for their comparison include cost and time, along with Relative Performance Index (RPI). The experimental results indicate that QC-algorithm QA achieves higher cost-efficiency, with an average cost reduction of 4 % compared to Grover and 25% compared to VQE, with a corresponding average reduction in time of about 14 % compared to Grover. VQE provides competitive behavior with particular VM configurations but provides poor stability behavior with a wider range of parameters. Statistical evaluations using five regression provides the Grover algorithm to have a superior predictive stability and stronger goodness-of-fit concerning cost and time compared to QA and VQE. Future research will be directed towards the design of hybrid quantum-classical scheduling systems and inclusion of additional performance indicators (including energy efficiency and throughput) and testing the mentioned systems on real quantum equipment to evaluate scalability and real-world feasibility in computational environments.
Variational quantum algorithms have promising applications in noisy intermediate-scale quantum (NISQ) devices. These algorithms rely on a classical optimization outer loop that minimizes a parameterized quantum circuit function. The optimization in variational quantum eigensolver (VQE) is NP-hard, meaning that finding the optimal solution is infeasible in the worst-case scenario. One way to address this challenge is through parallel optimization of parameters using multiple-parameterized quantum circuits. However, this approach is unsuitable for cloud-based quantum processing unit utilization due to the increased number of quantum circuit executions. Although NISQ devices have limitations in terms of gate depth, their size has been growing in recent years. Therefore, implementing multiple-parameterized quantum circuits in NISQ devices can suppress the increase in the number of executions. In this study, we propose a parallel-VQE, which leverages the parallel execution of parameterized quantum circuits to perform parallel parameter optimization in VQE, achieving convergence to solutions closer to the ground state. We validate the effectiveness of parallel-VQE in solving the random weighted max-cut problem using numerical simulations and a real quantum device. We present the results of running up to six circuits in parallel (120 qubits) and demonstrate the advantages of using multiple units to improve computational accuracy. This study provides a potential method for solving eigenvalue problems and combinatorial optimization problems for future quantum devices.
Quantum computation holds the seminal key to overcoming inherent limitations of classical computing, potentially unlocking profound advancements across every scientific and industrial frontier. Currently and in the near future, variational quantum eigensolver (VQE) is one of the most promising algorithms in solving multi-body problems. Under the VQE framework, the classical optimizer plays a critical role in estimating expectation values. However, it is not well studied how different optimizers perform in a quantum circuit. The answer to this question helps make VQE applicable to larger systems. In this work, we scrutinize 12 optimizers on their convergence performances in VQE calculations by varying the number of qubits, depths of the quantum circuit, initial guesses, and number of measurements. It is found that gradient-based methods generally outperform the derivative-free methods. The optimizers involving stochastic processes usually fail to locate the minimum. The step length is far from trivial to reach the convergence. In addition, the Powell method is the most promising to alleviate the barren plateau problem.
This study explores the application of a hybrid quantum-classical algorithm for solving the parallel machine scheduling problem (PMSP) with sequence-dependent set-up times, a pivotal scheduling problem that has applications in multiple industries. Using a column generation-based approach, we propose a heuristic that combines a classical linear relaxation for the master problem with quantum annealing (QA) for solving the pricing subproblem (PSP). Whereas the PSP generates columns (i.e. a sequence of jobs that are assigned to a machine), the master problem selects which columns to use in order to minimize the makespan of the schedule. To generate columns, the PSP solves a travelling salesman problem (TSP) that is formulated as a quadratic unconstrained binary optimization (QUBO) problem. The big advantage thereof is that subtours can be eliminated by use of quadratic terms in the objective function. In addition, our approach also leverages the quantum annealer's capability to generate many high-quality solutions (i.e. columns) in a very short time. To assess the performance of our hybrid column generation-based heuristic, we perform a computational experiment. The results of this experiment demonstrate the synergy of hybrid methods for tackling complex decision-making problems, achieving competitive high-quality solutions and computational advantages when compared with classical solution methods. This article is part of the theme issue 'Quantum theory and topology in models of decision making (Part 2)'.