Bremermann's Limit
   HOME

TheInfoList



OR:

Bremermann's limit, named after
Hans-Joachim Bremermann Hans-Joachim Bremermann (1926 – 1996) was a German-American mathematician and biophysicist. He worked on computer science and evolution, introducing ideas of how mating generates new gene combinations. Bremermann's limit, named after him, is th ...
, is a theoretical limit on the maximum rate of
computation A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computation are mathematical equation solving and the execution of computer algorithms. Mechanical or electronic devices (or, hist ...
that can be achieved in a self-contained system in the material universe. It is derived from
Einstein Albert Einstein (14 March 187918 April 1955) was a German-born theoretical physicist who is best known for developing the theory of relativity. Einstein also made important contributions to quantum mechanics. His mass–energy equivalence f ...
's mass–energy equivalency and the
Heisenberg uncertainty principle The uncertainty principle, also known as Heisenberg's indeterminacy principle, is a fundamental concept in quantum mechanics. It states that there is a limit to the precision with which certain pairs of physical properties, such as position a ...
, and is ''c''2/ ''h'' ≈ 1.3563925 × 1050
bits per second In telecommunications and computing, bit rate (bitrate or as a variable ''R'') is the number of bits that are conveyed or processed per unit of time. The bit rate is expressed in the unit bit per second (symbol: bit/s), often in conjunction ...
per kilogram. This value establishes an asymptotic bound on adversarial resources when designing
cryptographic Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adversarial behavior. More gen ...
algorithms, as it can be used to determine the minimum size of
encryption key A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key ...
s or hash values required to create an algorithm that could never be cracked by a
brute-force search In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of Iteration#Computing, systematically checking all possible candida ...
. For example, a computer with the mass of the entire
Earth Earth is the third planet from the Sun and the only astronomical object known to Planetary habitability, harbor life. This is enabled by Earth being an ocean world, the only one in the Solar System sustaining liquid surface water. Almost all ...
operating at Bremermann's limit could perform approximately 1075 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−36 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 1072 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 \Delta E can evolve into an orthogonal and hence distinguishable state to another, \textstyle \Delta t = \frac . In particular, Margolus and Levitin have shown that a quantum system with average energy ''E'' takes at least time \textstyle \Delta t = \frac to evolve into an orthogonal state. This is one of the quantum speed limit theorems. However, it has been shown that chaining multiple computations or access to
quantum memory In quantum computing, quantum memory is the Quantum mechanics, quantum-mechanical version of ordinary computer memory. Whereas ordinary memory stores information as Binary number, binary states (represented by "1"s and "0"s), quantum memory s ...
in principle allow computational algorithms that require arbitrarily small amount of energy/time per one elementary computation step.


See also

*
Quantum speed limit In quantum mechanics, a quantum speed limit (QSL) is a limitation on the minimum time for a quantum system to evolve between two distinguishable (orthogonal) states. QSL theorems are closely related to time-energy uncertainty relations. In 1945, Le ...
*
Landauer's principle Landauer's principle is a physical principle pertaining to a lower theoretical limit of energy consumption of computation. It holds that an irreversible change in information stored in a computer, such as merging two computational paths, dissipa ...
*
Bekenstein bound In physics, the Bekenstein bound (named after Jacob Bekenstein) is an upper limit on the thermodynamic entropy ''S'', or Shannon entropy ''H'', that can be contained within a given finite region of space which has a finite amount of energy—or co ...
*
Kolmogorov complexity In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that prod ...
*
Transcomputational problem In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information. Any number greater than 1093 is called a transcomputational number. The number 1093, called Bremermann's ...
*
Limits of computation The limits of computation are governed by a number of different factors. In particular, there are several physical and practical limits to the amount of computation or data storage that can be performed with a given amount of mass, volume, or ener ...
*
Ultrafinitism In the philosophy of mathematics, ultrafinitism (also known as ultraintuitionism,International Workshop on Logic and Computational Complexity, ''Logic and Computational Complexity'', Springer, 1995, p. 31. strict formalism,St. Iwan (2000),On the U ...


References

{{reflist


External links

* Gorelik, G. (2010
Bremermann's Limit in cGh-physics // arXiv:0910.3424v4
* Lokshin, A (2017)
Arbitrary choice, ‘understanding’ and Gorelik-Bremermann limit. ''Far East Journal of Mathematical Sciences'', V. 102, Issue 1, P. 215–222
Cybernetics Theory of computation Limits of computation