Lack of quantum advantage in approximate optimization of spin glasses ✛ ✎ ✦
Context
The development of quantum computers drives the search for problems where quantum computing provides a practical advantage. The Quantum Approximate Optimization Algorithm (QAOA) is one of the main contenders for a universal combinatorial solver. However, its real effectiveness compared to classical methods remains a subject of debate. The Sherrington–Kirkpatrick (SK) model is of particular interest, as it has a known exact optimum — the Parisi value. This model is ideal for testing the performance of QAOA under conditions of strong frustration and disorder.
Methods
The researchers performed quasiclassical modeling of QAOA using the truncated Wigner approximation (TWA). This method, widely used in quantum optics and condensed matter physics, replaces quantum evolution with classical spin rotations, while the quantum fluctuations of the initial state are accounted for via the Wigner function, which for large spins reduces to a Gaussian distribution. This approach allows control over the level of quantum noise through an effective spin S: at small S the noise is large, at large S it is suppressed, but then the initial state becomes an unstable fixed point of the classical dynamics. A key parameter was the uncertainty relation, which sets the minimum level of initial fluctuations according to the Heisenberg uncertainty principle.
Results
It was found that the dependence of residual energy on S is nonmonotonic. At small S, entropic noise dominates, hindering effective optimization of the objective function, while at large S, due to superposition the initial state, close to an unstable equilibrium, leads to exponential growth of fluctuations, which also degrades the result. The optimal balance is achieved at S ∝ p (circuit depth). In this regime, the energy converges to the exact Parisi value as log(p)/p, matching the behavior of classical algorithms. Furthermore, numerical experiments showed that the quasiclassics at optimal S yields an energy even lower than the exact QAOA for spin-1/2. This means the quantum version has no advantage. If one completely removes the initial noise and reoptimizes the parameters, the classical dynamics converges as 1/p, outperforming QAOA. Measurements at the end of the evolution binarize the spin variables, finally forming the solution.
Implications
This work calls into question quantum advantage in spin glass optimization problems and points to the need for a deeper understanding of the sources of quantum speedup. If classical methods exhibit similar asymptotics, the advantage of quantum devices may lie only in constant factors that are negated by technological difficulties. The results also highlight the importance of entropic effects in the initialization of quantum algorithms.
Future development
In the future, it will be necessary to investigate other spin glass models and more complex QAOA schemes, including adaptive strategies and noise suppression. Perhaps a combination of classical and quantum approaches that takes into account features of the dynamics will yield better results. It is also interesting to explore the connection with quantum information theory and algorithmic complexity.
Impact
The findings are important for developers of quantum algorithms and optimization specialists, as well as for physicists studying nonequilibrium dynamics in quantum systems.
Next steps
Plans are to verify the observed patterns on real quantum processors and extend the TWA analysis to other variational quantum algorithms. In addition, it will be necessary to rigorously prove the log(p)/p asymptotics for depth p.
Key open problems
The paper is directly connected to the fundamental problem of quantum advantage and the boundary between quantum and classical computing. It also touches on issues of ergodicity and thermalization in many-body systems, where the uncertainty principle limits controllability.
The knowledge machine's view
This section is addressed to the author of the paper and their colleagues. Neighbouring works were found by meaning-based search across our archive, not by word overlap. We do not review: we show the field around the work.
What the work does
The authors tested QAOA on the SK model using the quasiclassical TWA approximation, varying the effective spin S. They demonstrated a nonmonotonic dependence of the residual energy on S, with an optimum at S ∝ p, where the energy converges to the Parisi value as log(p)/p. They found that the optimal quasiclassical approach outperforms exact QAOA for spin 1/2, and purely classical dynamics without initial noise converges even faster.
Where its strength is
The study identifies and quantitatively describes the mechanism that limits quantum advantage in QAOA: the balance between entropic noise at small S and exponential instability of the initial state at large S. This provides a transparent criterion for parameter selection and calls into question the very idea of quantum speedup in this class of problems.
Where it could go next
- It might be interesting to compare the discovered optimum in S with the resources of real quantum devices. In our archive, there is a paper on a quantum computer that saves not only time but also energy: it addresses the efficient use of limited quantum resources, which directly resonates with choosing the optimal operating regime for QAOA.based on: Quantum computers save not just time, but also energy arXiv:2601.08068
- The idea of balancing noise and chaos could be useful for tasks on quantum simulators with giant atoms, where dynamic stability is also crucial. The archive contains an analysis of how giant atoms solve a quantum puzzle: it examines controlling interactions in disordered systems, which could help transfer your approach to physical platforms.based on: Giant Atoms Solve an Unsolvable Quantum Puzzle arXiv:2606.27224
- Your result on the advantage of classical dynamics when over-optimizing parameters is intriguing to compare with approaches where classical methods are used to improve quantum algorithms. We have a piece 'Quantum translator that learns from mistakes'—there, classical post-processing corrects quantum errors, which might suggest hybrid schemes combining your classical dynamics with quantum blocks.based on: A Quantum Translator That Learns from Its Mistakes arXiv:2604.27648
Worth trying
- Test whether the optimal scaling S ∝ p holds for other frustrated models, e.g., graphs with finite connectivity.
- Explore a hybrid scheme: use classical TWA dynamics with optimal noise to generate candidates, then a shallow quantum circuit for final refinement.
- Investigate whether exponential instability at large S can be suppressed by periodic 'cooling' of initial fluctuations, similar to stabilization methods in quantum optics.
Why this may matter
The discovery of an optimal regime where quasiclassics outperforms exact QAOA could shift the focus from the race for qubit count to finer tuning of noise and initial states. This may influence the design of future quantum optimizers and the criteria for assessing quantum supremacy.
Nearby works in our archive
- Quantum Rainbow: How a Tiny Computer Sorts Mountains of Datasimilarity 0.63
- Quantum First Aid for Power Gridssimilarity 0.61
- Quantum computers save not just time, but also energysimilarity 0.60
- Quantum Dispatcher for the Power Gridsimilarity 0.60
- Giant Atoms Solve an Unsolvable Quantum Puzzlesimilarity 0.59
- A Quantum Translator That Learns from Its Mistakessimilarity 0.59
The closest work in the archive sits at 0.63 by meaning — the usual level for our corpus.
Interestingly, the Sherrington–Kirkpatrick model was originally proposed to describe magnetic alloys, but today it is actively used in neural network theory and machine learning.
Key numbers
- Parisi value (energy per spin): −0.7631
- circuit depth p: up to 80
- optimal spin-to-depth ratio: S ∝ p
- asymptotic convergence of QAOA: log(p)/p
- convergence of classical algorithm without noise: 1/p