OGP LIMITS LIMIT SWAPPING IN QAOA

Abstract

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.