01113nas a2200169 4500008004100000245005200041210005200093260001500145520061800160100002300778700001900801700001900820700001800839700001700857700002500874856004400899 2002 eng d00aExponential algorithmic speedup by quantum walk0 aExponential algorithmic speedup by quantum walk c2002/09/243 a We construct an oracular (i.e., black box) problem that can be solved
exponentially faster on a quantum computer than on a classical computer. The
quantum algorithm is based on a continuous time quantum walk, and thus employs
a different technique from previous quantum algorithms based on quantum Fourier
transforms. We show how to implement the quantum walk efficiently in our
oracular setting. We then show how this quantum walk can be used to solve our
problem by rapidly traversing a graph. Finally, we prove that no classical
algorithm can solve this problem with high probability in subexponential time.
1 aChilds, Andrew, M.1 aCleve, Richard1 aDeotto, Enrico1 aFarhi, Edward1 aGutmann, Sam1 aSpielman, Daniel, A. uhttp://arxiv.org/abs/quant-ph/0209131v2