  Achieving high-quality solutions faster than classical solvers on
computationally hard problems is a challenge for quantum optimization to
deliver utility. Using a superconducting quantum computer, we experimentally
investigate the performance of a hybrid quantum-classical algorithm inspired by
semidefinite programming approaches for solving the maximum cut problem on
3-regular graphs up to several thousand variables. We leverage the structure of
the input problems to address sizes beyond what current quantum machines can
naively handle. We attain an average performance of 99% over a random ensemble
of thousands of problem instances. We benchmark the quantum solver against
similarly high-performing classical heuristics, including the Gurobi optimizer,
simulated annealing, and the Burer-Monteiro algorithm. A runtime analysis shows
that the quantum solver on large-scale problems is competitive against Gurobi
but short of others. We explore multiple leads to close the gap and discuss
prospects for a practical quantum speedup.
