Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

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.

Comments
108 pages, 8 figures, 2 tables

Related papers

Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size

Jahan Claes, Wim van Dam

This paper studies the application of the Quantum Approximate Optimization Algorithm (QAOA) to spin-glass models with random multi-body couplings in the limit of a large number of spins. We show that for such mixed-spin models the performance of depth 1 QAOA is independent of the specific instance in the limit of infinite sized systems and we give an explicit formula for the expected performance. We also give explicit expressions for the higher moments of the expected energy, thereby proving that the expected performance of QAOA concentrates.

arXiv:2102.12043•Quantum•Sep 15, 2021•13 citations

Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm

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.

arXiv:2505.07929•Physical Review Letters•Apr 14, 2026•2 citations

Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models

Joao Basso, David Gamarnik, Song Mei +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove concentration properties at any constant level (number of layers) on ensembles of random combinatorial optimization problems in the infinite size limit. These ensembles include mixed spin models and Max-q-XORSAT on sparse random hypergraphs. Our analysis can be understood via a saddlepoint approximation of a sum-over-paths integral. This is made rigorous by proving a generalization of the multinomial theorem, which is a technical result of independent interest. We then show that the performance of the QAOA at constant levels for the pure q-spin model matches asymptotically the ones for Max-q XORSAT on random sparse Erdôs-Rényi hypergraphs and every large-girth regular hypergraph. Through this correspondence, we establish that the average-case value produced by the QAOA at constant levels is bounded away from optimality for pure q-spin models when $q\geq 4$ and is even. This limitation gives a hardness of approximation result for quantum algorithms in a new regime where the whole graph is seen.

arXiv:2204.10306•Annual Symposium on Foundations of Computer Science•Oct 1, 2022•24 citations

Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models

Elisabeth Wybo, Martin Leib

The parity mapping provides a geometrically local encoding of the Quantum Approximate Optimization Algorithm (QAOA), at the expense of having a quadratic qubit overhead for all-to-all connected problems. In this work, we benchmark the parity-encoded QAOA on spin-glass models. We address open questions in the scaling of this algorithm. In particular, we show that for fixed number of parity-encoded QAOA layers, the performance or the output energy, vanishes towards zero (the value achieved by random guessing) with problem size N as N−1/2 . Our results suggest that the parity-encoded QAOA does not have a promising scaling compared to the standard version of QAOA. We perform tensor-network calculations to confirm our results, and comment on the concentration of optimal QAOA parameters over problem instances.

arXiv:2311.02151•Quantum•Dec 10, 2024•1 citation

The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p . While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within ( 1 − ϵ ) times the ground state energy. We hope to match its performance with the QAOA.Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the 2 p QAOA parameters, in the infinite size limit that can be evaluated on a computer with O ( 16 p ) complexity. We evaluate the formula up to p = 12 , and find that the QAOA at p = 11 outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as n → ∞ , measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.

arXiv:1910.08187•Quantum•Jul 7, 2022•226 citations

Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator

Guido Pagano, Aniruddha Bapat, Patrick Becker +13 more

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

arXiv:1906.02700•Proceedings of the National Academy of Sciences•Oct 6, 2020•261 citations
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.
This paper studies the application of the Quantum Approximate Optimization Algorithm (QAOA) to spin-glass models with random multi-body couplings in the limit of a large number of spins. We show that for such mixed-spin models the performance of depth 1 QAOA is independent of the specific instance in the limit of infinite sized systems and we give an explicit formula for the expected performance. We also give explicit expressions for the higher moments of the expected energy, thereby proving that the expected performance of QAOA concentrates.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove concentration properties at any constant level (number of layers) on ensembles of random combinatorial optimization problems in the infinite size limit. These ensembles include mixed spin models and Max-q-XORSAT on sparse random hypergraphs. Our analysis can be understood via a saddlepoint approximation of a sum-over-paths integral. This is made rigorous by proving a generalization of the multinomial theorem, which is a technical result of independent interest. We then show that the performance of the QAOA at constant levels for the pure q-spin model matches asymptotically the ones for Max-q XORSAT on random sparse Erdôs-Rényi hypergraphs and every large-girth regular hypergraph. Through this correspondence, we establish that the average-case value produced by the QAOA at constant levels is bounded away from optimality for pure q-spin models when q≥4q\geq 4q≥4 and is even. This limitation gives a hardness of approximation result for quantum algorithms in a new regime where the whole graph is seen.
The parity mapping provides a geometrically local encoding of the Quantum Approximate Optimization Algorithm (QAOA), at the expense of having a quadratic qubit overhead for all-to-all connected problems. In this work, we benchmark the parity-encoded QAOA on spin-glass models. We address open questions in the scaling of this algorithm. In particular, we show that for fixed number of parity-encoded QAOA layers, the performance or the output energy, vanishes towards zero (the value achieved by random guessing) with problem size N as N−1/2 . Our results suggest that the parity-encoded QAOA does not have a promising scaling compared to the standard version of QAOA. We perform tensor-network calculations to confirm our results, and comment on the concentration of optimal QAOA parameters over problem instances.
The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p . While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within ( 1 − ϵ ) times the ground state energy. We hope to match its performance with the QAOA.Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the 2 p QAOA parameters, in the infinite size limit that can be evaluated on a computer with O ( 16 p ) complexity. We evaluate the formula up to p = 12 , and find that the QAOA at p = 11 outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as n → ∞ , measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.
Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.