The 2D±J Ising spin glass: exact partition functions in polynomial time

Gyan V Bhanot, Jan Lacki

Lawrence K. Saul, Mehran Kardar A

We describe an exact integer algorithm to compute the partition function of a two-dimensional \ifmmode\pm\else\textpm\fi{}J Ising spin glass. Given a set of quenched random bonds, the algorithm returns the density of states as a function of energy. The computation time is polynomial in the lattice size. We investigate defects, low-lying excitations, and zeros of the partition function in the complex plane. We also discuss the potential to examine other types of quenched randomness.

Jovanka Lukic, Enzo Marinari, Olivier Martin

We study 2d Ising spin glasses with binary couplings, using exact computations of the partition functions on large lattices with periodic boundary conditions. We describe the algorithm used to compute the partition functions and then give some of our main results. A Migdal-Kadanoff approximation illustrates further the anomalous scaling of these systems.

A. Aguilar, E. Braun

John Stephenson

Daniel A. Lidar, Ofer Biham

We present a polynomial time algorithm for the construction of the Gibbs distribution of configurations in the Ising model, on a quantum computer. The algorithm is designed so that each run provides one configuration with exactly the correct quantum probability, namely, the corresponding thermodynamic weight. The partition function is thus approximated in the most efficient way. The algorithm does not suffer from critical slowing down, unlike its classical counterparts. Moreover, the algorithm can be applied in any dimension, to any of the frustrated Ising models, diluted Ising models, and spin glasses. In particular, we show that under certain plausible assumptions concerning the scaling of the number of low-lying metastable states, the ground state of any dimensional short-range spin glass can be found in poly(N_T) steps, N_T being the number of spins (N) in the system plus the number of bonds between them (N_B). Since the problem of finding the ground state of a spin glass in 3D is known to be NP-complete, we thus provide evidence that possibly P=NP on a quantum computer.