Thermodynamic Analysis of Classical and Quantum Search Algorithms

Published

January 19, 2018

Author(s)

Ray A. Perlner, Yi-Kai Liu

Abstract

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.

Proceedings Title

Quantum Information Processing (QIP 2018)

Conference Dates

January 15-19, 2018

Conference Location

Delft

Pub Type

Conferences

Download Paper

Local Download

Keywords

Quantum algorithms, thermodynamics of computation, reversible computation, quantum cryptanalysis, Grover search, collision finding

Citation

Perlner, R. and Liu, Y. (2018), Thermodynamic Analysis of Classical and Quantum Search Algorithms, Quantum Information Processing (QIP 2018), Delft, -1, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=924493 (Accessed October 10, 2025)