  We analyze the performance of classical and quantum search algorithms from a
thermodynamic perspective, focusing on resources such as time, energy, and
memory size. We consider two examples that are relevant to post-quantum
cryptography: Grover's search algorithm, and the quantum algorithm for
collision-finding. Using Bennett's "Brownian" model of low-power reversible
computation, we show classical algorithms that have the same asymptotic energy
consumption as these quantum algorithms. Thus, the quantum advantage in query
complexity does not imply a reduction in these thermodynamic resource costs. In
addition, we present realistic estimates of the resource costs of quantum and
classical search, for near-future computing technologies. We find that, if
memory is cheap, classical exhaustive search can be surprisingly competitive
with Grover's algorithm.
