Application of Quantum Annealing to Nurse Scheduling Problem

Area of Science:

• Quantum Computing
• Operations Research
• Heuristic Optimization

Background:

• Combinatorial optimization problems present significant computational challenges.
• Quantum annealing offers a novel heuristic approach for tackling these complex problems.
• The Nurse Scheduling Problem (NSP) is a critical real-world optimization task with numerous constraints.

Purpose of the Study:

• To empirically evaluate the performance of quantum annealing on the Nurse Scheduling Problem (NSP).
• To assess the solution quality and diversity generated by the D-Wave 2000Q quantum annealing device for NSP.
• To investigate the impact of reverse annealing on improving NSP solution quality.

Main Methods:

• Formulating the NSP as a novel Ising-type Hamiltonian.
• Utilizing the D-Wave 2000Q quantum annealing device for problem solving.
• Comparing forward and reverse annealing techniques for NSP solution refinement.

Main Results:

• Quantum annealing successfully recovered satisfying solutions for the NSP instances studied.
• The heuristic method demonstrated potential for practical application in scheduling.
• Reverse annealing significantly improved the quality of the obtained solutions.

Conclusions:

• Quantum annealing is a viable heuristic for solving the NSP with hard constraints.
• Reverse annealing is a valuable technique for refining quantum annealing results for NSP.
• The findings suggest quantum annealing's applicability to real-world optimization challenges.