From Maximum Cut to Maximum Independent Set

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.

Independence number of 1dc.2048 updated, new results for 1dc.4096 included, references added; 22 pages, 5 figures