Benchmarking hardware experiments for the quantum relax-and-round algorithm against classical combinatorial solvers

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 attain an average performance of 99% over a random ensemble of thousands of problem instances. We describe how we benchmark the quantum solver against similarly high-performing classical heuristics, including the Gurobi optimizer, simulated annealing, and the Burer-Monteiro algorithm, and show that the quantum solver on large-scale problems is competitive against Gurobi. We explore multiple leads to close the gap against the two other solvers and discuss prospects for a practical quantum speedup.