Catching up on classical combinatorial solvers

Combinatorial optimization was one of the first areas where the community saw a potential for noisy intermediate-scale quantum computers to deliver quantum utility. Despite progress in scaling and improving hardware and developing new quantum algorithms, several challenges remain to achieve competitiveness against classical solvers. Here, we implement a hybrid quantum-classical algorithm inspired by semidefinite programming approaches to solve the maximum cut problem on random 3-regular graphs [1, 2]. We leverage the structure of the input problems to address sizes beyond what current quantum machines can naively handle. We experimentally solve problems with up to several thousands of variables on Rigetti superconducting qubits and attain an average performance of 99% over a random ensemble of thousands of problem instances. Given the near-optimality of our quantum algorithm, we benchmark it against state-of-the-art classical methods such as simulated annealing, MQLib heuristics, and the commercial solver Gurobi. We show 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.