{
  "id": "0911.1102",
  "version": "v1",
  "published": "2009-11-05T19:01:14.000Z",
  "updated": "2009-11-05T19:01:14.000Z",
  "title": "Searching via walking: How to find a marked subgraph of a graph using quantum walks",
  "authors": [
    "Mark Hillery",
    "Daniel Reitzner",
    "Vladimir Buzek"
  ],
  "comment": "4 pages, 2 figures",
  "categories": [
    "quant-ph"
  ],
  "abstract": "We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has N vertices and the subgraph has K vertices, the particle becomes localized on the subgraph in O(N/K) steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resource needed for a quantitative comparison of the efficiency of classical and quantum searches -- the number of oracle calls.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-11-05T19:01:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03.67.Ac",
      "05.40.Fb",
      "42.50.Ex"
    ],
    "keywords": [
      "quantum walk",
      "marked subgraph",
      "complete graph",
      "specific phase shift",
      "quantum oracle"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "doi": "10.1103/PhysRevA.81.062324",
      "journal": "Physical Review A",
      "year": 2010,
      "month": "Jun",
      "volume": 81,
      "number": 6,
      "pages": "062324"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010PhRvA..81f2324H"
    }
  }
}