Exponential algorithmic speedup by a quantum walk

TLDR

The quantum algorithm is based on a continuous‑time quantum walk, differing from earlier quantum algorithms that use quantum Fourier transforms. The authors construct a black‑box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. They demonstrate how to efficiently implement a continuous‑time quantum walk that solves this problem exponentially faster than any classical algorithm. The quantum walk rapidly traverses the graph, solving the problem exponentially faster, and the authors prove that no classical algorithm can solve it in subexponential time.

Abstract

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.