Abstract The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erdös-Renyi hypergraph, then a random regular hypergraph is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even q ≥ 4, Max- q -XORSAT is bounded away from optimality when optimized using asymptotic analysis due to the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth p ≤ ϵ log n , providing an improvement over limitation at constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max- q -XORSAT problems. We also provide some numerical evidence that the limitation should be extended to odd q by showing that the OGP exists for the Max-3-XORSAT on random regular graphs.
Combinatorial optimization is regarded as a potentially promising application of near and long-term quantum computers. The best-known heuristic quantum algorithm for combinatorial optimization on gate-based devices, the Quantum Approximate Optimization Algorithm (QAOA), has been the subject of many theoretical and empirical studies. Unfortunately, its application to specific combinatorial optimization problems poses several difficulties: among these, few performance guarantees are known, and the variational nature of the algorithm makes it necessary to classically optimize a number of parameters. In this work, we partially address these issues for a specific combinatorial optimization problem: diluted spin models, with MAX-CUT as a notable special case. Specifically, generalizing the analysis of the Sherrington-Kirkpatrick model by Farhi et al., we establish an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree
d for an arbitrary constant number of layers
p and as the problem size tends to infinity. This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs of expected degree
d, in the limit
d→∞, and the Sherrington-Kirkpatrick model, and gives good QAOA variational parameters for MAX-CUT applied to Erdos-Renyi graphs. We then partially generalize the latter analysis to graphs with a degree distribution rather than a single degree
d, and finally to diluted spin-models with
D-body interactions (
D≥3). We validate our results with numerical experiments suggesting they may have a larger reach than rigorously established; among other things, our algorithms provided good initial, if not nearly optimal, variational parameters for very small problem instances where the infinite-size limit assumption is clearly violated.
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for combinatorial optimization problem. We show that under the assumption that the Overlap Gap Property (OGP) in the solution space for the Max-q-XORSAT is a monotonic increasing function, the swapping of limits in QAOA leads to suboptimal results limited by the OGP. Furthermore, since the performance of QAOA for the pure q-spin model matches asymptotically for Max-q-XORSAT on large-girth regular hypergraph, we show that the average-case value obtained by QAOA for the pure q-spin model for even q≥4 is bounded away from optimality even when the algorithm runs indefinitely. This suggests that a necessary condition for the validity of limit swapping in QAOA is the absence of OGP in a given combinatorial optimization problem. A corollary of this is that the spectral gap of a Hamiltonian exhibiting the OGP will close in the thermodynamic limit resulting in a limitation of the quantum adiabatic theorem and efficient optimization of QAOA parameters. Furthermore, the results suggests that even when sub-optimised, the performance of QAOA on spin glass is equal in performance to Montanari's classical algorithm in solving the mean field spin glass problem, the best known classical algorithm.
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) 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.
The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and practical performance, yet for general combinatorial optimization problems the expected performance and classical simulability of fixed-round QAOA remain unclear. Focusing on Max-Cut, we first show that for general graphs and any fixed round
p≥2, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is
NP-hard, and that approximating this expectation within additive error
2−O(n) in the number
n of vertices is already
NP-hard. To evaluate the expected performance of QAOA, we propose a dynamic programming algorithm leveraging tree decomposition. As a byproduct, when the
p-local treewidth grows at most logarithmically with the number of vertices, this yields a polynomial-time \emph{exact} evaluation algorithm in the graph size
n. Beyond Max-Cut, we extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO). Finally, we provide reproducible evaluations for rounds up to
p=3 on representative structured families, including the generalized Petersen graph
GP(15,2), double-layer triangular 2-lifts, and the truncated icosahedron graph
C60, and report cut ratios while benchmarking against locality-matched classical baselines.