Quantum, relax, and round

ORAL

Abstract

We introduce a relax-and-round approach [1] embedding the quantum approximate optimization algorithm (QAOA) with p≥1 layers. We show for many problems, including Sherrington-Kirkpatrick spin glasses, that at p=1, it is as accurate as its classical counterpart and better than the QAOA for all p. Employing a different rounding scheme, we prove the method shares the performance of the Goemans-Williamson algorithm for the maximum cut problem on certain graphs. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms.

[1] https://arxiv.org/abs/2307.05821

* – This work is supported by the Defense Advanced Research Projects Agency (DARPA) under Agreement No. HR00112090058.– This research used resources of the National Energy Research Scientific Computing Center (NERSC), a U.S. Department of Energy Office of Science User Facility located at Lawrence Berkeley National Laboratory, operated under Contract No. DE-AC02-05CH11231 using NERSC award DDR-ERCAP0024427.

–

Publication: https://arxiv.org/abs/2307.05821

Presenters

  • Maxime Dupont

    Rigetti Computing

Authors

  • Maxime Dupont

    Rigetti Computing

  • Bhuvanesh Sundar

    Rigetti Computing, Department of Physics and Astronomy, Rice University