  We show how to search N items arranged on a $\sqrt{N}\times\sqrt{N}$ grid in
time $O(\sqrt N \log N)$, using a discrete time quantum walk. This result for
the first time exhibits a significant difference between discrete time and
continuous time walks without coin degrees of freedom, since it has been shown
recently that such a continuous time walk needs time $\Omega(N)$ to perform the
same task. Our result furthermore improves on a previous bound for quantum
local search by Aaronson and Ambainis. We generalize our result to 3 and more
dimensions where the walk yields the optimal performance of $O(\sqrt{N})$ and
give several extensions of quantum walk search algorithms for general graphs.
The coin-flip operation needs to be chosen judiciously: we show that another
``natural'' choice of coin gives a walk that takes $\Omega(N)$ steps. We also
show that in 2 dimensions it is sufficient to have a two-dimensional coin-space
to achieve the time $O(\sqrt{N} \log N)$.
