



01290nas a2200121   4500008004100000245007000041210006900111260001500180520090300195100001701098700001601115856003701131       2017                        eng d00aThermodynamic Analysis of Classical and Quantum Search Algorithms0 aThermodynamic Analysis of Classical and Quantum Search Algorithm  c2017/09/293 a<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>1 aPerlner, Ray1 aLiu, Yi-Kai  uhttps://arxiv.org/abs/1709.10510