The Ising Partition Function: Zeros and Deterministic Approximation
The Ising Partition Function: Zeros and Deterministic Approximation
复制标题
DOI：
10.1007/s10955-018-2199-2
复制
发表时间：
2017-04
影响因子：
1.6
通讯作者：
Jingcheng Liu;A. Sinclair;P. Srivastava
中科院分区：
文献类型：
--
作者：
Jingcheng Liu;A. Sinclair;P. Srivastava
我们研究的问题，近似的铁磁伊辛模型的配分函数的两个成对以及更高阶的相互作用（等价地，在图以及超图）。我们的方法是基于经典的李-杨相变理论，沿着与一个新的李-杨定理的伊辛模型与高阶相互作用，和扩展的想法最近开发的Barvinok，帕特尔和Regts，可以被看作是一个算法实现的李-杨理论。我们的第一个结果是adeterministicpolynomial时间近似方案（FPTAS）的分区函数在有界度图，是有效的整个范围内的参数（相互作用）和（外部字段），除了的情况下（“零场”的情况下）。多项式时间随机化近似方案（FPRAS）的所有图和所有，基于马尔可夫链蒙特卡罗模拟，早已知道。与统计物理和计数问题的大多数其他确定性近似算法不同，我们的算法不依赖于“相关性衰减”性质，而是如上所述，依赖于李-杨理论。这种方法扩展到更一般的设置的有界度和边缘大小的超图的伊辛模型，其中没有以前的算法（甚至随机）已知的参数范围广泛。为了实现后一个扩展，我们建立了超图上Ising模型的Lee-Yang定理的一个严格版本，改进了Suzuki和Fisher的一个经典结果。
We study the problem of approximating the partition function of the ferromagnetic Ising model with both pairwise as well as higher order interactions (equivalently, in graphs as well as hypergraphs). Our approach is based on the classical Lee–Yang theory of phase transitions, along with a new Lee–Yang theorem for the Ising model with higher order interactions, and on an extension of ideas developed recently by Barvinok, and Patel and Regts that can be seen as an algorithmic realization of the Lee–Yang theory. Our first result is adeterministicpolynomial time approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters(the interaction) and(the external field), except for the case(the “zero-field” case). A polynomial timerandomizedapproximation scheme (FPRAS) for all graphs and all, based on Markov chain Monte Carlo simulation, has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the “decay of correlations” property, but, as pointed out above, on Lee–Yang theory. This approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this latter extension, we establish a tight version of the Lee–Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.