STOC Conference 2003 Conference Paper
Exponential algorithmic speedup by a quantum walk
- Andrew M. Childs
- Richard Cleve
- Enrico Deotto
- Edward Farhi
- Sam Gutmann
- Daniel A. Spielman
We construct a black box graph traversal 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 black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.