{
  "id": "1004.0188",
  "version": "v2",
  "published": "2010-04-01T17:31:07.000Z",
  "updated": "2010-07-21T23:33:53.000Z",
  "title": "Bounds for mixing time of quantum walks on finite graphs",
  "authors": [
    "Vladislav Kargin"
  ],
  "comment": "This is the journal version (except formatting); it is a significant revision of the previous version, in particular, it contains a new result about the convergence of quantum walks with decoherence; 16 pages",
  "journal": "J. Phys. A: Math. Theor. 43 (2010) 335302",
  "doi": "10.1088/1751-8113/43/33/335302",
  "categories": [
    "math.PR",
    "quant-ph"
  ],
  "abstract": "Several inequalities are proved for the mixing time of discrete-time quantum walks on finite graphs. The mixing time is defined differently than in Aharonov, Ambainis, Kempe and Vazirani (2001) and it is found that for particular examples of walks on a cycle, a hypercube and a complete graph, quantum walks provide no speed-up in mixing over the classical counterparts. In addition, non-unitary quantum walks (i.e., walks with decoherence) are considered and a criterion for their convergence to the unique stationary distribution is derived.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-07-21T23:33:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "mixing time",
      "finite graphs",
      "unique stationary distribution",
      "non-unitary quantum walks",
      "discrete-time quantum walks"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "journal": "Journal of Physics A Mathematical General",
      "year": 2010,
      "month": "Aug",
      "volume": 43,
      "number": 33,
      "pages": 335302
    },
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010JPhA...43G5302K"
    }
  }
}