dorsal/arxiv
View SchemaThe computational complexity of PEPS
| Authors | Norbert Schuch, Michael M. Wolf, Frank Verstraete, J. Ignacio Cirac |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0611050 |
| URL | https://arxiv.org/abs/quant-ph/0611050 |
| DOI | 10.1103/PhysRevLett.98.140506 |
| Journal | Phys. Rev. Lett. 98, 140506 (2007) |
Abstract
We determine the computational power of preparing Projected Entangled Pair States (PEPS), as well as the complexity of classically simulating them, and generally the complexity of contracting tensor networks. While creating PEPS allows to solve PP problems, the latter two tasks are both proven to be #P-complete. We further show how PEPS can be used to approximate ground states of gapped Hamiltonians, and that creating them is easier than creating arbitrary PEPS. The main tool for our proofs is a duality between PEPS and postselection which allows to use existing results from quantum compexity.
{
"annotation_id": "ab447d1d-a810-43d1-9802-8f1dfb13730d",
"date_created": "2026-03-02T18:02:30.289000Z",
"date_modified": "2026-03-02T18:02:30.289000Z",
"file_hash": "c31da7fb945fe2c43015baadfd7605356a930c4ce2a869e8283056b44182b2b1",
"private": false,
"record": {
"abstract": "We determine the computational power of preparing Projected Entangled Pair\nStates (PEPS), as well as the complexity of classically simulating them, and\ngenerally the complexity of contracting tensor networks. While creating PEPS\nallows to solve PP problems, the latter two tasks are both proven to be\n#P-complete. We further show how PEPS can be used to approximate ground states\nof gapped Hamiltonians, and that creating them is easier than creating\narbitrary PEPS. The main tool for our proofs is a duality between PEPS and\npostselection which allows to use existing results from quantum compexity.",
"arxiv_id": "quant-ph/0611050",
"authors": [
"Norbert Schuch",
"Michael M. Wolf",
"Frank Verstraete",
"J. Ignacio Cirac"
],
"categories": [
"quant-ph",
"cond-mat.other"
],
"doi": "10.1103/PhysRevLett.98.140506",
"journal_ref": "Phys. Rev. Lett. 98, 140506 (2007)",
"title": "The computational complexity of PEPS",
"url": "https://arxiv.org/abs/quant-ph/0611050"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4ca5b9de-71ff-46cd-a4f9-c09a94741b3e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}