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

arXiv:2308.13041

Advancing stable set problem solutions through quantum annealers

Janez Povh, Dunja Pucher

Published Aug 23, 2023• 2 citations
arXivHTMLPDF

Abstract

We assess the performance of D-wave quantum solvers for solving the stable set problem in a graph, one of the most studied NP-hard problems. We perform computations on some instances from the literature with up to 125 vertices and compare the quality of the obtained solutions with known optimum solutions. It turns out that the hybrid solver gives very good results, while the Quantum Processing Unit solver shows rather modest performance overall.

DOI
10.48550/arxiv.2308.13041

Related papers

Quantum computing and the stable set problem

Aljaž Krpan, Janez Povh, Dunja Pucher

Given an undirected graph, the stable set problem asks to determine the cardinality of the largest subset of pairwise non-adjacent vertices. This value is called the stability number of the graph, and its computation is an NP-hard problem. In this paper, we solve the stable set problem using the D-Wave quantum annealer. By formulating the problem as a quadratic unconstrained binary optimization problem with the penalty method, we show its optimal value equals the graph's stability number for specific penalty values. However, D-Wave's quantum annealer is a heuristic, so the solutions may be far from the optimum and may not represent stable sets. To address these, we introduce a post-processing procedure that identifies samples that could lead to improved solutions. Additionally, we propose a partitioning method to handle larger instances that cannot be embedded on D-Wave's quantum processing unit. Finally, we investigate how different penalty parameter values affect the solutions' quality. Extensive computational results show that the post-processing procedure significantly improves the solution quality, while the partitioning method successfully extends our approach to medium-size instances.

arXiv:2405.12845•Optimization methods & software•May 21, 2025•6 citations

Efficient Combinatorial Optimization Using Quantum Annealing

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

The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.

arXiv:1801.08653•Jan 26, 2018•65 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.

arXiv:1801.08649•Journal of Signal Processing Systems•May 3, 2018•74 citations

Quantum Annealing versus Digital Computing: An Experimental Comparison

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•62 citations

Accuracy and performance evaluation of quantum, classical and hybrid solvers for the Max-Cut problem

Jaka Vodeb, Vid Eržen, Timotej Hrga +1 more

Abstract This paper benchmarks quantum, classical, and hybrid solvers on NP-hard Max-Cut and QUBO problems, emphasizing solution quality relative to known global optima. We evaluate D-Wave’s fast annealing QPU and Hybrid solver against classical simulated annealing (SA) and Toshiba’s simulated bifurcation machine (SBM) using 139 Max-Cut instances (100 to 10,000 nodes). For small instances ( $$\le $$ ≤ 250 nodes) with known global optima, Hybrid and SA consistently achieve optimal solutions, outperforming the QPU. For larger instances, SBM and slower SA yield superior solutions, while Hybrid and faster SA perform less effectively. Computation time varies across solvers.

arXiv:2412.07460•Quantum Information Processing•Jul 3, 2026•9 citations

An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem

Alessandro Gherardi, Alberto Leporati

Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.

arXiv:2406.07587•Jun 11, 2024•4 citations
We assess the performance of D-wave quantum solvers for solving the stable set problem in a graph, one of the most studied NP-hard problems. We perform computations on some instances from the literature with up to 125 vertices and compare the quality of the obtained solutions with known optimum solutions. It turns out that the hybrid solver gives very good results, while the Quantum Processing Unit solver shows rather modest performance overall.
Given an undirected graph, the stable set problem asks to determine the cardinality of the largest subset of pairwise non-adjacent vertices. This value is called the stability number of the graph, and its computation is an NP-hard problem. In this paper, we solve the stable set problem using the D-Wave quantum annealer. By formulating the problem as a quadratic unconstrained binary optimization problem with the penalty method, we show its optimal value equals the graph's stability number for specific penalty values. However, D-Wave's quantum annealer is a heuristic, so the solutions may be far from the optimum and may not represent stable sets. To address these, we introduce a post-processing procedure that identifies samples that could lead to improved solutions. Additionally, we propose a partitioning method to handle larger instances that cannot be embedded on D-Wave's quantum processing unit. Finally, we investigate how different penalty parameter values affect the solutions' quality. Extensive computational results show that the post-processing procedure significantly improves the solution quality, while the partitioning method successfully extends our approach to medium-size instances.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, 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.
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.
Abstract This paper benchmarks quantum, classical, and hybrid solvers on NP-hard Max-Cut and QUBO problems, emphasizing solution quality relative to known global optima. We evaluate D-Wave’s fast annealing QPU and Hybrid solver against classical simulated annealing (SA) and Toshiba’s simulated bifurcation machine (SBM) using 139 Max-Cut instances (100 to 10,000 nodes). For small instances ( ≤\le ≤ ≤ 250 nodes) with known global optima, Hybrid and SA consistently achieve optimal solutions, outperforming the QPU. For larger instances, SBM and slower SA yield superior solutions, while Hybrid and faster SA perform less effectively. Computation time varies across solvers.
Quantum annealers can be used to solve many (possibly NP-hard) combinatorial optimization problems, by formulating them as quadratic unconstrained binary optimization (QUBO) problems or, equivalently, using the Ising formulation. In this paper we analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. Due to the embedding limit of 164 nodes imposed by the anneler, we conducted a study on graph decomposition to enable instance embedding. We thus propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes. We then statistically analysed how these variables affect the quality of the solutions found by the quantum annealer. The results of our investigation include recommendations on ratio and density limits not to be exceeded, as well as a series of precautions and a priori analyses to be carried out in order to maximise the probability of obtaining a solution close to the optimum.