On the computational complexity of Ising spin glass models

By F. Barahona. 1982

In a spin glass with Ising spins, the problems of computing the magnetic partition function and finding a ground state are studied. In a finite two-dimensional lattice these problems can be solved by algorithms that require a number of steps bounded by a polynomial function of the size of the lattice. In contrast to this fact, the same problems are shown to belong to the class of NP-hard problems, both in the two-dimensional case within a magnetic field, and in the three-dimensional case. NP-hardness of a problem suggests that it is very unlikely that a polynomial algorithm could exist to solve it.

Subfields: Optimization & Training, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “, 2012), while Y could be a combinatorial object such as a the ground state of a planar Ising model (without external field) which admits an efficient oracle (Barahona, 1982) but has potentially intractable projection.”
Exploiting Social Network Structure for Person-to-Person Sentiment Analysis (2014, methodology): “By reduction from TWO-LEVEL SPIN GLASS (TLSG), a problem known to be NP-hard (Barahona, 1982).”
Architectural Considerations in the Design of a Superconducting Quantum Annealing Processor (2014, background): “1) Non-planarity: We desire to tackle NP-complete problems, so non-planarity of the underlying graph is an important condition to making the corresponding Ising-spin problem NP-complete [13], [14].”
A practical heuristic for finding graph minors (2014, background): “This is a quadratic optimization over the boolean variables (the qubits) with real coefficients, an NP-complete problem [3, 5].”
Confinement Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory (2002, background): “Unfortunately, this problem is known to be NP-hard [22] and so appears to be computationally intractable.”
Sparse Blossom: correcting a million errors per core second with minimum-weight matching (2023, unknown): “See also [Bar82; Ber+99] for alternative reductions and [BDL22] for a recent review.”
Inferring the shape of global epistasis (2018, background): “For instance, finding the global maximum in a pairwise interaction fit is a nondeterministic polynomial time (NP)-complete problem (58), whereas the optimal genotype can be read off directly from the heat map of additive coefficients in our model of global epistasis.”
Tree consistency and bounds on the performance of the max-product algorithm and its generalizations (2004, methodology): “Examples include the minimum s − t cut and multiway-cut problems in combinatorial optimization (e.g., Grötschel et al. 1993), image segmentation on a grid (e.g., Geman and Geman 1984), and calculating ground states in the Ising model of statistical physics (e.g., Barahona 1982).”
Quantum machine learning: a classical perspective (2017, background): “Although it is clearly possible to encode NP-hard problems [122], quantum mechanics is not expected to solve these in polynomial time (however, the scaling constants of the quantum algorithm might be smaller).”
Realizing the classical XY Hamiltonian in polariton simulators. (2016, unknown): “Finding the global minimum of some classical spin models is known to be NP-complete [10], which means every other problem in NP can be eﬃciently transformed into it.”
Reinforcement Learning for Combinatorial Optimization: A Survey (2020, background): “Many real-world applications such as protein folding [22], financial portfolio management [23], and finding the ground state of the Ising Hamiltonian in physics [24] can be reduced to Maximum Cut problem.”
Large-scale Ising spin network based on degenerate optical parametric oscillators (2016, background): “It is well known that many combinatorial optimization problems can be mapped onto the ground-state-search problems of the Ising Hamiltonian [9].”
The NP-Completeness Column: An Ongoing Guide (1982, background): “Solvable in polynomial time for arbitrary interaction values if H = 1 (and hence G is planar), for then the problem becomes a special case of planar MAX CUT and can be solved in a number of ways [4,5,6].”
Network of time-multiplexed optical parametric oscillators as a coherent Ising machine (2014, background): “rmatics, Tokyo 101-8403, Japan, 3 Department of Information and Communication Engineering, University of Tokyo, Tokyo 113-8656, Japan. July 11, 2014 Finding the ground states of the Ising Hamiltonian [1] maps to various combinatorial optimization problems in biology, medicine, wireless communication”