Optimizing glassy p-spin models
arXiv:1010.2524 · doi:10.1103/PhysRevE.83.046709
Abstract
Computing the ground state of Ising spin-glass models with p-spin interactions is, in general, an NP-hard problem. In this work we show that unlike in the case of the standard Ising spin glass with two-spin interactions, computing ground states with p=3 is an NP-hard problem even in two space dimensions. Furthermore, we present generic exact and heuristic algorithms for finding ground states of p-spin models with high confidence for systems of up to several thousand spins.
10 pages, 8 figures
References in corpus (8)
- Topological Computation without Braiding
- Error Threshold for Color Codes and Random 3-Body Ising Models
- Matching Kasteleyn Cities for Spin Glass Ground States
- Statistical Mechanical Models and Topological Color Codes
- "Exact" Algorithm for Random-Bond Ising Models in 2D
- Exact Ground States of Large Two-Dimensional Planar Ising Spin Glasses
- Exact Algorithm for Sampling the 2D Ising Spin Glass
- Persistence and Memory in Patchwork Dynamics for Glassy Models
Cited by in corpus (6)
- Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
- Large-scale Ising Emulation with Four-Body Interaction and All-to-All Connection
- Towards Prediction of Financial Crashes with a D-Wave Quantum Computer
- Stability of topologically-protected quantum computing proposals as seen through spin glasses
- Sampling the ground-state magnetization of d-dimensional p-body Ising models
- Multiple transitions in an infinite range p-spin random-crystal field Blume Capel model