Optimizing glassyp-spin models

2010/10/31 by Creighton K. Thomas, Helmut G. Katzgraber
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Data Visualization and Analytics #Theoretical and Computational Physics #cond-mat.dis-nn

paper · pdf · doi:10.1103/physreve.83.046709

published as Phys. Rev. E 83, 046709 (2011) · 10 pages, 8 figures

openalex publication_date 2011/04/21 · arxiv created 2011/04/23 · arxiv updated 2015/03/17 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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.

Citations

• Evidence for nontrivial ground-state structure of 3d ± J spin glasses
• Matching Kasteleyn cities for spin glass ground states
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• Topological quantum memory
• Topological Computation without Braiding
• Fault-tolerant quantum computation by anyons
• Internal Energy, Specific Heat and Correlation Function of the Bond-Random Ising Model
• Paths, Trees, and Flowers