Exponential algorithmic speedup by quantum walk

TitleExponential algorithmic speedup by quantum walk
Publication TypeJournal Article
Year of Publication2002
AuthorsChilds, AM, Cleve, R, Deotto, E, Farhi, E, Gutmann, S, Spielman, DA
Date Published2002/09/24

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.

Short TitleProc. 35th ACM Symposium on Theory of Computing (STOC 2003)