COMPUTATIONAL RESEARCH in BOSTON and BEYOND (CRIBB)
| Date | May 6, 2022 |
|---|---|
| Speaker | Madelyn Cain (Harvard) |
| Topic | Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays |
| Abstract | Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. While it has long been known theoretically that many quantum algorithms can outscale classical algorithms, demonstrating quantum speedup on problems with practical utility has remained elusive. 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. |
| Biography |
Archives
Acknowledgements
We thank the generous support of MIT IS&T, CSAIL, and the Department of Mathematics for their support of this series.