  We introduce a relax-and-round approach embedding the quantum approximate
optimization algorithm (QAOA) with $p\geq 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 maintains the infinite-depth optimal
performance guarantee of the QAOA. 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.
