Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems
Open accessThe DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
Here we present a problem related to the local Hamiltonian problem (identifying whether the ground-state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for Hamiltonians with a fixed local dimension and $O\mathbf{(}\mathrm{log}(N)\mathbf{)}$-body local terms, or local dimension $N$ and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). We discuss the implications for the computational complexity of finding ground states of these systems and hence for any classical approximation techniques that one could apply including density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction---i.e., a generalization of the Bose-Hubbard model.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Perfect State Transfer in Quantum Spin Networks
Christandl, M., Datta, N., Ekert, A., & Landahl, A. J. (2004) · Physical Review Letters · doi:10.1103/physrevlett.92.187902 · Cited by 1,179
Matrix product states represent ground states faithfully
Verstraete, F., & Cirac, J. I. (2006) · Physical Review B · doi:10.1103/physrevb.73.094423 · Cited by 730
The Complexity of the Local Hamiltonian Problem
Kempe, J., Kitaev, A., & Regev, O. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704445226 · Cited by 648
Criticality, the Area Law, and the Computational Power of Projected Entangled Pair States
Verstraete, F., Wolf, M. M., Perez-Garcia, D., & Cirac, J. I. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.220601 · Cited by 580
Perfect transfer of arbitrary states in quantum spin networks
Christandl, M., Datta, N., Dorlas, T. C., Ekert, A., Kay, A., & Landahl, A. J. (2005) · Physical Review A · doi:10.1103/physreva.71.032312 · Cited by 512
Self-citationComputational complexity of projected entangled pair states
Schuch, N., Wolf, M. M., Verstraete, F., & Cirac, J. I. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.140506 · Cited by 313
Quantum Computational Complexity of the N -Representability Problem: QMA Complete
Liu, Y.-K., Christandl, M., & Verstraete, F. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.110503 · Cited by 211
Cited by
Entropy Scaling and Simulability by Matrix Product States
Schuch, N., Wolf, M. M., Verstraete, F., & Cirac, J. I. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.030504 · Cited by 409
Quantum Hamiltonian Complexity
Gharibian, S., Huang, Y., Landau, Z., & Shin, S. W. (2015) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000066 · Cited by 144
On entropy growth and the hardness of simulating time evolution
Schuch, N., Wolf, M. M., Vollbrecht, K. G. H., & Cirac, J. I. (2008) · New Journal of Physics · doi:10.1088/1367-2630/10/3/033032 · Cited by 113
Computational Difficulty of Finding Matrix Product Ground States
Schuch, N., Cirac, I., & Verstraete, F. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.250501 · Cited by 60
Bookatz, A. D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.5-6-1 · Cited by 26
Metadata
- Authors
- Kay, A.
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2007-09-20
- Volume
- 76
- Issue
- 3
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W1923484136
- Cited by
- 21
- References
- 7
- FWCI
- 2.04
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems. https://app.cochat.ai/papers/10.1103/physreva.76.030307
- The paper
- Kay, A. (2007). Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems. Physical Review A. https://doi.org/10.1103/physreva.76.030307
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.