Quantum Optimization of Maximum Independent Set Using Rydberg Atom Arrays

Madelyn Cain, Harvard University

Photo of Madelyn Cain

Realizing quantum speedup for solving practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays composed of up to 289 coupled qubits in two spatial dimensions, we experimentally investigate quantum optimization algorithms for solving the Maximum Independent Set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of nonplanar graphs with programmable connectivity. We find that the problem's hardness is controlled by the solution degeneracy and the number of local minima, and experimentally benchmark the quantum algorithm's performance against optimized classical simulated annealing. On the hardest instances, we observe a superlinear quantum speedup in finding exact solutions for sufficiently long evolution times beyond the shallow-circuit-depth regime, and analyze its origins.

Abstract Author(s): Madelyn Cain, Sepehr Ebadi, Alexander Keesling, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, Jin-Guo Liu, Rhine Samajdar, Xiu-Zhe Luo, Beatrice Nash, Xun Gao, Boaz Barak, Edward Farhi, Subir Sachdev, Nathan Gemelke, Leo Zhou