Scaling quantum optimization to the utility scale - solving nontrivial binary optimization problems with quantum computers

Quantum computing holds promise for revolutionizing how we solve complex optimization problems that are ubiquitous in various fields like logistics and networking. However, current noisy quantum hardware limits the applicability of hybrid quantum-classical algorithms that are theorized to perform well in ideal conditions. This study showcases how a novel hybrid algorithm combined with a comprehensive error suppression pipeline can efficiently solve large-scale binary optimization problems, pushing the boundaries of what is currently possible with existing quantum hardware and bringing us closer to an era where quantum computers can solve relevant real-world problems. Our novel implementation demonstrates exceptional performance in solving binary-optimization problems on a 156-qubit gate-model IBM quantum computer by leveraging advanced error suppression techniques. We solve MaxCut on graphs up to 156 nodes and consistently find the maximal cut. For 127-node cubic spin-glass problems, we found the true ground state for 4 of the 6 problems we studied, including for a problem where a quantum annealer previously failed to find the solution.