{
  "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
}