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

Experiences with Scheduling Problems on Adiabatic Quantum Computers

Tobias Stollenwerk, Achim Basermann

Published Jan 1, 2016• 5 citations
OpenAlex

Abstract

The realization of quantum computing models is nowadays a grand challenge regarding supercomputer architectures which may potentially exceed the scaling limits of Moore’s Law. The Canadian company D-Wave Systems Inc. developed a hardware for quantum annealing which is well suited for solving combinatorial optimization problems. We investigate the formulation of a scheduling problem for quantum annealing and report on our experience with the D-Wave system at NASA Ames.

Related papers

Performance of quantum annealing hardware

Damian S. Steiger, Bettina Heim, Troels F. Rønnow +1 more

In this paper, we provide an introduction to quantum annealers, which are analogue quantum computing devices, and their potential application to solve hard optimisation problems. We summarise our benchmarks performed on a "Wave Two" machine by Canadian company D-Wave Systems Inc.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Oct 22, 2015•4 citations

Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer

Immanuel Trummer, Christoph E. Koch

The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.

arXiv:1510.06437•Oct 21, 2015•8 citations

Multiple query optimization on the D-Wave 2X adiabatic quantum computer

Immanuel Trummer, Christoph E. Koch

The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.

Proceedings of the VLDB Endowment•May 1, 2016•75 citations

Quantum Computing in Test Automation: Optimizing Parallel Execution with Quantum Annealing in D-Wave Systems

Akhil Reddy Bairi, K Thangavelu, Arun Ayilliath Keezhadath

Test automation plays a crucial role in modern software development, ensuring faster releases and higher software quality. However, optimizing parallel test execution remains a challenge due to resource constraints and scheduling inefficiencies. This research explores the potential of quantum computing, specifically quantum annealing using D-Wave systems, to enhance test execution efficiency. By formulating test suite scheduling as a combinatorial optimization problem, we leverage quantum annealing to achieve optimal test distribution across available resources. Our proposed approach significantly reduces execution time and improves resource utilization compared to classical optimization techniques. Experimental results demonstrate the effectiveness of quantum-enhanced scheduling, highlighting the potential of quantum computing in revolutionizing test automation.

Journal of Artificial Intelligence General science (JAIGS)•Oct 10, 2024•0 citations

Evaluating the job shop scheduling problem on a D-wave quantum annealer

Costantino Carugno, Maurizio Ferrari Dacrema, Paolo Cremonesi

Job Shop Scheduling is a combinatorial optimization problem of particular importance for production environments where the goal is to complete a production task in the shortest possible time given limitations in the resources available. Due to its computational complexity it quickly becomes intractable for problems of interesting size. The emerging technology of Quantum Annealing provides an alternative computational architecture that promises improved scalability and solution quality. However, several limitations as well as open research questions exist in this relatively new and rapidly developing technology. This paper studies the application of quantum annealing to solve the job shop scheduling problem, describing each step required from the problem formulation to the fine-tuning of the quantum annealer and compares the solution quality with various classical solvers. Particular attention is devoted to aspects that are often overlooked, such as the computational cost of representing the problem in the formulation required by the quantum annealer, the relative qubits requirements and how to mitigate chain breaks. Furthermore, the impact of advanced tools such as reverse annealing is presented and its effectiveness discussed. The results indicate several challenges emerging at various stages of the experimental pipeline which bring forward important research questions and directions of improvement.

Scientific Reports•Apr 21, 2022•69 citations

Lösen von QUBO-Problemen auf einem Adiabatischen Quanten-Annealer

Elisabeth Lobe

The exploitation of quantum mechanical principles seems to provide a decisive advantage over classical computation technologies. In the recent years there has been big progress in realizing different quantum computer architectures, especially by the Canadian company D-Wave Systems, which developed the first commercially available adiabatic quantum annealer. By adiabatic evolution of quantum mechanical systems it can solve NP-hard discrete optimization problems probabilistically. Due to the restrictions of the hardware architecture the directly mappable problems are limited to quadratic unconstrained binary optimization (QUBO) problems over a so called Chimera interaction graph. After briefly introducing the physical and quantum computational background including the diffculties in determining the run time and success probability of the D-Wave machine, the presentation will focus on the mapping of more general problems onto their specific problem structure. In addition to the reductions to QUBOs the main part here is the minor embedding with the distribution of the weight of the original node onto several hardware nodes.

•May 19, 2017•0 citations
The realization of quantum computing models is nowadays a grand challenge regarding supercomputer architectures which may potentially exceed the scaling limits of Moore’s Law. The Canadian company D-Wave Systems Inc. developed a hardware for quantum annealing which is well suited for solving combinatorial optimization problems. We investigate the formulation of a scheduling problem for quantum annealing and report on our experience with the D-Wave system at NASA Ames.
The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.
The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.
Test automation plays a crucial role in modern software development, ensuring faster releases and higher software quality. However, optimizing parallel test execution remains a challenge due to resource constraints and scheduling inefficiencies. This research explores the potential of quantum computing, specifically quantum annealing using D-Wave systems, to enhance test execution efficiency. By formulating test suite scheduling as a combinatorial optimization problem, we leverage quantum annealing to achieve optimal test distribution across available resources. Our proposed approach significantly reduces execution time and improves resource utilization compared to classical optimization techniques. Experimental results demonstrate the effectiveness of quantum-enhanced scheduling, highlighting the potential of quantum computing in revolutionizing test automation.
Job Shop Scheduling is a combinatorial optimization problem of particular importance for production environments where the goal is to complete a production task in the shortest possible time given limitations in the resources available. Due to its computational complexity it quickly becomes intractable for problems of interesting size. The emerging technology of Quantum Annealing provides an alternative computational architecture that promises improved scalability and solution quality. However, several limitations as well as open research questions exist in this relatively new and rapidly developing technology. This paper studies the application of quantum annealing to solve the job shop scheduling problem, describing each step required from the problem formulation to the fine-tuning of the quantum annealer and compares the solution quality with various classical solvers. Particular attention is devoted to aspects that are often overlooked, such as the computational cost of representing the problem in the formulation required by the quantum annealer, the relative qubits requirements and how to mitigate chain breaks. Furthermore, the impact of advanced tools such as reverse annealing is presented and its effectiveness discussed. The results indicate several challenges emerging at various stages of the experimental pipeline which bring forward important research questions and directions of improvement.
The exploitation of quantum mechanical principles seems to provide a decisive advantage over classical computation technologies. In the recent years there has been big progress in realizing different quantum computer architectures, especially by the Canadian company D-Wave Systems, which developed the first commercially available adiabatic quantum annealer. By adiabatic evolution of quantum mechanical systems it can solve NP-hard discrete optimization problems probabilistically. Due to the restrictions of the hardware architecture the directly mappable problems are limited to quadratic unconstrained binary optimization (QUBO) problems over a so called Chimera interaction graph. After briefly introducing the physical and quantum computational background including the diffculties in determining the run time and success probability of the D-Wave machine, the presentation will focus on the mapping of more general problems onto their specific problem structure. In addition to the reductions to QUBOs the main part here is the minor embedding with the distribution of the weight of the original node onto several hardware nodes.