The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms

@misc{goh2026overlap,
  title = {{The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms}},
  author = {Mark Goh and Thorge Müller},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.35131},
  eprint = {2609.35131},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35131},
}

TY  - UNPB
TI  - The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms
AU  - Mark Goh
AU  - Thorge Müller
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.35131
UR  - https://arxiv.org/abs/2609.35131
AB  - 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.
ER  -