Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering

Abstract

Population annealing is a Monte Carlo algorithm that marries features from simulated annealing and parallel tempering Monte Carlo. As such, it is ideal to overcome large energy barriers in the free-energy landscape while minimizing a Hamiltonian. Thus, population annealing Monte Carlo can be used as a heuristic to solve combinatorial optimization problems. We illustrate the capabilities of population annealing Monte Carlo by computing ground states of the three-dimensional Ising spin glass with Gaussian disorder, whilst comparing to simulated annealing and parallel tempering Monte Carlo. Our results suggest that population annealing Monte Carlo is significantly more efficient than simulated annealing but comparable to parallel tempering Monte Carlo for finding spin-glass ground states.

9 pages, 7 figures

References in corpus (4)

• Optimized parallel tempering simulations of proteins
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Improved extremal optimization for the Ising spin glass
• Evidence against a mean field description of short-range spin glasses revealed through thermal boundary conditions

Cited by in corpus (26)

• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Hybrid quantum annealing for larger-than-QPU lattice-structured problems
• Coherent Ising machines with error correction feedback
• Understanding population annealing Monte Carlo simulations
• Model-Free Data-Driven Inference in Computational Mechanics
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Fair sampling of ground-state configurations of binary optimization problems
• Patch-planting spin-glass solution for benchmarking
• Accelerating equilibrium spin-glass simulations using quantum annealers via generative deep learning
• Amorphous quantum magnets in a two-dimensional Rydberg atom array
• Deep reinforced learning heuristic tested on spin-glass ground states: The larger picture
• An effective introduction to the Markov Chain Monte Carlo method
• Optimal schedules for annealing algorithms
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• Performance of machine-learning-assisted Monte Carlo in sampling from simple statistical physics models
• Quantum-enhanced Markov Chain Monte Carlo for systems larger than your Quantum Computer
• SWAP algorithm for lattice spin models
• Highly parallel algorithm for the Ising ground state searching problem
• Nonflat Histogram Techniques for Spin Glasses
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• Ground state interface exponents of the diluted Sherrington-Kirkpatrick spin glass
• Generalized Probabilistic Approximate Optimization Algorithm
• Genetic-tunneling driven energy optimizer for spin systems
• Population annealing with topological defect driven nonlocal updates for spin systems with quenched disorder
• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization