Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer

Understand

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 approximation ratio of 99% over a random ensemble of thousands of problem instances.