  Search is one of the most commonly used primitives in quantum algorithm
design. It is known that quadratic speedups provided by Grover's algorithm are
optimal, and no faster quantum algorithms for Search exist. While it is known
that at least some quantum computation is required to achieve these speedups,
the existing bounds do not rule out the possibility of an equally fast hybrid
quantum-classical algorithm where most of the computation is classical. In this
work, we study such hybrid algorithms and we show that classical computation,
unless it by itself can solve the Search problem, cannot assist quantum
computation. In addition, we generalize this result to algorithms with
subconstant success probabilities.
