Quantum Search with Better-than-Quadratic Speedup over Classical Random Walk

Thomas G. Wong, Andris Ambainis

Published 2015-02-17Version 1

A randomly walking classical particle can search on the $M$ simplex, with each of its $M+1$ vertices replaced by the complete graph of $M$ vertices, for a fully marked complete graph in $\Theta(M^2)$ steps. A discrete-time quantum walk performs the same search in $\Theta(M)$ steps, which is a quadratic speedup. The continuous-time quantum walk, however, searches in $\Theta(\sqrt{M})$ time. While this appears to be a quartic speedup over the classical walk, it is actually quadratic; the continuous-time quantum walk effectively takes $M$ walk steps for every oracle query, and a classical walk under the same scheme would take $\Theta(M)$ queries. Allowing the discrete-time quantum walk to also take additional walk steps per oracle query, it matches the continuous-time algorithm's $\Theta(\sqrt{M})$ queries while only needing $\Theta(\sqrt{M})$ walk steps per query. This is a cubic speedup over the corresponding classical random walk, which would take $\Theta(M^{3/2})$ queries under the same scheme, and the first example of a greater-than-quadratic speedup for quantum search over classical random walk.