Thermodynamic Limits of Quantum Search

R. Riedinger · 2026

Read Thermodynamic Limits of Quantum Search by R. Riedinger (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-13654.txt.

Introduction

Ralf Riedinger sets out the thermodynamic limits of quantum search and their meaning for cryptography. Symmetric ciphers are thought safe from quantum attacks if the key is long, but hard bounds on key length were missing. He finds a work-runtime trade-off for autonomous computers, with a fundamental lower bound. A tailored quantum protocol beats circuit and adiabatic approaches and saturates that bound, so the bound is tight. By that limit, an 831-bit key cannot be rebuilt in an expanding universe before star formation should cease.

Catalog record

CREATORR. Riedinger
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57048
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2603.13654

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Thermodynamic Limits of Quantum Search R. Riedinger Abstract Modern cryptography relies on keyed symmetric ciphers to ensure the secrecy and authenticity of high bandwidth data transfer. While the advent of quantum computers poses a challenge for public key cryptography, unbroken ciphers are considered safe against quantum attacks if their key is sufficiently long. However, concrete bounds on the required key length thus far remain elusive: Despite the well known asymptotic complexity of Grover’s quantum search, the optimal algorithm to recover a secret key, no implementation-agnostic tight bounds were established. Here, we discuss the quantum thermodynamic limits of generic search algorithms, and find a work-runtime trade-off for autonomous computers with a fundamental lower bound. By devising an application-specific quantum protocol, which outperforms circuit and adiabatic implementations, and saturates this bound, we demonstrate that it is tight. Applying this limit, we find that a secret key of 831 bit length cannot be reconstructed deterministically in an expanding, dark-energy-dominated universe until star formation is expected to cease. Implications for post quantum cryptography, and quantum key distribution are discussed. I Introduction Conventional computers use irreversible operations, like the NAND gate, which has two input bits, but only one output. The information lost in the process increases the entropy of the system, respectively, generates heat. Landauer realized that this poses a fundamental limit of irreversible computation, which can be expressed as the work required to keep the system at a constant temperature 20 . While current systems are far from reaching the Landauer limit, it still serves as a hard bound for the capacity of (irreversible) computers, for example for exhaustive search of cryptographic keys. This allows for defining concrete security levels for unbroken symmetric ciphers, assuming only the work available to an adversary, and the irreversibility of conventional logic gates. Quantum computation, in contrast, is natively a unitary operation and thus reversible. While error correction can add an irreversible component, there is no fundamental lower limit to it, and consequently, and thus far, no strict energy bounds have been established. It has even been argued, that energy considerations by themselves are insufficient to establish computational bounds 19 . Here, we demonstrate that a fundamental thermodynamic energy bound exists for reversible quantum search, too. The bound represents a new type of quantum speed limit and is independent of the specific implementation of Grover’s algorithm 15 ; 16 , merely assuming a suitable oracle is available. It can be adapted to other algorithms, which is, however, left for future work. We apply our quantum search bound to establish how long a cryptographic key need to be, for it to be considered quantum resistant. Notably, we find that doubling the key length in insufficient, to provide a comparable level of security in the post quantum age. This common believe 7 ; 17 ; 18 is based on the fact that Grover’s algorithm, which is asymptotically optimal 32 , can find an n -bit key with \mathcal{O}(2^{n/2}) gates, in contrast to the \mathcal{O}(2^{n}) operations required for classical exhaustive search. Implicitly, this assumes future quantum computers can achieve gate depths similar to current conventional computers. As unitary gates do not consume work, any assumption on gate depth is technological in nature, and thus subject to speculation. For example, it can and has been argued, that quantum algorithms are hard to parallelize and hence shorter keys may be sufficient 27 ; 13 . Estimates of key size requirements are often based on the specific implementations of computer architectures and algorithms 5 ; 14 ; 4 ; 21 ; 17 ; 2 . It is, however, notoriously hard to predict the trajectory of a new technology, where efficient application-specific implementations can tremendously change underlying assumptions of what is realistic 3 ; 24 ; 21 . The fundamental thermodynamic limit established here allows for determining concrete recommendations for quantum resistant key lengths independent of techonological implementation: The security level is determined by the work and time an classical or quantum adversary is able to invest into key recovery, as well as an acceptable success probability under these conditions. Based on these assumptions, we find that classically secure key lengths need to be approximately tripled to provide the same thermodynamically limited security against a quantum attacker. Further, we estimate the number of bits, beyond which extending a key provides diminishing added security from a thermodynamic point of view, by accounting for all energy inside the cosmic event horizon. This maximum useful key length, estimated to be n_{\text{max}}\sim 829 bits, provides an important reference for any application attempting to provide strong privacy, such as post quantum cryptography or quantum key distribution (QKD). First, we review existing thermodynamic limits for classical and quantum algorithms for exhaustive search, and then derive an system-agnostic bound for it. Using an example implementation, we demonstrate that the bound is tight. Finally, recommendations for quantum resistant key-lengths with security comparable to conventional cryptography standards are discussed. II Limits of classical search For a classical, irreversible machine, two fundamental limits of computation are relevant: (1) Landauer’s principle 20 states that whenever a bit is reset, the entropy of a reservoir with temperature T increases, requiring an energy of E_{L}\geq k_{B}T\ln 2 . (2) The Margolus-Levitin theorem 23 ; 26 ; 30 states that a system when changing between orthogonal states within time \delta t , needs an average energy of E_{ML}\geq h/4\delta t . Other quantum speed limits 9 , like the Mandelstam-Tamm bound 22 , can further bound the machine, but do not impose stricter energy limits (see A ). When imposing size limits, Bremmerman-Bekenstein bounds can impose further entropy-based restrictions, which we neglect here 11 . Hence, the minimum energy such a machine requires to recover a n -bit key from an n -bit cipher text with probability P_{s} in time t is E_{c}\geq 2^{n}P_{s}\left(k_{B}T\ln{2}+\frac{h}{4t}\right)+2nk_{B}T\ln 2, (1) when running at constant speed ( 1/\delta t=t/2^{n}P_{s} ), see A for details. For example, an irreversible classical machine, aiming to reconstruct a 256-bit key with a probability P_{s}\geq 10^{-10} would require the entire radiative energy the sun emits during the remainder of its lifetime ( t\sim 5 Ga), using the cosmic microwave background ( T_{\textrm{CMB}}=2.7 K) as cold bath 12 , see also table 1 . An adversary with access to a quantum computer can employ Grover’s algorithm 15 , which yields a result after \mathcal{O}(\sqrt{2^{n}}) iterations. More importantly, however, they may hardly be restricted by above limits: As quantum search is a unitary evolution, merely qubit initialization and readout are necessarily irreversible, and thus subject to the Landauer, or Bremmerman-Bekenstein bounds 11 . Furthermore, the system transfers to a (near-)orthogonal state only once during an adiabatic computation (initial state to solution state), such that quantum speed limits do not provide a strict bound either. In summary, the energy bounds for Grover’s search based on the Landauer- and Margolus-Levitin-limit E_{\textrm{q,LML}}\geq 2\left(nk_{B}T\ln{2}+\frac{h}{4t}\right) are exponentially lower than for classical search. The adiabatic quantum search 29 , suggests an energy bound E_{A}\geq\mathcal{O}(2^{n/2}/t) to ensure an upper bound to the computational error, albeit resonances with substantially lower error probability can be found numerically 28 . Hence, this cannot be used directly to establish a lower energy bound, either. III Limit of dynamic evolution in autonomous

Read the complete text