{
  "id": "quant-ph/0403127",
  "version": "v3",
  "published": "2004-03-17T18:05:06.000Z",
  "updated": "2004-05-11T11:46:36.000Z",
  "title": "Quantum Algorithms and Covering Spaces",
  "authors": [
    "Tobias J. Osborne",
    "Simone Severini"
  ],
  "comment": "24 pages, 1 figure, uses psfrag. Added reference. Fixed reference",
  "categories": [
    "quant-ph"
  ],
  "abstract": "In this paper we isolate the combinatorial property responsible (at least in part) for the computational speedups recently observed in some quantum walk algorithms. We find that continuous-time quantum walks can exploit the covering space property of certain graphs. We demonstrate that a quantum walk on a graph Y which covers a smaller graph X can be equivalent to a quantum walk on the smaller graph X. This equivalence occurs only when the walk begins on certain initial states, fibre-constant states, which respect the graph covering space structure. We illustrate these observations with walks on Cayley graphs; we show that walks on fibre-constant initial states for Cayley graphs are equivalent to walks on the induced Schreier graph. We also consider the problem of constructing efficient gate sequences simulating the time evolution of a continuous-time quantum walk. For the case of the walk on the m-torus graph T^m on 2^n vertices we construct a gate sequence which uses O(\\poly(n)) gates which is independent of the time t the walk is simulated for (and so the sequence can simulate the walk for exponential times). We argue that there exists a wide class of nontrivial operators based on quantum walks on graphs which can be measured efficiently. We introduce a new general class of computational problems, HiddenCover, which includes a variant of the general hidden subgroup problem as a subclass. We argue that quantum computers ought to be able to utilise covering space structures to efficiently solve HiddenCover problems.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2004-05-11T11:46:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum algorithms",
      "efficient gate sequences simulating",
      "continuous-time quantum walk",
      "covering space structure",
      "cayley graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004quant.ph..3127O"
    }
  }
}