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 May 10, 2024)
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)
,
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
Keywords
Quantum algorithms, thermodynamics of computation, reversible computation, quantum cryptanalysis, Grover search, collision finding
Citation
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