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

• 理论计算机科学 • 上一篇    下一篇

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

邱国良1, 张驰豪2   

  1. 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-liang1, ZHANG Chi-hao2   

  1. 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).

摘要: 双态自旋系统是统计物理学在处理互作用粒子系统时所建立的简化模型,计算该系统的配分函数(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: Partition function of ferromagnetic two-state spin systems, Approximate counting, Sampling

中图分类号: 

  • TP301
[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]//53rd 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]//60th 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(2nd 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.
[1] 梁喜涛,顾磊. 基于最近邻的主动学习分词方法[J]. 计算机科学, 2015, 42(6): 228-232.
[2] . 基于贝努里分布的贝叶斯网络结构学习算法[J]. 计算机科学, 2008, 35(1): 168-170.
[3] . 用于不均衡数据集的挖掘方法[J]. 计算机科学, 2007, 34(9): 139-141.
[4] 张维玺. 广义取样定理及其应用[J]. 计算机科学, 2004, 31(B07): 132-133.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .