Practicalities of solving Maximum Independent Set beyond King's lattice on Neutral Atom Quantum Computers

The problem of finding the Maximum Independent Set (MIS) has been widely researched with neutral-atom quantum computers [Science 376, 1209 (2022)]. The reason is that the ground state of the cost function Hamiltonian maximizes the total number of qubits in the Rydberg state under the blockade constraint. This state corresponds to the most extensive independent set, MIS. However, most demonstrations on neutral-atom quantum computers are limited to the connectivity of a King’s lattice. To effectively compete with classical methods, it is essential to focus on MIS instances that have higher connectivity. Recent studies show that more densely connected 2D embedded MIS problems may indicate a potential area for quantum advantage [PR Research 5, 043277 (2023)].

Bringing this problem back to the near-term quantum perspective, the main challenge is that higher connectivity requires maintaining more interactions within the blocked subspace, which makes simulations more difficult. Second, for hardware experiments, increasing connectivity might mean bringing atoms closer together, which could violate hardware constraints. In our approach, we optimize control schedules classically before deploying them on the quantum hardware, ensuring compliance with hardware constraints. In our work, we present solutions to classes of MIS instances beyond the King’s lattice using a neutral atom quantum computer.