QAOA-based Quantum Solver for Unconstrained and Constrained Binary Optimization Problems using up to 156 Qubits

We introduce a comprehensive QAOA-based quantum solver for binary combinatorial optimization problems on gate-model quantum computers that consistently delivers correct solutions for problems with up to 156 qubits. We provide an overview of the internal workflow, describing the integration of a customized ansatz and variational parameter update strategy, efficient error suppression in hardware execution, and scalable post-processing to correct for bit-flip errors. We benchmark this solver on IBM quantum computers for several classically nontrivial unconstrained and constrained binary optimization problems—the entire optimization is conducted on hardware with no use of classical simulation or prior knowledge of the solution. We demonstrate the performance of the solver on a variety of combinatorial optimization problems: Max-Cut, finding the ground state of a cubic Ising spin glass, Maximum Independent Set, Max-Sat, Max-k-Cut and more. For most problems investigated, graph topologies are not matched to device connectivity and demonstrate the ability to find the optimal solution with Max-Cut on regular graphs with density up to 15%. For the problems presented, the Q-CTRL solver outperforms a heuristic local solver used to indicate the relative difficulty of the problems pursued.