期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2015
卷号：112
期号：43
页码：13161-13166
DOI：10.1073/pnas.1505664112
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：SignificanceSpin systems are a primary object of study in statistical physics. Computational complexity is the rigorous study of the computational resources required to achieve specified computational goals. We examine the problem of estimating the partition function of a q-state spin system from the point of view of computational complexity. There are just three possible levels of computational difficulty, depending on the interaction strengths between adjacent spins. Every nontrivial q-state spin system, irrespective of the number q of spins, is computationally equivalent to one of two fundamental two-state spin systems. We give a simple characterization of the classification. We study the computational complexity of approximating the partition function of a q-state spin system with an external field. There are just three possible levels of computational difficulty, depending on the interaction strengths between adjacent spins: (i) efficiently exactly computable, (ii) equivalent to the ferromagnetic Ising model, and (iii) equivalent to the antiferromagnetic Ising model. Thus, every nontrivial q-state spin system, irrespective of the number q of spins, is computationally equivalent to one of two fundamental two-state spin systems.
关键词：computational complexity ; partition function ; spin system
