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

Discrete optimisation problems on an adiabatic quantum computer

Tobias Stollenwerk, Elisabeth Lobe, Anke Tröltzsch

Published Jan 1, 2015• 2 citations
OpenAlex

Abstract

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.

Related papers

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

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

Exploiting adiabatic quantum computing in deep space missions

Rebecca Casati, Enrico Prati

Abstract Several fundamental questions demand space exploration, posing tremendous computational tasks to address modelling and data processing. Quantum computing has been proposed to address deep space-related problems from quantum gravity, nuclear processes and many-body field theory simulation to artificial intelligence and related space mission planning. Adiabatic quantum computers have been proposed for solving optimization problems, such as space mission scheduling. The problem of assigning jobs to resources in a scientific mission, while satisfying certain constraints, can be tackled with the help of D-Wave’s quantum annealer, which exploits the adiabatic theorem to find the minimum energy solutions of a given system, encoded as the Hamiltonian of a quadratic unconstrained binary optimization (QUBO) problem. In its simplest em-bodiement, the scheduling can be implemented as a graph coloring (GC) problem, where the goal is to assign different colors (out of a given set) to connected nodes of an input graph, while respecting given constraints. The feasibility of our methods and the performance of quantum annealers are studied on randomly generated GC instances. A second framework studied is the job shop scheduling problem (JSP) that encodes more real-like scheduling problems of interest to agencies and industries. By implementing the problems with a QUBO formulation, we are able to find the optimal solution to three JSP instances present in the literature. The biggest one is solved with a quantum computation approach here for the first time.

Journal of Physics Conference Series•Jun 1, 2025•0 citations

Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization

Hartmut Neven, Geordie Rose, William G. Macready

Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.

arXiv:0804.4457•Apr 28, 2008•55 citations

Finding Maximum Cliques on a Quantum Annealer

Guillaume Chapuis, Hristo N. Djidjev, Georg Hahn +1 more

This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.

ACM International Conference on Computing Frontiers (CF)•May 15, 2017•31 citations

Finding Maximum Cliques on the D-Wave Quantum Annealer

Guillaume Chapuis, Hristo N. Djidjev, Georg Hahn +1 more

This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.

Journal of Signal Processing Systems•May 3, 2018•70 citations
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.
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.
Abstract Several fundamental questions demand space exploration, posing tremendous computational tasks to address modelling and data processing. Quantum computing has been proposed to address deep space-related problems from quantum gravity, nuclear processes and many-body field theory simulation to artificial intelligence and related space mission planning. Adiabatic quantum computers have been proposed for solving optimization problems, such as space mission scheduling. The problem of assigning jobs to resources in a scientific mission, while satisfying certain constraints, can be tackled with the help of D-Wave’s quantum annealer, which exploits the adiabatic theorem to find the minimum energy solutions of a given system, encoded as the Hamiltonian of a quadratic unconstrained binary optimization (QUBO) problem. In its simplest em-bodiement, the scheduling can be implemented as a graph coloring (GC) problem, where the goal is to assign different colors (out of a given set) to connected nodes of an input graph, while respecting given constraints. The feasibility of our methods and the performance of quantum annealers are studied on randomly generated GC instances. A second framework studied is the job shop scheduling problem (JSP) that encodes more real-like scheduling problems of interest to agencies and industries. By implementing the problems with a QUBO formulation, we are able to find the optimal solution to three JSP instances present in the literature. The biggest one is solved with a quantum computation approach here for the first time.
Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.
This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.
This paper assesses the performance of the D-Wave 2X (DW) quantum annealer for finding a maximum clique in a graph, one of the most fundamental and important NP-hard problems. Because the size of the largest graphs DW can directly solve is quite small (usually around 45 vertices), we also consider decomposition algorithms intended for larger graphs and analyze their performance. For smaller graphs that fit DW, we provide formulations of the maximum clique problem as a quadratic unconstrained binary optimization (QUBO) problem, which is one of the two input types (together with the Ising model) acceptable by the machine, and compare several quantum implementations to current classical algorithms such as simulated annealing, Gurobi, and third-party clique finding heuristics. We further estimate the contributions of the quantum phase of the quantum annealer and the classical post-processing phase typically used to enhance each solution returned by DW. We demonstrate that on random graphs that fit DW, no quantum speedup can be observed compared with the classical algorithms. On the other hand, for instances specifically designed to fit well the DW qubit interconnection network, we observe substantial speed-ups in computing time over classical approaches.