The idea for this question comes from an example in cryptography, where supposedly 256-bit symmetric keys will be enough for all time to come (brute-forcing a 256-bit key is sort-of equivalent to counting to $2^{255}$, with some constant in front of it). While I don't really doubt this, I think it is an interesting thought experiment to what number (approximately of course) a theoretical "perfectly efficient" (define this as you want) computer, with infinite time and all the energy (including matter but not dark matter) in our galaxy available could count to. Counting to $x$ is defined as having some physical object go through $x$ different, predefined, measurable states. Sadly I'm missing the theoretical background to do this calculation myself properly, I could try it but I would have no idea if I missed something essential. I hope a "fun" question like this isn't out of scope for this site (feel free to direct me to a better place to ask this).

Alternatively: What about all the energy in the known Universe?

Since the idea for this question was key-length in cryptography, feel free to consider (or not consider) Grover's algorithm.

Edit: As a comment suggests, if there's no good answer on what to consider a "perfectly efficient computer", maybe just take the values for a known processor.

  • hi cooky - I have a feeling your question is teetering on being loved/hated in physics SE. For one, I don't know how one measures the work of "computer counting", or if there is an ideally efficient computer. – anon01 May 22 '16 at 14:11
  • You could maybe frame it like: how much energy would it take the most efficient computers to...(insert your task) – anon01 May 22 '16 at 14:13
  • 1
    Using classical approaches, one can count to 2^256 using 3/4 of the mass/energy of the galaxy. I'd re run the math for you, but it looks like you already accepted a quantum answer. – Cort Ammon May 22 '16 at 16:45
  • 2
    @CortAmmon That looks like an interesting answer too, please elaborate - I for one have no idea what you're getting at. Moreover, given the OP's needs (estimates for judging soundness of cryptographic schemes by), a variety of different approaches to the problem would be helpful. – WetSavannaAnimal aka Rod Vance May 22 '16 at 23:28
  • Given the context of your question, you should also look at the Bremmermann Limit which apparently has some history of being used to assess safety of cryptographic algorithms. – WetSavannaAnimal aka Rod Vance May 23 '16 at 0:42
up vote 126 down vote accepted

A "perfectly efficient" computer can mean many things, but, for the purposes of this answer, let's take it to mean a reversible computer (explained further as we go).

The theoretical lower limit to energy needs in computing is the Landauer Limit, which states that the forgetting of one bit of information requires the input of work amounting $k\,T\,\log 2$ so as to comply with the second law of thermodynamics. If the computer is reversible, i.e. its state at all times can be inferred its state at any other time, then there is no theoretical lower limit to its energy needs. By state here we mean the computer theoretical state of the CPU, not the physical quantum state (the former being a very small part of the latter; microscopic laws are reversible so that the full quantum state at any time can always in theory be inferred from the full quantum state at any time). An example of a nonreversible computation is one where you add two numbers and write the result over the memory formerly occupied by the addends. The two addends cannot be inferred from the computer's state (i.e. the sum) after the addition has taken place. Briefly, the reason for this situation is that if your calculation forgets, Nature does not, so if you erase memory, then that "erased" information must somehow wind up encoded in the full quantum state of the computer since microscopic laws are indeed reversible. The only way a system can "absorb more information", i.e. fully encode its past in its quantum state, is by accessing more and more quantum states, and that almost always means by getting hotter [see 1]. So, somewhere along the line you have to add energy to make this happen, and eventually you'll need to cool the computer to keep it working. The second law of thermodynamics then shows that if we want to keep the computer at a constant macrostate, we need to input the amount of work prescribed by Landauer's principle to do so[see ref. 2].

Now let's look at your problem. Counting can clearly be made into a reversible computation: each step is invertible and you can imagine simply clocking a simple digital counter backwards to achieve this. So in theory we could build a quantum (or other reversible) computer to count with no energy input whilst it is counting. However, when tallying up the forgetting of information, one needs to take into account initialization. That is, you need to begin with initialized registers to count with. You start your machine up by initializing them all to nought ..... but that means that there is a quantum state of each register that is "forgotten" as the machine is initialized. So, if you need memory of $N$ bits for your counting, you need to come up with $N\,k\,T\,\log 2$ joules to get your reversible computer initialized. Wikipedia tells me the Milky Way's mass is estimated to be $10^{12}$ solar masses, or about $2\times 10^{30}\times 10^{12}\times 10^{17} =2\times 10^{59}$ joules. If you can cool your computer to the temperature of the Cosmic Background Microwave Radiation, or $2.7{\rm K}$, then the Landauer limit implies you can buy the initialization of $2\times 10^{59} / (2.7\times 1.38\times 10^{-23}\times \log 2) \approx 8\times 10^{81}$ bits. You can't run your computer below $2.7{\rm K}$ since it would then need energy for artificial cooling below its environment.

So that's then your rough answer: in theory you could count to the number :

$$2^{8\times 10^{81}}$$

with a reversible implementation of a counter given the stated energy budget.

Another limit that may be of interest in from the cryptographic viewpoint is the Bremmermann Limit, which limits how fast computations can evolve into their successive steps.

It should be noted how difficult it is to achieve the Landauer limit. If our counter forgets even one bit per counting cycle, the limit reduces to the still colossal $2\times 10ˆ{81}$. Yockey [see reference 3] claims in the early chapters of his book that the phenomenon of DNA replication during cell division thought of as a computer algorithm is the most efficient computation known, and consumes roughly one order of magnitude more energy than the Landauer limit, that is, roughly $10 k\,T$ per forgotten bit. In the light of the Landauer limit, modern computers are staggeringly inefficient. 32Gbyte of RAM being overwritten at 1GByte per second and consuming 5 watts at 300K in being so (these are the figures for the computer these words are being written on) represents a forgetting that is eleven orders of magnitude more wasteful ($5 / (8\times 10^9 \times k \times 300\,\log 2)\approx 2\times 10^{11}$) than the Landauer limit.


References and Footnotes:

[1]: To deepen your understanding of this statement, try working out and plotting the Shannon entropy of specification of the state of an ensemble of $N$ quantum harmonic oscillators at thermodynamic equilibrium as a function of temperature (answer: $\left(\frac{e^{\beta_\omega } \beta_\omega }{1-e^{\beta_\omega }}+\log \left(e^{\beta_\omega }-1\right)\right)/\log (2)$ bits per oscillator, where $\beta_\omega = \hbar\omega/(k\,T)$). You can immediately see what's going on: the Boltzmann probability distribution is here proportional to $p(n)\propto\exp\left(-(n+\frac{1}{2}) \frac{\hbar\,\omega}{k\,T}\right)$ and the tail gets longer, "accessing more states" as $T$ rises).

[2] An excellent review paper for these concepts is Charles Bennett, "The Thermodynamics of Computation: A Review", Int. J. Theo. Phys., 21, No. 12, 1982)

[3] "Information Theory, Evolution, and the Origin of Life", Hubert P. Yockey As a non biologist I don't feel qualified to judge this text. I did feel, however, that I understood the early chapters whence I gleaned the assertion about the efficiency of DNA replication well enough to be reasonably confident in the assertion's soundness, but I found most of the text beyond Chapter 2 utterly incomprehensible.

  • 3
    That qualitative explanation of why irreversible computation takes energy was great. I'd come across that fact, but hadn't seen an explanation before. – Peter Cordes May 22 '16 at 17:56
  • 1
    For completeness, it might be worth noting that if you need to do any kind of non-reversible computation at each step, then the limit becomes much lower. In fact, using your figures and assuming the erasure of (at least) one bit per step, the limit becomes approximately $8 \times 10^{81} \approx 2^{272}$ steps. – Ilmari Karonen May 22 '16 at 22:46
  • 5
    Given that there are ~$10^{80}$ atoms in the universe, it turns out that the limiting factor in a binary computer would be the the number of atoms (assuming you can get one bit per atom). We may figure out how to encode more densely than that someday, but we are still in the many atoms per bit regime. It is somewhat interesting, though, that these two numbers are within 2 orders of magnitude of each other. – user121330 May 23 '16 at 23:43
  • 1
    There is a Nature paper that experimentally validates the Landauer Principle. – WYSIWYG Jun 9 '16 at 8:39
  • 1
    @WYSIWYG Thanks for the reference. There is now quite a body of experimental work seeking to directly validate the LP. See for example here – WetSavannaAnimal aka Rod Vance Jun 9 '16 at 8:43

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.