Physics – Quantum Physics
Scientific paper
2004-03-17
Physics
Quantum Physics
24 pages, 1 figure, uses psfrag. Added reference. Fixed reference
Scientific paper
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.
Osborne Tobias J.
Severini Simone
No associations
LandOfFree
Quantum Algorithms and Covering Spaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Algorithms and Covering Spaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithms and Covering Spaces will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-152325