Patch-planting spin-glass solution for benchmarking
arXiv:1706.02825 · doi:10.1103/PhysRevE.96.023312
Abstract
We introduce an algorithm to generate (not solve) spin-glass instances with planted solutions of arbitrary size and structure. First, a set of small problem patches with open boundaries is solved either exactly or with a heuristic, and then the individual patches are stitched together to create a large problem with a known planted solution. Because in these problems frustration is typically smaller than in random problems, we first assess the typical computational complexity of the individual patches using population annealing Monte Carlo, and introduce an approach that allows one to fine-tune the typical computational complexity of the patch-planted system. The scaling of the typical computational complexity of these planted instances with various numbers of patches and patch sizes is investigated and compared to random instances.
9 pages, 12 figures, 2 tables
References in corpus (8)
- Universality in three-dimensional Ising spin glasses: A Monte Carlo study
- Quantum annealing correction for random Ising problems
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Evidence against a mean field description of short-range spin glasses revealed through thermal boundary conditions
- Efficient subgraph-based sampling of Ising-type models with frustration
- Persistence and Memory in Patchwork Dynamics for Glassy Models