Quantum, relax, and round*

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