A sharp interaction-degree threshold for simulating QAOA
This work provides a rigorous complexity-theoretic boundary for classical simulation of QAOA, relevant to quantum computing researchers assessing quantum advantage.
The paper identifies a sharp threshold in interaction degree for 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, while at degree 2, exact classical sampling from depth-p QAOA runs in polynomial time for p = O(log n).
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.