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.
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.
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.
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.
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.