  Continuous-time quantum walks can be used to solve the spatial search
problem, which is an essential component for many quantum algorithms that run
quadratically faster than their classical counterpart, in $\mathcal O(\sqrt n)$
time for $n$ entries. However the capability of models found in nature is
largely unexplored - e.g., in one dimension only nearest-neighbour Hamiltonians
have been considered so far, for which the quadratic speedup does not exist.
Here, we prove that optimal spatial search, namely with $\mathcal O(\sqrt n)$
run time and large fidelity, is possible in one-dimensional spin chains with
long-range interactions that decay as $1/r^\alpha$ with distance $r$. In
particular, near unit fidelity is achieved for $\alpha\approx 1$ and, in the
limit $n\to\infty$, we find a continuous transition from a region where optimal
spatial search does exist ($\alpha<1.5$) to where it does not ($\alpha>1.5$).
Numerically, we show that spatial search is robust to dephasing noise and that,
for realistic conditions, $\alpha \lesssim 1.2$ should be sufficient to
demonstrate optimal spatial search experimentally with near unit fidelity.
