Curator's Take
This article reveals a fascinating complexity cliff in quantum algorithms, showing that the classical simulability of QAOA (Quantum Approximate Optimization Algorithm) changes dramatically based on a single parameter: the interaction degree of the cost function. While degree-2 problems remain classically tractable even for logarithmically deep circuits, degree-3 problems become so hard that efficient classical simulation would collapse fundamental assumptions in computational complexity theory. This sharp threshold provides crucial guidance for quantum algorithm designers, suggesting that degree-3 QAOA instances could be natural candidates for demonstrating quantum advantage, though the authors note an important caveat that the hardest instances may not correspond to practically useful optimization problems. The work helps map the precise boundaries where quantum computers might outperform classical methods, moving beyond broad claims toward mathematically rigorous complexity separations.
— Mark Eatherly
Summary
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.