Computational Difficulty of Global Variations in the Density Matrix Renormalization Group
Open accessThe DOI matches its Crossref record; 5 of the 5 references it cites were found in a registry or an index.
Abstract
The density matrix renormalization group approach is arguably the most successful method to numerically find ground states of quantum spin chains. It amounts to iteratively locally optimizing matrix-product states, aiming at better and better approximating the true ground state. To date, both a proof of convergence to the globally best approximation and an assessment of its complexity are lacking. Here we establish a result on the computational complexity of an approximation with matrix-product states: The surprising result is that when one globally optimizes over several sites of local Hamiltonians, avoiding local optima, one encounters in the worst case a computationally difficult NP-hard problem (hard even in approximation). The proof exploits a novel way of relating it to binary quadratic programming. We discuss intriguing ramifications on the difficulty of describing quantum many-body systems.
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
The density-matrix renormalization group
Schollwöck, U. (2005) · Reviews of Modern Physics · doi:10.1103/revmodphys.77.259 · Cited by 3,323
Entanglement in Quantum Critical Phenomena
Vidal, G., Latorre, J. I., Rico, E., & Kitaev, A. (2003) · Physical Review Letters · doi:10.1103/physrevlett.90.227902 · Cited by 2,793
Matrix Product Density Operators: Simulation of Finite-Temperature and Dissipative Systems
Verstraete, F., García-Ripoll, J. J., & Cirac, J. I. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.207204 · Cited by 1,098
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
General Entanglement Scaling Laws from Time Evolution
Eisert, J., & Osborne, T. J. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.150404 · Cited by 201
Self-citation
Cited by
Colloquium : Area laws for the entanglement entropy
Eisert, J., Cramer, M., & Plenio, M. B. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.277 · Cited by 2,873
Self-citationVerstraete, F., Murg, V., & Cirac, J. I. (2008) · Advances in Physics · doi:10.1080/14789940801912366 · Cited by 1,762
An area law for one-dimensional quantum systems
Hastings, M. B. (2007) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2007/08/p08024 · Cited by 1,131
Training Variational Quantum Algorithms Is NP-Hard
Bittel, L., & Kliesch, M. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.120502 · Cited by 398
“For instance, optimization within the density matrix renormalization group (DMRG) method is NP-hard [22].”
MethodFagotti, M., & Calabrese, P. (2008) · Physical Review A · doi:10.1103/physreva.78.010306 · Cited by 378
Metadata
- Authors
- Eisert, J.
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2006-12-28
- Volume
- 97
- Issue
- 26
- Pages
- 260501-260501
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2055116690
- Cited by
- 36
- References
- 5
- FWCI
- 4.08
- 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: Computational Difficulty of Global Variations in the Density Matrix Renormalization Group. https://app.cochat.ai/papers/10.1103/physrevlett.97.260501
- The paper
- Eisert, J. (2006). Computational Difficulty of Global Variations in the Density Matrix Renormalization Group. Physical Review Letters. https://doi.org/10.1103/physrevlett.97.260501
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.