% IMPORTANT: The following is UTF-8 encoded.  This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.

@ARTICLE{Foos:1046979,
      author       = {Foos, Niklas and Epping, Bastian and Grundler, Jannik and
                      Ciobanu, Alexandru and Singh, Ajainderpal and Bode, Tim and
                      Helias, Moritz and Dahmen, David},
      title        = {{B}eyond-mean-field fluctuations for the solution of
                      constraint satisfaction problems},
      publisher    = {arXiv},
      reportid     = {FZJ-2025-04047},
      year         = {2025},
      abstract     = {Constraint Satisfaction Problems (CSPs) lie at the heart of
                      complexity theory and find application in a plethora of
                      prominent tasks ranging from cryptography to genetics.
                      Classical approaches use Hopfield networks to find
                      approximate solutions while recently, modern
                      machine-learning techniques like graph neural networks have
                      become popular for this task. In this study, we employ the
                      known mapping of MAX-2-SAT, a class of CSPs, to a spin-glass
                      system from statistical physics, and use Glauber dynamics to
                      approximately find its ground state, which corresponds to
                      the optimal solution of the underlying problem. We show that
                      Glauber dynamics outperforms the traditional
                      Hopfield-network approach and can compete with
                      state-of-the-art solvers. A systematic theoretical analysis
                      uncovers the role of stochastic fluctuations in finding CSP
                      solutions: even in the absense of thermal fluctuations at
                      $T=0$ a significant portion of spins, which correspond to
                      the CSP variables, attains an effective spin-dependent
                      non-zero temperature. These spins form a subspace in which
                      the stochastic Glauber dynamics continuously performs flips
                      to eventually find better solutions. This is possible since
                      the energy is degenerate, such that spin flips in this
                      free-spin space do not require energy. Our theoretical
                      analysis leads to new deterministic solvers that effectively
                      account for such fluctuations, thereby reaching
                      state-of-the-art performance.},
      keywords     = {Disordered Systems and Neural Networks (cond-mat.dis-nn)
                      (Other) / FOS: Physical sciences (Other)},
      cin          = {PGI-12},
      cid          = {I:(DE-Juel1)PGI-12-20200716},
      pnm          = {5214 - Quantum State Preparation and Control (POF4-521) /
                      Verbundprojekt: German Quantum Computer based on
                      Superconducting Qubits (GEQCOS) - Teilvorhaben:
                      Charakterisierung, Kontrolle und Auslese (13N15685)},
      pid          = {G:(DE-HGF)POF4-5214 / G:(BMBF)13N15685},
      typ          = {PUB:(DE-HGF)25},
      doi          = {10.48550/ARXIV.2507.10360},
      url          = {https://juser.fz-juelich.de/record/1046979},
}