dorsal/arxiv
View SchemaSimulating quantum computation by contracting tensor networks
| Authors | Igor L. Markov, Yaoyun Shi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0511069 |
| URL | https://arxiv.org/abs/quant-ph/0511069 |
| DOI | 10.1137/050644756 |
| Journal | SIAM Journal on Computing, 38(3):963-981, 2008 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with $T$ gates whose underlying graph has treewidth $d$ can be simulated deterministically in $T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in $T$ if $d=O(\log T)$. Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Physical Review Letters, 86:5188--5191, 2001), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph.
{
"annotation_id": "257c04c2-955e-4130-a535-d2e375c2e599",
"date_created": "2026-03-02T18:02:20.550000Z",
"date_modified": "2026-03-02T18:02:20.550000Z",
"file_hash": "ab41d02c66adb8f6ce14e54d15595c77308314c4db86a2a237b1a3ec236f5c41",
"private": false,
"record": {
"abstract": "The treewidth of a graph is a useful combinatorial measure of how close the\ngraph is to a tree. We prove that a quantum circuit with $T$ gates whose\nunderlying graph has treewidth $d$ can be simulated deterministically in\n$T^{O(1)}\\exp[O(d)]$ time, which, in particular, is polynomial in $T$ if\n$d=O(\\log T)$. Among many implications, we show efficient simulations for\nlog-depth circuits whose gates apply to nearby qubits only, a natural\nconstraint satisfied by most physical implementations. We also show that\none-way quantum computation of Raussendorf and Briegel (Physical Review\nLetters, 86:5188--5191, 2001), a universal quantum computation scheme with\npromising physical implementations, can be efficiently simulated by a\nrandomized algorithm if its quantum resource is derived from a small-treewidth\ngraph.",
"arxiv_id": "quant-ph/0511069",
"authors": [
"Igor L. Markov",
"Yaoyun Shi"
],
"categories": [
"quant-ph"
],
"doi": "10.1137/050644756",
"journal_ref": "SIAM Journal on Computing, 38(3):963-981, 2008",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Simulating quantum computation by contracting tensor networks",
"url": "https://arxiv.org/abs/quant-ph/0511069"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "19ee614d-3fbe-4b6a-8bfb-5856bf563268",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}