Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
arXiv:cond-mat/0209248 · doi:10.1142/S0129183103004498
Abstract
Monte Carlo simulation techniques, like simulated annealing and parallel tempering, are often used to evaluate low-temperature properties and find ground states of disordered systems. Here we compare these methods using direct calculations of ground states for three-dimensional Ising diluted antiferromagnets in a field (DAFF) and three-dimensional Ising spin glasses (ISG). For the DAFF, we find that, with respect to obtaining ground states, parallel tempering is superior to simple Monte-Carlo and to simulated annealing. However, equilibration becomes more difficult with increasing magnitude of the externally applied field. For the ISG with bimodal couplings, which exhibits a high degeneracy, we conclude that finding true ground states is easy for small systems, as is already known. But finding each of the degenerate ground states with the same probability (or frequency), as required by Boltzmann statistics, is considerably harder and becomes almost impossible for larger systems.
14 pages, 9 figures. Accepted for publication at Int. J. of Mod. Phys. C, issue 14(3)
References in corpus (26)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Simulated Tempering: A New Monte Carlo Scheme
- Critical Behavior of the Three-Dimensional Ising Spin Glass
- Extended Ensemble Monte Carlo
- Nature of the Spin Glass State
- Monte Carlo Simulations of Spin Glasses at Low Temperatures
- Spin and link overlaps in 3-dimensional spin glasses
- Critical Behavior of the 3d Random Field Ising Model: Two-Exponent Scaling or First Order Phase Transition?
- Critical Exponents of the Three Dimensional Random Field Ising Model
- Critical Exponents of the Three Dimensional Random Field Ising Model
- On the Phase Structure of the 3D Edwards Anderson Spin Glass
- Scaling of stiffness energy for 3d +/-J Ising spin glasses
- Specific-Heat Exponent of Random-Field Systems via Ground-State Calculations
- Universality in Three Dimensional Random-Field Ground States
- The 3-d Random Field Ising Model at zero temperature
- Evidences Against Temperature Chaos in Mean Field and Realistic Spin Glasses
- Calculation of ground states of four-dimensional +or- J Ising spin glasses
- Universality in Random Systems: the case of the 3-d Random Field Ising model
- Cluster-Exact Approximation of Spin Glass Groundstates
- Modified Scaling Relation for the Random-Field Ising Model
- Critical slowing down in polynomial time algorithms
- Frustrated Systems: Ground State Properties via Combinatorial Optimization
- Chaos in the Random Field Ising Model
- How to evaluate ground-state landscapes of disordered systems thermodynamical correctly
- Comment on "Evidence for nontrivial ground-state structure of 3d +/- J spin glasses"
- Nature and number of distinct phases in the random field Ising model
Cited by in corpus (49)
- Optimized simulated annealing for Ising spin glasses
- Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Probing the Almeida-Thouless line away from the mean-field model
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- Behavior of Ising Spin Glasses in a Magnetic Field
- Uncertain fate of fair sampling in quantum annealing
- Readiness of Quantum Optimization Machines for Industrial Applications
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- Universality-class dependence of energy distributions in spin glasses
- Reconstruction of silicon surfaces: a stochastic optimization problem
- Geometry of large-scale low-energy excitations in the one-dimensional Ising spin glass with power-law interactions
- Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
- The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
- Probing tails of energy distributions using importance-sampling in the disorder with a guiding function
- The ground state energy of the Edwards-Anderson spin glass model with a parallel tempering Monte Carlo algorithm
- Effects of setting the temperatures in the parallel tempering Monte Carlo algorithm
- Optimized GPU simulation of continuous-spin glass models
- Fair sampling of ground-state configurations of binary optimization problems
- Spin glasses and algorithm benchmarks: A one-dimensional view
- Diluted antiferromagnets in a field seem to be in a different universality class than the random-field Ising model
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Numerical Solution-Space Analysis of Satisfiability Problems
- Finding Ground States of Sherrington-Kirkpatrick Spin Glasses with Hierarchical BOA and Genetic Algorithms
- Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
- Patch-planting spin-glass solution for benchmarking
- Genetic embedded matching approach to ground states in continuous-spin systems
- borealis - A generalized global update algorithm for Boolean optimization problems
- Space as a low-temperature regime of graphs
- A comparative study of selected parallel tempering methods
- Dynamical mean field theory for manganites
- Feeding the multitude: A polynomial-time algorithm to improve sampling
- Low-energy excitations in the three-dimensional random-field Ising model
- Sampling the ground-state magnetization of d-dimensional p-body Ising models
- Ground-state energy and entropy of the two-dimensional Edwards-Anderson spin-glass model with different bond distributions
- Inference from Matrix Products: A Heuristic Spin Glass Algorithm
- Nonequilibrium dynamics of the three-dimensional Edwards-Anderson spin-glass model with Gaussian couplings: Strong heterogeneities and the backbone picture
- Parallel Tempering-Inspired Distributed Binary Optimization with In-Memory Computing
- Efficient sampling using Macrocanonical Monte Carlo and density of states mapping
- Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
- Computing Canonical Averages with Quantum and Classical Optimizers: Thermodynamic Reweighting for QUBO Models of Physical Systems
- Optimal Vertex Cover for the Small-World Hanoi Networks
- Ground-state statistics from annealing algorithms: Quantum vs classical approaches
- Optimization by Record Dynamics
- Critical behavior and out-of-equilibrium dynamics of a two-dimensional Ising model with dynamic couplings
- Changing the universality class of the three-dimensional Edwards-Anderson spin-glass model by selective bond dilution
- Study of the low-temperature behavior of a disordered antiferromagnet with random fields by the parallel-tempering method