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
| CREATOR | Ralfs Āboliņš, Andris Ambainis |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20671 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22758