Ultimate physical limits to computation

In the paper

“This is not the case: if one spreads the energy E amongst N logic gates, each one operates at a rate 2 E/π ¯ hN . The total number of operations per second, N 2 E/π ¯ hN = 2 E/π ¯ h , remains the same.”

In the paper

“First, most of the energy is locked up in the mass of the particles of which the computer is constructed, leaving only an infinitesimal fraction for performing logic.”

In the paper

“If the energy is allocated to fewer logic gates (more serial operation), the rate 1 / ∆ t ℓ at which they operate and the spread in energy per gate ∆ E ℓ go up. If the energy is allocated to more logic gates (more parallel operation) then the rate at which they operate and the spread in energy per gate go down.”

In the paper

“In this case, r = 2, and for a one kilogram computer confined to a volume of a liter we have k B T = 8 . 10 × 10 -15 joules, or T = 5 . 87 × 10 8 K.”

In the paper

“A kilogram of ordinary matter holds on the order of 10 25 nuclei.”

In the paper

“For O (10 1 -10 2 ) such species, C is on the order of 10 -3 -10 -2 , leading to a lifetime for a 1 kilogram black hole of ≈ 10 -19 seconds, during which time the hole can perform ≈ 10 32 operations on its ≈ 10 16 bits.”

In the paper

“If, in addition, one uses the natural electromagnetic interactions between nuclei and electrons in the matter to perform logical operations, one is limited to a rate of approximately 10 15 operations per bit per second, yielding an overall information processing rate of ≈ 10 40 operations per second in ordinary matter.”

In the paper

“The entropy is S = 2 . 04 × 10 8 joule/K, which corresponds to an amount of available memory space I = S/k B ln 2 = 2 . 13 × 10 31 bits.”

In the paper

“All current designs for quantum computers operate at low energy levels and temperatures, exactly so that precise control can be exerted on their parts.”

In the paper

“The time it takes a bit to flip from a state | ↑〉 to an orthogonal state | ↓〉 is given by π ¯ h/ 2 µB = π ¯ h/ 2 E , where µ is the spin's magnetic moment, B is the magnetic field, and E = µB is the average energy of interaction between the spin and the magnetic field.”

In the paper

“Even if it achieves such an error rate, it must have an energy throughput (free energy in and thermal energy out) of 4 . 04 × 10 26 watts turning over its own rest mass energy of mc 2 ≈ 10 17 joules in a nanosecond!”

In the paper

“For the ultimate laptop, with 2 R = 10 -1 meters, 2 E/π ¯ h ≈ 10 51 operations per second, and S/k B ln 2 ≈ 10 31 bits, t com /tfl ip ≈ 10 10 .”

In the paper

“A computer compressed to the size of a black hole can perform 5 . 4258 × 10 50 operations per second, the same as the 1 liter computer.”

In the paper

“Accordingly, the maximum error rate that the ultimate computer can tolerate is ǫ ≤ π ln 2¯ hcS/ 2 ER = 2 tfl ip /t com . That is, the maximum error rate that can be tolerated by the ultimate computer is the inverse of its degree of parallelization.”

In the paper

“The amount of information that can be stored by the ultimate laptop, ≈ 10 31 bits, is much higher than the ≈ 10 10 bits stored on current laptops.”

In the paper

“At the Planck scale, gravitational effects and quantum effects are both important: the Compton wavelength of a particle of mass m , λ C = 2 π ¯ h/mc is on the order of its Schwarzschild radius, 2 Gm/c 2 .”

In the paper

“The amount of time it takes to send a message from one side of a computer of radius R to the other is t com = 2 R/c .”

In the paper

“The maximum entropy can be estimated to be approximately to be 4 per relativistic pion (to within a factor of less than 2 associated with the overall production rate per mesons) of which there are approximately 10 4 per central collision in which only a few tens of nucleons are spectators. Accordingly, the total amount of memory space available is S/k B ln 2 ≈ 10 4 -10 5 bits.”

In the paper

“The ultimate laptop performs 2 mc 2 /π ¯ h = 5 . 4258 × 10 50 logical operations per second on ≈ 10 31 bits.”

In the paper

“In the ultimate laptop, each bit can flip ≈ 10 19 times per second, while the time to communicate from one side of the one liter computer to the other is on the order of 10 9 seconds: the ultimate laptop is highly parallel.”

In the paper

“Before presenting methods for calculating these limits, it is important to note that there is no guarantee that these limits will ever be attained, no matter how ingenious computer designers become.”

In the paper

“Computers are physical systems: what they can and cannot do is dictated by the laws of physics 1 -86 .”

What the sources say

• Not checked yetcites 1 -86

In the paper

“A collection of m two-state systems has 2 m accessible states and can register m bits of information.”

In the paper

“The difference between the entropy as calculated using the canonical ensemble and that calculated using the microcanonical ensemble is minimal.”

In the paper

“Redundancy is required for error correction, however, as will be discussed below.”

In the paper

“The precise, correct statement of the role of entropy in computation was due to Landauer 5 , who showed that reversible, i.e. one-to-one, logical operations such as NOT can be performed without dissipation in principle, but that irreversible, many-to-one operations such as AND or ERASE require dissipation at least k B ln 2 for each bit of information lost.”

What the sources say

• Not checked yetcites [5] Landauer, R. Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 183–191 (1961). source

In the paper

“If the information goes into observable degrees of freedom of the computer, such as another bit, then it has not been erased but merely moved; but if it goes into unobservable degrees of freedom such as the microscopic motion of molecules it results in an increase of entropy of at least k B ln 2.”

In the paper

“Electronic circuits based on reversible logic have been built and exhibit considerable reductions in dissipation over conventional reversible circuits 33 -35 .”

What the sources say

• Not checked yetcites [33] Seitz, C. L. et al. in Proceedings of the 1985 Chapel Hill Conference on VLSI (ed. Fuchs, H.) (Computer Science Press, Rockville, MD, 1985).
• Not checked yetcites [34] Merkle, R. C. Reversible electronic logic using switches. Nanotechnology 34, 21–40 (1993). source
• Not checked yetcites [35] Younis, S. G. & Knight, T. F. in Proceedings of the 1993 Symposium on Integrated Systems, Seattle, Washington (eds Berrielo, G. & Ebeling, C.) (MIT Press, Cambridge, MA, 1993).

In the paper

“Computers in which energy is relatively evenly distributed over a larger volume are better suited for performing parallel computations. More compact computers and computers with an uneven”

In the paper

“Existing quantum logic gates in optical-atomic and NMR quantum computers actually attain this limit.”

In the paper

“Parallelization can help perform certain computations more efficiently, but it does not alter the total number of operations per second.”

In the paper

“The entropy governs the amount of information the system can register and the temperature governs the number of operations per bit per second it can perform.”

In the paper

“That is, a computer can perform no more than”

In the paper

“The laws of physics do not require redundancy to perform logical operations: recently constructed quantum microcomputers use one quantum degree of freedom for each bit and operate at the Heisenberg limit ∆ t = π ¯ h/ 2∆ E for the time needed to flip a bit 64 -65 , 76 -80 .”

What the sources say

• Not checked yetcites [64] Turchette, Q. A., Hood, C. J., Lange, W., Mabuchi, H. & Kimble, H. J. Measurement of conditional phase-shifts for quantum logic. Phys. Rev. Lett. 75, 4710– 4713 (1995). source
• Not checked yetcites [65] Monroe, C., Meekhof, D. M., King, B. E., Itano, W. M. & Wineland, D. J. Demonstration of a fundamental quantum logic gate. Phys. Rev. Lett. 75, 4714–4717 (1995). source
• Not checked yetcites [76] Cory, D. G., Fahmy, A. F. & Havel, T. F. in Proceedings of the Fourth Workshop on Physics and Computation—PhysComp96 (eds Toffoli, T., Biafore, M. & Leão, J.) 87–91 (New England Complex Systems Institute, Boston, MA, 1996).
• Not checked yetcites [77] Gershenfeld, N. A. & Chuang, I. L. Bulk spin-resonance quantum computation. Science 275, 350– 356 (1997). source
• Not checked yetcites [78] Chuang, I. L., Vandersypen, L. M. K., Zhou, X., Leung, D. W. & Lloyd, S. Experimental realization of a quantum algorithm. Nature 393, 143– 146 (1998). source
• Not checked yetcites [79] Jones, J. A., Mosca, M. & Hansen, R. H. Implementation of a quantum search algorithm on a quantum computer. Nature 393, 344– 346 (1998). source
• Not checked yetcites [80] Chuang, I. L., Gershenfeld, N. & Kubinec, M. Experimental implementation of fast quantum searching . Phys. Rev. Lett. 80, 3408– 3411 (1998). source

In the paper

“Information is stored on nuclear spins, with one spin registering one bit.”

In the paper

“In addition, the well-known statement that 'a black hole has no hair'-i.e., from a distance all black holes with the same charge and angular momentum look essentially alike - is now known to be not always true 91 -93 .”

What the sources say

• Not checked yetcites [91] Fiola, T. M., Preskill, J. & Strominger A. Black-hole thermodynamics and information loss in 2 dimensions. Phys. Rev. D 50, 3987– 4014 (1994). source
• Not checked yetcites [92] Susskind, L. & Uglum, J. Black-hole entropy in canonical quantum-gravity and superstring theory. Phys. Rev. D 50, 2700–2711 (1994). source
• Not checked yetcites [93] Strominger A. & Vafa, C. Microscopic origin of the Bekenstein-Hawking entropy. Phys. Lett. B 37, 99– 104 (1996). source

In the paper

“As the energy density in the computer goes up, different regimes in high energy physics are necessarily explored in the course of the computation. First the weak unification scale is reached, then the grand unification scale. Finally, as the linear size of the computer approaches its Schwarzchild radius, the Planck scale is reached.”

In the paper

“Although NMR quantum computers already operate at the limits to computation set by physics, they are nonetheless much slower and process much less information than the ultimate laptop described above.”

In the paper

“This is because conventional laptops use many degrees of freedom to store a bit where the ultimate laptop uses just one.”

In the paper

“This is because their energy is largely locked up in mass, thereby limiting both their speed and their memory.”

In the paper

“As the number of operations per second 2 E/π ¯ h is independent of the number of bits available, the number of operations per bit per second can be increased by using a smaller number of bits.”

In the paper

“As ordinary matter obeys the Beckenstein bound 20 -22 , k B RE/ ¯ hcS > 1 / 2 π , however, as one compresses the computer t com /tfl ip ≈ k B RE/ ¯ hcS will remain greater than one: i.e., the operation will still be somewhat parallel.”

What the sources say

• Not checked yetcites [20] Bekenstein, J. D. Universal upper bound on the entropy-to-energy ration for bounded systems . Phys. Rev. D 23, 287– 298 (1981). source
• Not checked yetcites [21] Bekenstein, J. D. Energy cost of information transfer. Phys. Rev. Lett. 46, 623–626 (1981). source
• Not checked yetcites [22] Bekenstein, J. D. Entropy content and information flow in systems with limited energy. Phys. Rev. D 30, 1669–1679 (1984). source

In the paper

“The computation can be speeded up and made more serial by compressing the computer.”

In the paper

“If, as seems highly unlikely, it is possible to extrapolate the exponential progress of Moore's law into the future, then it will only take two hundred and fifty years to make up the forty orders of magnitude in performance between current computers that perform 10 10 operations per second on 10 10 bits and our one kilogram ultimate laptop that performs 10 51 operations per second on 10 31 bits.”

In the paper

“The heavy ion system could be programmed by manipulating and preparing the initial momenta and internal nuclear states of the ions.”

In the paper

“(The fact that only one operation per bit is performed suggests that there is insufficient time to reach thermal equilibrium, an observation that is confirmed by detailed simulations.)”

In the paper

“In addition to the theoretical evidence that most systems are computationally universal, the computer on which I am writing this article provides strong experimental evidence that whatever the correct underlying theory of physics is, it supports universal computation.”