Polynomial-time classical simulation of quantum ferromagnets
Polynomial-time classical simulation of quantum ferromagnets
复制标题
量子铁磁体的多项式时间经典模拟
DOI：
10.1103/physrevlett.119.100503
复制
发表时间：
2016
影响因子：
8.6
通讯作者：
David Gosset
中科院分区：
文献类型：
--
作者：
S. Bravyi;David Gosset
我们考虑一类量子自旋系统，作为特例，它包括任意图上的铁磁XY模型和铁磁Ising模型，无论有无横向磁场。我们证明了在这个家庭中的任何模型的配分函数可以有效地近似到一个给定的相对误差ε使用一个经典的随机算法与运行时多项式ε^{-1}，系统大小，和逆温度。因此，我们得到一个多项式时间的算法，它近似的自由能或基态能量到一个给定的附加误差。首先，我们展示了如何近似的配分函数的完美匹配和有限图与积极的边权重。虽然完美匹配的总和是不知道是有效的近似在一般情况下，通过我们的方法得到的图有一个特殊的结构，通过一个随机算法，由于Jerrum和Sinclair，有利于有效的近似。
We consider a family of quantum spin systems which includes, as special cases, the ferromagnetic XY model and ferromagnetic Ising model on any graph, with or without a transverse magnetic field. We prove that the partition function of any model in this family can be efficiently approximated to a given relative error ε using a classical randomized algorithm with runtime polynomial in ε^{-1}, system size, and inverse temperature. As a consequence, we obtain a polynomial time algorithm which approximates the free energy or ground energy to a given additive error. We first show how to approximate the partition function by the perfect matching sum of a finite graph with positive edge weights. Although the perfect matching sum is not known to be efficiently approximable in general, the graphs obtained by our method have a special structure which facilitates efficient approximation via a randomized algorithm due to Jerrum and Sinclair.