A sharp interaction-degree threshold for simulating QAOA

Ralfs Āboliņš, Andris Ambainis · 2026

Read A sharp interaction-degree threshold for simulating QAOA by Ralfs Āboliņš, Andris Ambainis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22758.txt.

Description

Āboliņš and Ambainis pin down a degree threshold for classical simulation of QAOA on two local cost functions. At degree 3, even approximate depth 1 sampling within a generous multiplicative error would collapse the polynomial hierarchy down to its third level. At degree 2, exact sampling from depth p QAOA runs in polynomial time whenever depth grows at most logarithmically. The hard degree 3 instances carry trivially optimizable costs, so sampling hardness alone does not imply a quantum optimization edge. The threshold thus separates easy and hard simulation regimes cleanly.

Catalog record

CREATORRalfs Āboliņš, Andris Ambainis
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20671
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.22758

Browse the full library · About the Tower of Babel