{
  "id": "quant-ph/0405120",
  "version": "v1",
  "published": "2004-05-20T16:10:21.000Z",
  "updated": "2004-05-20T16:10:21.000Z",
  "title": "Spatial search and the Dirac equation",
  "authors": [
    "Andrew M. Childs",
    "Jeffrey Goldstone"
  ],
  "comment": "5 pages, 1 figure",
  "journal": "Phys. Rev. A 70, 042312 (2004)",
  "doi": "10.1103/PhysRevA.70.042312",
  "categories": [
    "quant-ph"
  ],
  "abstract": "We consider the problem of searching a d-dimensional lattice of N sites for a single marked location. We present a Hamiltonian that solves this problem in time of order sqrt(N) for d>2 and of order sqrt(N) log(N) in the critical dimension d=2. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of d=4), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-05-20T16:10:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "spatial search",
      "dirac equation",
      "corresponding discrete-time quantum walk algorithm",
      "quantum walk search algorithm",
      "order sqrt"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "APS",
      "journal": "Phys. Rev. A"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}