dorsal/arxiv
View SchemaComputational Difficulty of Global Variations in the Density Matrix Renormalization Group
| Authors | J. Eisert |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0609051 |
| URL | https://arxiv.org/abs/quant-ph/0609051 |
| DOI | 10.1103/PhysRevLett.97.260501 |
| Journal | Phys. Rev. Lett. 97, 260501 (2006) |
Abstract
The density matrix renormalization group (DMRG) 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.
{
"annotation_id": "eb943da2-727c-4ea2-8968-da391c322b45",
"date_created": "2026-03-02T18:02:30.971000Z",
"date_modified": "2026-03-02T18:02:30.971000Z",
"file_hash": "7c93eae0fbb518f66a3dc60b3b4f73cf60b95e039c49aab11a4c75b2f5f15648",
"private": false,
"record": {
"abstract": "The density matrix renormalization group (DMRG) approach is arguably the most\nsuccessful method to numerically find ground states of quantum spin chains. It\namounts to iteratively locally optimizing matrix-product states, aiming at\nbetter and better approximating the true ground state. To date, both a proof of\nconvergence to the globally best approximation and an assessment of its\ncomplexity are lacking. Here we establish a result on the computational\ncomplexity of an approximation with matrix-product states: The surprising\nresult is that when one globally optimizes over several sites of local\nHamiltonians, avoiding local optima, one encounters in the worst case a\ncomputationally difficult NP-hard problem (hard even in approximation). The\nproof exploits a novel way of relating it to binary quadratic programming. We\ndiscuss intriguing ramifications on the difficulty of describing quantum\nmany-body systems.",
"arxiv_id": "quant-ph/0609051",
"authors": [
"J. Eisert"
],
"categories": [
"quant-ph",
"cond-mat.stat-mech",
"math-ph",
"math.MP"
],
"doi": "10.1103/PhysRevLett.97.260501",
"journal_ref": "Phys. Rev. Lett. 97, 260501 (2006)",
"title": "Computational Difficulty of Global Variations in the Density Matrix Renormalization Group",
"url": "https://arxiv.org/abs/quant-ph/0609051"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "25a2e8e6-2d4a-4f5b-89a5-d7ae2f2c8510",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}