Quantum computing and the stable set problem

Abstract

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.

References in corpus (7)

• Ising formulations of many NP problems
• Mathematical Foundation of Quantum Annealing
• Solving large Maximum Clique problems on a quantum annealer
• Refined Estimates Concerning Sumsets Contained in the Roots of Unity
• Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
• BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints
• The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization

Cited by in corpus (1)

• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods