Degree-Guided Adiabatic Quantum Algorithm for MIS with Neutral Atoms
Abstract
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.
Related
- General circuit mapping algorithm for neutral atom quantum computers
- Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization
- Adiabatic controlled-Z gate for neutral atoms with Förster-enhanced Rydberg dressing
- Trainable, self-verifying variational quantum eigensolver using adiabatic warm starts
- Geometric perspective on quantum Rabi model: Super adiabatic universality and curvature non-adiabatic effects
BibTeX
@misc{karni2026degreeguided,
title = {{Degree-Guided Adiabatic Quantum Algorithm for MIS with Neutral Atoms}},
author = {Guy Karni and Noam Cohen and Adi Pick},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.16944},
eprint = {2605.16944},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.16944},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Degree-Guided Adiabatic Quantum Algorithm for MIS with Neutral Atoms
AU - Guy Karni
AU - Noam Cohen
AU - Adi Pick
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2605.16944
UR - https://arxiv.org/abs/2605.16944
AB - 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.
ER -