Abstract
The low temperature phase of discontinuous mean-field spin glasses is characterized by the appearance of an exponential number of metastable states. Which ones among these states dominate the out-of-equilibrium dynamics of these systems? In order to answer this question, we compare high-precision numerical simulations of a diluted $p$-spin model with a cavity computation of the threshold energy. Our main conclusion is that the aging dynamics is dominated by different layers of metastable states depending on the cooling schedule. In order to perform our analysis, we present a method for computing the marginality condition of diluted spin glasses at non-zero temperature.
Introduction
When a liquid is cooled into a glass, its dynamics slow down dramatically, and the system becomes trapped in one of an exponential number of "metastable states" (local energy minima). A long-standing question in statistical physics is: Which of these states actually dominate the behavior of the system? This paper investigates whether the final energy reached by a glass is universal or dependent on its "cooling history." Understanding this is crucial not just for physics, but for computer science, as these glassy transitions mirror the complexity seen in hard combinatorial optimization problems.
Methodology: The Diluted $p$-Spin Model
The authors focus on a diluted Ising $p$-spin model. Unlike "fully connected" models where every particle interacts with every other particle, this model uses a random hypergraph where each spin only interacts with a few neighbors ($c=4, 5, 8$). This makes it more representative of real-world optimization problems like K-SAT.
The study combines two powerful approaches:
- Numerical Simulations: High-precision Monte Carlo simulations (up to $10^6$ spins) track how energy relaxes over time.
- Analytical Cavity Method: A new method to compute the marginality condition for diluted models at non-zero temperatures using "One-Step Replica Symmetry Breaking" (1RSB). This allows for the calculation of theoretical energy bounds like the "threshold energy" and "iso-complexity energy."
Quenching vs. Slow Cooling
The most striking insight is that the final state of a mean-field glass depends fundamentally on its cooling schedule. In simple models, it was often assumed that the final energy reached was the same regardless of the method. However, this research demonstrates a clear divergence.
A fast quench traps the system in high-energy "threshold" states. In contrast, slow cooling allows the system to follow a path of constant "complexity" (the "iso-complexity" path), bypassing higher energy barriers to reach deeper, more stable energy layers. Mathematically, the energy reached via quenching ($E_{quench}$) is strictly higher than that reached via slow cooling ($E_{cool}$).
The Energy Landscape and Stability
The energy landscape of these systems is partitioned into different regions based on the stability of the metastable states. The "dynamical energy" ($e_d$) represents the highest energy states that remain metastable, while the "thermodynamical energy" represents the absolute minimum.
The authors found that slow cooling can bring the system to an energy below the marginal stability line. This was unexpected, as many believed the dynamics would always be pinned to the edge of stability (the marginal energy). The numerical results for infinitely slow cooling perfectly match the analytical iso-complexity energy curves derived from the cavity method, confirming that the system "equilibrates" within the first layer of metastable states it encounters.
Conclusion and Optimization Relevance
The findings suggest that for hard computational problems, the "cost" achieved by a local search algorithm depends heavily on the annealing path. A "smart" deformation of the cost function or a tailored cooling schedule could potentially lead to much better solutions than a standard quench. While the study assumes the absence of "temperature chaos," it opens the door for designing better optimization algorithms by selecting specific layers of metastable states.
Summary updated