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.

*Center for Ultracold Atoms, the National Science Foundation, Vannevar Bush Faculty Fellowship, the Department of Energy, Office of Naval Research, Army Research Office MURI, DARPA ONISQ program, QuEra Computing, Amazon Web Services, DOE CSGF award, NDSEG award, NSF GRFP award, The Fannie and John Hertz Foundation, Max Planck/Harvard Research Center for Quantum Optics, Army Research Office

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