Divide and Conquer-based Quantum Algorithms for Maximum Independent Set on Large Separable Graphs

Noisy Intermediate-Scale Quantum (NISQ) computers currently available have a few thousand qubits, and could potentially solve combinatorial optimization problems efficiently. However, the sizes of the problems that could be solved are limited by the number of qubits, their connectivity, high noise, and short coherence times. In this work, we propose hybrid quantum-classical algorithms based on the divide and conquer paradigm for solving larger Maximum Independent Set (MIS) and Maximum Weighted Independent Set (MWIS) problems on graphs than would otherwise be possible on NISQ devices. The machines include D-Wave Quantum Annealers and QuEra Quantum Computers with Neutral Atoms. Our algorithms are designed for separable graphs, which are classes of graphs with good vertex separators; these include planar graphs, finite element meshes with good aspect ratios, nearest neighbor graphs, and certain classes of geometrically defined graphs. The algorithms recursively employ vertex separators to create a collection of small subgraphs, from which NISQ computers obtain disjoint maximal independent sets, which are then augmented by independent vertices from the separators. We demonstrate competitive results compared to the classical Luby's algorithm, and KaMIS, a state-of-the-art classical MIS solver, on graphs with several thousand vertices. These divide and conquer-based algorithms are also well-suited for distributed quantum computer architectures.