  An ideal quantum walk transitions from one vertex to another with perfect
fidelity, but in physical systems, the particle may be hindered by potential
energy barriers. Then the particle has some amplitude of tunneling through the
barriers, and some amplitude of staying put. We investigate the algorithmic
consequence of such barriers for the quantum walk formulation of Grover's
algorithm. We prove that the failure amplitude must scale as $O(1/\sqrt{N})$
for search to retain its quantum $O(\sqrt{N})$ runtime; otherwise, it searches
in classical $O(N)$ time. Thus searching larger "databases" requires
increasingly reliable hop operations or error correction. This condition holds
for both discrete- and continuous-time quantum walks.
