  One of the most important algorithmic applications of quantum walks is to
solve spatial search problems. A widely used quantum algorithm for this
problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)],
finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk.
This algorithm is said to be optimal if it can find any of the nodes in
$O(\sqrt{n})$ time. However, given a graph, no general conditions for the
optimality of the algorithm are known and previous works demonstrating optimal
quantum search for certain graphs required an instance-specific analysis. In
fact, the demonstration of necessary and sufficient conditions a graph must
fulfill for quantum search to be optimal has been a long-standing open problem.
  In this work, we make significant progress towards solving this problem. We
derive general expressions, depending on the spectral properties of the
Hamiltonian driving the walk, that predict the performance of this quantum
search algorithm provided certain spectral conditions are fulfilled. Our
predictions are valid, for example, for (normalized) Hamiltonians whose
spectral gap is considerably larger than $n^{-1/2}$. This allows us to derive
necessary and sufficient conditions for optimal quantum search in this regime,
as well as provide new examples of graphs where quantum search is sub-optimal.
In addition, by extending this analysis, we are also able to show the
optimality of quantum search for certain graphs with very small spectral gaps,
such as graphs that can be efficiently partitioned into clusters. Our results
imply that, to the best of our knowledge, all prior results analytically
demonstrating the optimality of this algorithm for specific graphs can be
recovered from our general results.
