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

Approximability of Partition Functions of Ferromagnetic Two-state Spin Systems

作　　者：邱国良 张驰豪[2] QIU Guo-liang;ZHANG Chi-hao(School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 610000,China;John Hopcroft Center for Computer Science,Shanghai Jiao Tong University,Shanghai 200240,China)

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

出　　处：《计算机科学》2020年第5期22-26,共5页Computer Science

基　　金：国家自然科学基金青年科学基金(NSFC61902241)。

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]