



@article {2100,
	title = {Thermodynamic Analysis of Classical and Quantum Search Algorithms},
	year = {2017},
	month = {2017/09/29},
	abstract = {<p>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\&rsquo;s search algorithm, and the quantum algorithm for collisionfinding. Using Bennett\&rsquo;s \&ldquo;Brownian\&rdquo; 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\&rsquo;s algorithm.</p>},
	url = {https://arxiv.org/abs/1709.10510},
	author = {Ray Perlner and Yi-Kai Liu}
}
