Application of Quantum Annealing to Nurse Scheduling Problem
arXiv:1904.12139 · doi:10.1038/s41598-019-49172-3
Abstract
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 sufficient 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 a returned results by using the annealing process a second time. We compare the performance NSP using both forward and reverse annealing methods and describe how these approach might be used in practice.
arXiv comment20 pages, 13 figures
References in corpus (17)
- Quantum Computing in the NISQ era and beyond
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- A practical heuristic for finding graph minors
- Quantum Optimization of Fully-Connected Spin Glasses
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Quantum Annealing Implementation of Job-Shop Scheduling
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
- An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
- Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer
- Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
- Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
- Quantum speedup in stoquastic adiabatic quantum computation
Cited by in corpus (35)
- Quantum Annealing for Industry Applications: Introduction and Review
- Probabilistic Nonunitary Gate in Imaginary Time Evolution
- Foundation of Quantum Optimal Transport and Applications
- Towards optimization of photonic-crystal surface-emitting lasers via quantum annealing
- Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
- Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning
- Information processing at the speed of light
- A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem
- Encoding-Independent Optimization Problem Formulation for Quantum Computing
- Greedy parameter optimization for diabatic quantum annealing
- Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
- Counterdiabatic Reverse Annealing
- Parity Quantum Optimization: Encoding Constraints
- Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems
- An Optimization Case Study for solving a Transport Robot Scheduling Problem on Quantum-Hybrid and Quantum-Inspired Hardware
- Quantum-machine-assisted Drug Discovery
- Mean-field Coherent Ising Machines with artificial Zeeman terms
- Quantum-inspired optimization for wavelength assignment
- Particle Track Classification Using Quantum Associative Memory
- Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
- Diagnosing First and Second Order Phase Transitions with Probes of Quantum Chaos
- Petri Net Modeling for Ising Model Formulation in Quantum Annealing
- Demonstration of long-range correlations via susceptibility measurements in a one-dimensional superconducting Josephson spin chain
- Dynamic Asset Allocation with Expected Shortfall via Quantum Annealing
- Topological Aspects of Matters and Langlands Program
- Analyzing the Effectiveness of Quantum Annealing with Meta-Learning
- Reverse quantum annealing assisted by forward annealing
- Minor Embedding for Quantum Annealing with Reinforcement Learning
- Universal Computation with Quantum Fields
- Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer
- Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
- Self-Adaptive Ising Machines for Constrained Optimization
- Noise Effects on Diabatic Quantum Annealing Protocols
- BALANCE: Bitrate-Adaptive Limit-Aware Netcast Content Enhancement Utilizing QUBO and Quantum Annealing
- A Hybrid Framework Using a QUBO Solver For Permutation-Based Combinatorial Optimization