More Web Proxy on the site http://driver.im/

research-article

Computational complexity of the ground state energy density problem

Authors:

James D. Watson,

Toby S. CubittAuthors Info & Claims

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

Pages 764 - 775

https://doi.org/10.1145/3519935.3520052

Published: 10 June 2022 Publication History

Abstract

We study the complexity of finding the ground state energy density of a local Hamiltonian on a lattice in the thermodynamic limit of infinite lattice size. We formulate this rigorously as a function problem, in which we request an estimate of the ground state energy density to some specified precision; and as an equivalent promise problem, GSED, in which we ask whether the ground state energy density is above or below specified thresholds.

The ground state energy density problem is unusual, in that it concerns a single, fixed Hamiltonian in the thermodynamic limit, whose ground state energy density is just some fixed, real number. The only input to the computational problem is the precision to which to estimate this fixed real number, corresponding to the ground state energy density. Hardness of this problem for a complexity class therefore implies that the solutions to all problems in the class are encoded in this single number (analogous to Chaitin’s constant in computability theory).

This captures computationally the type of question most commonly encountered in condensed matter physics, which is typically concerned with the physical properties of a single Hamiltonian in the thermodynamic limit. We show that for classical, translationally invariant, nearest neighbour Hamiltonians on a 2D square lattice, P^NEEXP⊆EXP^GSED⊆ EXP^NEXP, and for quantum Hamiltonians P^NEEXP⊆EXP^GSED⊆ EXP^QMA_EXP. With some technical caveats on the oracle definitions, the EXP in some of these results can be strengthened to PSPACE. We also give analogous complexity bounds for the function version of GSED.

References

[1]

Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. 2007. The Power of Quantum Systems on a Line. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS07), https://doi.org/10.1109/focs.2007.46

[2]

Dorit Aharonov and Sandy Irani. 2021. Hamiltonian Complexity in the Thermodynamic Limit. arXiv e-prints, Article arXiv:2107.06201, July, arXiv:2107.06201 pages. https://doi.org/10.48550/arXiv.2107.06201 arxiv:2107.06201.

[3]

Andris Ambainis. 2014. On Physical Problems that are Slightly More Difficult than QMA. 2014 IEEE 29th Conference on Computational Complexity (CCC), https://doi.org/10.1109/ccc.2014.12

Digital Library

[4]

Francisco Barahona. 1982. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15, 10 (1982), 3241.

[5]

Johannes Bausch, Toby S. Cubitt, Angelo Lucia, and David Perez-Garcia. 2020. Undecidability of the spectral gap in one dimension. Physical Review X, 10, 3 (2020), https://doi.org/10.1103/physrevx.10.031038

[6]

Johannes Bausch, Toby S. Cubitt, Angelo Lucia, David Perez-Garcia, and Michael M. Wolf. 2018. Size-driven quantum phase transitions. Proceedings of the National Academy of Sciences, 115, 1 (2018), jan, 19–23. issn:0027-8424 https://doi.org/10.1073/pnas.1705042114 arxiv:1512.05687.

[7]

Johannes Bausch, Toby S. Cubitt, and James D. Watson. 2021. Uncomputability of phase diagrams. Nature Communications, 12, 1 (2021), https://doi.org/10.1038/s41467-020-20504-6

[8]

Robert Berger. 1966. The undecidability of the domino problem. Memoirs of the American Mathematical Society, https://doi.org/10.1090/memo/0066

[9]

Brielin Brown, Steven T. Flammia, and Norbert Schuch. 2011. Computational Difficulty of Computing the Density of States. Physical Review Letters, 107, 4 (2011), https://doi.org/10.1103/physrevlett.107.040501

[10]

Jonathan F. Buss. 1988. Relativized alternation and space-bounded computation. J. Comput. System Sci., 36, 3 (1988), 351–378. https://doi.org/10.1016/0022-0000(88)90034-7

Digital Library

[11]

Gregory J. Chaitin. 1975. A theory of program size formally identical to information theory. J. ACM, 22, 3 (1975), 329–340. https://doi.org/10.1145/321892.321894

Digital Library

[12]

Toby S. Cubitt, David Perez-Garcia, and Michael M. Wolf. 2015. Undecidability of the spectral gap. Nature, 528, 7581 (2015), 12, 207–211. issn:0028-0836 https://doi.org/10.1038/nature16059 arxiv:1502.04573.

[13]

Toby S. Cubitt, David Perez-Garcia, and Michael M. Wolf. 2015. Undecidability of the spectral gap. https://doi.org/10.48550/arXiv.1502.04573

[14]

Samir Datta and Rameshwar Pratap. 2011. Computing Bits of Algebraic Numbers. arXiv e-prints, Article arXiv:1112.4295, Dec., arXiv:1112.4295 pages. https://doi.org/10.48550/arXiv.1112.4295 arxiv:1112.4295.

[15]

Lance Fortnow. 1994. The Role of Relativization in Complexity Theory. Bulletin of the European Association for Theoretical Computer Science, 52 (1994), 52–229.

[16]

Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. 2015. Quantum hamiltonian complexity. Foundations and Trends® in Theoretical Computer Science, 10, 3 (2015), 159–282. https://doi.org/10.1561/0400000066

Digital Library

[17]

Sevag Gharibian, Stephen Piddock, and Justin Yirka. 2020. Oracle Complexity Classes and Local Measurements on Physical Hamiltonians. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Christophe Paul and Markus Bläser (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 154). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 20:1–20:37. isbn:978-3-95977-140-5 issn:1868-8969 https://doi.org/10.4230/LIPIcs.STACS.2020.20

[18]

Sevag Gharibian and Jamie Sikora. 2018. Ground State Connectivity of Local Hamiltonians. ACM Trans. Comput. Theory, 10, 2 (2018), Article 8, April, 28 pages. issn:1942-3454 https://doi.org/10.1145/3186587

Digital Library

[19]

Sevag Gharibian and Justin Yirka. 2019. The complexity of simulating local measurements on quantum systems. Quantum, 3 (2019), Sept., 189. issn:2521-327X https://doi.org/10.22331/q-2019-09-30-189

[20]

Daniel Gottesman and Sandy Irani. 2009. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. In Foundations of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on. 95–104. https://doi.org/10.1109/focs.2009.22

Digital Library

[21]

Juris Hartmanis, Richard Chang, Jim Kadin, and Stephen G. Mitchell. 1993. Some Observations about Relativization of Space Bounded Computations. Current Trends in Theoretical Computer Science, 423–434. https://doi.org/10.1142/9789812794499_0031

[22]

Lloyd C. L. Hollenberg and Nicholas S. Witte. 1994. General nonperturbative estimate of the energy density of lattice Hamiltonians. Physical Review D, 50, 5 (1994), 3382–3386. https://doi.org/10.1103/physrevd.50.3382

[23]

Stephen P. Jordan, David Gosset, and Peter J. Love. 2010. Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices. Physical Review A, 81, 3 (2010), https://doi.org/10.1103/physreva.81.032331

[24]

Richard M. Karp and Richard J. Lipton. 1980. Some connections between nonuniform and uniform complexity classes. Proceedings of the twelfth annual ACM symposium on Theory of computing - STOC 80, https://doi.org/10.1145/800141.804678

Digital Library

[25]

Alexei Yu. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. 2002. Classical and quantum computing. In Quantum Information. Springer New York, New York, NY. 203–217. https://doi.org/10.1007/978-0-387-36944-0_13

[26]

Richard E. Ladner and Nancy A. Lynch. 1976. Relativization of questions about log space computability. Mathematical Systems Theory, 10, 1 (1976), 19–32. https://doi.org/10.1007/bf01683260

[27]

Der-Tsai Lee and Bruce J. Schachter. 1980. Two algorithms for constructing a Delaunay triangulation. International Journal of Computer & Information Sciences, 9, 3 (1980), 219–242. https://doi.org/10.1007/bf00977785

[28]

Jacek Miekisz. 1997. Stable Quasicrystalline Ground States. Journal of Statistical Physics, 88, 3/4 (1997), 691–711. https://doi.org/10.1023/b:joss.0000015168.25151.22

[29]

Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge. isbn:9780511976667 https://doi.org/10.1017/CBO9780511976667

[30]

Christos H. Papadimitriou. 1994. Computational complexity. Addison-Wesley.

[31]

John P. Perdew, J. A. Chevary, S. H. Vosko, Koblar A. Jackson, Mark R. Pederson, D. J. Singh, and Carlos Fiolhais. 1992. Atoms, molecules, solids, and surfaces: Applications of the generalized gradient approximation for exchange and correlation. Physical Review B, 46, 11 (1992), 6671–6687. https://doi.org/10.1103/physrevb.46.6671

[32]

Raphael M. Robinson. 1971. Undecidability and nonperiodicity for tilings of the plane. Inventiones mathematicae, 12, 3 (1971), 09, 177–209. issn:0020-9910 https://doi.org/10.1007/BF01418780

[33]

James D. Watson, Johannes Bausch, and Sevag Gharibian. 2020. The Complexity of Translationally Invariant Problems beyond Ground State Energies. arXiv e-prints, Article arXiv:2012.12717, Dec., arXiv:2012.12717 pages. https://doi.org/10.48550/arXiv.2012.12717

[34]

James D. Watson and Toby S. Cubitt. 2021. Computational Complexity of the Ground State Energy Density Problem. arXiv e-prints, Article arXiv:2107.05060, July, arXiv:2107.05060 pages. https://doi.org/10.48550/arXiv.2107.05060

Cited By

Fawzi HFawzi OScalet S(2024)Certified algorithms for equilibrium states of local quantum HamiltoniansNature Communications10.1038/s41467-024-51592-315:1Online publication date: 27-Aug-2024
https://doi.org/10.1038/s41467-024-51592-3
Trivedi RFranco Rubio ACirac J(2024)Quantum advantage and stability to errors in analogue quantum simulatorsNature Communications10.1038/s41467-024-50750-x15:1Online publication date: 2-Aug-2024
https://doi.org/10.1038/s41467-024-50750-x
Anschuetz EBauer AKiani BLloyd S(2023)Efficient classical algorithms for simulating symmetric quantum systemsQuantum10.22331/q-2023-11-28-11897(1189)Online publication date: 28-Nov-2023
https://doi.org/10.22331/q-2023-11-28-1189
Show More Cited By

Index Terms

Computational complexity of the ground state energy density problem
1. Theory of computation
  1. Computational complexity and cryptography

Recommendations

Product-state approximations to quantum ground states
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalization of constraint satisfaction problems (CSPs) and has a key role ...
Complexity Classification of Local Hamiltonian Problems
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science

The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically ...
Complexity of commuting Hamiltonians on a square lattice of qubits

We consider the computational complexity of Hamiltonians which are sums of commuting terms acting on plaquettes in a square lattice of qubits, and we show that deciding whether the ground state minimizes the energy of each local term individually is in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

June 2022

1698 pages

ISBN:9781450392648

DOI:10.1145/3519935

General Chair:
Stefano Leonardi
Sapienza University of Rome, Italy
,
Program Chair:
Anupam Gupta
Carnegie Mellon University, USA

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '22

Sponsor:

SIGACT

STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing

June 20 - 24, 2022

Rome, Italy

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
120
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fawzi HFawzi OScalet S(2024)Certified algorithms for equilibrium states of local quantum HamiltoniansNature Communications10.1038/s41467-024-51592-315:1Online publication date: 27-Aug-2024
https://doi.org/10.1038/s41467-024-51592-3
Trivedi RFranco Rubio ACirac J(2024)Quantum advantage and stability to errors in analogue quantum simulatorsNature Communications10.1038/s41467-024-50750-x15:1Online publication date: 2-Aug-2024
https://doi.org/10.1038/s41467-024-50750-x
Anschuetz EBauer AKiani BLloyd S(2023)Efficient classical algorithms for simulating symmetric quantum systemsQuantum10.22331/q-2023-11-28-11897(1189)Online publication date: 28-Nov-2023
https://doi.org/10.22331/q-2023-11-28-1189
Fawzi HFawzi OScalet S(2023)A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limitQuantum10.22331/q-2023-05-22-10117(1011)Online publication date: 22-May-2023
https://doi.org/10.22331/q-2023-05-22-1011
Ayral TBesserve PLacroix DRuiz Guzman E(2023)Quantum computing with and for many-body physicsThe European Physical Journal A10.1140/epja/s10050-023-01141-159:10Online publication date: 13-Oct-2023
https://doi.org/10.1140/epja/s10050-023-01141-1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents