A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit

Hamza Fawzi1, Omar Fawzi2, and Samuel O. Scalet1

1Department of Applied Mathematics and Theoretical Physics, University of Cambridge, United Kingdom
2Univ Lyon, Inria, ENS Lyon, UCBL, LIP, Lyon, France

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We introduce a classical algorithm to approximate the free energy of local, translation-invariant, one-dimensional quantum systems in the thermodynamic limit of infinite chain size. While the ground state problem (i.e., the free energy at temperature $T = 0$) for these systems is expected to be computationally hard even for quantum computers, our algorithm runs for any fixed temperature $T \gt 0$ in subpolynomial time, i.e., in time $O((\frac{1}{\varepsilon})^{c})$ for any constant $c \gt 0$ where $\varepsilon$ is the additive approximation error. Previously, the best known algorithm had a runtime that is polynomial in $\frac{1}{\varepsilon}$. Our algorithm is also particularly simple as it reduces to the computation of the spectral radius of a linear map. This linear map has an interpretation as a noncommutative transfer matrix and has been studied previously to prove results on the analyticity of the free energy and the decay of correlations. We also show that the corresponding eigenvector of this map gives an approximation of the marginal of the Gibbs state and thereby allows for the computation of various thermodynamic properties of the quantum system.

► BibTeX data

► References

[1] Julia Kempe, Alexei Kitaev, and Oded Regev. ``The complexity of the local hamiltonian problem''. SIAM Journal on Computing 35, 1070–1097 (2006).

[2] Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin, et al. ``Quantum hamiltonian complexity''. Foundations and Trends® in Theoretical Computer Science 10, 159–282 (2015).

[3] Daniel Gottesman and Sandy Irani. ``The quantum and classical complexity of translationally invariant tiling and hamiltonian problems''. Theory of Computing 9, 31–116 (2013).

[4] Johannes Bausch, Toby Cubitt, and Maris Ozols. ``The complexity of translationally invariant spin chains with low local dimension''. Annales Henri Poincaré 18, 3449–3513 (2017).

[5] Álvaro M. Alhambra. ``Quantum many-body systems in thermal equilibrium'' (2022). arXiv:2110.15466.

[6] Anders W. Sandvik. ``Computational studies of quantum spin systems''. In AIP Conference Proceedings. Volume 1297, pages 135–338. American Institute of Physics (2010).

[7] James D. Watson and Toby S. Cubitt. ``Computational complexity of the ground state energy density problem''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Page 764–775. STOC 2022New York, NY, USA (2022). ACM.

[8] Dorit Aharonov and Sandy Irani. ``Hamiltonian complexity in the thermodynamic limit''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Page 750–763. STOC 2022New York, NY, USA (2022). ACM.

[9] Tomotaka Kuwahara, Kohtaro Kato, and Fernando G. S. L. Brandão. ``Clustering of conditional mutual information for quantum gibbs states above a threshold temperature''. Physical Review Letters 124, 220601 (2020).

[10] Aram W. Harrow, Saeed Mehraban, and Mehdi Soleimanifar. ``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. Page 378–386. ACM (2020).

[11] Ryan L. Mann and Tyler Helmuth. ``Efficient algorithms for approximating quantum partition functions''. Journal of Mathematical Physics 62, 022201 (2021).

[12] Tomotaka Kuwahara and Keiji Saito. ``Polynomial-time classical simulation for one-dimensional quantum gibbs states'' (2018). arXiv:1807.08424.

[13] M. B. Hastings. ``Quantum belief propagation: An algorithm for thermal quantum systems''. Physical Review B 76, 201102 (2007).

[14] Andreas Bluhm, Ángela Capel, and Antonio Pérez-Hernández. ``Exponential decay of mutual information for gibbs states of local hamiltonians''. Quantum 6, 650 (2022).

[15] Tomotaka Kuwahara, Álvaro M. Alhambra, and Anurag Anshu. ``Improved thermal area law and quasilinear time algorithm for quantum gibbs states''. Physical Review X 11, 011047 (2021).

[16] Álvaro M. Alhambra and J. Ignacio Cirac. ``Locally accurate tensor networks for thermal states and time evolution''. PRX Quantum 2, 040331 (2021).

[17] Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan. ``On the complexity of quantum partition functions'' (2021). arXiv:2110.15466.

[18] Matthias Troyer, Stefan Wessel, and Fabien Alet. ``Flat histogram methods for quantum systems: Algorithms to overcome tunneling problems and calculate the free energy''. Physical Review Letters 90, 120201 (2003).

[19] M Suzuki. ``Quantum monte carlo methods in condensed matter physics''. World Scientific. (1993).

[20] Steven R. White. ``Density matrix formulation for quantum renormalization groups''. Physical Review Letters 69, 2863–2866 (1992).

[21] Ulrich Schollwöck. ``The density-matrix renormalization group in the age of matrix product states''. Annals of Physics 326, 96–192 (2011).

[22] Zeph Landau, Umesh Vazirani, and Thomas Vidick. ``A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians''. Nature Physics 11, 566–569 (2015).

[23] Sacha Friedli and Yvan Velenik. ``Statistical mechanics of lattice systems: A concrete mathematical introduction''. Cambridge University Press. (2017).

[24] Huzihiro Araki. ``Gibbs states of a one dimensional quantum lattice''. Communications in Mathematical Physics 14, 120–157 (1969).

[25] Rajendra Bhatia. ``Matrix analysis''. Volume 169. Springer Science & Business Media. (2013).

[26] Allan Sly. ``Computational transition at the uniqueness threshold''. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. Pages 287–296. (2010).

[27] Allan Sly and Nike Sun. ``The computational hardness of counting in two-spin models on d-regular graphs''. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. Pages 361–369. (2012).

[28] Masanori Ohya and Denes Petz. ``Quantum entropy and its use''. Theoretical and Mathematical Physics. Springer. Berlin, Germany (2004).

[29] David Pérez-García and Antonio Pérez-Hernández. ``Locality estimates for complex time evolution in 1d''. Communications in Mathematical Physics 399, 929–970 (2023).

[30] Marco Lenci and Luc Rey-Bellet. ``Large deviations in quantum lattice systems: One-phase region''. Journal of Statistical Physics 119, 715–746 (2005).

[31] David E. Evans and Raphael Høegh-Krohn. ``Spectral Properties of Positive Maps on $C^*$-Algebras''. Journal of the London Mathematical Society s2-17, 345–355 (1978).

[32] Michael M Wolf. ``Quantum channels & operations: Guided tour'' (2012).

[33] David Reeb, Michael J Kastoryano, and Michael M Wolf. ``Hilbert's projective metric in quantum information theory''. Journal of mathematical physics 52, 082201 (2011).

[34] Elon Kohlberg and John W Pratt. ``The contraction mapping approach to the Perron-Frobenius theory: Why Hilbert's metric?''. Mathematics of Operations Research 7, 198–210 (1982).

[35] L. N. Bulaevskii. ``Theory of non-uniform antiferromagnetic spin chains''. Journal of Experimental and Theoretical Physics 17, 684 (1963).

[36] R J Bursill, T Xiang, and G A Gehring. ``The density matrix renormalization group for a quantum spin chain at non-zero temperature''. Journal of Physics: Condensed Matter 8, L583–L590 (1996).

[37] Walter Rudin. ``Principles of mathematical analysis''. International series in pure and applied mathematics. McGraw-Hill Professional. New York, NY (1976). 3 edition.

Cited by

[1] Álvaro M. Alhambra, "Quantum Many-Body Systems in Thermal Equilibrium", PRX Quantum 4 4, 040201 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-15 08:53:30) and SAO/NASA ADS (last updated successfully 2024-04-15 08:53:31). The list may be incomplete as not all publishers provide suitable and complete citation data.