Spin glasses, disordered magnets with conflicting random interactions, present a significant challenge in finding their ground states. This challenge stems from the inherent frustrations within the system, making it computationally difficult to minimize all interactions simultaneously. The Hamiltonian for the Ising spin glass model, often represented on a D-dimensional hypercubic lattice, is given by H = -Σ_<ij> J_ijσ_iσ_j, where J_ij are Gaussian random variables representing interaction strengths and σ_i = ±1 represents the spin value at site i. The Edwards-Anderson (EA) model, a prominent example, presents a significant hurdle due to the abundance of short loops leading to increased frustration. The motivation for finding ground states is threefold: (1) it is key to understanding the complex behavior of spin glasses, such as glassy phases and ergodicity breaking; (2) it addresses an NP-hard problem relevant to numerous hard combinatorial optimization problems (including Karp's 21 NP-complete problems, the max-cut problem, and the traveling salesman problem); and (3) it contributes to advancements in neural network models and optimization tools such as the cavity method and Belief Propagation. Exact methods, such as the branch-and-bound approach, are limited to very small systems. While polynomial-time solutions exist for 2D lattices with specific boundary conditions, general solutions for large systems remain elusive, relying primarily on heuristic methods like simulated annealing (SA), population annealing, and parallel tempering (PT). Reinforcement learning (RL) has emerged as a promising alternative for combinatorial optimization problems, but its application to large-scale spin glass ground state calculation remains a challenge. This research aims to address this gap.

Existing methods for finding the ground states of spin glasses have limitations. Exact methods like branch-and-bound are computationally expensive and only feasible for small systems. Heuristic methods such as simulated annealing (SA) and parallel tempering (PT) are widely used but often suffer from slow convergence and difficulties in escaping local minima, especially in higher dimensions. Recent applications of reinforcement learning (RL) to spin glass problems have shown promise, particularly in enhancing simulated annealing by improving temperature control. However, these RL-enhanced approaches also fail to efficiently solve larger systems in three or higher dimensions. This paper builds upon these previous efforts by introducing a novel RL-based framework designed to directly address the challenges of finding spin glass ground states in large systems.

The authors introduce DIRAC (Deep reinforcement learning for spin-glass Ground-state Calculation), a novel reinforcement learning (RL) framework for directly calculating spin glass ground states. DIRAC formulates the ground state search as a Markov decision process (MDP). The state *s* encompasses the spin configuration {σ_i} and coupling strengths {J_ij}. The action *a* represents flipping a spin *i*, and the reward *r*(s, a, s′) is the energy change after the flip. The goal is to learn a policy π_θ(*a*| *s*) that maximizes the expected future cumulative rewards. The framework uses a graph neural network (SGNN, Spin Glass Neural Network) as an encoder to represent states and actions effectively. This SGNN architecture incorporates both edge-centric and node-centric updates, crucial for capturing the influence of coupling strengths, unlike traditional graph neural networks that often only include node-centric updates. The encoder outputs embedding vectors for each node, reflecting the node's position and long-range couplings. A multilayer perceptron (MLP) acts as a decoder, mapping concatenated state and action embeddings to a Q-value, predicting the expected future cumulative reward for a given action. The Q-value is learned through n-step Q-learning, minimizing the loss function ℒ = 𝔼_{(st, at, rt, st+n)}[(rt + γ max Q(st+n, at+n; Θ) - Q(st, at; Θ))²]. Offline training involves self-teaching the DIRAC agent on randomly generated small-scale EA spin glass instances, updating parameters via mini-batch gradient descent. Online application employs two strategies: DIRAC¹, a greedy approach flipping a fraction of highest-Q spins, and DIRAC^m, an iterative refinement using gauge transformations (GTs). GTs allow the system to transform between configurations while preserving energy, enabling the exploration of diverse configurations. DIRAC can also be incorporated into existing thermal annealing methods (SA and PT), replacing the Metropolis-Hastings criterion with a DIRAC-based procedure (DMH) for more effective configuration search. In DIRAC-SA and DIRAC-PT, the system randomly selects between DMH and the energy-based Metropolis-Hastings (EMH) procedure.

DIRAC demonstrates superior performance compared to state-of-the-art methods in finding spin glass ground states. The probability of finding the ground state (P₀) is significantly higher for DIRAC variants (DIRAC¹, DIRAC^m, DIRAC-SA, DIRAC-PT) compared to Greedy, SA, and PT across various system sizes (D=2,3,4) and initial configurations (n_initial). The minimum number of initial configurations (n_initial) required by DIRAC^m to achieve P₀=1.0 is significantly smaller than for PT, especially for higher dimensions. In larger systems, where finding the true ground state becomes computationally prohibitive, DIRAC-SA consistently achieves the lowest average ground-state energy per spin (e₀) compared to SA and PT across various system sizes. DIRAC-SA consistently outperforms SA and DIRAC-PT outperforms PT, showing statistically significant improvements (p<0.05) in energy minimization. The iterative application of DIRAC¹ with gauge transformations (DIRAC^m) shows a clear advantage over DIRAC¹, highlighting the effectiveness of GT in escaping local minima. DIRAC is computationally efficient, exhibiting better scalability than other methods. Even including offline training time, in some cases, DIRAC's total cost is lower than PT's time to achieve a comparable energy level. The authors demonstrate the long-sightedness of DIRAC compared to a purely energy-based greedy approach. DIRAC temporarily sacrifices short-term energy gains to reach lower energy states in the long run. DIRAC also exhibits enhanced performance in an extreme case of a purely anti-ferromagnetic Ising model, quickly achieving the ground state with a checkerboard pattern, whereas other algorithms struggle to escape local minima. Finally, the authors demonstrate DIRAC's application to the max-cut problem, showcasing its superior performance compared to other max-cut solvers.

DIRAC successfully addresses the research question by providing a highly effective and efficient algorithm for finding spin glass ground states. The results demonstrate DIRAC's superior performance over existing state-of-the-art methods, indicating significant advancements in the field. The superior performance of DIRAC can be attributed to its ability to learn a long-sighted strategy, making short-term sacrifices for long-term energy reduction, a capability not possessed by purely energy-based methods. The successful integration of DIRAC with existing thermal annealing methods (SA and PT) shows its potential as a general plugin for improving the performance of various optimization algorithms. The gauge transformation technique plays a crucial role in enhancing DIRAC's performance by allowing exploration of a wider range of configurations and enabling efficient escape from local minima. The findings have broad implications, including a deeper understanding of the low-temperature spin glass phase and the development of efficient solutions for numerous NP-hard combinatorial optimization problems. The success of DIRAC also emphasizes the potential of integrating physics-informed approaches with deep reinforcement learning.

DIRAC, a deep reinforcement learning framework, significantly advances the ability to efficiently calculate ground states of Edwards-Anderson spin glasses. It consistently outperforms existing methods in terms of both accuracy and efficiency, leveraging a unique combination of graph neural networks, reinforcement learning, and gauge transformations. The framework is adaptable to other NP-hard problems, opening avenues for future research into broader combinatorial optimization challenges. Future work could involve improving the encoder with advanced deep graph representations and employing more efficient RL training techniques to further enhance DIRAC’s performance and broaden its applicability.

While DIRAC shows remarkable performance, some limitations exist. The offline training process requires substantial computational resources. The hyperparameters were determined using an informal grid search, implying that a more systematic optimization might further improve performance. The generalizability to systems with different coupling distributions or topological structures beyond those tested may require further investigation. Finally, extending the framework to handle k-body interactions (k>2) requires further development.