4
$\begingroup$

There is (or at least was) a thermodynamic reasoning that any form of brute force key search would require an energy at least $k\,T$ per key tested, where $k$ is Boltzman's constant and $T$ the device's absolute temperature in Kelvin. It concludes that at the evaporation temperature of helium, our sun's whole radiated energy is short to challenge 192-bit crypto in decades, or 256-bit crypto ever.

Does such thermodynamic limit apply to (still hypothetical) quantum computers doing key search for a symmetric cryptosystem by Grover's algorithm or the like?

$\endgroup$
3
$\begingroup$

From this Thermodynamic Analysis of Classical and Quantum Search Algorithms, Sep 29, 2017;

For the problem of collision finding, previous work suggested that quantum algorithms were unlikely to provide an asymptotic advantage in terms of circuit size (despite using fewer oracle queries). Our thermodynamic analysis leads to a similar conclusion. We compare in detail the classical collision finding algorithm of Van-Oorschot and Wiener, and the quantum collision finding algorithm of Brassard, Høyer, and Tapp (BHT) including parallelized generalizations of BHT. We find that the energy consumption required to search for collisions on a range of size $N$ using a memory of size $M < \mathcal{O}(N)$ in time $t$ is $\mathcal{O}(N/Mt)$, regardless of the choice of algorithm

For the problem of unstructured search, it was known previously that Grover’s algorithm does achieve a quadratic speedup over classical exhaustive search, both in terms of circuit size, and in terms of oracle queries. Quite surprisingly, we do not find a quantum advantage using our thermodynamic analysis. On the contrary, we find that a Brownian implementation of classical random search can achieve the same asymptotic performance as Grover’s algorithm (up to logarithmic factors), where we measure the performance in terms of running time, memory size and energy consumption.

According to this article Battle between Quantum and Thermodynamic Laws Heats Up, March 30, 2017 in Scientific American, we don't have the same heat and efficiency rules there, yet.

Many physicists hope that rebuilding thermodynamics from the laws of quantum mechanics will help to settle long-debated conundrums. Whether the concepts of heat and efficiency apply to tiny electronic components and even atom-sized machines.


The Quantum Thermodynamics Revolution is also a nice article to read.

$\endgroup$
1
$\begingroup$

The reasoning background is a summary taken from Applied Cryptography book:

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information.

Grover algorithm comes from manipulating/processing a superposition state to grow "the right" coefficients in that superposition. Thermodynamics is probably a too coarse model for superposition, I guess. It still fits most "natural" everyday phenomena well. If you really need classical description here, I would apply it for representing the result of that search, after measurement.

In thermodynamics, "heat" is about asymptotic behavior while Grover algorithm is about concrete finite as-small-as-possible system. "Heat" is about equilibrium while quantum computing is very much about error correction. Probably best known fallacy is superconductors with quantum-only models.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.