A Methodology for Simulating High Depth QAOA

Sami Boulebnane, Abid Khan, Minzhao Liu +4 more

The quantum approximate optimization algorithm (QAOA) achieves monotonically improving performance with circuit depth p, yet the study of the high-depth regime has been obstructed by the exponential in p cost of existing exact evaluation techniques. In this Letter, we prove that, in the infinite-size limit, the depth-p QAOA state for the Sherrington-Kirkpatrick (SK) model converges to the state of a spin coupled to p bosonic modes. We simulate the spi-boson system using matrix product states and provide numerical evidence that QAOA obtains a (1-ε) approximation to the optimal energy of the SK model with circuit depth O(n/ε^{1.13}) in the average case. The modest computational cost of our approach allows us to optimize QAOA parameters and observe that QAOA achieves ϵ≲2.2% at p=160 in the infinite-size limit, extending far beyond p≤20 accessible to prior exact methods. Our mapping provides a many-body route to study and optimize high-depth QAOA in regimes previously inaccessible to exact evaluation.

Gereon Koßmann, Lennart Binkowski, Lauritz van Luijk +2 more

Gereon Koßmann, Lennart Binkowski, Lauritz van Luijk +2 more

Sami Boulebnane, Abid Khan, Pragna Subrahmanya +4 more

The Quantum Approximate Optimization Algorithm (QAOA) is regarded as a promising candidate for near-term quantum advantage in combinatorial optimization, yet our ability to study it at scale is limited. Exact recursive formulas have been introduced for predicting QAOA performance on large spin glasses, but the computational cost of evaluating them grows exponentially with the number of QAOA layers, preventing the study of QAOA in the promising high-depth regime. In this work, we show that for the task of computing QAOA energy on any mixed dense spin glass problem, spins approximately decouple into independent spin-boson systems. In the infinite-size limit, the decoupling becomes exact, establishing the spin-boson mapping as a natural framework for the many-body physics of QAOA. This generalized spin-boson mapping gives a recursive procedure for computing QAOA energies that can be executed at modest cost using tensor networks. As a numerical application, we optimize QAOA on pure and mixed spin glasses at depths intractable for prior techniques, observing that higher-degree problems require more layers for a comparable approximation ratio while angle optimization becomes more challenging. While decoupling enables the evaluations of QAOA energies at large size and depth, it does not enable strong simulation of QAOA; a quantum computer is required to sample the bitstring corresponding to the predicted energy.

Danylo Lykov, Ruslan Shaydulin, Yue Sun +2 more

Until high-fidelity quantum computers with a large number of qubits become widely available, classical simulation remains a vital tool for algorithm design, tuning, and validation. We present a simulator for the Quantum Approximate Optimization Algorithm (QAOA). Our simulator is designed with the goal of reducing the computational cost of QAOA parameter optimization and supports both CPU and GPU execution. Our central observation is that the computational cost of both simulating the QAOA state and computing the QAOA objective to be optimized can be reduced by precomputing the diagonal Hamiltonian encoding the problem. We reduce the time for a typical QAOA parameter optimization by eleven times for n = 26 qubits compared to a state-of-the-art GPU quantum circuit simulator based on cuQuantum. Our simulator is available on GitHub: https://github.com/jpmorganchase/QOKit

Matthew Brunet, Shilpi Shah, Mostafa Atallah +2 more