arXiv:2408.06758

From Maximum Cut to Maximum Independent Set

Chuixiong Wu, Jianan Wang, Fen Zuo

Published Aug 13, 2024• 1 citation

Abstract

The Maximum Cut (Max-Cut) problem could be naturally expressed either in a Quadratic Unconstrained Binary Optimization (QUBO) formulation, or as an Ising model. It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. Therefore, it would be natural to attack MIS with various Max-Cut/Ising solvers. It turns out that this strategy greatly improves the approximation for the independence number of random Erdős-Rényi graphs. It also exhibits perfect performance on a benchmark arising from coding theory. These results pave the way for further development of approximate quantum algorithms on MIS, and specifically on the corresponding coding problems.

DOI: 10.48550/arxiv.2408.06758

Related papers

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

Abstract The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

Mathematical Programming ComputationApr 15, 202338 citations

A comprehensive benchmark of an Ising machine on the Max-Cut problem

Salwa Shaglel, Markus Kirsch, Mårten Winkler +4 more

Abstract Quadratic unconstrained binary optimization (QUBO) formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum–classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.

arXiv:2507.22117New Journal of PhysicsJun 5, 20260 citations

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

arXiv:2202.02305Feb 4, 20221 citation

Max-independent set and the quantum alternating operator ansatz

Zain H. Saleem

The maximum-independent set (MIS) problem of graph theory using the quantum alternating operator ansatz is studied. We perform simulations on the Rigetti Forest simulator for the square ring, [Formula: see text], and [Formula: see text] graphs and analyze the dependence of the algorithm on the depth of the circuit and initial states. The probability distribution of observation of the feasible states representing maximum-independent sets is observed to be asymmetric for the MIS problem, which is unlike the Max-Cut problem where the probability distribution of feasible states is symmetric. For asymmetric graphs, it is shown that the algorithm clearly favors the independent set with the larger number of elements even for finite circuit depth. We also compare the approximation ratios for the algorithm when we choose different initial states for the square ring graph and show that it is dependent on the choice of the initial state.

arXiv:1905.04809International Journal of Quantum InformationJun 1, 202028 citations

First Results Solving Arbitrarily Structured Maximum Independent Set Problems Using Quantum Annealing

Sheir Yarkoni, Aske Plaat, Thomas Bäck

Commercial quantum processing units (QPUs) such as those made by D-Wave Systems are being increasingly used for solving complex combinatorial optimization problems. In this paper, we review a canonical NP-hard problem, the Maximum Independent Set (MIS) problem. We show how to map MIS problems to quadratic unconstrained binary optimization (QUBO) problems, and use a D-Wave 2000Q QPU to solve them. We compare the results from the D-Wave system to classical algorithms such as simulated thermal annealing and the graphical networks package NetworkX. To our knowledge, these are the first results of experiments involving arbitrarily-structured MIS inputs using a D-Wave QPU. We find that the QPU can be used as a heuristic optimizer for randomly generated inputs, but due to physical control errors, can be outperformed by simulated thermal annealing.

IEEE Congress on Evolutionary Computation (CEC)Jul 1, 201829 citations

Quantum Computing for solving the 3SAT problem by reduction to the MIS combinatorial optimization problem

Samuel Deleplanque

This work tries to anticipate the main issues related to the D-Wave machines topology for solving the 3Sat problem. The polynomial reduction to the Maximum Independent Set Problem (MIS) is employed for solving a 3Sat instance to furnish a less dense graph to the machine. These analog quantum machines, based on the quantum annealing process, takes a Quadratic Unconstrained Binary Optimization model (QUBO) as input, which is a specific mathematical program easy to build considering the MIS.

Apr 17, 20230 citations