Exactly where does quantum optimization become hard to fake classically?

Quantum approximate optimization (QAOA) gets hard to simulate classically at degree-3 interactions — meaning 3-way connections between variables — but stays efficiently simulable at degree 2 even for logarithmically deep circuits. The catch: the hard degree-3 cases have cost functions so simple that a classical computer could already solve the optimization problem trivially. This sharp threshold shows that sampling hardness alone doesn't guarantee a practical quantum advantage in optimization.