Curator's Take
This article shows that even when the quantum approximate optimization algorithm is lifted to a semiclassical large‑spin setting, it does not beat the standard spin‑½ QAOA on the Sherrington‑Kirkpatrick model, converging to the optimal Parisi energy only as log(p)/p (or 1/p with noise removal). By revealing that both quantum and semiclassical versions share the same asymptotic scaling, the work tempers expectations of a generic quantum speedup for dense spin‑glass optimization and highlights the need for new algorithmic ideas or problem structures. It also provides a concrete benchmark for future QAOA variants, reminding practitioners that depth alone may not be enough to unlock a practical advantage.
— Mark Eatherly
Summary
We perform a semiclassical, large-spin S, analysis of the quantum approximate optimization algorithm (QAOA) on the Sherrington-Kirkpatrick (SK) model, using the truncated Wigner approximation. Fixing the QAOA angles to their previously determined optimal S=1/2 values, we observe a non-monotonic dependence of the final energy on the spin. At small S the semiclassics is dominated by noise, while the large-S limit is constrained by the exponential growth of the initial fluctuations. For a depth-p QAOA one achieves the optimal balance at S of order p, resulting in a convergence of the final energy to the Parisi value like log(p)/p. We find that the semiclassics slightly outperforms the true spin-1/2 QAOA, and thus suggest they both converge to the Parisi value in the same way. Finally, removing all the initial noise, and re-optimizing the parameters to account for that change, results in superior performance with 1/p convergence.