We present a polynomial-time Markov chain Monte Carlo algorithm for estimating the partition function of the antiferromagnetic Ising model on any line graph. The analysis of the algorithm exploits the "winding" technology devised by McQuillan [CoRR abs/1301.2880 (2013)] and developed by Huang, Lu and Zhang [Proc. 27th Symp. on Disc. Algorithms (SODA16), 514-527]. We show that exact computation of the partition function is #P-hard, even for line graphs, indicating that an approximation algorithm is the best that can be expected. We also show that Glauber dynamics for the Ising model is rapidly mixing on line graphs, an example being the kagome lattice.
翻译:我们在任何线形图中展示了估算反地磁磁学模型分区功能的多元时时Markov链 Monte Carlo算法。对算法的分析利用了由McQuillan[CORR abs/1301.2880 (2013)]设计、由黄、卢和张开发的“风”技术[关于阿尔哥里特姆碎片(SOD16),514-527]。我们显示,对分区功能的精确计算是 #P-硬,即使是线形图也是如此,这表明近似算法是最佳的预期。我们还显示,Ising模型的Glauber动态正在迅速在线形图上混合,一个例子就是kagome lattice。