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

Quantum Annealing for Solving a Nurse-physician Scheduling Problem in Covid-19 Clinics

Kunal K. Das, Sahil Zaman, Arindam Sadhu, Asmita Banerjee, Faisal Shah Khan

Published Aug 1, 2020• 6 citations
OpenAlex

Abstract

Quantum annealing (QA) is a metaheuristic methodologythat has recently been used to analyze the performance of first generation adiabatic quantum processors, like the oneavailable from D-wave Systems, in solving combinatorial optimization problems. In this paper, we formulate QA representation of problems essential to mitigating the effects of the COVID-19 pandemic, namely, the Nurse Scheduling Problem (NSP), the Physician Scheduling Problem (PSP), and the Nurse-Physician Scheduling Problem (NPSP). The proposed objective functions for each problem are scripted to the Ising model and then transformed into thequadratic unconstrained binary optimization (QUBO)format. An optimal solutionis soughtfor a set of constraints, including thenumber ofnurses or physicians per shift andthe maximum number of shifts for each nurse or physician.After reducingtheproposed NSP, PSP, and NPSP QUBOs to a novel Ising type Hamiltonian, we obtain solutions from a classical (simulated) annealer,and then from the D-wave 2000Q forward and reverse annealer. Results from the reverse quantum annealer show a dramatic improvement in solution quality as compared to those from the classical annealer. We observe that the reverse annealing method gives us the most satisfactory output from among three heuristic processes used, for each scheduling problem.

Related papers

Application of Quantum Annealing to Nurse Scheduling Problem

Kazuki Ikeda, Yuma Nakamura, Travis S. Humble

Quantum annealing is a promising heuristic method to solve combinatorial optimization problems, and efforts to quantify performance on real-world problems provide insights into how this approach may be best used in practice. We investigate the empirical performance of quantum annealing to solve the Nurse Scheduling Problem (NSP) with hard constraints using the D-Wave 2000Q quantum annealing device. NSP seeks the optimal assignment for a set of nurses to shifts under an accompanying set of constraints on schedule and personnel. After reducing NSP to a novel Ising-type Hamiltonian, we evaluate the solution quality obtained from the D-Wave 2000Q against the constraint requirements as well as the diversity of solutions. For the test problems explored here, our results indicate that quantum annealing recovers satisfying solutions for NSP and suggests the heuristic method is potentially achievable for practical use. Moreover, we observe that solution quality can be greatly improved through the use of reverse annealing, in which it is possible to refine returned results by using the annealing process a second time. We compare the performance of NSP using both forward and reverse annealing methods and describe how this approach might be used in practice.

arXiv:1904.12139•Scientific Reports•Sep 6, 2019•139 citations

Quantum optimization for the Physician Scheduling Problem

Baha Mlaouhi, Chahid Ahabchane, Iyed Benslimen

Scheduling medical staff in healthcare institutions is a complex and critical task that requires balancing operational constraints, personnel availability, quality of care, and staff well-being. These interdependent factors make the creation of optimal schedules particularly challenging necessitating sophisticated approaches that effectively reconcile institutional needs and medical staff expectations. This project explores an innovative alternative approach: quantum optimization. By formulating the scheduling problem as a QUBO (Quadratic Unconstrained Binary Optimization) model, we aim to leverage the capabilities of quantum algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA) This framework allows constraints and objectives to be reformulated as quadratic functions, facilitating their integration into Ising models and their resolution on quantum gate_based circuit systems.To this end, we implement a hybrid quantum-classical solution using QAOA on IBM’s Qiskit platform. We analyze QAOA’s performance on problem instances of up to 27 qubits, and compare it against classical solvers such as CPLEX. Through this comparative approach, we assess the practical viability of quantum optimization in medical staff scheduling and contribute to the broader investigation of quantum computing in operational planning within healthcare systems.

International Conference on Embedded Systems and Artificial Intelligence (ESAI)•Dec 18, 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

Solving the resource constrained project scheduling problem with quantum annealing

Luis Fernando Pérez Armas, Stefan Creemers, Samuel Deleplanque

Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing to solve the RCPSP, analyzing 12 well-known mixed integer linear programming (MILP) formulations and converting the most qubit-efficient one into a quadratic unconstrained binary optimization (QUBO) model. We then solve this model using the D-wave advantage 6.3 quantum annealer, comparing its performance against classical computer solvers. Our results indicate significant potential, particularly for small to medium-sized instances. Further, we introduce time-to-target and Atos Q-score metrics to evaluate the effectiveness of quantum annealing and reverse quantum annealing. The paper also explores advanced quantum optimization techniques, such as customized anneal schedules, enhancing our understanding and application of quantum computing in operations research.

Scientific Reports•Jul 22, 2024•30 citations

Applying Quantum Annealing for Shift Scheduling Problem for Call Centers

Natsuki Hamada, Kazuhiro Saito, Hideyuki Kawashima

Quantum annealing (QA) has shown good solutions quickly in benchmarks of combinatorial optimization problems. There are not many real-world problems that illustrate the effectiveness of QA compared to the typical optimization methods. We applied QA to a shift scheduling problem for call centers with four conditions. The shift scheduling problem for call centers optimizes shifts for a specific period of time while satisfying various constraints, such as satisfying the desired worker's shifts. In this paper, we formulated the shift scheduling problem for call centers in QUBO to apply QA. We tuned various parameters required to execute the QA. Then, we compared QA with six typical optimization methods using a classical computer to investigate QA's effectiveness for the shift scheduling problem for call centers. The results show that for three instances with up to 126 variables, QA is about 3-14 times faster than other methods and obtains enough quality of solutions. This shows that QA can be one of the effective methods to solve practical applications in the real-world.

International Journal of Networking and Computing•Jan 1, 2023•4 citations

Quantum Annealing versus Digital Computing

Michael Jünger, Elisabeth Lobe, Petra Mutzel +4 more

Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.

arXiv:1904.11965•ACM Journal of Experimental Algorithmics•Jul 9, 2021•48 citations
Quantum annealing (QA) is a metaheuristic methodologythat has recently been used to analyze the performance of first generation adiabatic quantum processors, like the oneavailable from D-wave Systems, in solving combinatorial optimization problems. In this paper, we formulate QA representation of problems essential to mitigating the effects of the COVID-19 pandemic, namely, the Nurse Scheduling Problem (NSP), the Physician Scheduling Problem (PSP), and the Nurse-Physician Scheduling Problem (NPSP). The proposed objective functions for each problem are scripted to the Ising model and then transformed into thequadratic unconstrained binary optimization (QUBO)format. An optimal solutionis soughtfor a set of constraints, including thenumber ofnurses or physicians per shift andthe maximum number of shifts for each nurse or physician.After reducingtheproposed NSP, PSP, and NPSP QUBOs to a novel Ising type Hamiltonian, we obtain solutions from a classical (simulated) annealer,and then from the D-wave 2000Q forward and reverse annealer. Results from the reverse quantum annealer show a dramatic improvement in solution quality as compared to those from the classical annealer. We observe that the reverse annealing method gives us the most satisfactory output from among three heuristic processes used, for each scheduling problem.
Quantum annealing is a promising heuristic method to solve combinatorial optimization problems, and efforts to quantify performance on real-world problems provide insights into how this approach may be best used in practice. We investigate the empirical performance of quantum annealing to solve the Nurse Scheduling Problem (NSP) with hard constraints using the D-Wave 2000Q quantum annealing device. NSP seeks the optimal assignment for a set of nurses to shifts under an accompanying set of constraints on schedule and personnel. After reducing NSP to a novel Ising-type Hamiltonian, we evaluate the solution quality obtained from the D-Wave 2000Q against the constraint requirements as well as the diversity of solutions. For the test problems explored here, our results indicate that quantum annealing recovers satisfying solutions for NSP and suggests the heuristic method is potentially achievable for practical use. Moreover, we observe that solution quality can be greatly improved through the use of reverse annealing, in which it is possible to refine returned results by using the annealing process a second time. We compare the performance of NSP using both forward and reverse annealing methods and describe how this approach might be used in practice.
Scheduling medical staff in healthcare institutions is a complex and critical task that requires balancing operational constraints, personnel availability, quality of care, and staff well-being. These interdependent factors make the creation of optimal schedules particularly challenging necessitating sophisticated approaches that effectively reconcile institutional needs and medical staff expectations. This project explores an innovative alternative approach: quantum optimization. By formulating the scheduling problem as a QUBO (Quadratic Unconstrained Binary Optimization) model, we aim to leverage the capabilities of quantum algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA) This framework allows constraints and objectives to be reformulated as quadratic functions, facilitating their integration into Ising models and their resolution on quantum gate_based circuit systems.To this end, we implement a hybrid quantum-classical solution using QAOA on IBM’s Qiskit platform. We analyze QAOA’s performance on problem instances of up to 27 qubits, and compare it against classical solvers such as CPLEX. Through this comparative approach, we assess the practical viability of quantum optimization in medical staff scheduling and contribute to the broader investigation of quantum computing in operational planning within healthcare systems.
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.
Quantum annealing emerges as a promising approach for tackling complex scheduling problems such as the resource-constrained project scheduling problem (RCPSP). This study represents the first application of quantum annealing to solve the RCPSP, analyzing 12 well-known mixed integer linear programming (MILP) formulations and converting the most qubit-efficient one into a quadratic unconstrained binary optimization (QUBO) model. We then solve this model using the D-wave advantage 6.3 quantum annealer, comparing its performance against classical computer solvers. Our results indicate significant potential, particularly for small to medium-sized instances. Further, we introduce time-to-target and Atos Q-score metrics to evaluate the effectiveness of quantum annealing and reverse quantum annealing. The paper also explores advanced quantum optimization techniques, such as customized anneal schedules, enhancing our understanding and application of quantum computing in operations research.
Quantum annealing (QA) has shown good solutions quickly in benchmarks of combinatorial optimization problems. There are not many real-world problems that illustrate the effectiveness of QA compared to the typical optimization methods. We applied QA to a shift scheduling problem for call centers with four conditions. The shift scheduling problem for call centers optimizes shifts for a specific period of time while satisfying various constraints, such as satisfying the desired worker's shifts. In this paper, we formulated the shift scheduling problem for call centers in QUBO to apply QA. We tuned various parameters required to execute the QA. Then, we compared QA with six typical optimization methods using a classical computer to investigate QA's effectiveness for the shift scheduling problem for call centers. The results show that for three instances with up to 126 variables, QA is about 3-14 times faster than other methods and obtains enough quality of solutions. This shows that QA can be one of the effective methods to solve practical applications in the real-world.
Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.