APS Logo

Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays

POSTER

Abstract

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.

Publication: Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays (2022, in preparation)

Presenters

  • Madelyn Cain

    Harvard University

Authors

  • Sepehr Ebadi

    Harvard University

  • Alexander Keesling

    Harvard University, QuEra, QuEra Computing, Harvard University

  • Madelyn Cain

    Harvard University

  • Tout T Wang

    Harvard University

  • Harry Levine

    Harvard University, AWS Center for Quantum Computing, Harvard University, AWS Center for Quantum Computing

  • Dolev Bluvstein

    Harvard University

  • Giulia Semeghini

    Harvard University

  • Ahmed Omran

    Harvard University, QuEra Computing

  • Jin-Guo Liu

    Harvard University, QuEra Computing

  • Rhine Samajdar

    Harvard University

  • Xiu-Zhe Luo

    University of Waterloo, QuEra Computing, Perimeter Institute for Theoretical Physics

  • Beatrice Nash

    Harvard University

  • Xun Gao

    Harvard University

  • Boaz Barak

    Harvard University

  • Edward Farhi

    Massachusetts Institute of Technology, Google Quantum AI

  • Subir Sachdev

    Harvard University

  • Nathan Gemelke

    QuEra Computing, Inc., QuEra Computing

  • Leo Zhou

    Harvard University, California Institute of Technology

  • Soonwon Choi

    Center for Theoretical Physics, MIT, University of California, Berkeley, Massachusetts Institute of Technology

  • Hannes Pichler

    Caltech, Innsbruck, University of Innsbruck; Austrian Academy of Sciences, University of Innsbruck, IQOQI

  • Sheng-Tao Wang

    QuEra Computing Inc., QuEra Computing, Inc., QuEra Computing

  • Markus Greiner

    Harvard University

  • Vladan Vuletic

    Massachusetts Institute of Technology MIT, Massachusetts Institute of Technology

  • Mikhail Lukin

    Harvard University