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

Hard scheduling problems for early quantum annealer

Zhihui Wang, Tony T. Tran, Bryan O’Gorman, N. Minh, Jeremy Frank, Eleanor Gilbert Rieffel

Published Mar 14, 2016• 0 citations
OpenAlex

Related papers

Performance of Quantum Annealers on Hard Scheduling Problems

Bibek Pokharel, Davide Venturelli, Eleanor Gilbert Rieffel

Bulletin of the American Physical Society•Mar 13, 2017•1 citation

Computational Method Using Quantum Annealing for TDMA Scheduling Problem in Wireless Sensor Networks

Fumio Ishizaki

In this paper, we consider a wireless sensor network where the network topology is a tree and medium access control is TDMA. We focus on TDMA scheduling problem studied in [1]. Since scheduling problems are considered as a member in the class of NP-hard, it is difficult to obtain the optimal solution in the scheduling problem. To overcome the difficulty, we develop a computational method using quantum annealing in order to find near-optimal solutions in the TDMA scheduling problem. We provide some numerical results to compare the computational method using quantum annealing with other methods in terms of quality of solution, computation time and size of problem.

International Conference on Signal Processing and Communication Systems•Dec 1, 2019•8 citations

Finding optimal quantum annealer architectures

Zoe Gonzalez Izquierdo

Bulletin of the American Physical Society•Mar 5, 2018•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

Building an iterative heuristic solver for a quantum annealer

Gili Rosenberg, Mohammad M. Vazifeh, Brad Woods +1 more

arXiv:1507.07605•Computational Optimization and Applications•Apr 23, 2016•49 citations

Lagrangian Relaxation Based Parallelized Quantum Annealing and Its Application in Network Function Virtualization

Wenlu Xuan, Zhongqi Zhao, Lei Fan +1 more

Quantum computing is commonly considered one highly efficient computing method with the potential to revolutionize computation technology and solve problems that are currently unsolvable. However, due to the limitation of hardware equipment and an immature experimental base, quantum technology is still in its early stages and is far from achieving the expected performance, especially in solving large-scale complex problems. To break through these barriers, we propose a parallelized quantum annealing algorithm based on Lagrangian relaxation. The proposed algorithm divides the large-scale problem into several small problems and then employs multiple quantum computers to solve them. Our proposed approach overcomes the limited number of qubits and allows quantum computing to solve largescale optimization problems. Additionally, we incorporate a local search method to ensure this Lagrangian relaxation based quantum algorithm achieves an optimal solution. We use the proposed parallelized quantum annealing algorithm to solve optimal scheduling problems in network function virtualization networks. The problem is expressed in a linear optimization model that is NP-hard. Our proposed algorithm presents excellent time performance in solving this virtualized network functions scheduling problem, compared with the Lagrangian relaxation based classical algorithm.

IEEE Open Journal of the Communications Society•Jan 1, 2024•1 citation
In this paper, we consider a wireless sensor network where the network topology is a tree and medium access control is TDMA. We focus on TDMA scheduling problem studied in [1]. Since scheduling problems are considered as a member in the class of NP-hard, it is difficult to obtain the optimal solution in the scheduling problem. To overcome the difficulty, we develop a computational method using quantum annealing in order to find near-optimal solutions in the TDMA scheduling problem. We provide some numerical results to compare the computational method using quantum annealing with other methods in terms of quality of solution, computation time and size of 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.
Quantum computing is commonly considered one highly efficient computing method with the potential to revolutionize computation technology and solve problems that are currently unsolvable. However, due to the limitation of hardware equipment and an immature experimental base, quantum technology is still in its early stages and is far from achieving the expected performance, especially in solving large-scale complex problems. To break through these barriers, we propose a parallelized quantum annealing algorithm based on Lagrangian relaxation. The proposed algorithm divides the large-scale problem into several small problems and then employs multiple quantum computers to solve them. Our proposed approach overcomes the limited number of qubits and allows quantum computing to solve largescale optimization problems. Additionally, we incorporate a local search method to ensure this Lagrangian relaxation based quantum algorithm achieves an optimal solution. We use the proposed parallelized quantum annealing algorithm to solve optimal scheduling problems in network function virtualization networks. The problem is expressed in a linear optimization model that is NP-hard. Our proposed algorithm presents excellent time performance in solving this virtualized network functions scheduling problem, compared with the Lagrangian relaxation based classical algorithm.