Quasi-exact ground-state algorithm for the random-field Potts model
arXiv:2204.11745 · doi:10.1016/j.cpc.2023.108685
Abstract
The use of combinatorial optimization algorithms has contributed substantially to the major progress that has occurred in recent years in the understanding of the physics of disordered systems, such as the random-field Ising model. While for this system exact ground states can be computed efficiently in polynomial time, the related random-field Potts model is {\em NP\} hard computationally. While thus exact ground states cannot be computed for large systems in this case, approximation schemes based on graph cuts and related techniques can be used. Here we show how a combination of such methods with repeated runs allows for a systematic extrapolation of relevant system properties to the ground state. The method is benchmarked on a special class of disorder samples for which exact ground states are available.
arXiv comment9 pages, 9 figures, 1 table
References in corpus (16)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
- The three-dimensional random field Ising magnet: interfaces, scaling, and the nature of states
- Universality in the three-dimensional random-field Ising model
- Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
- Phase transitions in disordered systems: the example of the random-field Ising model in four dimensions
- GPU accelerated population annealing algorithm
- A new look at reweighted message passing
- Critical behavior of the Random-Field Ising model at and beyond the Upper Critical Dimension
- Understanding population annealing Monte Carlo simulations
- Domain walls and Schramm-Loewner evolution in the random-field Ising model
- Massively parallel multicanonical simulations
- Ground States and Defect Energies of the Two-dimensional XY Spin Glass from a Quasi-Exact Algorithm
- Genetic embedded matching approach to ground states in continuous-spin systems
- Interaction effects on quantum Hall transitions: dynamical scaling laws and superuniversality
- Efficient algorithms for computing ground states of the 2D random-field Ising model