This article by David Deutsch appeared in Frontiers magazine, December 1998 and is copyright © by David Deutsch 1998.
Our universe is just one of many, linked together by the astounding phenomena of the quantum world. David Deutsch believes this multiverse view of reality could hold the future of computing.
A growing number of physicists, myself included, are convinced that the thing we call ‘the universe’ — namely space, with all the matter and energy it contains — is not the whole of reality. According to quantum theory — the deepest theory known to physics — our universe is only a tiny facet of a larger multiverse, a highly structured continuum containing many universes.
Everything in our universe — including you and me, every atom and every galaxy — has counterparts in these other universes. Some counterparts are in the same places as they are in our universe, while others are in different places. Some have different shapes, or are arranged in different ways; some are so different that they are not worth calling counterparts. There are even universes in which a given object in our universe has no counterpart — including universes in which I was never born and you wrote this article instead.
On large scales, universes obey the laws of classical physics, and so each behaves as though the others were not there. But on microscopic scales, quantum mechanics becomes dominant and the universes are far from independent. Universes that are very alike are close together in the multiverse and affect each other strongly, though only in subtle, indirect ways — a phenomenon known as quantum interference.
Without quantum interference, electrons would spiral into atomic nuclei, destroying every atom literally in a flash. Solid matter would be unstable, and the phenomena of biological evolution and human thought would be impossible. And as I shall explain, it is quantum interference that provides our evidence for the existence of the multiverse.
Through interference, each particle in our universe can be affected by its counterparts in other universes. What we see as a single subatomic particle is really a sprawling trans-universe structure, spanning a large region of the multiverse. Although we cannot see the parts of this structure that are outside our universe, we can infer their presence from the results of experiments. Perhaps the most striking involve quantum computers — devices that collaborate with nearby universes to perform useful computations.
How do they do that? While conventional, non-quantum computers perform calculations on fundamental pieces of information called bits, which can take the values 0 or 1, quantum computers use objects called quantum bits, or qubits (pronounced queue-bits). A qubit can also either represent 0 or 1, but its value can vary from universe to universe. Hence in the time it takes a conventional computer to perform a given calculation, a quantum computer with its counterparts in other universes can perform many such calculations. In particular, they can each perform different pieces of a complex computation simultaneously. Using quantum interference, the computer in our universe can then combine its results with those of its counterparts, to arrive at the overall answer.
Not all types of computation are capable of being shared out among universes in this way. Within one universe we are free to shuffle information about from place to place, and to perform whatever logical operations we like on it, but in the multiverse, things are not so convenient. The laws of physics severely restrict the operations that we can perform. Nevertheless, quantum computers offer fundamentally new capabilities, including absolutely secure methods of communication, ways of breaking the best existing codes, and seemingly miraculous algorithms for solving mathematical problems that are currently intractable.
For instance, Deep Blue, IBM’s chess-playing supercomputer, can examine about 200 million chess positions per second by sharing the work among its 256 processors, each of which examines almost one million positions per second. A quantum computer, running a search algorithm discovered by Lov Grover of AT&T’s Bell Laboratories in New Jersey, could outclass Deep Blue by sharing the work among many universes. Grover proved that if there were time to search N items using a conventional computer in one universe, his algorithm could exploit the multiverse to search a total of N2 items in the same time. Thus a single quantum processor, with the same clock rate as one of Deep Blue’s processors, could examine a trillion chess positions in one second — and in two seconds it could examine four trillion, in three seconds nine trillion, and so on [see corrections below – DD].
Research groups worldwide are now racing to build the first practical quantum computer. Any physical object that can store a bit can in principle also serve as a qubit, but in practice, because interference is harder to control in larger systems, qubits have to be microscopic objects such as individual ions or atomic nuclei. The most powerful prototype quantum computers in existence have only a handful of qubits each, but they can already demonstrate modes of computation that no existing computer can match.
To predict that future quantum computers, made to a given specification, will work in the ways I have described, one need only solve a few uncontroversial equations. But to explain exactly how they will work, some form of multiple-universe language is unavoidable. Thus quantum computers provide irresistible evidence that the multiverse is real. One especially convincing argument is provided by quantum algorithms — even more powerful than Grover’s — which calculate more intermediate results in the course of a single computation than there are atoms in the visible universe. When a quantum computer delivers the output of such a computation, we shall know that those intermediate results must have been computed somewhere, because they were needed to produce the right answer. So I issue this challenge to those who still cling to a single-universe world view: if the universe we see around us is all there is, where are quantum computations performed? I have yet to receive a plausible reply.
Oxford physicist David Deutsch laid the theoretical foundations of quantum computing. He examines the multiverse, quantum computers and other topics in his book The Fabric of Reality, published by Penguin.* This was a bad example. Scott Aaronson at UC Berkeley has since drawn my attention to somecomments by Richard Cleve (quant-ph/9906111) pointing out thatchess and chess-like games (with a fixed number of choices per move,especially if this number is small) are not very suitable for speedup byGrover searching. At best one would expect a speedup by a moderate, fixedfactor. This does not rule out quantum chess-playing algorithms altogether, justalgorithms based on Grover-accelerated brute-force searching. But there isno special reason to expect better quantum chess algorithms to exist.
Note added March 2007: But it turns out that they do.