{
  "id": "1112.3337",
  "version": "v1",
  "published": "2011-12-14T20:55:56.000Z",
  "updated": "2011-12-14T20:55:56.000Z",
  "title": "Search by quantum walks on two-dimensional grid without amplitude amplification",
  "authors": [
    "Andris Ambainis",
    "Arturs Backurs",
    "Nikolajs Nahimovs",
    "Raitis Ozols",
    "Alexander Rivosh"
  ],
  "comment": "22 pages, 3 figures",
  "categories": [
    "quant-ph",
    "cs.CC",
    "cs.DS"
  ],
  "abstract": "We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh (quant-ph/0402107) takes O(\\sqrt{N log N}) steps and finds a marked location with probability O(1/log N) for grid of size \\sqrt{N} * \\sqrt{N}. This probability is small, thus amplitude amplification is needed to achieve \\Theta(1) success probability. The amplitude amplification adds an additional O(\\sqrt{log N}) factor to the number of steps, making it O(\\sqrt{N} log N). In this paper, we show that despite a small probability to find a marked location, the probability to be within an O(\\sqrt{N}) neighbourhood (at an O(\\sqrt[4]{N}) distance) of the marked location is \\Theta(1). This allows to skip amplitude amplification step and leads to an O(\\sqrt{log N}) speed-up. We describe the results of numerical experiments supporting this idea, and we prove this fact analytically.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-12-14T20:55:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum walk",
      "two-dimensional grid",
      "marked location",
      "skip amplitude amplification step",
      "amplitude amplification adds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1112.3337A"
    }
  }
}