The Universe as Quantum Computer

Seth Lloyd

Department of Mechanical Engineering Massachusetts Institute of Technology Cambridge

MA 02139 USA

December 17, 2013

This article reviews the history of digital computation, and investigates just how far the concept of computation can be taken. In particular, I address the question of whether the universe itself is in fact a giant computer, and if so, just what kind of computer it is. I will show that the universe can be regarded as a giant quantum computer.
The quantum computational model of the universe explains a variety of observed phenomena not encompassed by the ordinary laws of physics.
In particular, the model shows that the the quantum com- putational universe automatically gives rise to a mix of randomness and order, and to both simple and complex systems.

The computing universe

The physical universe bears little resemblance to the collection of wires, transistors, and electrical circuitry that make up a conventional digital computer.
How then, can one claim that the universe is a computer? The answer lies in the definition of computation, of which Turing was the primary developer. According to Turing, a universal digital computer is a system that can be programmed to perform any desired sequence of logical operations. Turing’s invention of the universal Turing machine makes this notion precise.
The question of whether the universe is itself a universal digital computer can be broken down into two parts: (I) Does the universe compute? and (II) Does the universe do nothing more than compute?.
More precisely, (I) Is the universe capable of performing universal digital computation in the sense of Turing? That is, can the universe or some part of it be programmed to simulate a universal Turing machine? (II) Can a universal Turing machine efficiently simulate the dynamics of the universe itself?
At first the answers to these questions might appear, straightforwardly, to be Yes. When we construct electronic digital computers, we are effectively programming some piece of the universe to behave like a universal digital computer, capable of simulating a universal Turing machine.
Similarly, the Church-Turing hypothesis implies, that any effectively calculable physical dynamics – including the known laws of physics, and any laws that may be discovered in the – can be computed using a digital computer.
But the straightforward answers are not correct. First, to simulate a universal Turing machine requires a potentially infinite supply of memory space. In Turing’s original formulation, when a Turing machine reaches the end of its tape, new blank squares can always be added: the tape is ‘indefinitely extendable.
Whether the universe that we inhabit provides us with indefinitely extendable memory is an open question of quantum cosmology, and will be discussed further below.
So a more accurate answer to the first question is ‘Maybe.’ The question of whether or not infinite memory space is available is not so serious, as one can formulate notions of universal computation with limited memory. After all, we treat our existing electronic computers as uni- versal machines even though they have finite memory (until, of course, we run out of disc space!).
The fact that we possess computers is strong empirical evidence that laws of physics support universal digital computation.
The straightforward answer to question (II) is more doubtful.

Although the outcomes of any calculable laws of physics can almost certainly be simulated on a universal Turing machine, it is an open question whether this simulation can be performed efficiently in the sense that a relatively small amount of computational resources are devoted to simulating what happens in a small volume of space and time. The current theory of computational complexity suggests that the answer to the second question is ‘Probably not.’
An even more ambitious programme for the computational theory of the universe is the question of architecture.
The observed universe possesses the feature that the laws of physics are localthey involve only interactions between neighboring regions of space and time. Moreover, these laws are homogeneous and isotropic, in that they appear to take the same form in all observed regions of space and time. The computational version of a ho- mogeneous system with local laws is a cellular automaton, a digital system consisting of cells in regular array. Each cell possesses a finite number of possible states, and is updated as a function of its own state and those of its neighbors. Cellular automata were proposed by von Neumann and by the mathematician Stanislaw Ulam in the 1940s, and used by them to investigate mechanisms of self-reproduction.
Von Neumann and Ulam showed that cellular automata were capable of universal computation in the sense of Turing. In the 1960s, Zuse and computer scientist Edward Fredkin proposed that cellular automata could be used as the basis for the laws of physics – i.e., the universe is nothing more or less than a giant cellular automaton.
More recently, this idea was promulgated by Stephen Wolfram.
The idea that the universe is a giant cellular automaton is the strong ver- sion of the statement that the universe is a computer. That is, not only does the universe compute, and only compute, but also if one looks at the ‘guts’ of the universe – the structure of matter at its smallest scale – then those guts consist of nothing more than bits undergoing local, digital operations. The strong version of the statement that the universe is a computer can be phrased as the question, (III) ‘Is the universe a cellular automaton?’
As will now be seen, the answer to this question is No. In particular, basic facts about quantum mechanics prevent the local dynamics of the universe from being reproduced by a finite, local, classical, digital dynamics.
Quantum mechanics is the physical theory that describes how systems behave at their most fundamental scales. It was studying von Neumann’s book.
The mathematical foundations of quantum mechanics that inspired Turing to work on mathematics (In particular, Turing was interested in reconciling questions of determinism and free will with the apparently indeterministic nature of quantum mechanics.)
Quantum mechanics is well-known for ex- hibiting strange, counter-intuitive features.
Chief amongst these features is the phenomenon known as entanglement, which Einstein termed ‘spooky ac- tion at a distance’ (spukhafte Fernwirkung).
In fact, entanglement does not engender non-locality in the sense of non-local interactions or superluminal communication. However, a variety of theorems from von Neumann to Bell and beyond show that the types of correlations implicit in entanglement can not be described by classical local models involving hidden variables.
In particular, such quantum correlations cannot be reproduced by local classical digital models such as cellular automata.
Accordingly, the answer to question (III), is the universe a cellular automaton, is ‘No.’
The inability of classical digital systems to cope with entanglement also seems to prevent ordinary computers from simulating quantum systems ef- ficiently. Merely to represent the state of a quantum system with N sub- systems, e.g., N nuclear spins, requires O(2N) bits on a classical computer. To represent how that state evolves requires the exponentiation of a 2N by 2N matrix.
Although it is conceivable that exponential compression tech- niques could be found that would allow a classical computer to simulate a generic quantum system efficiently, none are known. So the currently accepted answer to question (II), can a Turing machine simulate a quantum system efficiently, is ‘Probably not.’
The difficulty that classical computers have reproducing quantum effects makes it difficult to sustain the idea that the universe might at bottom be a classical computer. Quantum computers, by definition, are good at re- producing quantum effects, however.
Let’s investigate the question of whether the universe might be, at bottom, a quantum computer.
A quantum computer is a computer that uses quantum effects such as su- perposition and entanglement to perform computations in ways that classical computers cannot. Quantum computers were proposed by Paul Benioff in 1980.
The notion of a quantum Turing machine that used quantum su- perposition to perform computations in a novel way was proposed by David Deutsch in 1985.
For a decade or so, quantum computation remained something of a curiosity.

The previous year, Lloyd had showed how quantum computers could be constructed by applying electromagnetic pulses to arrays of coupled quantum systems.
The resulting parallel quantum computer is in effect a quantum cellular automaton.
In 1995, Ignacio Cirac and Peter Zoller showed how ion traps could be used to implement quantum computation.
Since then, a wide variety of designs for quantum computers have been proposed. Further quantum algorithms have been developed, and prototype quantum computers have been constructed and used to demonstrate sim- ple quantum algorithms. This allows us to begin addressing the question of whether the universe is a quantum computer.
If we ‘quantize’ our three ques- tions, the first one, ‘Does the universe allow quantum computation?’ has the provisional answer, ‘Yes.’
As before, the question of whether the uni- verse affords a potentially unlimited supply of quantum bits remains open. Moreover, it is not clear that human beings currently possess the technical ability to build large scale quantum computers capable of code breaking.
However, from the perspective of determining whether the universe supports quantum computation, it is enough that the laws of physics allow it.
Now quantize the second question. (Q2) ‘Can a quantum computer effi- ciently simulate the dynamics of the universe?’ Because they operate using the same principles that apply to nature at fundamental scales, quantum computers – though difficult to construct – represent a way of processing information that is closer to the way that nature processes information at the microscale.
In 1982, Richard Feynman suggested that quantum devices could function as quantum analog computers to simulate the dynamics of extended quantum systems.

In 1996, Lloyd developed a quantum algorithm for implementing such universal quantum simulators.
The Feynman-Lloyd results show that, unlike classical computers, quantum computers can simulate efficiently any quantum system that evolves by local interactions, in- cluding for example the standard model of elementary particles. While no universally accepted theory of quantum gravity currently exists, as long as that theory involves local interactions between quantized variables, then it can be efficiently simulated on a quantum computer. So the answer to the quantized question 2 is ‘Yes.’
There are of course subtleties to how a quantum computer can simulate the known laws of physics. Fermions supply special problems of simulation, which however can be overcome.
A short-distance (or high-energy) cutoff in the dynamics is required to insure that the amount of quantum information required to simulate local dynamics is finite. However, such cutoffs – for example, at the Planck scale – are widely expected to be a fundamental feature of nature.
Finally, we can quantize question three: Is the universe a quantum 12 cellular automaton?’ While we cannot unequivocally answer this question in the affirmative, we note that the proofs that show that a quantum computer can simulate any local quantum system efficiently immediately imply that any homogeneous, local quantum dynamics, such as that given by the standard model and (presumably) by quantum gravity, can be directly reproduced by a quantum cellular automaton. Indeed, lattice gauge theories, in Hamiltonian form, map directly onto quantum cellular automata.
Accord- ingly, all current physical observations are consistent with the theory that the universe is indeed a quantum cellular automaton.

The universe as quantum computer

We saw above that basic aspects of quantum mechanics, such as entanglement, make it difficult to construct a classical computational model of the universe as a universal Turing machine or a classical cellular automaton. By contrast, the power of quantum computers to encompass quantum dynamics allows the construction of quantum computational models of the universe.
The immediate question is ‘So what?’
Does the fact that the universe is observationally indistinguishable from a giant quantum computer tell us anything new or interesting about its behavior? The answer to this question is a resounding ‘Yes!’.
In particular, the quantum computational model of the universe answers a question that has plagued human beings ever since they first began to wonder about the origins of the universe, namely, Why is the universe so ordered and yet so complex?
The ordinary laws of physics tell us nothing about why the universe is so complex. Indeed, the complexity of the universe is quite mysterious in ordinary physics.
The reason is that the laws of physics are apparently quite simple.

The known ones can be written down on the back of a tee shirt. Moreover, the initial state of the universe appears also to have been simple. Just before the big bang, the universe was highly flat, homogeneous, isotropic, and almost entirely lacking in detail. Simple laws and simple initial conditions should lead to states that are, in principle, themselves very simple. But that is not what we see when we look out the window. Instead we see vast variety and detail animals and plants, houses and humans, and overhead, at night, stars and planets wheeling by. Highly complex systems and behaviors abound.
The quantum computational model of the universe not only explains this complexity: it requires it to exist.
To understand why the quantum computational model necessarily gives rise to complexity, consider the old story of monkeys typing on typewriters. The original version of this story was proposed by the French probabilist E?mile Borel, at the beginning of the twentieth century (for a detailed account of the history of typing monkeys see).
Borel imagined a million typing monkeys (singes dactylographes) and pointed out that over the course of single year, the monkeys had a finite chance of producing all the texts in all the libraries in the world. He then immediately noted that with very high probability, they would would produce nothing but gibberish.
Consider, by contrast, the same monkeys typing into computers. Rather than regarding the monkeys random scripts as mere texts, the computers in- terpret them as programs, sets of instructions to perform logical operations. At first it might seem that the computers would also produce mere gibberish ‘garbage in, garbage out,’ as the programmer’s maxim goes.

While it is true that many of the programs might result in garbage or error messages, it can be shown mathematically that the monkeys have a relatively high chance of producing complex, ordered structures. The reason is that many complex, ordered structures can be produced from short computer programs, albeit after lengthy calculations. Some short program will instruct the computer to calculate the digits of ?, for example, while another will cause it to produce intricate fractals. Another will instruct the computer to evaluate the consequences of the standard model of elementary particles, interacting with gravity, starting from the big bang. A particularly brief program instructs the computer to prove all possible theorems. Moreover, the shortest programs to produce these complex structures are necessarily random.
If they were not, then there would be an even shorter program that could produce the same structure.
So the monkeys, by generating random programs, are producing exactly the right conditions to generate structures of arbitrarily great complexity.
For this argument to apply to the universe itself, two ingredients are necessary - first, a computer, and second, monkeys.
But as shown above, the universe itself is indistinguishable from a quantum computer.
In addition, quantum fluctuations – e.g., primordial fluctuations in energy density – automatically provide the random bits that are necessary to seed the quantum computer with a random program.
That is, quantum fluctuations are the monkeys that program the quantum computer that is the universe.
Such a quantum computing universe necessarily generates complex, ordered structures with high probability.