THE COMPUTATIONAL UNIVERSE: SETH LLOYD [10.24.02]
Every physical system registers information, and just by evolving in time, by doing its thing, it changes that information, transforms that information, or, if you like, processes that information. Since I've been building quantum computers I've come around to thinking about the world in terms of how it processes information.
SETH LLOYD is Professor of Mechanical Engineering at MIT and a principal investigator at the Research Laboratory of Electronics. He is also adjunct assistant professor at the Santa Fe Institute. He works on problems having to do with information and complex systems from the very smallhow do atoms process information, how can you make them compute, to the very large how does society process information? And how can we understand society in terms of its ability to process information?
His seminal work in the fields of quantum computation and quantum communications including proposing the first technologically feasible design for a quantum computer, demonstrating the viability of quantum analog computation, proving quantum analogs of Shannon's noisy channel theorem, and designing novel methods for quantum error correction and noise reduction has gained him a reputation as an innovator and leader in the field of quantum computing. Lloyd has been featured widely in the mainstream media including the front page of The New York Times, The LA Times, The Washington Post, The Economist, Wired, The Dallas Morning News, and The Times (London), among others. His name also frequently appears (both as writer and subject) in the pages of Nature, New Scientist, Science and Scientific American.
THE COMPUTATIONAL UNIVERSE
I'm a professor of mechanical engineering at MIT. I build
quantum computers that store information on individual atoms
and then massage the normal interactions between the atoms
to make them compute. Rather than having the atoms do what
they normally do, you make them do elementary logical operations
like bit flips, not operations, and-gates, and or-gates. This
allows you to process information not only on a small scale,
but in ways that are not possible using ordinary computers.
In order to figure out how to make atoms compute, you have
to learn how to speak their language and to understand how
they process information under normal circumstances.
A few years ago I wrote a paper in Nature called "Fundamental
Physical Limits to Computation," in which I showed that you
could rate the information processing power of physical systems.
Say that you're building a computer out of some collection
of atoms. How many logical operations per second could you
perform? Also, how much information could these systems register?
Using relatively straightforward techniques you can show,
for instance, that the number of elementary logical operations
per second that you can perform with that amount of energy,
E, is just E/H - well, it's 2E divided by pi times h-bar.
[h-bar is essentially 10[-34] (10 to the -34) Joule-seconds,
meaning that you can perform 10[-50] (10 to the 50) ops per
second.)]If you have a kilogram of matter, which has mc2
or around 10 Joules (10 to the 17) Joules worth
of energy and you ask how many ops per second it could perform,
it could perform 10 (ten to the 17) Joules / h-bar. It
would be really spanking if you could have a kilogram of matter
about what a laptop computer weighs that could
process at this rate. Using all the conventional techniques
that were developed by Maxwell, Boltzmann, and Gibbs, and
then developed by von Neumann and others back at the early
part of the 20th century for counting numbers of states, you
can count how many bits it could register. What you find is
that if you were to turn the thing into a nuclear fireball
which is essentially turning it all into radiation,
probably the best way of having as many bits as possible
then you could register about 10 (10 to the 30) bits.
Actually that's many more bits than you could register if
you just stored a bit on every atom, because Avogadro's number
of atoms store about 10 (10 to the 24) bits.
I did this calculation, which was relatively simple. You take, first of all, the observed density of matter in the universe, which is roughly one hydrogen atom per cubic meter. The universe is about thirteen billion years old, and using the fact that there are pi times 10 (10 to the 7) seconds in a year, you can calculate the total energy that's available in the whole universe. Remembering that there's a certain amount of energy, you then divide by Planck's Constant which tells you how many ops per second can be performed and multiply by the age of the universe, and you get the total number of elementary logical operations that could have been performed since the universe began. You get a number that's around 10 (10 to the 120). It's a little bigger 10 (10 to the 122) or something like that but within astrophysical units, where if you're within a factor of one hundred, you feel that you're okay;
The other way you can calculate it is by calculating how it progresses as time goes on. The universe has evolved up to now, but how long could it go? One way to figure this out is to take the phenomenological observation of how much energy there is, but another is to assume, in a Guthian fashion, that the universe is at its critical density. Then there's a simple formula for the critical density of the universe in terms of its age; G, the gravitational constant; and the speed of light. You plug that into this formula, assuming the universe is at critical density, and you find that the total number of ops that could have been performed in the universe over time (T) since the universe began is actually the age of the universe divided by the Planck scale the time at which quantum gravity becomes important quantity squared. That is, it's the age of the universe squared, divided by the Planck length, quantity squared. This is really just taking the energy divided by h-bar, and plugging in a formula for the critical density, and that's the answer you get.
This is just a big number. It's reminiscent of other famous big numbers that are bandied about by numerologists. These large numbers are, of course, associated with all sorts of terrible crank science. For instance, there's the famous Eddington Dirac number, which is 10 (10 to the 40). It's the ratio between the size of the universe and the classical size of the electron, and also the ratio between the electromagnetic force of, say, the hydrogen atom, and the gravitational force on the hydrogen atom. Dirac went down the garden path to try to make a theory in which this large number had to be what it was. The number that I've come up with is suspiciously reminiscent of (10) (10 to the 40, quantity cubed). This number, 10, (10 to the 120) is normally regarded as a coincidence, but in fact it's not a coincidence that the number of ops that could have been performed since the universe began is this number cubed, because it actually turns out to be the first one squared times the other one. So whether these two numbers are the same could be a coincidence, but the fact that this one is equal to them cubed is not.
Having calculated the number of elementary logical operations that could have been performed since the universe began, I went and calculated the number of bits, which is a similar, standard sort of calculation. Say that we took all of this beautiful matter around us on lovely Eastover Farm, and vaporized it into a fireball of radiation. This would be the maximum entropy state, and would enable it to store the largest possible amount of information. You can easily calculate how many bits could be stored by the amount of matter that we have in the universe right now, and the answer turns out to be 10 (10 to the 90). This is necessary, just by standard cosmological calculations it's (10)[3/4] (10 to the 120, quantity to the 3/4 power). We can store 10 (10 to the 90) bits in matter, and if one believes in somewhat speculative theories about quantum gravity such as holography in which the amount of information that can be stored in a volume is bounded by the area of the volume divided by the Planck Scale squared and if you assume that somehow information can be stored mysteriously on unknown gravitational degrees of freedom, then again you get 10 (10 to the 120). This is because, of course, the age of the universe squared divided by the Planck length squared is equal to the size of the universe squared divided by the Planck length. So the age of the universe squared, divided by the Planck time squared is equal to the size of the universe divided by the Planck length, quantity squared. So we can do 10 (10 to the 120) ops on 10 (10 to the 90) bits.
I made these calculations not to suggest any grandiose plan or to reveal large numbers, although of course I ended up with some large numbers, but I was curious what these numbers were. When I calculated I actually thought that these can't be right because they are too small. I can think of much bigger numbers than 10 (10 to the 120). There are lots of bigger numbers than that. It was fun to calculate the computational capacity of the universe, but I wanted to get at some picture of how much computation the universe could do if we think of it as performing a computation. These numbers can be interpreted essentially in three ways, two of which are relatively uncontroversial. The first one I already gave you: it's an upper bound to the size of a computer that we could build if we turned everything in the universe into a computer running Windows 2540. That's uncontroversial. So far nobody's managed to find a way to get around that. There's also a second interpretation, which I think is more interesting. One of the things we do with our quantum computers is to use them as analog computers to simulate other physical systems. They're very good at simulating other quantum systems, at simulating quantum field theories, at simulating all sort of effects, down to the quantum mechanical scale that is hard to understand and hard to simulate classically. These numbers are a lower limit to the size of a computer that could simulate the whole universe, because to simulate something you need at least as much stuff as is there. You need as many bits in your simulator as there are bits registered in the system if you are going to simulate it accurately. And if you're going to follow it step by step throughout its evolution, you need at least as many steps in your simulator as the number of steps that occur in the system itself. So these numbers, 10 (10 to the 120) ops, 10 (10 to the 90) bits of matter 10 if you believe in something like holography also form a lower bound on the size of a computer you would need to simulate the universe as a whole, accurately and exactly. That's also uncontroversial.
The third interpretation, which of course is more controversial, arises if we imagine that the universe is itself a computer and that what it's doing is performing a computation. If this is the case, these numbers say how big that computation is how many ops have been performed on how many bits within the horizon since the universe began. That, of course, is more controversial, and since publishing this paper I've received what is charitably described as "hate mail" from famous scientists. There have been angry letters to the editor of Physical Review Letters. "How dare you publish a paper like this?" they say. Or "It's just absolutely inconceivable. The standards have really gotten low." Thinking of the universe as a computer is controversial. I don't see why it should be so controversial, because many books of science fiction have already regarded the universe as a computer. Indeed, we even know the answer to the question it's computing it's 42. The universe is clearly not a computer with a Pentium inside. It's not an electronic computer, though of course it operates partly by quantum electro-dynamics, and it's not running Windows at least not yet. Some of us hope that never happens though you never can tell if only because you don't want the universe as a whole to crash on you all of a sudden. Luckily, whatever operating system it has seems to be slightly more reliable so far. But if people try to download the wrong software, or upgrade it in some way, we could have some trouble.
So why is this controversial? For one, it seems to be making a statement that's obviously false. The universe is not an electronic digital computer, it's not running some operating system, and it's not running Windows. Why does it make sense to talk about the universe as performing a computation at all? There's one sense in which it's actually obvious that the universe is performing a computation. If you take any physical system say this quarter, for example. The quarter can register a lot of information. It registers each atom in it, has a position which registers a certain amount of information, has some jiggling motion which registers a few bits of information, and can be heads or tails. Whether it's heads or tails in the famous flipping a coin is generating a famous bit of information unless it's Rosenkranz and Guildenstern Are Dead, in which case it always comes up heads. Because the quarter is a physical system, it's also dynamic and evolves in time. Its physical state is transforming. It's easier to notice if I flip it in the air it evolves in time, it changes, and as it changes it transforms that information, so the information that describes it goes from one state to another from heads to tails, heads to tails, heads to tails really fast. The bit flips, again and again and again. In addition, the positions, momentum, and quantum states of the atoms inside are changing, so the information that they're registering is changing. Merely by existing and evolving in time by existing any physical system registers information, and by evolving in time it transforms or processes that information.
It doesn't necessarily transform it or process it in the same way that a digital computer does, but it's certainly performing informationprocessing. From my perspective, it's also uncontroversial that the universe registers 10 bits of information, transforms and processes that information at a rate which is determined by its energy divided by Planck's constant. All physical systems can be thought of as registering and processing information, and how one wishes to define computation will determine your view of what computation consists of. If you think of computation as being merely information-processing, then it's rather uncontroversial that the universe is computing, but of course many people regard computation as being more than information-processing. There are formal definitions of what computation consists of. For instance, there are universal Turing machines, and there is a nice definition that's now 70-odd years old of what it means for something to be able to perform digital computation. Indeed, the kind of computers we have sitting on our desks, as opposed to the kinds we have sitting in our heads or the kind that were in that little inchworm that was going along, are universal digital computers. So information-processing where a physical system is merely evolving in time is a more specific, and potentially more powerful kind of computing, because one way to evolve in time is just to sit there like a lump. That's a perfectly fine way of evolving in time, but you might not consider it a computation. Of course, my computer spends a lot of time doing that, so that seems to be a common thing for computers to do.
One of the things that I've been doing recently in my scientific research is to ask this question: Is the universe actually capable of performing things like digital computations? Again, we have strong empirical evidence that computation is possible, because I own a computer. When it's not sitting there like a lump, waiting to be rebooted, it actually performs computation. Whatever the laws of physics are, and we don't know exactly what they are, they do indeed support computation in the form of existing computers. That's one bit of empirical evidence for it.
There's more empirical evidence in the form of these quantum computers that I and colleagues like Dave Cory, Tai Tsun Wu, Ike Chuang, Jeff Kimball, Dave Huan, and Hans Mooij have built. They're actually computers. If you look at a quantum computer you don't see anything, because these molecules are too small. But if you look at what's happening in a quantum computer, it's actually attaining these limits that I described before, these fundamental limits of computation. I have a little molecule, and each atom in the molecule registers a bit of information, because spin up is zero, spin down is one. I flip this bit, by putting it in an NMR spectrometer, zapping it with microwaves and making the bit flip. I ask, how fast does that bit flip, given the energy of interaction between the electromagnetic field I'm putting on that spin and the amount of time it takes to flip? You find out that the bit flips in exactly this time that's given by this ultimate limit to computation. I take the energy of the interaction, divide by h-bar if I want, I can make it more accurate, multiplying it by two over pi times h-bar and I find that that's exactly how fast that this bit flips. Similarly, I can do a more complicated operation, like an exclusive or-operation where, if I have two spins, I make this one flip if and only if this spin is spun out, and then the other one flips. It's relatively straightforward to do. In fact, people have been doing it since 1948, and if they'd thought of building quantum computers in 1948 they could have, because they actually already had the wherewithal to do it. When this happens and it's indeed the sort of thing that happens naturally inside an atom it also takes place at the limits that are given by this fundamental physics of computation. It goes exactly at the speed that it's allowed to go and no faster. It's saturating its bound for how fast you can perform a computation.
The other neat thing about these quantum computers is that they're also storing a bit of information on every available degree of freedom. Every nuclear spin in the molecules stores exactly one bit of information. We have examples of computers that saturate these ultimate limits of computation, and they look like actual physical systems. They look like alanine molecules, or amino acids, or like chloroform. Similarly, when we do quantum computation using photons, etc. we also perform computation at this limit.
I have not proved that the universe is, in fact, a digital computer and that it's capable of performing universal computation, but it's plausible that it is. It's also a reasonable scientific program to look at the dynamics of the standard model and to try to prove from that dynamics that it is computationally capable. We have strong evidence for this case. Why would this be interesting? For one thing it would justify Douglas Adams and all of the people who've been saying it's a computer all along. But it would also explain some things that have been otherwise paradoxical or confusing about the universe. Alan has done work for a long time on why the universe is so homogeneous, flat, and isotropic. This was unexplained within the standard cosmological model, and your great accomplishment here was to make a wonderful, simple, and elegant model that explains why the universe has these existing features. Another feature that everybody notices about the universe is that it's complex. Why is it complicated? Well nobody knows. It turned out that way. Or if you're a creationist you say God made it that way. If you take a more Darwinian point of view the dynamics of the universe are such that as the universe evolved in time, complex systems arose out of the natural dynamics of the universe. So why would the universe being capable of computation explain why it's complex?
There's a very nice explanation about this, which I think was given back in the '60s, and actually Marvin, maybe you can enlighten me about when this first happened, because I don't know the first instance of it. Computers are famous for being able to do complicated things starting from simple programs. You can write a very short computer program which will cause your computer to start spitting out the digits of pi. If you want to make it slightly more complex you can make it stop spitting out those digits at some point so you can use it for something else. There are short programs that generate all sorts of complicated things. That in itself doesn't constitute an explanation for why the universe itself exhibits all this complexity, but if you combine the fact that you have something that's dynamically, computationally universal with the fact that you're constantly having information injected into the universe, by the basic laws of quantum mechanics, full of quantum fluctuations are all the time injecting, programming the universe with bits of information then you do have a reasonable explanation, which I'll close with.
About a hundred and twenty years ago, Ludwig Boltzmann proposed
an explanation for why the universe is complex. He said that
it's just a big thermal fluctuation. His is a famous explanation:
the monkeys-typing-on-typewriters explanation for the universe.
Say there were a bunch of monkeys typing a bunch of random
descriptions into a typewriter. Eventually we would get a
book, right? But Boltzman among other people realized right
away that this couldn't be right, because the probability
of this happening is vanishingly small. If you had one dime
that assembled itself miraculously by a thermal fluctuation,
the chances of finding another dime would be vanishingly small;
you'd never find that happening in the same universe because
it's just too unlikely.
I would suggest, merely as a metaphor here, but also as the basis for a scientific program to investigate the computational capacity of the universe, that this is also a reasonable explanation for why the universe is complex. It gets programmed by little random quantum fluctuations, like the same sorts of quantum fluctuations that mean that our galaxy is here rather than somewhere else. According to the standard model billions of years ago some little quantum fluctuation, perhaps a slightly lower density of matter, maybe right where we're sitting right now, caused our galaxy to start collapsing around here. It was just a little quantum fluctuation, but it programmed the universe and it's important for where we are, because I'm very glad to be here and not billions of miles away in outer space. Similarly, another famous little quantum fluctuation that programs you is the exact configuration of your DNA. The program takes strands of DNA from your mother and from your father, splits them up, and wires them together, recombines them. This is a process that has lots of randomness in it, as you know if you have siblings. If you trace that randomness down, you find that that randomness is actually arising from little quantum fluctuations, which masquerade as thermal and chemical fluctuations. Your genes got programmed by quantum fluctuation. There's nothing wrong with that, nothing to be ashamed of that's just the way things are. Your genes are very important to you, and they themselves form a kind of program for your life, and how your body functions.
In this metaphor we actually have a picture of the computational
universe, a metaphor which I hope to make scientifically precise
as part of a research program. We have a picture for how complexity
arises, because if the universe is computationally capable,
maybe we shouldn't be so surprised that things are so entirely
out of control.