铁磁性双态自旋系统配分函数的可近似性

doi:10.11896/jsjkx.200200119

计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 22-26.doi: 10.11896/jsjkx.200200119

所属专题：理论计算机科学

铁磁性双态自旋系统配分函数的可近似性

邱国良¹, 张驰豪²

1 电子科技大学计算机科学与工程学院成都610000
2 上海交通大学约翰·霍普克罗夫特计算机科学中心上海200240

收稿日期:2020-02-26 出版日期:2020-05-15 发布日期:2020-05-19
通讯作者: 张驰豪(chihao@sjtu.edu.cn)
作者简介:guoliang.qiu96@gmail.com
基金资助:
国家自然科学基金青年科学基金(NSFC 61902241)

Approximability of Partition Functions of Ferromagnetic Two-state Spin Systems

QIU Guo-liang¹, ZHANG Chi-hao²

1 School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 610000,China
2 John Hopcroft Center for Computer Science,Shanghai Jiao Tong University,Shanghai 200240,China

Received:2020-02-26 Online:2020-05-15 Published:2020-05-19
About author:QIU Guo-liang,born in 1996,postgra-duate.His main research interest is theo-retical computer science.
ZHANG Chi-hao,born in 1988,Ph.D,Ph.D supervisor,is a member of China Computer Federation.His main research interest is theoretical computer science.
Supported by:
This work was supported by the Young Scientists Fund of the National Natural Science Foundation of China (NSFC 61902241).

摘要/Abstract

摘要： 双态自旋系统是统计物理学在处理互作用粒子系统时所建立的简化模型,计算该系统的配分函数(partition function)在统计物理及计算机科学中均有重要意义。对于一般的系统,配分函数的精确计算已被证明是＃P难的,但其是否能被高效地近似计算一直是理论计算机科学关注的问题。近年来,这一领域取得了较大的突破。研究者建立了配分函数的可近似性与该物理系统相变的联系,并且在很大的参数范围内理解了可近似性。文中对铁磁性双态自旋系统配分函数的可近似性研究进行了综述,介绍了目前针对该问题设计近似算法的三类技巧的主要思想,并把这些算法的结果与该问题在不可近似方面的结果进行了比较。

关键词: 近似计数, 取样, 铁磁双态自旋系统配分函数

Abstract: The two-spin system is a simplified model for the interaction of the multiparticle system in statistical physics.Computing the partition function of the system is of great significance in both statistical physics and computer science.It is well-known that the exact computation of the partition function is ＃P-hard for general systems.Therefore,the approximability of the partition function has attracted a lot of attention of computer scientists.Notable progress has been made along this line of research in recent years.Close connections between the approximability of the partition function and the phase transition of the physical mo-dels have been revealed.Based on these connections,approximation algorithms have been discovered for the model in a wide range of parameters.This paper reviews the research on the approximability of the partition functions of ferromagnetic 2-spin systems,introduces the main ideas of three classes of algorithms for this problem,including MCMC based algorithms,decay of correlation based algorithm and recent polynomial interpolation based algorithms.Moreover,the results of these algorithms are compared with the current inapproximability results.

Key words: Approximate counting, Partition function of ferromagnetic two-state spin systems, Sampling

中图分类号:

TP301

邱国良, 张驰豪. 铁磁性双态自旋系统配分函数的可近似性[J]. 计算机科学, 2020, 47(5): 22-26. https://doi.org/10.11896/jsjkx.200200119

QIU Guo-liang, ZHANG Chi-hao. Approximability of Partition Functions of Ferromagnetic Two-state Spin Systems[J]. Computer Science, 2020, 47(5): 22-26. https://doi.org/10.11896/jsjkx.200200119

参考文献

[1]BULATOV A,GROHE M.The Complexity of Partition Functions[J].Theoretical Computer Science,2004,348(2/3):148-186.
[2]WEITZ D.Counting independent sets up to the tree threshold[C]//Proceeding of the 38th Annual ACM Symposium on Theo-ry of Computing.2006:140-149.
[3]LI L,LU P Y,YIN Y T.Correlation decay up to uniqueness in spin systems[C]//Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms.2013:67-84.
[4]SLY A,SUN N.The computational hardness of counting in two-spin models on d-regular graphs[C]//53^rd Annual IEEE Symposium on Foundations of Computer Science.2012:361-369.
[5]SINCLAIR A,SRIVASTAVA P,THURLEY M.Approxima-tion Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs[J].Journal of Statistical Phy-sics,2014,155(4):666-686.
[6]JERRUM M,VALIANT L G,VAZIRANI V V.Random genera-tion of combinatorial structures from a uniform distribution[J].Theoretical Computer Science,1986,43:169-188.
[7]LEVIN D,PERES Y.Markov Chains and Mixing Times[M].American Mathematical Society,2017.
[8]MOSSEL E,SLY A.Exact threshold for Ising-Gibbs samplerson general graphs[J].The Annals of Probability,2013,41(1):294-328.
[9]LIU J C,LU P Y,ZHANG C H.The complexity of ferromagnetic two-spin systems with external fields[C]//Proceedings of RANDOM.2014:843-856.
[10]GOLDBERG A L,JERRUM M,PATERSON M.The computational complexity of two-state spin systems[J].Random Structures & Algorithms,2003,23(2):133-154.
[11]JERRUM M,SINCLAIR A.Polynomial-time approximation algorithms for the Ising model[C]// International Colloquium on Automata,Languages & Programming.Springer-Verlag,1990.
[12]GAMARNIK D,KATZ D.Correlation decay and deterministic FPTAS for counting colorings of a graph[J].Journal of Discrete Algorithms,2012,12:29-47.
[13]GUO H,LU P Y.Uniqueness,spatial mixing,and approxima-tion for ferromagnetic 2-spin systems[J].TOCT,2018,10(4):17:1-17:25.
[14]BARVINOK A.Combinatorics and Complexity of PartitionFunctions[M].Springer International Publishing,2016.
[15]PATEL V,REGTS G.Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials[J].SIAM Journal on Computing,2017,46(6):1893-1919.
[16]SCOTT A D,SOKAL A D.The Repulsive Lattice Gas,the Independent-Set Polynomial,and the Lovász Local Lemma[J].Journal of Statistical Physics,2005,118(5/6):1151-1261.
[17]PETERS H,REGTS G.On a conjecture of sokal concerningroots of the independence polynomial[J].The Michigan Mathematical Journal,2019,68(1):33-55.
[18]SOKAL A.A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models[J].Markov Process,2001(1):21-38.
[19]LIU J C,SINCLAIR A,SRIVASTAVA P.A deterministic algorithm for counting colorings with 2-delta colors[C]//60^th IEEE Annual Symposium on Foundations of Computer Science.2019:1380-1404.
[20]ASANO T.Theorems on the partition functions of the Heisenberg ferromagnets[J].The Physical Society of Japan,1970,29:350-359.
[21]RUELLE DAVID.Extension of the lee-yang circle theorem[J].Physical Review Letters,1971,26:303-304.
[22]GUO H,LIAO C,LU P Y,et al.Zeros of Holant problems:locations and algorithms[C]//Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms.2019:2262-2278.
[23]GUO H,LIU J C,LU P Y.Zeros of ferromagnetic 2-spin systems[C]// Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms.2020:181-192.
[24]GEORGII H O.Gibbs Measures and Phase Transitions(2^nd Edition)[M].Berlin:Springer,2011.
[25]DYER M,GOLDBERG L A,GREENHILL C,et al.The Relative Complexity of Approximate Counting Problems[J].Algorithmica,2004,38(3):471-500.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

铁磁性双态自旋系统配分函数的可近似性

Approximability of Partition Functions of Ferromagnetic Two-state Spin Systems

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

Metrics

本文评价

推荐阅读 0

[1]	梁喜涛,顾磊. 基于最近邻的主动学习分词方法 Active Learning in Chinese Word Segmentation Based on Nearest Neighbor 计算机科学, 2015, 42(6): 228-232. https://doi.org/10.11896/j.issn.1002-137X.2015.06.048
[2]	. 基于贝努里分布的贝叶斯网络结构学习算法计算机科学, 2008, 35(1): 168-170.
[3]	. 用于不均衡数据集的挖掘方法计算机科学, 2007, 34(9): 139-141.
[4]	张维玺. 广义取样定理及其应用计算机科学, 2004, 31(B07): 132-133.