qReduMIS: A Quantum-Informed Reduction Algorithm for the Maximum Independent Set Problem

We propose and implement a quantum-informed reduction algorithm for the maximum independent set problem that integrates classical kernelization techniques with information extracted from quantum devices.

Our larger framework consists of dedicated application, algorithm, and hardware layers, and easily generalizes to the maximum weight independent set problem.

In this hybrid quantum-classical framework, which we call qReduMIS, the quantum computer is used as a co-processor to inform classical reduction logic about frozen vertices that are likely (or unlikely) to be in large independent sets, thereby opening up the reduction space after removal of targeted subgraphs.

We systematically assess the performance of qReduMIS based on experiments with up to 231 qubits run on Rydberg quantum hardware available through Amazon Braket.

Our experiments show that qReduMIS can help address fundamental performance limitations faced by a broad set of (quantum) solvers including Rydberg quantum devices.

We outline implementations of qReduMIS with alternative platforms, such as superconducting qubits or trapped ions, and we discuss potential future extensions.