Degree-Guided Adiabatic Quantum Algorithm for MIS with Neutral Atoms

We present a quantum adiabatic algorithm for solving MIS with Rydberg atoms, which uses graph degrees to engineer the Hamiltonian for adiabatic evolution. Our approach extends the algorithm of Pichler et al. for MIS state preparation, which uses time-dependent global controls to excite atoms while the Rydberg blockade mechanism suppresses adjacent excitations. To accelerate adiabatic evolution, we introduce local light shifts that favor excitation of low-degree nodes and constrain the final Hamiltonian so that energy scales inversely with the number of Rydberg excitations, preventing convergence to non-MIS states. Benchmarking our degree-dependent MIS algorithm with the traditional adiabatic algorithm on a set of 1000 MIS instances, we demonstrate numerically that our algorithm inflates the minimal spectral gap and, consequently, accelerates the convergence. By fitting power-law relations for both the time-to-solution and success probability metrics as a function of the hardness parameter, we demonstrate a superior scaling exponent for our algorithm over the traditional global protocol. Furthermore, the classical Hamiltonian engineering step required to construct degree-dependent controls introduces only polynomial overhead. These results indicate that our algorithm can be used to extend the size of graphs for which MIS can be found on physical hardware. Moreover, our approach extends beyond MIS to additional graph problems such as MAX-CUT.