A sharp interaction-degree threshold for simulating QAOA

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 with small multiplicative error would collapse the polynomial hierarchy to its third level. At degree 2, exact classical sampling from depth-p QAOA on n qubits runs in time n^O(1) whenever p = O\(log n\). The hard degree-3 instances have trivially optimizable cost functions, so sampling hardness does not by itself imply a quantum optimization advantage.