Computational thresholds for the fixed-magnetization Ising model

DOI10.1145/3519935.3520003MaRDI QIDQ6083601zbMATH OpenOpenAlexFDO

Authors Ewan Davies, Alexandra Kolla, Will Perkins

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.03033

zbMATH Keywords

approximate counting and samplingcomputational thresholdfixed magnetizationIsing modellocal central limit theorem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here we show that hidden inside the model are hard computational problems. For the class of bounded-degree graphs we find computational thresholds for the approximate counting and sampling problems for the ferromagnetic Ising model at fixed magnetization (that is, fixing the number of $+1$ and $-1$ spins). In particular, letting $$ denote the critical inverse temperature of the zero-field Ising model on the infinite $Delta$-regular tree, and $$ denote the mean magnetization of the zero-field $+$ measure on the infinite $Delta$-regular tree at inverse temperature $$, we prove, for the class of graphs of maximum degree $Delta$: 1. For $$ there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for all magnetizations $eta$. 2. For $$, there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for magnetizations $eta$ such that $$. 3. For $$, there is no FPRAS for the fixed-magnetization Ising model for magnetizations $eta$ such that $$ unless NP=RP@.

Recommendations

• Sharp thresholds for the random-cluster and Ising models
• Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Complexity of Ferromagnetic Ising with Local Fields
• Accurate Monte Carlo critical exponents for Ising lattices
• scientific article; zbMATH DE number 177833
• Monte Carlo simulations of Ising models
• Approximability of the ground state problem for certain Ising spin glasses
• Simulation reductions for the Ising model
• Parallel Processing and Applied Mathematics

Cited in

(6)

• Sharp threshold for the Ising perceptron model
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Parameter estimation for Gibbs distributions
• Ising disks: topology preserving Glauber dynamics
• Coloring reconfiguration under color swapping

This page was built for publication: Computational thresholds for the fixed-magnetization Ising model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083601)