Quantum-enhanced Markov chain Monte Carlo for combinatorial optimization

Quantum computers may help solve combinatorial optimization problems more efficiently than classical computation alone. In this work, we explore the application of quantum-enhanced Markov chain Monte Carlo (QeMCMC), originally developed for approximating challenging probability distributions, in the context of combinatorial optimization. We focus on Maximum Independent Set (MIS), a class of combinatorial optimization problems known to be difficult to solve with state-of-the-art classical solvers for relatively small system sizes. Non-trivial instances of these are provided by the Quantum Optimization Benchmarking Library. More specifically, we combine heuristics of QeMCMC with parallel tempering, a method used to find ground states of many body systems, to tackle MIS graph problems with more than 100 decision variables. In the original work of Layden et al., QeMCMC showed promise as a near-term sampling algorithm with tangible resilience to noise. Our work applies QeMCMC to practical optimization applications and demonstrates the capabilities of existing and near-term quantum computers to solve hard, relevant optimization problems at scale. We present the success of our algorithm in solving a 123-node problem using 123 qubits on IBM quantum hardware. Finally, supported by analysis of what can be achieved with access to larger devices and improved error-rates, these results help build a clearer path to finding advantage in optimization for quantum computing.