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

International Conference on Control Systems and Computer Science

Solving Hard Problems on Adiabatic Quantum Computers

Daniel Ciocirlan, Nicolae Ţăpuş, Dan Dragomir

Published May 1, 2015• 0 citations
Publisher

Abstract

Quantum Computation has thus far proven a promising new research field, with results that vastly surpass their classical counterparts, but programming a quantum computer is in its infant stage, at best. D-Wave have successfully implemented a computing machine based on adiabatic evolution which natively solves Ising problems by construction. In this paper we present additional solutions to known computational problems by reducing them to mathematical expressions. They will be passed to the quantum computer through Blackbox, a mechanism that maps objective functions to the native Ising form the D-Wave machine recognizes.

DOI
10.1109/cscs.2015.100

Related papers

Discrete optimisation problems on an adiabatic quantum computer

Tobias Stollenwerk, Elisabeth Lobe, Anke Tröltzsch

In the recent years the field of adiabatic quantum computing has gained importance due to the advances in the realisation of such machines, especially by the company D-Wave Systems. In contrast to a quantum computer in the conventional sense, an adiabatic quantum computer can solve a discrete optimisation problem by encoding the objective function into a quantum mechanical system. By carefully evolving the system in time from an initial state into the lowest energy state, the optimisation problem is solved. Due to the quantum nature of the device it is assumed that there is a substantial speedup compared to classical HPC facilities. The D-Wave machines are capable of finding the minimum of a subclass of the Ising model, a quadratic unconstrained binary optimisation problem. In this paper, we present a way of mapping more general problems to the subclass of Ising problems in order to make them solvable on an adiabatic quantum computer. As an example, we choose the maximum clique problem where one needs to find the maximal complete subgraph in an undirected graph. The corresponding decision problem is NP-complete. It has applications in social media or computational chemistry. Moreover, the solution of the maximum clique problem can be used to increase the number of logical variables which can be realised on a D-Wave machine. In addition, we investigate the applicability of adiabatic quantum computing to the scheduling optimisation of satellite missions performed by the German Aerospace Center.

•Jan 1, 2015•2 citations

Adiabatic quantum computing

Elisabeth Lobe, Tobias Stollenwerk, Anke Tröltzsch

In the recent years, the field of adiabatic quantum computing has gained importance due to the advances in the realisation of such machines, especially by the company D-Wave Systems. These machines are suited to solve discrete optimisation problems which are typically very hard to solve on a classical computer. Due to the quantum nature of the device it is assumed that there is a substantial speedup compared to classical HPC facilities. We explain the basic principles of adiabatic quantum computing as well as its advantages and limitations. By using a quantum computer simulation software we present how discrete optimisation problems, like map colouring and the maximal Clique problem, can be solved. In addition, we investigate the applicability of adiabatic quantum computing to DLR specific problems.

•Jan 1, 2015•6 citations

Programming a D-wave annealing-based quantum computer: tools and techniques

Scott Pakin, Steven P. Reinhardt

Quantum annealing is a form of quantum computing that exploits quantum effects to probabilistically solve a specific, NP-hard problem: finding the ground state of a classical, Ising-model Hamiltonian. Because physical quantum annealers are already available, there exists the pressing question of how to program such systems. That is, how can one map a computational problem into the coefficients of an Ising-model Hamiltonian for solution by quantum-annealing hardware? In this article, we address that question primarily from a practical standpoint. We survey extant software tools intended for programming D-wave annealing-based quantum processors and examine the programming model and solution technique promoted by each tool in an attempt to showcase the variety of contemporary approaches to solving computationally challenging problems on an existing annealing-based quantum computer.

Quantum Information and Computation•Sep 1, 2019•1 citation

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

Quantum Annealing versus Digital Computing

Michael Jünger, Elisabeth Lobe, Petra Mutzel +4 more

Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.

arXiv:1904.11965•ACM Journal of Experimental Algorithmics•Jul 9, 2021•48 citations

Gates for Adiabatic Quantum Computing

Richard H. Warren

The goal of this paper is to introduce building blocks for adiabatic quantum algorithms. Adiabatic quantum computing uses the principle of quantum annealing, which implies that a carefully controlled energy solution is optimal and corresponds to minimizing a discrete function. The input function can be influenced by rewards and penalties to favor a solution that meets restrictions that are imposed by the problem. We show how to accomplish this influence for gates in adiabatic quantum computing, particularly the controlled-NOT gate (CNOT gate) which is fundamental to all quantum gates on two or more qubits. In addition, we adapt the Toffoli gate, the Fredkin gate, and the Hadamard gate to the Ising objective function which is a foundation for discrete optimization on D-Wave System machines. The quantum work in this paper encompasses Boolean operations, some of which are used to construct gates. We think the possible advantages of the building blocks in this paper will enhance quantum algorithms on D-Wave System computers.

arXiv:1405.2354•May 7, 2014•2 citations
Quantum Computation has thus far proven a promising new research field, with results that vastly surpass their classical counterparts, but programming a quantum computer is in its infant stage, at best. D-Wave have successfully implemented a computing machine based on adiabatic evolution which natively solves Ising problems by construction. In this paper we present additional solutions to known computational problems by reducing them to mathematical expressions. They will be passed to the quantum computer through Blackbox, a mechanism that maps objective functions to the native Ising form the D-Wave machine recognizes.
In the recent years the field of adiabatic quantum computing has gained importance due to the advances in the realisation of such machines, especially by the company D-Wave Systems. In contrast to a quantum computer in the conventional sense, an adiabatic quantum computer can solve a discrete optimisation problem by encoding the objective function into a quantum mechanical system. By carefully evolving the system in time from an initial state into the lowest energy state, the optimisation problem is solved. Due to the quantum nature of the device it is assumed that there is a substantial speedup compared to classical HPC facilities. The D-Wave machines are capable of finding the minimum of a subclass of the Ising model, a quadratic unconstrained binary optimisation problem. In this paper, we present a way of mapping more general problems to the subclass of Ising problems in order to make them solvable on an adiabatic quantum computer. As an example, we choose the maximum clique problem where one needs to find the maximal complete subgraph in an undirected graph. The corresponding decision problem is NP-complete. It has applications in social media or computational chemistry. Moreover, the solution of the maximum clique problem can be used to increase the number of logical variables which can be realised on a D-Wave machine. In addition, we investigate the applicability of adiabatic quantum computing to the scheduling optimisation of satellite missions performed by the German Aerospace Center.
In the recent years, the field of adiabatic quantum computing has gained importance due to the advances in the realisation of such machines, especially by the company D-Wave Systems. These machines are suited to solve discrete optimisation problems which are typically very hard to solve on a classical computer. Due to the quantum nature of the device it is assumed that there is a substantial speedup compared to classical HPC facilities. We explain the basic principles of adiabatic quantum computing as well as its advantages and limitations. By using a quantum computer simulation software we present how discrete optimisation problems, like map colouring and the maximal Clique problem, can be solved. In addition, we investigate the applicability of adiabatic quantum computing to DLR specific problems.
Quantum annealing is a form of quantum computing that exploits quantum effects to probabilistically solve a specific, NP-hard problem: finding the ground state of a classical, Ising-model Hamiltonian. Because physical quantum annealers are already available, there exists the pressing question of how to program such systems. That is, how can one map a computational problem into the coefficients of an Ising-model Hamiltonian for solution by quantum-annealing hardware? In this article, we address that question primarily from a practical standpoint. We survey extant software tools intended for programming D-wave annealing-based quantum processors and examine the programming model and solution technique promoted by each tool in an attempt to showcase the variety of contemporary approaches to solving computationally challenging problems on an existing annealing-based quantum computer.
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.
Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.
The goal of this paper is to introduce building blocks for adiabatic quantum algorithms. Adiabatic quantum computing uses the principle of quantum annealing, which implies that a carefully controlled energy solution is optimal and corresponds to minimizing a discrete function. The input function can be influenced by rewards and penalties to favor a solution that meets restrictions that are imposed by the problem. We show how to accomplish this influence for gates in adiabatic quantum computing, particularly the controlled-NOT gate (CNOT gate) which is fundamental to all quantum gates on two or more qubits. In addition, we adapt the Toffoli gate, the Fredkin gate, and the Hadamard gate to the Ising objective function which is a foundation for discrete optimization on D-Wave System machines. The quantum work in this paper encompasses Boolean operations, some of which are used to construct gates. We think the possible advantages of the building blocks in this paper will enhance quantum algorithms on D-Wave System computers.