Bremermann's limit

{{short description|Highest possible rate of computation in this universe}}

Bremermann's limit, named after Hans-Joachim Bremermann, is a theoretical limit on the maximum rate of computation that can be achieved in a self-contained system in the material universe. It is derived from Einstein's mass–energy equivalency and the Heisenberg uncertainty principle, and is c²/h ≈ 1.3563925 × 10⁵⁰ bits per second per kilogram.Bremermann, H.J. (1962) [http://holtz.org/Library/Natural%20Science/Physics/Optimization%20Through%20Evolution%20and%20Recombination%20-%20Bremermann%201962.htm Optimization through evolution and recombination] In: Self-Organizing systems 1962, edited M.C. Yovits et al., Spartan Books, Washington, D.C. pp. 93–106.Bremermann, H.J. (1965) [http://projecteuclid.org/euclid.bsmsp/1200513783 Quantum noise and information]. 5th Berkeley Symposium on Mathematical Statistics and Probability; Univ. of California Press, Berkeley, California.

This value establishes an asymptotic bound on adversarial resources when designing cryptographic algorithms, as it can be used to determine the minimum size of encryption keys or hash values required to create an algorithm that could never be cracked by a brute-force search. For example, a computer with the mass of the entire Earth operating at Bremermann's limit could perform approximately 10⁷⁵ mathematical computations per second. If one assumes that a cryptographic key can be tested with only one operation, then a typical 128-bit key could be cracked in under 10⁻³⁶ seconds. However, a 256-bit key (which is already in use in some systems) would take about two minutes to crack. Using a 512-bit key would increase the cracking time to approaching 10⁷² years, without increasing the time for encryption by more than a constant factor (depending on the encryption algorithms used).

The limit has been further analysed in later literature as the maximum rate at which a system with energy spread $\backslash Delta\; E$ can evolve into an orthogonal and hence distinguishable state to another, $\backslash textstyle\; \backslash Delta\; t\; =\; \backslash frac\{\; \backslash pi\; \backslash hbar\}\; \{2\; \backslash Delta\; E\}.${{Cite journal| last1 = Aharonov

| first1 = Y.| last2 = Bohm| first2 = D.| doi = 10.1103/PhysRev.122.1649| title = Time in the Quantum Theory and the Uncertainty Relation for Time and Energy| journal = Physical Review| volume = 122| issue = 5| pages = 1649–1658| year = 1961| url = http://dieumsnh.qfb.umich.mx/archivoshistoricosmq/ModernaHist/Aharonov%20a.pdf| bibcode = 1961PhRv..122.1649A| access-date = 2013-05-23| archive-url = https://web.archive.org/web/20160304055851/http://dieumsnh.qfb.umich.mx/archivoshistoricosmq/ModernaHist/Aharonov%20a.pdf

| archive-date = 2016-03-04| url-status = dead}}{{Cite journal| last1 = Lloyd | first1 = Seth| title = Ultimate physical limits to computation| journal = Nature| volume = 406| issue = 6799| pages = 1047–1054| year = 2000| doi = 10.1038/35023282| pmid = 10984064| arxiv = quant-ph/9908043|bibcode = 2000Natur.406.1047L | s2cid = 75923}}

In particular, Margolus and Levitin have shown that a quantum system with average energy E takes at least time $\backslash textstyle\; \backslash Delta\; t\; =\; \backslash frac\{\; \backslash pi\; \backslash hbar\}\; \{2\; E\}$ to evolve into an orthogonal state.{{Cite journal| last1 = Margolus | first1 = N.| last2 = Levitin | first2 = L. B.| doi = 10.1016/S0167-2789(98)00054-2| title = The maximum speed of dynamical evolution| journal = Physica D: Nonlinear Phenomena| volume = 120| issue = 1–2| pages = 188–195|date=September 1998| arxiv = quant-ph/9710043|bibcode = 1998PhyD..120..188M | s2cid = 468290}} This is one of the quantum speed limit theorems.

However, it has been shown that chaining multiple computations or access to quantum memory in principle allow computational algorithms that require arbitrarily small amount of energy/time per one elementary computation step.{{cite journal|last=Jordan|first=Stephen P.|title=Fast quantum computation at arbitrarily low energy|journal = Phys. Rev. A | volume = 95 |issue=3| pages=032305 | year=2017 |arxiv = 1701.01175|bibcode = 2017PhRvA..95c2305J |doi = 10.1103/PhysRevA.95.032305 |s2cid=118953874}}{{cite journal|last=Sinitsyn|first=Nikolai A.|title=Is there a quantum limit on speed of computation?|journal=Physics Letters A|volume=382|issue=7|pages=477–481|year=2018|arxiv = 1701.05550|bibcode = 2018PhLA..382..477S |doi=10.1016/j.physleta.2017.12.042|s2cid=55887738}}