by Seth Lloyd
There have been many valiant attempts to construct a quantum-mechanical theory of gravity. A clear summary of these efforts can be found in the theoretical physicist Lee Smolin’s 2001 book Three Roads to Quantum Gravity. But none of these roads has yet reached its destination. Quantum computation provides a “fourth road,” if you will. As with the other approaches, lots of roadwork remains to be done. And at any point in the development of such a theory, a fatal collision with experiment or observation can turn the theory to roadkill. Nonetheless, here is a map to the quantum-computational road to quantum gravity.
Quantum Computation and Quantum Gravity
Once you have grasped how quantum computations work, it is only a short distance to understand how general relativity works and how quantum computation could give rise to a unified theory of gravity and elementary particles. To see how quantum computation leads to general relativity, think of a circuit diagram for a quantum computation.
Figure 14. A Quantum Circuit Model for Spacetime
The fabric of spacetime in the computational universe is woven out of gates and wires. At each gate, two qubits interact: the gates are connected by wires that map out the paths that qubits take as they come together, interact, and move apart.
This circuit diagram describes what happens to the qubits in the quantum computation. The qubits go down “quantum wires” that take them to logic gates, where they interact. Additional wires then take them to other logic gates, where they interact with other qubits. Any quantum computation can be built up from these simple elements. The circuit diagram specifies the computation by giving its causal structure (the wires) together with its logical structure (the logic gates). The causal structure and the logical structure completely specify the quantum computation.
To construct a quantum theory of gravity from quantum computation, we need to show that quantum computations encompass the concept of space and time, together with the quantum matter that inhabits that space and time—and that Einstein’s theory of general relativity can be derived from quantum computation. The derivation of gravity from quantum computation should specify how gravity reacts to quantum-mechanical matter and how the behavior of quantum-mechanical matter reacts to gravity. To be of any use, the theory should be predictive; that is, it should allow us to make retrodictions about what happened at the first instant of the universe and predictions about what happens when black holes evaporate—about the ultimate future of the universe.
This is a tall order, and we’re certainly not going to solve all those problems here and now. The quantum-computational approach to the universe is an ongoing research program, not a solution to all the problems of physics (though we’ll try to solve a few of them here).
General relativity is a theory of space and time and their interaction with matter. Each possible configuration of space and time interacting with matter is called a spacetime. Our universe is a particular spacetime.
In the computational-universe paradigm, the concepts of space and time, together with their interaction with matter, are to be derived from an underlying quantum computation. That is, each quantum computation corresponds to a possible spacetime—or more precisely, a quantum superposition of spacetimes—whose features are derived from the features of the computation. Our first goal is to show that the resulting spacetime obeys Einstein’s theory of general relativity. Then we’ll look at the predictions our theory makes for the computational universe.
Imagine the quantum computation as embedded in space and time. Each logic gate now sits at a point in space and time, and the wires represent physical paths along which quantum bits flow from one point to another. The first feature to note is that there are many ways to embed the quantum computation in space and time. Each quantum logic gate can be put down at any point where there is not another quantum logic gate, and the wires can squiggle all over the place to connect the logic gates. What happens to quantum information in the computation is independent of how the quantum computation is embedded in the spacetime. In the language of general relativity, the dynamical content of the quantum computation is “generally covariant”—that is, the quantum computation “doesn’t care” how it is embedded in space and time as long as the qubits interact with one another in the right sequence.
The fact that a quantum computation doesn’t care how it is embedded in spacetime means that the spacetime derived from the quantum computation obeys the laws of general relativity. Why? Because Einstein derived the laws of general relativity by requiring that those laws don’t care how the underlying physical dynamics of matter is embedded in spacetime. Under the proper assumptions, general relativity is the only theory of gravity that is generally covariant.
The explicit verification that the spacetime derived from the quantum computation obeys the laws of general relativity is somewhat mathematical, but can be summarized as follows. The wiring diagram for the quantum computation dictates where information can go; it supplies a causal structure for spacetime. But general relativity tells us that the causal structure of spacetime fixes almost all features of the spacetime; just about the only feature that remains to be fixed are local length scales.
It’s straightforward to see why local length scales are needed to determine the full structure of spacetime. Suppose I measure a distance here at MIT using a stick marked off into equal subunits. I measure the distance along MIT’s “infinite corridor” (a very long but finite corridor that runs the length of the Main Building, in which my office sits). I find that it is twenty-five units long. Now I send you an e-mail message, wherever you are: “The infinite corridor is twenty-five units long.” This e-mail message conveys no information to you about the infinite corridor’s actual length unless you know the length of the unit I’m using. To convey to you the size of the unit, we need to establish a common standard of length. So if I tell you that my unit is equal to 1,650,763.73 wavelengths of orange-red light emitted by a krypton-86 atom (i.e., my unit is 10 meters), and if you have a krypton-86 atom, then you now know how long the infinite corridor is in terms of your local length scale. Nowadays, since time can be measured more accurately than length, the meter is defined as 1⁄299,792,458 of the distance light travels in a second. If you prefer, I can define my unit to be 10 times 1⁄299,792,458 of the distance light travels in a second (i.e., my unit is still 10 meters). Now you know how long the infinite corridor is—if you have some light and a clock capable of measuring small fractions of a second, that is.
Now return to the computational universe. Once the causal structure of the quantum computation has been specified, the only features of spacetime that remain to be fixed are local length scales, and these are to be fixed in terms of the wavelike properties of the local quantum-mechanical matter. The “matter” in the computational universe arises out of the quantum logic gates. Recall that any form of quantum-mechanical matter that arises out of local interactions can be simulated or constructed out of quantum logic gates. The quantum bits make up a sort of “quantum computronium,” a computational form of matter capable of behaving like any elementary particle. Like a particle, each quantum logic gate corresponds to a wave, which wiggles up and down some number of times as the quantum bits are transformed by the quantum logic gate. The number of wiggles in the logic gate’s wave is called the action of the logic gate.
As we follow the qubits through the computation, they accumulate action. The total action is just the total number of wiggles undergone by all the qubits in the course of the computation. It’s a well-known fact of mechanics, both classical and quantum, that the behavior of any physical system is completely determined by its action. The action of the quantum logic gates completely determines what happens during the computation. As I like to put it, the action is where the action is.
Einstein’s equations relate the geometry of spacetime to the behavior of the matter in it. That geometry tells matter where to go, and the matter tells the geometry how to curve. Einstein’s equations relate the curvature of spacetime
at a given point to the action at that point—in our case, to the number of wiggles in the wave of the quantum logic gate. We have to verify that Einstein’s equations hold for our computational picture of gravity.
To fully fix the curvature requires us to choose local length scales. Once these scales are chosen, the structure of the computational spacetime is entirely fixed. It is straightforward to show that the local length scales can always be chosen so that the resulting spacetime obeys Einstein’s equations for general relativity. This agreement with general relativity is no accident. (Because the quantum computation doesn’t care how it is embedded in spacetime, our theory is automatically covariant. As a result, once it has been embedded in spacetime, the quantum computation has essentially no choice but to obey Einstein’s equations.)
Einstein challenged John Wheeler to sum up general relativity in a simple phrase. Wheeler rose to the challenge: “Matter tells space how to curve,” he said, “and space tells matter where to go.” Let’s rephrase Wheeler’s dictum for the computational universe: “Information tells space how to curve; and space tells information where to go.” In the computational universe, space is filled with “wires,” paths along which information flows. The wires tell information where to go. The wires meet at quantum logic gates, where that information is transformed and processed. The quantum logic gates, in turn, tell space how much to curve at that point. The structure of spacetime is derived from the structure of the underlying computation.
The computational universe picture of quantum gravity predicts a variety of features of the universe around us. It gives a straightforward picture of how spacetime responds to the presence of quantum-mechanical matter. It can be used to calculate how quantum fluctuations in the early universe programmed the density of matter and the locations of future galaxies. It supports models for black-hole formation and evaporation. The interacting qubits of the underlying quantum computation are perfectly capable of reproducing the phenomenology of the Standard Model for elementary particles. In other words, quantum computation represents what physicists like to call a Theory of Everything (or TOE). Mindful that theories of everything are too often theories of almost nothing, I prefer to call it a potential theory of everything (or PTOE). The motto of this potential theory of everything is, to paraphrase John Wheeler, “It from qubit!”
The computational universe paradigm for the interaction of quantum mechanics with general relativity represents a distinct road to quantum gravity. It travels through a very different landscape than Smolin’s three roads, but its final goal is the same. This paradigm is a work in progress. It makes explicit predictions for the behavior of the early universe and for processes such as black-hole evaporation. These explicit predictions can be tested by observation—for example, by detailed observations of the cosmic microwave background, the remnant radiation of the Big Bang. Time will tell whether the computational-universe paradigm is a road to understanding quantum gravity or whether collision with observation and experiment will kill it.
Despite the inevitable uncertainty of science in the making, the theory of general relativity as a consequence of quantum computation has passed a scientific milestone that has not yet been passed along any of the other three roads. Because quantum computation so easily encompasses and reproduces quantum dynamics, the computational-universe theory of quantum gravity combines general relativity and the Standard Model of elementary particles in a straightforward and self-consistent way. This accomplishment suggests that if we follow the road of the computational universe, it may well lead us to our goal, to understand the universe, and everything in it, in terms of how it processes information.
CHAPTER 8
Complexity Simplified
Making Things Complex
The primary consequence of the computational nature of the universe is that the universe naturally generates complex systems, such as life. Although the basic laws of physics are comparatively simple in form, they give rise, because they are computationally universal, to systems of enormous complexity. Besides encompassing the Standard Model of elementary particles and leading at least part of the way to a theory of quantum gravity, the computational universe provides an explanation for one of the most important features of the universe: its complexity. In the beginning, the universe was simple. Now it isn’t. So what happened?
As far as astronomers and cosmologists can tell, the universe at the moment of the Big Bang was a rather uncomplicated affair. It was very hot everywhere, and everywhere looked the same; that is, the initial state of the universe was characterized by regularity, symmetry, and simplicity. Look to the skies now and the picture is very different. There are planets, stars, galaxies, clusters of galaxies, superclusters of galaxies. The universe is clumpy and highly asymmetric. Now look out your window: plants, animals, people, cars, buildings. Life on Earth is far from simple. Just how did the universe manage to become so complex? The results presented in this book allow us to give a scientifically testable answer to this question.
We have already established a framework for describing the operation of the universe in terms of quantum information processing. We’ve seen that a quantum computer can simulate the universe in an efficient way, and that the universe is thus observationally indistinguishable from a quantum computer. To buttress these theoretical arguments, we have strong empirical evidence that the universe supports computation: I am writing this on a computer that obeys the laws of physics. Therefore the laws of physics support digital computation, and if I can keep on buying new memory space, my computer is a universal digital computer. Clearly, whatever the underlying laws of physics are, they allow the construction of computers at relatively macroscopic scales.
There is also strong evidence that the universe supports computation at the most microscopic levels. The quantum computers my colleagues and I are building bear witness to the ability of matter and energy to perform computation at the smallest scales: we are able to control the behavior of atoms, electrons, and photons in a precise fashion. Regardless of what form matter and energy take at ever smaller scales, as long as they obey the laws of quantum mechanics they can be used to compute. In the cosmological universal computer (the universal computer consisting of the universe itself), every atom is a bit, every photon moves its bit from one part of the computation to another, and every time an electron or a nuclear particle changes its spin from clockwise to counterclockwise, its bit flips. Until we obtain a full quantum theory of all fundamental physical phenomena, including gravity, we will not be able to verify the computational mechanics of the universe in detail. But we can (and do) hope that one day such verification will be possible.
If the universe is indeed a quantum computer, this presents an immediate explanation of the complexity we see around us. To understand why the computational ability of the universe essentially guarantees its current complexity, let’s return to the story of Ludwig Boltzmann and the typing monkeys. Recall that Boltzmann claimed that the complexity of the universe arose from chance. What we see around us, he asserted, is just the result of a statistical fluctuation, no different from the outcome of a long sequence of coin tosses. At first, this might seem to be an appealing explanation: in an infinitely long sequence of coin tosses, any desired finite sequence of heads and tails will eventually occur, including a representation of any desired text or mathematical expression encoded in binary form. Such a random construction of texts is the basis of Jorge Luis Borges’s story “The Library of Babel,” which describes a fictional library containing all possible texts. The story of monkeys typing Hamlet is a variant on this version of the origins of complexity.
Figure 15a. Monkeys Typing
Monkeys typing on typewriters (figure 15a) generate gibberish. When the same monkeys type into computers (figure 15b), the gibberish they generate is interpreted as a computer program by the computers, and generates complex structures.
Figure 15b. Monkeys Typing
But Boltzmann’s explanation of the origins of com
plexity is demonstrably incorrect. The vast majority of sequences of coin flips exhibit no apparent order or complexity. If complexity arises only at random, then no matter how much ordered or complex behavior has been revealed so far, what occurs next will be random. No matter how far into Hamlet a monkey may get, its next keystroke is likely to be a mistake. In a universe where everything arises at random, our next breath is definitely our last, as our atoms immediately reconfigure to a random state. (In Borges’s story, a book taken off the shelves at random will be gibberish, and the call number for any book is as long as the book itself. The Library of Babel is useless.)
Boltzmann realized that his explanation of the universe as statistical fluctuation was wrong and apparently did not pursue the question further. However, there is still a germ of truth in Boltzmann’s idea. As in chapter 3, to obtain a more plausible explanation of the origins of complexity, we imagine that the monkeys are typing not on typewriters but into computers. The computers then interpret the gibberish as a set of instructions to execute, written in, say, Java. What comes out of the computers? Garbage in, garbage out: with high probability the monkey-wielded computers will produce an error message. But sometimes one of them will produce something more interesting. The probability of the monkeys generating any given program decreases rapidly with its length. But short programs exist for producing a wide variety of interesting outputs.
At the beginning of the 1960s, computer scientists developed a detailed theory of how likely it was for a randomly programmed computer to produce interesting outputs. That theory is based on the idea of “algorithmic information.”
