arXiv:2609.35131
The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms
Mark Goh, Thorge Müller
Abstract
In this paper, we prove that the Mean-Field Approximate Optimization Algorithm (MF-AOA), a quantum-inspired classical algorithm of the Quantum Approximate Optimization Algorithm (QAOA), is unable to give arbitrary near optimal solution for problems exhibiting the Overlap Gap Property (OGP). We show this by relating the MF-AOA to finite-memory Approximate Message Passing (AMP) algorithms, which are known to be limited in performance by the OGP. Thus, our paper argues that problems exhibiting the OGP are one such instance where the QAOA can outperform the MF-AOA and AMP algorithms in general. We supplement this by numerically simulating the performance of the QAOA on instances of Max-$4$-XORSAT that exhibit the OGP and find that the QAOA is able to surpass the barrier, while our finite-size scaling analysis favors a super-polynomial over a polynomial depth dependence. In addition, we observe a non-differentiable point in the performance of the QAOA near by the OGP barrier, where the optimal QAOA parameters change from an adiabatic to a non-adiabatic schedule.
AI Summary
The paper asks whether the overlap gap property (OGP) separates QAOA from its classical mean-field analogue, MF-AOA, and what QAOA depth is needed to cross an OGP-associated energy threshold. The theoretical component represents MF-AOA’s effective-field dynamics as finite-memory approximate message passing (AMP). For a fixed number of iterations $T$, the history-dependent update functions are Lipschitz, with a bound $2\sqrt{T}$ for the spin-response function. With coordinatewise truncation, this permits application of an existing AMP obstruction, conditional on a conjectured extension of OGP to $[-1,1]^N$ for even-order mean-field spin glasses with $q\geq4$. The cited theorem controls the continuous output before final binary projection; the formal result concerns fixed-step, truncated dynamics. Classical simulations compare QAOA on sparse Max-$4$-XORSAT instances classified by their finite-instance overlap spectra with MaxCut and non-OGP instances. They find barrier crossing at sufficiently large depth and a change from adiabatic-like to nonadiabatic optimized schedules near the threshold; one $N=15$ example transitions around $p=28$. Ground-state-overlap optimization removes this observed kink. Fits for $N=27,28,29$ favor a logarithmic-depth decay model over a power-law model, with an approximately elevenfold reduction in fitting RMSE. An explicitly optimistic linear extrapolation from $N=15$–$22$ predicts crossing near $p=250$ at $N=50$; it is not claimed as an asymptotic law. Simplified hardware estimates place these depths beyond current superconducting capabilities. The scaling evidence remains finite-size and numerical, rather than an asymptotic quantum-speedup result.
Central claim may not hold: The advertised obstruction for OGP problems relies on a conditional theorem for even-q mean-field spin glasses, not a theorem covering arbitrary OGP problems or the sparse instances simulated. The AMP identification requires fixed iteration count, truncated fields, and bounded initialization, without showing that these modifications preserve conventional MF-AOA's performance. The continuous-output AMP obstruction is not transferred to MF-AOA's returned binary string, whose energy need not obey the continuous-output bound. The evidence favoring super-polynomial depth dependence concerns exact-ground-state success probability rather than the separately measured OGP-barrier crossing depth. Comparing sufficiently deep QAOA against a fixed-step classical obstruction does not establish a separation against MF-AOA or AMP with growing iteration counts.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.