Tommaso Marena

The Quantum Approximate Optimization Algorithm (QAOA) promises quantum advantage on combinatorial optimization, yet consistently fails on sparse random instances like 3-regular MaxCut despite strong performance on dense models. This work proves the failure arises from a topological barrier: the Overlap Gap Property (OGP). We formalize "distributional stability" for local quantum circuits via Wasserstein distance (Theorem 1: shallow QAOA satisfies $W_1(P_\xi, P_{\xi'}) \le O(p\Delta\log\Delta)\cdot k$ for $k$ differing constraints). OGP---well-separated near-optimal solution clusters---makes stability incompatible with success: circuits cannot bridge $\Theta(n)$ Hamming gaps along instance interpolation paths unless $p = \Omega(n/\Delta)$ (Theorem 2). Sparse-dense contrast explains empirics: 3-regular MaxCut exhibits $35%-95%$ OGP gaps (bimodal overlaps); SK lacks OGP (continuous via Parisi RSB). Barren plateau fixes address trainability, not reachability. Experiments ($n=8,10,12$) confirm predicted signatures. Impact: NISQ should target non-OGP problems. Local QAOA needs superlinear depth on sparse NP-hard instances. Provides first unified topological hardness for quantum optimization.