{
  "id": "quant-ph/0511069",
  "version": "v7",
  "published": "2005-11-08T06:11:31.000Z",
  "updated": "2009-07-12T18:58:35.000Z",
  "title": "Simulating quantum computation by contracting tensor networks",
  "authors": [
    "Igor L. Markov",
    "Yaoyun Shi"
  ],
  "comment": "7 figures",
  "journal": "SIAM Journal on Computing, 38(3):963-981, 2008",
  "doi": "10.1137/050644756",
  "categories": [
    "quant-ph"
  ],
  "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.",
  "revisions": [
    {
      "version": "v7",
      "updated": "2009-07-12T18:58:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "contracting tensor networks",
      "simulating quantum computation",
      "universal quantum computation scheme",
      "one-way quantum computation",
      "physical implementations"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005quant.ph.11069M"
    }
  }
}