Overview of the main technical result: the equivalence between the task of computing the infinite-size limit QAOA energy in the average case and the task of simulating a spin-boson system. Image: Abid Khan, JPMorganChase
Evidence that the QAOA Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case
Overview of the main technical result: the equivalence between the task of computing the infinite-size limit QAOA energy in the average case and the task of simulating a spin-boson system. Image: Abid Khan, JPMorganChase
Quantum computers offer a path to solving optimization problems that are intractable for even the most powerful classical machines. A foundational method in quantum computing research, the Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid classical-quantum algorithm designed to tackle complex combinatorial optimization problems in domains such as finance, physics, and machine learning. Using the ALCF’s Polaris supercomputer, researchers from JPMorganChase and Argonne National Laboratory have demonstrated that QAOA can efficiently approximate solutions to a challenging model for disordered systems, providing new insights into the performance and scalability of quantum algorithms.
Challenge
The Sherrington-Kirkpatrick (SK) model has become a key tool for understanding the behavior of complex energy landscapes. Finding its exact ground state is an NP-hard optimization problem in the worst case, and even approximate solutions typically require super-polynomial time on classical machines. While quantum algorithms like QAOA have been proposed to outperform classical methods, past studies of QAOA on the SK model were limited by exponential computational costs that prevented exploration at large circuit depths.
Approach
To overcome this bottleneck, the researchers leveraged the ALCF’s Polaris supercomputer to develop a method to compute average QAOA energy for the SK model in the infinite-size limit by mapping it to a spin-1/2 particle coupled to multiple bosonic modes. The team used tensor network simulations, specifically matrix product state (MPS) techniques, to model this spin-boson system efficiently while constraining entanglement and truncating the Fock-space dimension. By distributing workloads across up to 160 NVIDIA GPUs, Polaris enabled large-scale parallel simulations, with QAOA parameters optimized up to depth p = 80 and energies computed up to p = 160.
Results
The team demonstrated that QAOA achieves progressively better approximations to the SK model’s optimal energy as circuit depth increases, reaching a 2.2 percent deviation at depth 160. Their analysis suggests that a (1 – ε) approximation can be achieved in time scaling as O(n/ε1.13), providing numerical evidence for a potential polynomial quantum speedup over classical approaches. When applied to finite-size SK instances (up to 30 qubits) using parameters from the infinite-size simulations, QAOA achieved success probabilities consistent with theoretical predictions, demonstrating that it can efficiently approximate the SK model in the average case.
Impact
The team’s work provides the strongest numerical evidence to date that QAOA can efficiently approximate solutions to the SK model. The techniques developed here not only extend the frontier of QAOA simulation but also provide a practical benchmark for evaluating quantum advantage. As quantum hardware continues to evolve, these findings support the promise of QAOA as a scalable algorithm for combinatorial optimization problems in finance, physics, and beyond.
Publications
Boulebnane, S., A. Khan, M. Liu, J. Larson, D. Herman, R. Shaydulin, and M. Pistoia. “Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case,” arXiv (preprint). https://doi.org/10.48550/arXiv.2505.07929
