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

Bulletin of the American Physical Society

Performance of Quantum Annealers on Hard Scheduling Problems

Bibek Pokharel, Davide Venturelli, Eleanor Gilbert Rieffel

Published Mar 13, 2017• 1 citation
OpenAlex

Related papers

Hard scheduling problems for early quantum annealer

Zhihui Wang, Tony T. Tran, Bryan O’Gorman +3 more

Bulletin of the American Physical Society•Mar 14, 2016•0 citations

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

Applications on quantum annealers

Dennis Willsch

•Jan 1, 2026•0 citations

Heavy Tails in the Distribution of Time to Solution for Classical and Quantum Annealing

Damian S. Steiger, Troels F. Rønnow, Matthias Troyer

For many optimization algorithms the time to solution depends not only on the problem size but also on the specific problem instance and may vary by many orders of magnitude. It is then necessary to investigate the full distribution and especially its tail. Here, we analyze the distributions of annealing times for simulated annealing and simulated quantum annealing (by path integral quantum Monte Carlo simulation) for random Ising spin glass instances. We find power-law distributions with very heavy tails, corresponding to extremely hard instances, but far broader distributions-and thus worse performance for hard instances-for simulated quantum annealing than for simulated annealing. Fast, nonadiabatic, annealing schedules can improve the performance of simulated quantum annealing for very hard instances by many orders of magnitude.

arXiv:1504.07991•Physical Review Letters•Dec 4, 2015•39 citations

Finding optimal quantum annealer architectures

Zoe Gonzalez Izquierdo

Bulletin of the American Physical Society•Mar 5, 2018•0 citations

A Hybrid Quantum Annealing Algorithm for Solving a Constraint-Based University Timetabling Problem

Kevin Tole, Edward Fondo, Fullgence Mwachoo Mwakondo

University timetabling is a classical NP-Hard combinatorial constraint problem that involves scheduling of courses, lecturers, students, classrooms, and timeslots while satisfying a set of constraints, with the main goal of minimizing conflicts. To solve this problem, we propose a novel Quantum Annealing and Topological Data Analysis (QA–TDA) algorithm that starts with an initial feasible solution, followed by iterative refinement using Quantum annealing configurations. TDA analyses the optimization landscape through persistent homology by detecting promising regions of interest in the solution space, which are clustered and subjected to quantum re-annealing using customized Hamiltonians-adaptive annealing schedules. QA-TDA model achieves a balance between global exploration and local exploitation, which improves convergence efficiency and solution robustness. Experimental results demonstrate that our hybrid model consistently outperforms baseline models across all evaluation metrics. In particularly on the most complex dataset, QA– TDA achieved a Conflict-Free Rate (CFR) of 94.3%. Additionally, an ablation study was conducted to validate the contribution of each component of the proposed model. Furthermore, clustering and K-Nearest Neighbour (K-NN) analyses confirm the robustness and consistency of the proposed approach across datasets of varying sizes and complexity. These findings highlight the great performance, scalability, and reliability of the integrated QA–TDA model for real-world academic scheduling applications.

Multidisciplinary Journal of Technical University of Mombasa•Jun 30, 2026•0 citations
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.
For many optimization algorithms the time to solution depends not only on the problem size but also on the specific problem instance and may vary by many orders of magnitude. It is then necessary to investigate the full distribution and especially its tail. Here, we analyze the distributions of annealing times for simulated annealing and simulated quantum annealing (by path integral quantum Monte Carlo simulation) for random Ising spin glass instances. We find power-law distributions with very heavy tails, corresponding to extremely hard instances, but far broader distributions-and thus worse performance for hard instances-for simulated quantum annealing than for simulated annealing. Fast, nonadiabatic, annealing schedules can improve the performance of simulated quantum annealing for very hard instances by many orders of magnitude.
University timetabling is a classical NP-Hard combinatorial constraint problem that involves scheduling of courses, lecturers, students, classrooms, and timeslots while satisfying a set of constraints, with the main goal of minimizing conflicts. To solve this problem, we propose a novel Quantum Annealing and Topological Data Analysis (QA–TDA) algorithm that starts with an initial feasible solution, followed by iterative refinement using Quantum annealing configurations. TDA analyses the optimization landscape through persistent homology by detecting promising regions of interest in the solution space, which are clustered and subjected to quantum re-annealing using customized Hamiltonians-adaptive annealing schedules. QA-TDA model achieves a balance between global exploration and local exploitation, which improves convergence efficiency and solution robustness. Experimental results demonstrate that our hybrid model consistently outperforms baseline models across all evaluation metrics. In particularly on the most complex dataset, QA– TDA achieved a Conflict-Free Rate (CFR) of 94.3%. Additionally, an ablation study was conducted to validate the contribution of each component of the proposed model. Furthermore, clustering and K-Nearest Neighbour (K-NN) analyses confirm the robustness and consistency of the proposed approach across datasets of varying sizes and complexity. These findings highlight the great performance, scalability, and reliability of the integrated QA–TDA model for real-world academic scheduling applications.