Approximate ground states of the random-field Potts model from graph cuts

Abstract

While the ground-state problem for the random-field Ising model is polynomial, and can be solved using a number of well-known algorithms for maximum flow or graph cut, the analogue random-field Potts model corresponds to a multi-terminal flow problem that is known to be NP hard. Hence an efficient exact algorithm is very unlikely to exist. As we show here, it is nevertheless possible to use an embedding of binary degrees of freedom into the Potts spins in combination with graph-cut methods to solve the corresponding ground-state problem approximately in polynomial time. We benchmark this heuristic algorithm using a set of quasi-exact ground states found for small systems from long parallel tempering runs. For not too large number $q$ of Potts states, the method based on graph cuts finds the same solutions in a fraction of the time. We employ the new technique to analyze the breakup length of the random-field Potts model in two dimensions.

arXiv comment10 pages, 11 figures, 1 table

References in corpus (28)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Feedback-optimized parallel tempering Monte Carlo
• Phase changes in 38 atom Lennard-Jones clusters. I: A parallel tempering study in the canonical ensemble
• Probing for quantum speedup in spin glass problems with planted solutions
• Universality in the three-dimensional random-field Ising model
• Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
• The incomplete beta function law for parallel tempering sampling of classical canonical systems
• Continuity of the phase transition for planar random-cluster and Potts models with $1\le q\le 4$
• Make life simple: unleash the full power of the parallel tempering algorithm
• Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
• Quenched Randomness at First-Order Transitions
• Phase transitions in disordered systems: the example of the random-field Ising model in four dimensions
• Evidence for softening of first-order transition in 3D by quenched disorder
• GPU accelerated population annealing algorithm
• Monte Carlo Study of Phase Transitions in the Bond-Diluted 3D 4-State Potts Model
• Weak Randomness for large q-State Potts models in Two Dimensions
• Partition function of two- and three-dimensional Potts ferromagnets for arbitrary values of q>0
• Disorder, Order, and Domain Wall Roughening in the 2d Random Field Ising Model
• Domain-wall excitations in the two-dimensional Ising spin glass
• Scattering Properties of Paramagnetic Ground States in the Three-Dimensional Random-Field Ising Model
• Domain walls and Schramm-Loewner evolution in the random-field Ising model
• Ground States and Defect Energies of the Two-dimensional XY Spin Glass from a Quasi-Exact Algorithm
• Star-graph expansions for bond-diluted Potts models
• Percolation and Schramm-Loewner evolution in the 2D random-field Ising model
• Patch-planting spin-glass solution for benchmarking
• Genetic embedded matching approach to ground states in continuous-spin systems
• Crossover effects in the bond-diluted Ising model in three dimensions
• Towards an optimal flow: Density-of-states-informed replica-exchange simulations

Cited by in corpus (6)

• Charge-$4e$ superconductivity from multi-component nematic pairing: Application to twisted bilayer graphene
• Protect Measurement-Induced Phase Transition from Noise
• Critical behavior of the three-state random-field Potts model in three dimensions
• Phase Transitions of the Variety of Random-Field Potts Models
• Massively parallel simulations for disordered systems
• Ordering kinetics in q-state random-bond clock model: Role of Vortices and Interfaces