A Caltech Library Service

Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

Harrow, Aram W. and Mehraban, Saeed and Soleimanifar, Mehdi (2020) Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery , New York, NY, pp. 378-386. ISBN 9781450369794.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 of n particles above the phase transition point, the correlation between two observables whose distance is at least Ω(logn) decays exponentially. We can improve the factor of logn to 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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Harrow, Aram W.0000-0003-3220-7682
Additional Information:© 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. We thank Fernando Brandão, Kohtaro Kato, Tomotaka Kuwahara, Zeph Landau, Milad Marvian, and John Wright for helpful discussions. This work was funded by NSF grants CCF-1452616, CCF-1729369, PHY-1818914; ARO contract W911NF-17-1-0433; and a Samsung Advanced Institute of Technology Global Research Partnership. The Institute for Quantum Information and Matter is an NSF Physics Frontiers Center.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-17-1-0433
Samsung Advanced Institute of TechnologyUNSPECIFIED
Subject Keywords:quantum many-body systems, partition function, decay of correlations, complex zeros, thermal phase transition, approximation algorithms, Hamiltonian complexity
Record Number:CaltechAUTHORS:20210226-083215255
Persistent URL:
Official Citation:Aram W. Harrow, Saeed Mehraban, and Mehdi Soleimanifar. 2020. Classical Algorithms, Correlation Decay, and Complex Zeros of Partition Functions of Quantum Many-Body Systems. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC ’20), June 22–26, 2020, Chicago, IL, USA. ACM, New York, NY, USA, 9 pages. 1145/3357713.3384322
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108231
Deposited By: Tony Diaz
Deposited On:26 Feb 2021 17:46
Last Modified:16 Nov 2021 19:10

Repository Staff Only: item control page