arXiv:2609.40309
Decoupling of the QAOA into independent spin-boson systems and high-depth performance on pure and mixed spin glasses
Sami Boulebnane, Abid Khan, Pragna Subrahmanya, Dylan Herman, Edward Farhi, Benjamin Villalonga, Ruslan Shaydulin
Abstract
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.
AI Summary
The paper studies how QAOA performance on dense Gaussian spin glasses can be evaluated at depths beyond exact recursive formulas, and how optimized energies approach algorithmic thresholds. It covers arbitrary finite mixtures of interaction orders, extending an existing spin-boson mapping for the quadratic Sherrington–Kirkpatrick model. A cavity calculation in the circuit’s spin path integral establishes that, after disorder averaging and at fixed depth $p$, temporal $Z$ correlators on any constant-size spin set factorize in the thermodynamic limit. Each factor is reproduced by a single spin coupled to $p$ bosonic modes with recursively determined couplings. The resulting energy recursion can be evaluated using matrix product states. Extracting equal-time spin–annihilation expectations replaces evolution of $p$ separate states, reducing memory and sequential computation by a factor of $p$. Numerical optimization covers pure orders $2\leq q\leq17$, typically reaching tens of layers, and reaches $p=160$ for $q=2$. Higher orders show slower improvement and increasingly narrow optimization basins. Power-law fits with asymptotes fixed to known algorithmic thresholds give exponents decreasing from $0.88$ at $q=2$ to $0.39$ at $q=17$. A quadratic–eighth-order interpolation exhibits discontinuous optimized angles and cusps in optimized energy. The mapping does not provide instance-specific output sampling, and efficient MPS evaluation is empirical rather than guaranteed. Threshold-pinned fits test consistency, not convergence. Finite-size energy-error bounds decay as $n^{-\alpha_p}$ up to logarithms, but $\alpha_p$ deteriorates inverse-factorially with depth and sufficient-size prefactors grow superexponentially; these bounds are explicitly regarded as loose.
Error found: The abstract's decoupling statement omits that the proved factorization concerns disorder-averaged path-integral correlators on fixed-size subsystems at fixed depth in the thermodynamic limit, rather than individual-instance or full-state independence. The abstract's assertion that a quantum computer is required for sampling is unsupported and, as a blanket statement over the allowed models, contradicted by the classically sampleable q=1 random-field case.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 108 pages, 8 figures, 2 tables