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

arXiv:2109.03745 · EPJ Quantum Technology

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

David Amaro, Matthias Rosenkranz, Nathan Fitzpatrick, Koji Hirano, Mattia Fiorentini

Published Feb 10, 2022• 82 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1140/epjqt/s40507-022-00123-4

Related papers

A Non-Variational Quantum Approach to the Job Shop Scheduling Problem

Miguel Angel Lopez-Ruiz, Emily L. Tucker, Arnold, Emma M. +3 more

Quantum heuristics offer a potential advantage for combinatorial optimization but are constrained by near-term hardware limitations. We introduce Iterative-QAOA, a variant of QAOA designed to mitigate these constraints. The algorithm combines a non-variational, shallow-depth circuit approach using fixed-parameter schedules with an iterative warm-starting process. We benchmark the algorithm on Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) instances on IonQ Forte Generation QPUs, representing some of the largest such problems ever executed on quantum hardware. We compare the performance of the algorithm against both the Variational Quantum Imaginary Time Evolution (VarQITE) algorithm and the non-variational Linear Ramp (LR) QAOA algorithm. We find that Iterative-QAOA robustly converges to find optimal solutions as well as high-quality, near-optimal solutions for all problem instances evaluated. We evaluate the algorithm on larger problem instances up to 97 qubits using tensor network simulations. The scaling behavior of the algorithm indicates potential for solving industrial-scale problems on fault-tolerant quantum computers.

arXiv:2510.26859•Oct 30, 2025•0 citations

Solving the Job Shop Scheduling Problem: QUBO model and Quantum Annealing

Riad Aggoune, Samuel Deleplanque

Quantum optimization which is the use of quantum computers and algorithms for solving complex optimization problems, is one of the topics in quantum computing with the highest potential. Two types of approaches are generally used to solve combinatorial optimization problems with quantum computers: exact methods such as the Grover’s search algorithm, and meta-heuristics such as the Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA). Exact methods and variational methods like QAOA make use of universal gate-based quantum computers, such as the ones developed by the IBM company.Quantum annealing is designed for analogic quantum computers developed by D-Wave. Solving a combinatorial optimization problem with heuristics generally requires a transformation of the problem to a format suitable for the quantum computer. While some existing frameworks can cope with Constrained Quadratic Models (CQM), Quadratic Unconstrained Binary Optimization (QUBO) is the best option to map an optimization problem to a quantum computer or simulator. We consider in this paper the job shop scheduling problem.

•Apr 17, 2023•0 citations

Highly efficient encoding for job-shop scheduling problems and its application on quantum computers

Mathias Schmid, Sarah Braun, Rudolf Sollacher +1 more

Abstract Combinatorial optimization problems are considered to be an application, where quantum computing can have transformative impact. In the industrial context, job shop scheduling problems that aim at finding the optimal schedule for a set of jobs to be run on a set of machines are of immense interest. Here we introduce an efficient encoding of job shop scheduling problems, which requires much fewer bit-strings for counting all possible schedules than previously employed encodings. For problems consisting of N jobs with N operations, the number of required bit-strings is at least reduced by a factor N / log 2 ⁡ ( N ) as compared to time indexed encodings. This is particularly beneficial for solving job shop scheduling problems on quantum computers, since much fewer qubits are needed to represent the problem. Our approach applies to the large class of flexible and usual job-shop scheduling problems, where operations can possibly be executed on multiple machines. Using variational quantum algorithms, we show that the encoding we introduce leads to significantly better performance of quantum algorithms than previously considered strategies. Importantly, the encoding we develop also enables significantly more compact classical representations and will therefore be highly useful even beyond applicability on quantum hardware.

arXiv:2401.16381•Quantum Science and Technology•Dec 10, 2024•8 citations

Application of quantum approximate optimization algorithm to job shop scheduling problem

Krzysztof Kurowski, Tomasz Pecyna, Mateusz Slysz +3 more

The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.

European Journal of Operational Research•Mar 12, 2023•62 citations

Differentiable Quantum Architecture Search For Job Shop Scheduling Problem

Yize Sun, Jiarui Liu, Yunpu Ma +1 more

The Job shop scheduling problem (JSSP) plays a pivotal role in industrial applications, such as signal processing (SP) and steel manufacturing, involving sequencing machines and jobs to maximize scheduling efficiency. Before, JSSP was solved using manually defined circuits by variational quantum algorithm (VQA). Finding a good circuit architecture is task-specific and time-consuming. Differentiable quantum architecture search (DQAS) is a gradient-based framework that can automatically design circuits. However, DQAS is only tested on quantum approximate optimization algorithm (QAOA) and error mitigation tasks. Whether DQAS applies to JSSP based on a more flexible algorithm, such as variational quantum eigensolver (VQE), is still open for optimization problems. In this work, we redefine the operation pool and extend DQAS to a framework JSSP-DQAS by evaluating circuits to generate circuits for JSSP automatically. The experiments conclude that JSSP-DQAS can automatically find noise-resilient circuit architectures that perform much better than manually designed circuits. It helps to improve the efficiency of solving JSSP.

arXiv:2401.01158•IEEE International Conference on Acoustics Speech and Signal Processing•Mar 18, 2024•10 citations

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, 2024•0 citations
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.
Quantum heuristics offer a potential advantage for combinatorial optimization but are constrained by near-term hardware limitations. We introduce Iterative-QAOA, a variant of QAOA designed to mitigate these constraints. The algorithm combines a non-variational, shallow-depth circuit approach using fixed-parameter schedules with an iterative warm-starting process. We benchmark the algorithm on Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) instances on IonQ Forte Generation QPUs, representing some of the largest such problems ever executed on quantum hardware. We compare the performance of the algorithm against both the Variational Quantum Imaginary Time Evolution (VarQITE) algorithm and the non-variational Linear Ramp (LR) QAOA algorithm. We find that Iterative-QAOA robustly converges to find optimal solutions as well as high-quality, near-optimal solutions for all problem instances evaluated. We evaluate the algorithm on larger problem instances up to 97 qubits using tensor network simulations. The scaling behavior of the algorithm indicates potential for solving industrial-scale problems on fault-tolerant quantum computers.
Quantum optimization which is the use of quantum computers and algorithms for solving complex optimization problems, is one of the topics in quantum computing with the highest potential. Two types of approaches are generally used to solve combinatorial optimization problems with quantum computers: exact methods such as the Grover’s search algorithm, and meta-heuristics such as the Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA). Exact methods and variational methods like QAOA make use of universal gate-based quantum computers, such as the ones developed by the IBM company.Quantum annealing is designed for analogic quantum computers developed by D-Wave. Solving a combinatorial optimization problem with heuristics generally requires a transformation of the problem to a format suitable for the quantum computer. While some existing frameworks can cope with Constrained Quadratic Models (CQM), Quadratic Unconstrained Binary Optimization (QUBO) is the best option to map an optimization problem to a quantum computer or simulator. We consider in this paper the job shop scheduling problem.
Abstract Combinatorial optimization problems are considered to be an application, where quantum computing can have transformative impact. In the industrial context, job shop scheduling problems that aim at finding the optimal schedule for a set of jobs to be run on a set of machines are of immense interest. Here we introduce an efficient encoding of job shop scheduling problems, which requires much fewer bit-strings for counting all possible schedules than previously employed encodings. For problems consisting of N jobs with N operations, the number of required bit-strings is at least reduced by a factor N / log 2 ⁡ ( N ) as compared to time indexed encodings. This is particularly beneficial for solving job shop scheduling problems on quantum computers, since much fewer qubits are needed to represent the problem. Our approach applies to the large class of flexible and usual job-shop scheduling problems, where operations can possibly be executed on multiple machines. Using variational quantum algorithms, we show that the encoding we introduce leads to significantly better performance of quantum algorithms than previously considered strategies. Importantly, the encoding we develop also enables significantly more compact classical representations and will therefore be highly useful even beyond applicability on quantum hardware.
The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.
The Job shop scheduling problem (JSSP) plays a pivotal role in industrial applications, such as signal processing (SP) and steel manufacturing, involving sequencing machines and jobs to maximize scheduling efficiency. Before, JSSP was solved using manually defined circuits by variational quantum algorithm (VQA). Finding a good circuit architecture is task-specific and time-consuming. Differentiable quantum architecture search (DQAS) is a gradient-based framework that can automatically design circuits. However, DQAS is only tested on quantum approximate optimization algorithm (QAOA) and error mitigation tasks. Whether DQAS applies to JSSP based on a more flexible algorithm, such as variational quantum eigensolver (VQE), is still open for optimization problems. In this work, we redefine the operation pool and extend DQAS to a framework JSSP-DQAS by evaluating circuits to generate circuits for JSSP automatically. The experiments conclude that JSSP-DQAS can automatically find noise-resilient circuit architectures that perform much better than manually designed circuits. It helps to improve the efficiency of solving JSSP.
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.