Ultimate physical limits to computation

When the ultimate laptop is using all its memory, the number of operations per bit per second it can perform is kB 2 ln 2 E/π hbar S ∝ kB T/hbar.

“Combining this formula with the formula 2 E/π ¯ h for the number of logical operations that can be performed per second, we see that when it is using all its memory, the number of operations per bit per second that our ultimate laptop can perform is k B 2 ln 2 E/π ¯ hS ∝ k B T/ ¯ h , where T = ( ∂S/∂E ) -1 is the temperature of a kilogram of matter in a maximum entropy in a liter volume.”

The ultimate laptop can perform a maximum of 5.4258 × 10^50 operations per second.

“Accordingly, the ultimate laptop can perform a maximimum of 5 . 4258 × 10 50 operations per second.”

• Also stated in: § 1.3 Ultimate limits to speed of computation · p. 5 · plain

  “Applying this result to a one kilogram computer with energy E = mc 2 = 8 . 9874 × 10 16 joules show that our ultimate laptop can perform a maximum of 5 . 4258 × 10 50 operations per second.”

In the parallel case, the overall spread in energy of the computer as a whole is considerably smaller than the average energy: ΔE ≈ √N ΔE_l while E ≈ N E_l.

“Note that in this parallel case, the overall spread in energy of the computer as a whole is considerably smaller than the average energy: in general ∆ E = √∑ ℓ ∆ E 2 ℓ ≈ √ N ∆ E ℓ while E = ∑ E ℓ ≈ NE ℓ .”

Integrating the relationship T = (∂S/∂E)^-1 over E yields T = CE/S, where C is a constant of order unity.

“Integrating the relationship T = ( ∂S/∂E ) -1 over E yields T = CE/S , where C is a constant of order unity (e.g., C = 4 / 3 for black-body radiation, C = 3 / 2 for an ideal gas, and C = 1 / 2 for a black hole).”

A one kilogram computer has average energy E = mc^2 = 8.9874 × 10^16 joules.

“A one kilogram computer has average energy E = mc 2 = 8 . 9874 × 10 16 joules.”

Applying the potential effects a NOT operation in a time that attains the limit given by quantum mechanics.

“That is, applying the potential effects a NOT operation in a time that attains the limit given by quantum mechanics.”

Conventional laptops operate much more slowly than the ultimate laptop.

“Conventional laptops operate much more slowly than the ultimate laptop.”

A conventional computer employs many degrees of freedom (billions and billions of electrons) for registering a single bit.

“Second, a conventional computer employs many degrees of freedom (billions and billions of electrons) for registering a single bit.”

In a computer compressed to its Schwarzschild radius, the energy per bit is E/I = mc^2/I = ln2 ħc^3 / 4πmG = ln2 k_B T/2, where T is the Hawking radiation temperature.

“In a computer that has been compressed to its Schwarzschild radius, the energy per bit is E/I = mc 2 /I = ln2¯ hc 3 / 4 πmG = ln2 k B T/ 2, where T = ( ∂S/∂E ) -1 = ¯ hc/ 4 πk B R S is the temperature of the Hawking radiation emitted by the hole.”

At an input/output rate of 10^12 bits per second, an Avogadro-scale computer with 10^23 bits would take about 10,000 years to perform a serial read/write operation on the entire memory.

“At an input/output rate of 10 12 bits per second, an Avogadro-scale computer with 10 23 bits would take about 10 , 000 years to perform a serial read/write operation on the entire memory.”

When the ultimate laptop is using all its memory space it can perform 2 ln 2 k_B E/π hbar S = 3 ln 2 k_B T/2π hbar ≈ 10^19 operations per bit per second.

“When the ultimate laptop is using all its memory space it can perform 2 ln 2 k B E/π ¯ hS = 3ln2 k B T/ 2 π ¯ h ≈ 10 19 operations per bit per second.”

• AssumptionThe authors state this as an assumption: All available bits are used.

The Schwarzschild radius of a 1 kilogram computer is R_S = 2Gm/c^2 = 1.485×10^-27 meters.

“The Schwarzschild radius of a 1 kilogram computer is R S = 2 Gm/c 2 = 1 . 485 × 10 -27 meters.”

The Stefan-Boltzmann law for black-body radiation implies that the number of bits per unit area that can be sent out to the environment is B = π^2 k_B^3 T^3 / 60 ln 2 hbar^3 c^2 = 7.195 × 10^42 bits per meter^2 per second.

“The StefanBoltzmann law for black-body radiation then implies that the number of bits per unit area than can be sent out to the environment is B = π 2 k 3 B T 3 / 60 ln 2¯ h 3 c 2 = 7 . 195 × 10 42 bits per meter 2 per second.”

The maximum information processing rate in ordinary matter, approximately 10^40 operations per second, is less than the approximately 10^51 operations per second in the ultimate laptop.

“Although less than the ≈ 10 51 operations per second in the ultimate laptop, the maximum information processing rate in 'ordinary matter' is still quite respectable.”

The maximum rate at which information can be rejected to the environment is, up to a geometric factor, ln2 cS/R.

“The maximum rate at which information can be rejected to the environment is, up to a geometric factor, ln 2 cS/R (all bits in the computer moving outward at the speed of light).”

The amount of information that can be stored by the 1 kilogram computer in the black-hole limit is 3.827×10^16 bits.

“The amount of information that can be stored by the 1 kilogram computer in the black-hole limit is 3 . 827 × 10 16 bits.”

According to a distant observer, the time to flip a bit is on the same order as the time to communicate from one side of the hole to the other by going around the horizon: t_com/t_flip = ln2/π.

“In other words, according to a distant observer, the amount of time it takes to flip a bit, tfl ip , is on the same order as the amount of time t com = πR S /c it takes to communicate from one side of the hole to the other by going around the horizon: t com /tfl ip = ln 2 /π .”

Using Page's results on the rate of evaporation of a black hole, the lifetime for a 1 kilogram black hole is t_life = G^2 m^3 / 3 C ħc^4, where C depends on the number of species of particles with mass less than k_B T.

“Using Page's results on the rate of evaporation of a black hole 88 , we obtain a lifetime for the hole t life = G 2 m 3 / 3 C ¯ hc 4 , where C is a constant that is depends on the number of species of particles with a mass less than k B T , where T is the temperature of the hole.”

• cites [88] Pagels, H. The Cosmic Code: Quantum Physics as the Language of Nature (Simon and Schuster, New York, 1982).Not checked yet

  Not checked in the free run.

The average time to flip a bit in a black-hole computer is t_flip = π ħ I / 2E = π^2 R_S / c ln2.

“As a result, the time it takes to flip a bit on average is tfl ip = π ¯ hI/ 2 E = π 2 R S /c ln 2.”

The average time it takes a bit to flip in the ultimate laptop is t_flip = π ħ S / (k_B 2 ln 2 E).

“The average time it takes a bit to flip in the ultimate laptop is the inverse of the number of operations per bit per second calculated above: tfl ip = π ¯ hS/k B 2 ln 2 E .”

As the computer gets smaller while keeping energy fixed, the energy density inside the computer goes up.

“As the computer gets smaller, keeping the energy fixed, the energy density inside the computer goes up.”

S depends only insensitively on the total number of species with mass less than k_B T/2 c^2.

“Note that S depends only insensitively on the total number of species with mass less than k B T/ 2 c 2 .”

• AssumptionThe authors state this as an assumption: The volume occupied by the computer can be modeled as a collection of modes of elementary particles with total average energy E.
• AssumptionThe authors state this as an assumption: The only conserved quantities other than the computer's energy are angular momentum and electric charge, which are taken to be zero.

To perform a quantum logic operation between two spins takes a time πħ/2E_γ, where E_γ is the energy of interaction between the two spins.

“To perform a quantum logic operation between two spins takes a time π ¯ h/ 2 E γ , where E γ is the energy of interaction between the two spins.”

If one collides 100 on 100 nucleons at 200 GeV per nucleon, the operation time is πħ/2E ≈ 10^-29 seconds.

“If one collides 100 on 100 nucleons at 200 GeV per nucleon, the operation time is π ¯ h/ 2 E ≈ 10 -29 seconds.”

Each species contributes (2π)^5 r_l / 90 ln 2 ≈ 10^2 bits of memory space per cubic thermal wavelength λ_T^3 where λ_T = 2π hbar c/k_B T.

“As the formula for S in terms of T shows, each species contributes (2 π ) 5 r ℓ / 90 ln 2 ≈ 10 2 bits of memory space per cubic thermal wavelength λ 3 T where λ T = 2 π ¯ hc/k B T .”

• AssumptionThe authors state this as an assumption: The volume occupied by the computer can be modeled as a collection of modes of elementary particles with total average energy E.
• AssumptionThe authors state this as an assumption: The only conserved quantities other than the computer's energy are angular momentum and electric charge, which are taken to be zero.

Contemporary quantum microcomputers constructed using nuclear magnetic resonance operate at the limits of speed and memory space described above.

“In fact, contemporary quantum 'microcomputers' such as those constructed using nuclear magnetic resonance 76 -80 do indeed operate at the limits of speed and memory space described above.”

• cites [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 yet

  Not checked in the free run.

• cites [77] Gershenfeld, N. A. & Chuang, I. L. Bulk spin-resonance quantum computation. Science 275, 350– 356 (1997). sourceNot checked yet

  Not checked in the free run.

• cites [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). sourceNot checked yet

  Not checked in the free run.

• cites [79] Jones, J. A., Mosca, M. & Hansen, R. H. Implementation of a quantum search algorithm on a quantum computer. Nature 393, 344– 346 (1998). sourceNot checked yet

  Not checked in the free run.

• cites [80] Chuang, I. L., Gershenfeld, N. & Kubinec, M. Experimental implementation of fast quantum searching . Phys. Rev. Lett. 80, 3408– 3411 (1998). sourceNot checked yet

  Not checked in the free run.

If each logical operation performed by the ultimate computer has probability ǫ of being erroneous, the total number of errors committed per second is 2ǫE/πħ.

“Suppose that each logical operation performed by the ultimate computer has a probability ǫ of being erroneous. The total number of errors committed by the ultimate computer per second is then 2 ǫE/π ¯ h .”

The amount of information that can be stored in a black hole is I = 4πGm^2 / ln2 ħc = 4πm^2 / ln2 m_P^2.

“Accordingly, the amount of information that can be stored in a black hole is I = 4 πGm 2 / ln 2¯ hc = 4 πm 2 / ln 2 m 2 P .”

Since the ultimate laptop has a surface area of 10^-2 square meters and is performing ≈10^50 operations per second, it must have an error rate of less than 10^-10 per operation in order to avoid over-heating.

“Since the ultimate laptop has a surface area of 10 -2 square meters and is performing ≈ 10 50 operations per second, it must have an error rate of less than 10 -10 per operation in order to avoid over-heating.”

• AssumptionThe authors state this as an assumption: The computer encodes erroneous bits in the form of black-body radiation at the characteristic temperature 5.87 × 10^8 K of the computer's memory.

During the heavy-ion collision, there is time to perform approximately 10^4 operations on 10^4 bits, a relatively simple computation.

“During the collision, then, there is time to perform approximately 10 4 operations on 10 4 bits a relatively simple computation.”

The strength of the interaction between two charged particles, e^2/r, determines the time t_flip = πħr/2e^2 it takes to perform a quantum logic operation such as a ControlledNOT on the two particles.

“The strength of the interaction between the particles, e 2 /r , determines the amount of time t flip = π ¯ hr/ 2 e 2 it takes to perform a quantum logic operation such as a ControlledNOT on the two particles.”

The time to perform such an operation divided by the time to send a signal at the speed of light between the bits is a universal constant, t_flip/t_com = πħc/2e^2 = π/2α, where α = e^2/ħc ≈ 1/137 is the fine structure constant.

“Interestingly, the time it takes to perform such an operation divided by the amount of time it takes to send a signal at the speed of light between the bits t com = r/c is a universal constant, t flip /t com = π ¯ hc/ 2 e 2 = π/ 2 α , where α = e 2 / ¯ hc ≈ 1 / 137 is the fine structure constant.”

In the center of mass frame the two nuclei are Lorentz contracted to D/γ where D = 12-13 fermi and γ = 100, giving a total collision time of approximately 10^-25 seconds.

“The collision time is short: in the center of mass frame the two nuclei are Lorentz contracted to D/γ where D = 12 -13 fermi and γ = 100, giving a total collision time of ≈ 10 -25 seconds.”

A one-kilogram computer compressed to the black hole limit of R_S = 2Gm/c^2 = 1.485×10^-27 meters can perform 5.4258×10^50 operations per second on its I = 4πGm^2/ln2ħc = 3.827×10^16 bits.

“A one-kilogram computer that has been compressed to the black hole limit of R S = 2 Gm/c 2 = 1 . 485 × 10 -27 meters can perform 5 . 4258 × 10 50 operations per second on its I = 4 πGm 2 / ln 2¯ hc = 3 . 827 × 10 16 bits.”

The amount of information that a physical device can process is limited by the number of degrees of freedom it possesses.

“In particular, the speed with which a physical device can process information is limited by its energy 11 -26 and the amount of information that it can process is limited by the number of degrees of freedom it possesses 5 -40 .”

• cites 5 -40Not checked yet

  Not checked in the free run.

Prototype quantum computers that store and process information on individual atoms have already been demonstrated.

“Although an Avogadro scale computer that can act on 10 23 bits might seem implausible, prototype quantum computers that store and process information on individual atoms have already been demonstrated 64 -65 , 76 -80 .”

• cites [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). sourceNot checked yet

  Not checked in the free run.

• cites [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). sourceNot checked yet

  Not checked in the free run.

• cites [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 yet

  Not checked in the free run.

• cites [77] Gershenfeld, N. A. & Chuang, I. L. Bulk spin-resonance quantum computation. Science 275, 350– 356 (1997). sourceNot checked yet

  Not checked in the free run.

• cites [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). sourceNot checked yet

  Not checked in the free run.

• cites [79] Jones, J. A., Mosca, M. & Hansen, R. H. Implementation of a quantum search algorithm on a quantum computer. Nature 393, 344– 346 (1998). sourceNot checked yet

  Not checked in the free run.

• cites [80] Chuang, I. L., Gershenfeld, N. & Kubinec, M. Experimental implementation of fast quantum searching . Phys. Rev. Lett. 80, 3408– 3411 (1998). sourceNot checked yet

  Not checked in the free run.

The speed with which a physical device can process information is limited by its energy.

“In particular, the speed with which a physical device can process information is limited by its energy 11 -26 and the amount of information that it can process is limited by the number of degrees of freedom it possesses 5 -40 .”

• cites [11] Lebedev, D. S. & Levitin, L. B. Information transmission by electromagnetic field. Inform. Control 9, 1–22 (1966). sourceNot checked yet

  Not checked in the free run.

• cites [12] Levitin, L. B. in Proceedings of the 3rd International Symposium on Radio Electronics part 3, 1–15 (Varna, Bulgaria, 1970).Not checked yet

  Not checked in the free run.

• cites [13] Levitin, L. B. Physical limitations of rate, depth, and minimum energy in information processing . Int. J. Theor. Phys. 21, 299– 309 (1982). sourceNot checked yet

  Not checked in the free run.

• cites [14] Levitin, L. B. Energy cost of information transmission (along the path to understanding) . Physica D 120, 162–167 (1998). sourceNot checked yet

  Not checked in the free run.

• cites [15] Margolus, N. & Levitin, L. B. in Proceedings of the Fourth Workshop on Physics and Computation—PhysComp96 (eds Toffoli, T., Biafore, M. & Leão, J.) (New England Complex Systems Institute, Boston, MA, 1996).Not checked yet

  Not checked in the free run.

• cites [16] Margolus, N. & Levitin, L. B. The maximum speed of dynamical evolution. Physica D 120, 188– 195 (1998). sourceNot checked yet

  Not checked in the free run.

• cites [17] Bremermann, H. J. in Self-Organizing Systems (eds Yovits, M. C., Jacobi, G. T. & Goldstein, G. D.) 93–106 (Spartan Books, Washington DC, 1962).Not checked yet

  Not checked in the free run.

• cites [18] Bremermann, H. J. in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability (eds LeCam, L. M. & Neymen, J.) Vol. 4, 15–20 (Univ. California Press, Berkeley, CA, 1967).Not checked yet

  Not checked in the free run.

• cites [19] Bremermann, H. J. Minimum energy requirements of information transfer and computing. Int. J. Theor. Phys. 21, 203–217 (1982). sourceNot checked yet

  Not checked in the free run.

• cites [20] Bekenstein, J. D. Universal upper bound on the entropy-to-energy ration for bounded systems . Phys. Rev. D 23, 287– 298 (1981). sourceNot checked yet

  Not checked in the free run.

A great deal can be determined concerning the ultimate physical limits of computation simply from knowledge of the speed of light, Planck's reduced constant, and the gravitational constant.

“In fact, as will now be shown, a great deal can be determined concerning the ultimate physical limits of computation simply from knowledge of the speed of light, c = 2 . 9979 × 10 8 meters per second, Planck's reduced constant, ¯ h = 1 . 0545 × 10 -34 joule seconds, and the gravitational constant, G = 6 . 673 × 10 -11 meters cubed per kilogram second squared.”

The fact that quantum computers work at all indicates that there is nothing in the laws of physics that forbids the construction of an Avogadro-scale computer.

“Although existing quantum computers are small and simple, able to perform a few hundred operations on fewer than ten quantum bits or 'qubits,' the fact that they work at all indicates that there is nothing in the laws of physics that forbids the construction of an Avogadro-scale computer.”

Entropy limits memory.

“Energy limits speed. Entropy limits memory.”

The energy used to perform a logical operation can be borrowed from a store of free energy, invested in the logic gate that performs the operation, and returned to storage after the operation has been performed, with a net profit in the form of processed information.

“The energy used to perform a logical operation can be 'borrowed' from a store of free energy such as a battery, 'invested' in the logic gate that performs the operation, and returned to storage after the operation has been performed, with a net 'profit' in the form of processed information.”

The limit that a computer can perform no more than 2E/π hbar operations per second is independent of computer architecture.

“An interesting feature of this limit is that it is independent of computer architecture.”

A system with average energy E can perform a maximum of 2E/π hbar logical operations per second.

“As a consequence, a system with average energy E can perform a maximum of 2 E/π ¯ h logical operations per second.”

The degree of parallelizability of the computation to be performed determines the most efficient distribution of energy among the parts of the computer.

“As will be seen below, the degree of parallelizability of the computation to be performed determines the most efficient distribution of energy among the parts of the computer.”

To perform an elementary logical operation in time Δt requires an average amount of energy E ≥ π hbar/2Δt.

“As will now be shown, to perform an elementary logical operation in time ∆ t requires an average amount of energy E ≥ π ¯ h/ 2∆ t .”

The rate at which a computer can compute is limited by its energy.

“In other words, the rate at which a computer can compute is limited by its energy.”

A system with N accessible states can register log2 N bits of information.

“In general, a system with N accessible states can register log 2 N bits of information.”

More complicated logic operations that cycle through a larger number of quantum states can be performed at a rate E/π hbar, half as fast as the simpler operations.

“More complicated logic operations that cycle through a larger number of quantum states (such as those on non-binary or continuous quantum variables) can be performed at a rate E/π ¯ h - half as fast as the simpler operations 15 -16 .”

• cites [15] Margolus, N. & Levitin, L. B. in Proceedings of the Fourth Workshop on Physics and Computation—PhysComp96 (eds Toffoli, T., Biafore, M. & Leão, J.) (New England Complex Systems Institute, Boston, MA, 1996).Not checked yet

  Not checked in the free run.

• cites [16] Margolus, N. & Levitin, L. B. The maximum speed of dynamical evolution. Physica D 120, 188– 195 (1998). sourceNot checked yet

  Not checked in the free run.

The total number of bits of memory space available to the computer is S(E,V)/kB ln 2, where S(E,V) is the thermodynamic entropy of a system with expectation value of the energy E confined to volume V.

“Accordingly, the total number of bits of memory space available to the computer is S ( E,V ) /k B ln 2, where S ( E,V ) is the thermodynamic entropy of a system with expectation value of the energy E confined to volume V .”

The amount of information that can be registered by a physical system is I = S(E)/kB ln 2, where S(E) is the thermodynamic entropy of a system with expectation value for the energy E.

“The amount of information that can be registered by a physical system is I = S ( E ) /k B ln 2, where S ( E ) is the thermodynamic entropy of a system with expectation value for the energy E .”

The canonical ensemble tells how many bits of memory are available for all possible ways of programming the computer while keeping its average energy equal to E.

“The canonical ensemble tells how many bits of memory are available for all possible ways of programming the computer while keeping its average energy equal to E .”

AND and FANOUT, like NOT, can be performed at a rate 2E/π hbar times per second, where E is the average energy of the logic gate that performs the operation.

“By embedding a Controlled-ControlledNOT gate in a quantum context, it is straightforward to see that AND and FANOUT , like NOT , can be performed at a rate 2 E/π ¯ h times per second, where E is the average energy of the logic gate that performs the operation.”

A quantum system with average energy E takes time at least Δt = π hbar/2E to evolve to an orthogonal state.

“More recently, Margolus and Levitin 15 -16 extended this result to show that a quantum system with average energy E takes time at least ∆ t = π ¯ h/ 2 E to evolve to an orthogonal state.”

• cites [15] Margolus, N. & Levitin, L. B. in Proceedings of the Fourth Workshop on Physics and Computation—PhysComp96 (eds Toffoli, T., Biafore, M. & Leão, J.) (New England Complex Systems Institute, Boston, MA, 1996).Not checked yet

  Not checked in the free run.

• cites [16] Margolus, N. & Levitin, L. B. The maximum speed of dynamical evolution. Physica D 120, 188– 195 (1998). sourceNot checked yet

  Not checked in the free run.

Bennett showed that all computations could be performed using reversible logical operations only.

“In 1973, Bennett 28 -30 showed that all computations could be performed using reversible logical operations only.”

• cites [28] Bennett, C. H. Logical reversibility of computation. IBM J. Res. Dev. 17, 525–532 (1973). sourceNot checked yet

  Not checked in the free run.

• cites [29] Bennett, C.H. Thermodynamics of computation—a review. Int. J. Theor. Phys. 21, 905–940 ( 1982). sourceNot checked yet

  Not checked in the free run.

• cites [30] Bennett, C. H. Demons, engines and the second law. Sci. Am. 257, 108 (1987). sourceNot checked yet

  Not checked in the free run.

The laws of physics do not require redundancy to perform logical operations.

“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 .”

The amount of information that a physical system can store and process is related to the number of distinct physical states accessible to the system.

“The amount of information that a physical system can store and process is related to the number of distinct physical states accessible to the system.”

The number of accessible states of a physical system, W, is related to its thermodynamic entropy by S = kB ln W.

“But it has been known for more than a century that the number of accessible states of a physical system, W , is related to its thermodynamic entropy by the formula: S = k B ln W , where k B is Boltzmann's constant.”

The temperature governs the number of operations per bit per second, kB ln 2 E/ hbar S ≈ kB T/ hbar, that a system can perform.

“Accordingly, the temperature governs the number of operations per bit per second, k B ln 2 E/ ¯ hS ≈ k B T/ ¯ h , that a system can perform.”

No quantum system with average energy E can move to an orthogonal state in a time less than Δt = π hbar/2E.

“It is straightforward to show 15 -16 that no quantum system with average energy E can move to an orthogonal state in a time less than ∆ t . That is, the speed with which a logical operation can be performed is limited not only by the spread in energy, but by the average energy.”

• cites [15] Margolus, N. & Levitin, L. B. in Proceedings of the Fourth Workshop on Physics and Computation—PhysComp96 (eds Toffoli, T., Biafore, M. & Leão, J.) (New England Complex Systems Institute, Boston, MA, 1996).Not checked yet

  Not checked in the free run.

• cites [16] Margolus, N. & Levitin, L. B. The maximum speed of dynamical evolution. Physica D 120, 188– 195 (1998). sourceNot checked yet

  Not checked in the free run.

By Landauer's principle, computation does not require dissipation.

“Consequently, by Landauer's principle, computation does not require dissipation.”

The one-to-one dynamics of Hamiltonian systems implies that when a bit is erased the information that it contains has to go somewhere.

“Essentially, the one-to-one dynamics of Hamiltonian systems implies that when a bit is erased the information that it contains has to go somewhere.”

The correct interpretation of the time-energy Heisenberg uncertainty principle is that a quantum state with spread in energy ΔE takes time at least Δt = π hbar/2ΔE to evolve to an orthogonal state.

“In particular, the correct interpretation of the time-energy Heisenberg uncertainty principle ∆ E ∆ t ≥ ¯ h is not that it takes time ∆ t to measure energy to an accuracy ∆ E (a fallacy that was put to rest by Aharonov and Bohm 23 -24 ) but rather that that a quantum state with spread in energy ∆ E takes time at least ∆ t = π ¯ h/ 2∆ E to evolve to an orthogonal (and hence distinguishable) state 2”

• cites [23] Aharonov, Y. & Bohm, D. Time in the quantum theory and the uncertainty relation for the time and energy domain. Phys. Rev. 122, 1649–1658 ( 1961). sourceNot checked yet

  Not checked in the free run.

• cites [24] Aharonov, Y. & Bohm, D. Answer to Fock concerning the time-energy indeterminancy relation. Phys. Rev. B 134, 1417–1418 (1964). sourceNot checked yet

  Not checked in the free run.

• cites [25] Anandan, J. & Aharonov, Y. Geometry of quantum evolution. Phys. Rev. Lett. 65, 1697–1700 (1990). sourceNot checked yet

  Not checked in the free run.

• cites [26] Peres, A. Quantum Theory: Concepts and Methods (Kluwer, Hingham, 1995).Not checked yet

  Not checked in the free run.

Certain of the physical limits on computation have already been attained within a circumscribed context in the construction of working quantum computers.

“Human ingenuity has proved great in the past, however, and before writing off physical limits as unattainable, one should realize that certain of these limits have already been attained within a circumscribed context in the construction of working quantum computers.”

The laws of quantum mechanics determine the maximum rate at which a system with spread in energy ΔE can move from one distinguishable state to another.

“The problem of how much energy is required for information processing was first investigated in the context of communications theory by Levitin 11 -16 , Bremermann 17 -19 , Beckenstein 20 -22 and others, who showed that the laws of quantum mechanics determine the maximum rate at which a system with spread in energy ∆ E can move from one distinguishable state to another.”

• cites [11] Lebedev, D. S. & Levitin, L. B. Information transmission by electromagnetic field. Inform. Control 9, 1–22 (1966). sourceNot checked yet

  Not checked in the free run.

• cites [12] Levitin, L. B. in Proceedings of the 3rd International Symposium on Radio Electronics part 3, 1–15 (Varna, Bulgaria, 1970).Not checked yet

  Not checked in the free run.

• cites [13] Levitin, L. B. Physical limitations of rate, depth, and minimum energy in information processing . Int. J. Theor. Phys. 21, 299– 309 (1982). sourceNot checked yet

  Not checked in the free run.

• cites [14] Levitin, L. B. Energy cost of information transmission (along the path to understanding) . Physica D 120, 162–167 (1998). sourceNot checked yet

  Not checked in the free run.

• cites [15] Margolus, N. & Levitin, L. B. in Proceedings of the Fourth Workshop on Physics and Computation—PhysComp96 (eds Toffoli, T., Biafore, M. & Leão, J.) (New England Complex Systems Institute, Boston, MA, 1996).Not checked yet

  Not checked in the free run.

• cites [16] Margolus, N. & Levitin, L. B. The maximum speed of dynamical evolution. Physica D 120, 188– 195 (1998). sourceNot checked yet

  Not checked in the free run.

• cites [17] Bremermann, H. J. in Self-Organizing Systems (eds Yovits, M. C., Jacobi, G. T. & Goldstein, G. D.) 93–106 (Spartan Books, Washington DC, 1962).Not checked yet

  Not checked in the free run.

• cites [18] Bremermann, H. J. in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability (eds LeCam, L. M. & Neymen, J.) Vol. 4, 15–20 (Univ. California Press, Berkeley, CA, 1967).Not checked yet

  Not checked in the free run.

• cites [19] Bremermann, H. J. Minimum energy requirements of information transfer and computing. Int. J. Theor. Phys. 21, 203–217 (1982). sourceNot checked yet

  Not checked in the free run.

• cites [20] Bekenstein, J. D. Universal upper bound on the entropy-to-energy ration for bounded systems . Phys. Rev. D 23, 287– 298 (1981). sourceNot checked yet

  Not checked in the free run.

The total number of bits available to be processed in the hypothetical black-hole computation is not far from the number available to current computers.

“Interestingly, although this hypothetical computation is performed at ultra-high densities and speeds, the total number of bits available to be processed is not far from the number available to current computers operating in more familiar surroundings.”

To describe behavior at the Planck length, Planck time, and Planck mass scales, a unified theory of quantum gravity is required.

“In other words, to describe behavior at length scales of the size ℓ P = √ ¯ hG/c 3 = 1 . 616 × 10 -35 meter, time scales t P = √ ¯ hG/c 5 = 5 . 391 × 10 -44 second, and mass scales of m P = √ ¯ hc/G = 2 . 177 × 10 -8 kilograms, a unified theory of quantum gravity is required.”

There is no physical reason why it should not be possible to store one bit of information per atom.

“In particular, there is no physical reason why it should not be possible to store one bit of information per atom.”

To take full advantage of the memory space available, the ultimate laptop must turn all its matter into energy.

“in order to take full advantage of the memory space available, the ultimate laptop must turn all its matter into energy.”

Packaging issues alone make it unlikely that the ultimate memory limit can be obtained, even setting aside difficulties of stability and control.

“Clearly, packaging issues alone make it unlikely that this limit can be obtained, even setting aside the difficulties of stability and control.”

The ratio t_com/t_flip is approximately equal to the ratio between the size of the system and its thermal wavelength.

“That is, the amount of time it takes to communicate from one side of the computer to the other, divided by the amount of time it takes to flip a bit, is approximately equal to the ratio between the size of the system and its thermal wavelength.”

If a computation is highly parallelizable or requires many bits of memory, the volume of the computer should be greater and the energy should be spread out evenly.

“Generally speaking, if the computation to be performed is highly parallelizable or requires many bits of memory, the volume of the computer should be greater and the energy available to perform the computation should be spread out evenly amongst the different parts of the computer.”

In practice, any computer - even the ultimate laptop - will dissipate energy.

“In practice, however, any computer - even our ultimate laptop - will dissipate energy.”

If a computation is highly serial and requires fewer bits of memory, the energy should be concentrated in particular parts of the computer.

“Conversely, if the computation to be performed is highly serial and requires fewer bits of memory, the energy should be concentrated in particular parts of the computer.”

Computation at the horizon of a black hole is highly serial: every bit is essentially connected to every other bit over the course of a single logic operation.

“In contrast to computation at lesser densities, which is highly parallel as noted above, computation at the horizon of a black hole is highly serial: every bit is essentially connected to every other bit over the course of a single logic operation.”

Only at the ultimate limit of compression-a black hole-is the computation entirely serial.

“Only at the ultimate limit of compression - a black hole - is the computation entirely serial.”

The rate at which errors can be detected and rejected to the environment by error correction routines puts a fundamental limit on the rate at which errors can be committed.

“As the discussion of error correction above indicates, the rate at which errors can be detected and rejected to the environment by error correction routines puts a fundamental limit on the rate at which errors can be committed.”

A greater degree of serial computation can be obtained at the cost of decreasing memory space by compressing the size of the computer or making the distribution of energy more uneven.

“A greater degree of serial computation can be obtained at the cost of decreasing memory space by compressing the size of the computer or making the distribution of energy more uneven.”

The ultimate limits to memory space may prove easier to approach than the ultimate limits to speed.

“In other words, the ultimate limits to memory space may prove easier to approach than the ultimate limits to speed.”

If a computer is subject to an error rate of ε bits per second, error-correcting codes can be used to detect those errors and reject them to the environment at a dissipative cost of ε kB T_E ln 2 joules per second.

“If our computer is subject to an error rate of ǫ bits per second, for example, then error-correcting codes can be used to detect those errors and reject them to the environment at a dissipative cost of ǫk B T E ln 2 joules per second, where T E is the temperature of the environment.”

At a particular temperature T, the entropy is dominated by the contributions from particles with mass less than k_B T/2 c^2.

“At a particular temperature T , the entropy is dominated by the contributions from particles with mass less than k B T/ 2 c 2 .”

• AssumptionThe authors state this as an assumption: The volume occupied by the computer can be modeled as a collection of modes of elementary particles with total average energy E.
• AssumptionThe authors state this as an assumption: The only conserved quantities other than the computer's energy are angular momentum and electric charge, which are taken to be zero.

A typical state of the ultimate laptop's memory looks like a plasma at a billion degrees Kelvin.

“A typical state of the ultimate laptop's memory looks like a plasma at a billion degrees Kelvin: the laptop's memory looks like a thermonuclear explosion or a little piece of the Big Bang!”

Error-correcting routines in the ultimate computer function as working analogs of Maxwell's demon, getting information and using it to reduce entropy at an exchange rate of kB T ln 2 joules per bit.

“Such error-correcting routines in our ultimate computer function as working analogs of Maxwell's demon, getting information and using it to reduce entropy at an exchange rate of k B T ln 2 joules per bit.”

kB T ln 2 is the minimal amount of energy required to send a bit down an information channel with noise temperature T.

“( k B T ln 2 is the minimal amount of energy required to send a bit down an information channel with noise temperature T . 14 )”

• cites [14] Levitin, L. B. Energy cost of information transmission (along the path to understanding) . Physica D 120, 162–167 (1998). sourceNot checked yet

  Not checked in the free run.

The ultimate laptop is highly parallel.

“The ultimate laptop is highly parallel.”

The entropy of a black hole has a well-defined value.

“This is because the entropy of a black hole has a well-defined value.”

• cites [90] Preskill, J. Quantum hair. Phys. Scr. T 36, 258– 264 (1991). sourceNot checked yet

  Not checked in the free run.

The thermal load of correcting large numbers of errors suggests the necessity of operating at a slower speed than the maximum allowed by the laws of physics.

“The thermal load of correcting large numbers of errors clearly suggests the necessity of operating at a slower speed than the maximum allowed by the laws of physics.”

The serial nature of computation at the black-hole limit can be deduced from the fact that black holes attain the Bekenstein bound, k_B RE/ħcS = 1/2π.

“As noted above, the serial nature of computation at the black-hole limit can be deduced from the fact that black holes attain the Beckenstein bound 20 -22 , k B RE/ ¯ hcS = 1 / 2 π .”

• cites [20] Bekenstein, J. D. Universal upper bound on the entropy-to-energy ration for bounded systems . Phys. Rev. D 23, 287– 298 (1981). sourceNot checked yet

  Not checked in the free run.

• cites [21] Bekenstein, J. D. Energy cost of information transfer. Phys. Rev. Lett. 46, 623–626 (1981). sourceNot checked yet

  Not checked in the free run.

• cites [22] Bekenstein, J. D. Entropy content and information flow in systems with limited energy. Phys. Rev. D 30, 1669–1679 (1984). sourceNot checked yet

  Not checked in the free run.

In principle, computation does not require dissipation.

“In principle, computation does not require dissipation.”

The ultimate laptop must reject errors to the environment at a high rate to maintain reliable operation.

“The ultimate laptop must reject errors to the environment at a high rate to maintain reliable operation.”

If a substantial fraction of the nuclei in a kilogram of ordinary matter can be made to register a bit, then one can get quite close to the ultimate physical limit of memory without thermonuclear explosions.

“If a substantial fraction of these nuclei can be made to register a bit, then one can get quite close to the ultimate physical limit of memory without having to resort to thermonuclear explosions.”

While it performs a computation that uses all its resources of energy and memory space, the ultimate laptop appears to an outside observer to be in a thermal state at approximately 10^9 degrees Kelvin.

“Although its computational machinery is in fact in a highly specified physical state with zero entropy, while it performs a computation that uses all its resources of energy and memory space it appears to an outside observer to be in a thermal state at ≈ 10 9 degrees Kelvin.”

At the black-hole limit, computation is fully serial: the time it takes to flip a bit and the time it takes a signal to communicate around the horizon of the hole are the same.

“At the black-hole limit, computation is fully serial: the time it takes to flip a bit and the time it takes a signal to communicate around the horizon of the hole are the same.”

A wide variety of physical systems-ranging from nearest neighbor Ising models to quantum electrodynamics and conformal field theories-are known to be computationally universal.

“Although computational universality might at first seem to be a stringent demand on a physical system, a wide variety of physical systems - ranging from nearest neighbor Ising models 52 to quantum electrodynamics 84 and conformal field theories 86 - are known to be computationally universal 51 -53 , 55 -65 .”

• cites [51] Lloyd, S. Quantum-mechanical computers and uncomputability. Phys. Rev. Lett. 71, 943–946 ( 1993). sourceNot checked yet

  Not checked in the free run.

• cites [52] Lloyd, S. A potentially realizable quantum computer. Science 261, 1569–1571 (1993). sourceNot checked yet

  Not checked in the free run.

• cites [53] Lloyd, S. Necessary and sufficient conditions for quantum computation. J. Mod. Opt. 41, 2503–2520 (1994). sourceNot checked yet

  Not checked in the free run.

• cites [55] Lloyd, S. Quantum-mechanical computers. Sci. Am. 273, 140–145 (1995). sourceNot checked yet

  Not checked in the free run.

• cites [56] DiVincenzo, D. Quantum computation. Science 270, 255– 261 (1995). sourceNot checked yet

  Not checked in the free run.

• cites [57] DiVincenzo, D. P. 2-Bit gates are universal for quantum computation. Phys. Rev. A 51, 1015–1022 ( 1995). sourceNot checked yet

  Not checked in the free run.

• cites [58] Sleator, T. & Weinfurter, H. Realizable universal quantum logic gates. Phys. Rev. Lett. 74, 4087– 4090 (1995). sourceNot checked yet

  Not checked in the free run.

• cites [59] Barenco, A. et al. Elementary gates for quantum computation. Phys. Rev. A 52, 3457–3467 ( 1995). sourceNot checked yet

  Not checked in the free run.

• cites [60] Lloyd, S. Almost any quantum logic gate is universal. Phys. Rev. Lett. 75, 346–349 (1995). sourceNot checked yet

  Not checked in the free run.

• cites [61] Deutsch, D., Barenco, A. & Ekert, A. Universality in quantum computation. Proc. R. Soc. Lond. A 449, 669–677 (1995). sourceNot checked yet

  Not checked in the free run.

The rate at which the components of a computer can communicate is limited by the speed of light.

“The rate at which the components of a computer can communicate is limited by the speed of light.”

Essentially any quantum system that admits controllable nonlinear interactions can be shown to be computationally universal.

“Essentially any quantum system that admits controllable nonlinear interactions can be shown to be computationally universal 60 -61 .”

• cites [60] Lloyd, S. Almost any quantum logic gate is universal. Phys. Rev. Lett. 75, 346–349 (1995). sourceNot checked yet

  Not checked in the free run.

• cites [61] Deutsch, D., Barenco, A. & Ekert, A. Universality in quantum computation. Proc. R. Soc. Lond. A 449, 669–677 (1995). sourceNot checked yet

  Not checked in the free run.

No computer can be compressed to smaller than its Schwarzschild radius without becoming a black hole.

“But no computer can be compressed to smaller than its Schwarzschild radius without becoming a black hole.”

Computational universality seems to be the rule rather than the exception.

“Indeed, computational universality seems to be the rule rather than the exception.”

The ordinary electrostatic interaction between two charged particles can be used to perform universal quantum logic operations between two quantum bits.

“For example, the ordinary electrostatic interaction between two charged particles can be used to perform universal quantum logic operations between two quantum bits.”