A sharp interaction-degree threshold for simulating QAOA

Ralfs Āboliņš, Andris Ambainis

We identify a sharp interaction-degree threshold for the classical simulation of QAOA with $2$-local cost functions. At degree~$3$, classical sampling from depth-$1$ QAOA, even wit…