Estimating the Density of States of Frustrated Spin Systems
arXiv:1808.04340 · doi:10.1088/1367-2630/ab2e39
Abstract
Estimating the density of states of systems with rugged free energy landscapes is a notoriously difficult task of the utmost importance in many areas of physics ranging from spin glasses to biopolymers. Density of states estimation has also recently become an indispensable tool for the benchmarking of quantum annealers when these function as samplers. Some of the standard approaches suffer from a spurious convergence of the estimates to metastable minima, and these cases are particularly hard to detect. Here, we introduce a sampling technique based on population annealing enhanced with a multi-histogram analysis and report on its performance for spin glasses. We demonstrate its ability to overcome the pitfalls of other entropic samplers, resulting in some cases in large scaling advantages that can lead to the uncovering of new physics. The new technique avoids some inherent difficulties in established approaches and can be applied to a wide range of systems without relevant tailoring requirements. Benchmarking of the studied techniques is facilitated by the introduction of several schemes that allow us to achieve exact counts of the degeneracies of the tested instances.
arXiv comment32 pages, 11 figures, 1 table
References in corpus (43)
- An efficient, multiple range random walk algorithm to calculate the density of states
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
- Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
- Characterizing Quantum Supremacy in Near-Term Devices
- Quantum Boltzmann Machine
- Architectural considerations in the design of a superconducting quantum annealing processor
- Feedback-optimized parallel tempering Monte Carlo
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Fast Algorithm to Calculate Density of States
- Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
- Probing for quantum speedup in spin glass problems with planted solutions
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- A generic, hierarchical framework for massively parallel Wang-Landau sampling
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Population Annealing with Weighted Averages: A Monte Carlo Method for Rough Free Energy Landscapes
- JANUS: an FPGA-based System for High Performance Scientific Computing
- Make life simple: unleash the full power of the parallel tempering algorithm
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- Population Monte Carlo algorithms
- Population annealing: Theory and application in spin glasses
- Unraveling Quantum Annealers using Classical Hardness
- GPU accelerated population annealing algorithm
- Thermalization, freeze-out and noise: deciphering experimental quantum annealers
- Tunneling spectroscopy using a probe qubit
- Error estimation and reduction with cross correlations
- Computational Difficulty of Computing the Density of States
- Domain-wall excitations in the two-dimensional Ising spin glass
- Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses
- Cross-correlations in scaling analyses of phase transitions
- Optimization of population annealing Monte Carlo for large-scale spin-glass simulations
- Massively parallel multicanonical simulations
- Advantages of Unfair Quantum Ground-State Sampling
- Analysis and Optimization of Population Annealing
- Control of accuracy in the Wang-Landau algorithm
- Exploring first-order phase transitions with population annealing
- Patch-planting spin-glass solution for benchmarking
- Random-cluster multi-histogram sampling for the q-state Potts model
- Convergence of Stochastic Approximation Monte Carlo and modified Wang-Landau algorithms: Tests for the Ising model
- Histogram-Free Multicanonical Monte Carlo Sampling to Calculate the Density of States
Cited by in corpus (8)
- Understanding population annealing Monte Carlo simulations
- Perils of Embedding for Sampling Problems
- Equilibrium Microcanonical Annealing for First-Order Phase Transitions
- Sampling diverse near-optimal solutions via algorithmic quantum annealing
- A quantum Monte Carlo algorithm for arbitrary spin-1/2 Hamiltonians
- Flat histogram method comparison on 2D Ising Model
- Massively parallel simulations for disordered systems
- Posiform Planting: Generating QUBO Instances for Benchmarking