{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T01:58:44Z","timestamp":1793239124846,"version":"4.5.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T00:00:00Z","timestamp":1724716800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T00:00:00Z","timestamp":1724716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"RCUK | Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/W524141\/1"],"award-info":[{"award-number":["EP\/W524141\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Commun"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Predicting observables in equilibrium states is a central yet notoriously hard question in quantum many-body systems. In the physically relevant thermodynamic limit, certain mathematical formulations of this task have even been shown to result in undecidable problems. Using a finite-size scaling of algorithms devised for finite systems often fails due to the lack of certified convergence bounds for this limit. In this work, we design certified algorithms for computing expectation values of observables in the equilibrium states of local quantum Hamiltonians, both at zero and positive temperature. Importantly, our algorithms output rigorous lower and upper bounds on these values. This allows us to show that expectation values of local observables can be approximated in finite time, contrasting related undecidability results. When the Hamiltonian is commuting on a 2-dimensional lattice, we prove fast convergence of the hierarchy at high temperature and as a result for a desired precision\n                    <jats:italic>\u03b5<\/jats:italic>\n                    , local observables can be approximated by a convex optimization program of quasi-polynomial size in 1\/\n                    <jats:italic>\u03b5<\/jats:italic>\n                    .\n                  <\/jats:p>","DOI":"10.1038\/s41467-024-51592-3","type":"journal-article","created":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T14:03:44Z","timestamp":1724767424000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Certified algorithms for equilibrium states of local quantum Hamiltonians"],"prefix":"10.1038","volume":"15","author":[{"given":"Hamza","family":"Fawzi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8491-0359","authenticated-orcid":false,"given":"Omar","family":"Fawzi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9770-3137","authenticated-orcid":false,"given":"Samuel O.","family":"Scalet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,8,27]]},"reference":[{"key":"51592_CR1","doi-asserted-by":"publisher","first-page":"022001","DOI":"10.1088\/0034-4885\/75\/2\/022001","volume":"75","author":"TJ Osborne","year":"2012","unstructured":"Osborne, T. J. Hamiltonian complexity. Rep. Progr. Phys. 75, 022001 (2012).","journal-title":"Rep. Progr. Phys."},{"key":"51592_CR2","doi-asserted-by":"crossref","unstructured":"Gharibian, S. et al. Quantum Hamiltonian Complexity (Now Publishers, 2015).","DOI":"10.1561\/9781680830071"},{"key":"51592_CR3","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1137\/S0097539704445226","volume":"35","author":"J Kempe","year":"2006","unstructured":"Kempe, J., Kitaev, A. & Regev, O. The complexity of the local Hamiltonian problem. SIAM J. Comput. 35, 1070\u20131097 (2006).","journal-title":"SIAM J. Comput."},{"key":"51592_CR4","doi-asserted-by":"crossref","unstructured":"Gottesman, D. & Irani, S. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science 95\u2013104 (IEEE, 2009).","DOI":"10.1109\/FOCS.2009.22"},{"key":"51592_CR5","doi-asserted-by":"crossref","unstructured":"Ambainis, A. On physical problems that are slightly more difficult than QMA. In 2014 IEEE 29th Conference on Computational Complexity (CCC) 32\u201343 (IEEE, 2014).","DOI":"10.1109\/CCC.2014.12"},{"key":"51592_CR6","doi-asserted-by":"crossref","unstructured":"Aharonov, D. & Irani, S. Hamiltonian complexity in the thermodynamic limit. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 750\u2013763 (ACM, 2022).","DOI":"10.1145\/3519935.3520067"},{"key":"51592_CR7","doi-asserted-by":"crossref","unstructured":"Watson, J. D. & Cubitt, T. S. Computational complexity of the ground state energy density problem. In Proc. 54th Annual ACM SIGACT Symposium on Theory of Computing 764\u2013775 (ACM, 2022).","DOI":"10.1145\/3519935.3520052"},{"key":"51592_CR8","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1038\/nature16059","volume":"528","author":"TS Cubitt","year":"2015","unstructured":"Cubitt, T. S., P\u00e9rez-Garc\u00eda, D. & Wolf, M. M. Undecidability of the spectral gap. Nature 528, 207\u2013211 (2015).","journal-title":"Nature"},{"key":"51592_CR9","doi-asserted-by":"publisher","first-page":"022301","DOI":"10.1103\/PhysRevA.61.022301","volume":"61","author":"BM Terhal","year":"2000","unstructured":"Terhal, B. M. & DiVincenzo, D. P. Problem of equilibration and the computation of correlation functions on a quantum computer. Phys. Rev. A 61, 022301 (2000).","journal-title":"Phys. Rev. A"},{"key":"51592_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1038\/nature09770","volume":"471","author":"K Temme","year":"2011","unstructured":"Temme, K., Osborne, T. J., Vollbrecht, K. G., Poulin, D. & Verstraete, F. Quantum metropolis sampling. Nature 471, 87\u201390 (2011).","journal-title":"Nature"},{"key":"51592_CR11","doi-asserted-by":"publisher","first-page":"1132","DOI":"10.22331\/q-2023-10-10-1132","volume":"7","author":"P Rall","year":"2023","unstructured":"Rall, P., Wang, C. & Wocjan, P. Thermal state preparation via rounding promises. Quantum 7, 1132 (2023).","journal-title":"Quantum"},{"key":"51592_CR12","unstructured":"Chen, C.-F., Kastoryano, M. J., Brand\u00e3o, F. G. & Gily\u00e9n, A. Quantum thermal state preparation. Preprint at arXiv:2303.18224 (2023)."},{"key":"51592_CR13","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-020-20504-6","volume":"12","author":"J Bausch","year":"2021","unstructured":"Bausch, J., Cubitt, T. S. & Watson, J. D. Uncomputability of phase diagrams. Nat. Commun. 12, 452 (2021).","journal-title":"Nat. Commun."},{"key":"51592_CR14","unstructured":"Cho, M. et al. Bootstrapping the ising model on the lattice. Preprint at arXiv:2206.12538 (2022)."},{"key":"51592_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BF01625778","volume":"52","author":"H Araki","year":"1977","unstructured":"Araki, H. & Sewell, G. L. KMS conditions and local thermodynamical stability of quantum lattice systems. Commun. Math. Phys. 52, 103\u2013109 (1977).","journal-title":"Commun. Math. Phys."},{"key":"51592_CR16","doi-asserted-by":"publisher","first-page":"2858","DOI":"10.1137\/22M1500216","volume":"33","author":"H Fawzi","year":"2023","unstructured":"Fawzi, H. & Saunderson, J. Optimal self-concordant barriers for quantum relative entropies. SIAM J. Optim. 33, 2858\u20132884 (2023).","journal-title":"SIAM J. Optim."},{"key":"51592_CR17","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s10208-018-9385-0","volume":"19","author":"H Fawzi","year":"2019","unstructured":"Fawzi, H., Saunderson, J. & Parrilo, P. A. Semidefinite approximations of the matrix logarithm. Found. Comput. Math. 19, 259\u2013296 (2019).","journal-title":"Found. Comput. Math."},{"key":"51592_CR18","doi-asserted-by":"crossref","unstructured":"Cho, M. & Sun, X. Bootstrap, Markov Chain Monte Carlo, and LP\/SDP hierarchy for the lattice Ising model. J. High Energ. Phys. 2023, 47 (2023).","DOI":"10.1007\/JHEP11(2023)047"},{"key":"51592_CR19","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1021\/ar050029d","volume":"39","author":"DA Mazziotti","year":"2006","unstructured":"Mazziotti, D. A. Quantum chemistry without wave functions: two-electron reduced density matrices. Account. Chem. Res. 39, 207\u2013215 (2006).","journal-title":"Account. Chem. Res."},{"key":"51592_CR20","doi-asserted-by":"publisher","first-page":"2157","DOI":"10.1137\/090760155","volume":"20","author":"S Pironio","year":"2010","unstructured":"Pironio, S., Navascu\u00e9s, M. & Ac\u00edn, A. Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM J. Optim. 20, 2157\u20132180 (2010).","journal-title":"SIAM J. Optim."},{"key":"51592_CR21","doi-asserted-by":"publisher","first-page":"023027","DOI":"10.1088\/1367-2630\/14\/2\/023027","volume":"14","author":"T Baumgratz","year":"2012","unstructured":"Baumgratz, T. & Plenio, M. B. Lower bounds for ground states of condensed matter systems. New J. Phys. 14, 023027 (2012).","journal-title":"New J. Phys."},{"key":"51592_CR22","doi-asserted-by":"publisher","first-page":"200404","DOI":"10.1103\/PhysRevLett.108.200404","volume":"108","author":"T Barthel","year":"2012","unstructured":"Barthel, T. & H\u00fcbener, R. Solving condensed-matter ground-state problems by semidefinite relaxations. Phys. Rev. Lett. 108, 200404 (2012).","journal-title":"Phys. Rev. Lett."},{"key":"51592_CR23","doi-asserted-by":"publisher","first-page":"223001","DOI":"10.1088\/1751-8121\/aa6dc3","volume":"50","author":"JC Bridgeman","year":"2017","unstructured":"Bridgeman, J. C. & Chubb, C. T. Hand-waving and interpretive dance: an introductory course on tensor networks. J. Phys. A Math. Theor. 50, 223001 (2017).","journal-title":"J. Phys. A Math. Theor."},{"key":"51592_CR24","doi-asserted-by":"publisher","first-page":"045003","DOI":"10.1103\/RevModPhys.93.045003","volume":"93","author":"JI Cirac","year":"2021","unstructured":"Cirac, J. I., P\u00e9rez-Garc\u00eda, D., Schuch, N. & Verstraete, F. Matrix product states and projected entangled pair states: concepts, symmetries, theorems. Rev. Mod. Phys. 93, 045003 (2021).","journal-title":"Rev. Mod. Phys."},{"key":"51592_CR25","doi-asserted-by":"publisher","first-page":"2863","DOI":"10.1103\/PhysRevLett.69.2863","volume":"69","author":"SR White","year":"1992","unstructured":"White, S. R. Density matrix formulation for quantum renormalization groups. Phys. Rev. Lett. 69, 2863\u20132866 (1992).","journal-title":"Phys. Rev. Lett."},{"key":"51592_CR26","doi-asserted-by":"crossref","unstructured":"Wang, J. et al. Certifying Ground-State Properties of Many-Body Systems. Phys. Rev. X 14, 031006 (2024).","DOI":"10.1103\/PhysRevX.14.031006"},{"key":"51592_CR27","unstructured":"Han, X. Quantum many-body bootstrap. Preprint at arXiv:2006.06002 (2020)."},{"key":"51592_CR28","unstructured":"Ara\u00fajo, M., Klep, I., V\u00e9rtesi, T., Garner, A. J. P. & Navascu\u00e9s, M. Karush-Kuhn-Tucker conditions for non-commutative optimization problems. (2023)."},{"key":"51592_CR29","doi-asserted-by":"publisher","unstructured":"Poulin, D. & Hastings, M. B. Markov entropy decomposition: a variational dual for quantum belief propagation. Phys. Rev. Lett. https:\/\/doi.org\/10.1103\/physrevlett.106.080403 (2011).","DOI":"10.1103\/physrevlett.106.080403"},{"key":"51592_CR30","doi-asserted-by":"publisher","first-page":"015002","DOI":"10.1103\/RevModPhys.91.015002","volume":"91","author":"D Poland","year":"2019","unstructured":"Poland, D., Rychkov, S. & Vichi, A. The conformal bootstrap: theory, numerical techniques, and applications. Rev. Modern Phys. 91, 015002 (2019).","journal-title":"Rev. Modern Phys."},{"key":"51592_CR31","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1038\/nphys3345","volume":"11","author":"Z Landau","year":"2015","unstructured":"Landau, Z., Vazirani, U. & Vidick, T. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians. Nat. Phys. 11, 566\u2013569 (2015).","journal-title":"Nat. Phys."},{"key":"51592_CR32","doi-asserted-by":"publisher","unstructured":"Hastings, M. B. Solving gapped Hamiltonians locally. Phys. Rev. B https:\/\/doi.org\/10.1103\/physrevb.73.085115 (2006).","DOI":"10.1103\/physrevb.73.085115"},{"key":"51592_CR33","doi-asserted-by":"publisher","first-page":"045138","DOI":"10.1103\/PhysRevB.91.045138","volume":"91","author":"A Molnar","year":"2015","unstructured":"Molnar, A., Schuch, N., Verstraete, F. & Cirac, J. I. Approximating Gibbs states of local Hamiltonians efficiently with projected entangled pair states. Phys. Rev. B 91, 045138 (2015).","journal-title":"Phys. Rev. B"},{"key":"51592_CR34","doi-asserted-by":"publisher","unstructured":"Kuwahara, T., Alhambra, A. M. & Anshu, A. Improved thermal area law and quasilinear time algorithm for quantum Gibbs states. Phys. Rev. X https:\/\/doi.org\/10.1103\/physrevx.11.011047 (2021).","DOI":"10.1103\/physrevx.11.011047"},{"key":"51592_CR35","doi-asserted-by":"publisher","first-page":"1011","DOI":"10.22331\/q-2023-05-22-1011","volume":"7","author":"H Fawzi","year":"2023","unstructured":"Fawzi, H., Fawzi, O. & Scalet, S. O. A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit. Quantum 7, 1011 (2023).","journal-title":"Quantum"},{"key":"51592_CR36","doi-asserted-by":"publisher","first-page":"220601","DOI":"10.1103\/PhysRevLett.124.220601","volume":"124","author":"T Kuwahara","year":"2020","unstructured":"Kuwahara, T., Kato, K. & Brand\u00e3o, F. G. Clustering of conditional mutual information for quantum gibbs states above a threshold temperature. Phys.Rev. Lett. 124, 220601 (2020).","journal-title":"Phys.Rev. Lett."},{"key":"51592_CR37","doi-asserted-by":"crossref","unstructured":"Harrow, A. W., Mehraban, S. & Soleimanifar, M. 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, 2020).","DOI":"10.1145\/3357713.3384322"},{"key":"51592_CR38","doi-asserted-by":"publisher","unstructured":"Mann, R. L. & Helmuth, T. Efficient algorithms for approximating quantum partition functions. J. Math. Phys. https:\/\/doi.org\/10.1063\/5.0013689 (2021).","DOI":"10.1063\/5.0013689"},{"key":"51592_CR39","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1038\/s41567-022-01742-5","volume":"18","author":"S Bravyi","year":"2022","unstructured":"Bravyi, S., Chowdhury, A., Gosset, D. & Wocjan, P. Quantum Hamiltonian complexity in thermal equilibrium. Nat. Phys. 18, 1367\u20131370 (2022).","journal-title":"Nat. Phys."},{"key":"51592_CR40","unstructured":"Wu, D. et al. Variational benchmarks for quantum many-body problems. Preprint at arXiv:2302.04919 (2023)."},{"key":"51592_CR41","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Fawzi, O. & Scalet, S. O. Entropy constraints for ground energy optimization. J. Math. Phys. 65, 032201 (2024).","DOI":"10.1063\/5.0159108"},{"key":"51592_CR42","doi-asserted-by":"crossref","unstructured":"Kull, I., Schuch, N., Dive, B. & Navascu\u00e9s, M. Lower bounding ground-state energies of local Hamiltonians through the renormalization group. Phys. Rev. X 14, 021008 (2024).","DOI":"10.1103\/PhysRevX.14.021008"},{"key":"51592_CR43","doi-asserted-by":"publisher","first-page":"761","DOI":"10.22331\/q-2022-07-11-761","volume":"6","author":"R Zhang","year":"2022","unstructured":"Zhang, R., Wang, G. & Johnson, P. Computing ground state properties with early fault-tolerant quantum computers. Quantum 6, 761 (2022).","journal-title":"Quantum"}],"container-title":["Nature Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s41467-024-51592-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41467-024-51592-3","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41467-024-51592-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T14:05:35Z","timestamp":1724767535000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s41467-024-51592-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,27]]},"references-count":43,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["51592"],"URL":"https:\/\/doi.org\/10.1038\/s41467-024-51592-3","relation":{},"ISSN":["2041-1723"],"issn-type":[{"value":"2041-1723","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,27]]},"assertion":[{"value":"4 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"7394"}}