Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
复制标题
量子多体系统配分函数的经典算法、相关衰减和复零点
DOI：
10.1145/3357713.3384322
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Soleimanifar, Mehdi
中科院分区：
文献类型：
--
作者：
Harrow, Aram W.;Mehraban, Saeed;Soleimanifar, Mehdi
我们提出了一个准多项式时间的经典算法，估计量子多体系统的配分函数的温度高于热相变点。已知在最坏的情况下，相同的问题在该点以下是NP难的。与我们的工作一起，这表明量子系统的相变也伴随着近似硬度的转变。我们还证明，在相变点以上的n个粒子系统中，距离至少为Ω（logn）的两个可观测量之间的相关性呈指数衰减。当哈密顿量含有交换项或在一维链上时，我们可以将logn因子改进为常数。我们的研究结果的关键是一个表征的相变和临界行为的系统中的复杂的零点的配分函数。我们的工作扩展了Dobrushin和Shlosman关于经典自旋模型中相关衰减与自由能解析性之间等价性的开创性工作。在算法方面，我们的结果扩展了最近的方法，由于Barvinok解决经典计数问题的量子多体系统的范围。
We present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system ofnparticles above the phase transition point, the correlation between two observables whose distance is at least Ω(logn) decays exponentially. We can improve the factor of lognto a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems.