LIPIcs.ITCS.2023.49.pdf
- Filesize: 0.61 MB
- 6 pages
Document
A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit
Authors
-
Part of:
Volume:
14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-02-01
Cite As Get BibTex
Hamza Fawzi, Omar Fawzi, and Samuel O. Scalet. A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 49:1-49:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.49
Abstract
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 > 0 in subpolynomial time, i.e., in time O((1/ε)^c) for any constant c > 0 where ε is the additive approximation error. Previously, the best known algorithm had a runtime that is polynomial in 1/ε where the degree of the polynomial is exponential in the inverse temperature 1/T. 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.
Subject Classification
ACM Subject Classification
- Theory of computation → Quantum information theory
- Theory of computation → Design and analysis of algorithms
- Theory of computation → Quantum complexity theory
Keywords
- One-dimensional quantum systems
- Free energy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Dorit Aharonov and Sandy Irani. Hamiltonian complexity in the thermodynamic limit. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 750-763, New York, NY, USA, 2022. ACM. URL: https://doi.org/10.1145/3519935.3520067.
- Álvaro M Alhambra. Quantum many-body systems in thermal equilibrium. arXiv preprint, 2022. URL: https://doi.org/10.48550/arXiv.2204.08349.
- Huzihiro Araki. Gibbs states of a one dimensional quantum lattice. Communications in Mathematical Physics, 14(2):120-157, June 1969. URL: https://doi.org/10.1007/bf01645134.
- Johannes Bausch, Toby Cubitt, and Maris Ozols. The complexity of translationally invariant spin chains with low local dimension. Annales Henri Poincaré, 18(11):3449-3513, October 2017. URL: https://doi.org/10.1007/s00023-017-0609-7.
- Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013. URL: https://doi.org/10.1007/978-1-4612-0653-8.
- 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. URL: https://doi.org/10.22331/q-2022-02-10-650.
- Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan. On the complexity of quantum partition functions. arXiv preprint, 2021. URL: http://arxiv.org/abs/2110.15466.
- Hamza Fawzi, Omar Fawzi, and Samuel O. Scalet. A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit, 2022. URL: https://doi.org/10.48550/arXiv.2209.14989.
- Sacha Friedli and Yvan Velenik. Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781316882603.
- Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin, et al. Quantum hamiltonian complexity. Foundations and Trendsregistered in Theoretical Computer Science, 10(3):159-282, 2015. URL: https://doi.org/10.1561/0400000066.
- Daniel Gottesman and Sandy Irani. The quantum and classical complexity of translationally invariant tiling and hamiltonian problems. Theory of Computing, 9(2):31-116, 2013. URL: https://doi.org/10.4086/toc.2013.v009a002.
- 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. ACM, June 2020. URL: https://doi.org/10.1145/3357713.3384322.
- M. B. Hastings. Quantum belief propagation: An algorithm for thermal quantum systems. Physical Review B, 76:201102, November 2007. URL: https://doi.org/10.1103/PhysRevB.76.201102.
- Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem. SIAM Journal on Computing, 35(5):1070-1097, 2006. URL: https://doi.org/10.1137/S0097539704445226.
- 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. URL: https://doi.org/10.1103/PhysRevLett.124.220601.
- Tomotaka Kuwahara and Keiji Saito. Polynomial-time classical simulation for one-dimensional quantum gibbs states. arXiv preprint, 2018. URL: https://doi.org/10.48550/arXiv.1807.08424.
- Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians. Nature Physics, 11(7):566-569, 2015. URL: https://doi.org/10.1038/nphys3345.
- Ryan L. Mann and Tyler Helmuth. Efficient algorithms for approximating quantum partition functions. Journal of Mathematical Physics, 62(2):022201, 2021. URL: https://doi.org/10.1063/5.0013689.
- Anders W Sandvik. Computational studies of quantum spin systems. In AIP Conference Proceedings, volume 1297, pages 135-338. American Institute of Physics, 2010. URL: https://doi.org/10.1063/1.3518900.
- Ulrich Schollwöck. The density-matrix renormalization group in the age of matrix product states. Annals of Physics, 326(1):96-192, 2011. January 2011 Special Issue. URL: https://doi.org/10.1016/j.aop.2010.09.012.
- Allan Sly. Computational transition at the uniqueness threshold. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 287-296, 2010. URL: https://doi.org/10.1109/FOCS.2010.34.
- 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. URL: https://doi.org/10.1109/FOCS.2012.56.
- M Suzuki. Quantum Monte Carlo Methods in Condensed Matter Physics. World Scientific, 1993. URL: https://doi.org/10.1142/2262.
- 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(12), March 2003. URL: https://doi.org/10.1103/physrevlett.90.120201.
- 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, STOC 2022, pages 764-775, New York, NY, USA, 2022. ACM. URL: https://doi.org/10.1145/3519935.3520052.
- Steven R. White. Density matrix formulation for quantum renormalization groups. Physical Review Letters, 69:2863-2866, November 1992. URL: https://doi.org/10.1103/PhysRevLett.69.2863.