BIMSA >
YMSC-BIMSA Quantum Information Seminar
Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
Organizer
Speaker
Madelyn Cain
Time
Friday, March 11, 2022 9:30 AM - 12:15 PM
Venue
JCY-1
Online
Zoom 388 528 9728
(BIMSA)
Abstract
Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. I will present experimental investigations of quantum algorithms for solving the Maximum Independent Set problem using Rydberg atom arrays with up to 289 qubits in two spatial dimensions. I will outline how we use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and apply them to systematically explore a class of graphs with programmable connectivity. Next, I will discuss the results of benchmarking the quantum algorithm's performance against classical simulated annealing and explain graph properties that control the problem hardness. Finally, I will explain our observations of a superlinear quantum speedup on the hardest graphs in finding exact solutions in the deep circuit regime and analyze its origins.