Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Thermodynamic Analysis of Classical and Quantum Search Algorithms

Published

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

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 July 22, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created January 19, 2018, Updated January 26, 2018