  It is well-known that quantum algorithms such as Grover's can provide a
quadradic speed-up for unstructured search problems. By adding topological
structure to a search problem, we show that it is possible to achieve a
constant search-time quantum algorithm with a constant improvement of the
search probability over classical search. Specifically, we study the spatial
search algorithm implemented by a two-dimensional split-step quantum random
walks that realize topologically nontrivial phases and show the asymptotic
search behavior is constant with growing system size. Using analytical and
numerical calculations, we determine the efficient search regions in the
parameter space of the quantum walker. These regions correspond to pairs of
trapped states formed near a lattice defect. By studying the spectral
properties of the discrete time-evolution-operators, we show that these trapped
states have large overlap with the initial state. This correspondence, which is
analogous to localization by constructive interference of bound states, makes
it possible to reach the best possible search-time asymptotic and produce a
disorder-protected fast search in quantum random walks.
