Simulating QAOA with Spin-Boson Systems

The Quantum Approximate Optimization Algorithm (QAOA) is a leading quantum heuristic for combinatorial optimization, with potential for quantum advantage on intermediate-term hardware. While QAOA guarantees optimal solutions at infinite depth, its behavior at large but finite depths pp is not well understood. We develop a mapping between evaluating average QAOA energies for spin-glass systems in the thermodynamic limit and simulating a related spin-boson system. Using this mapping, we provide evidence that QAOA efficiently solves the Sherrington-Kirkpatrick model in the average case, with simulations reaching depths up to p=160s. This approach generalizes to higher-order and mixed-order spin-glass models, enabling exploration of QAOA’s performance on challenging instances. Our results advance the understanding of QAOA in regimes relevant to intermediate-term quantum devices and offer a new framework for benchmarking QAOA on well-studied problems.