David Deutch - The Fabric of Reality

This remarkable non-random interference phenomenon is just as inescapable a piece of evidence for the existence of the multiverse as is the phenomenon of shadows. For the outcome that I have described is incompatible with either of the two possible paths that a particle in a single universe might have taken. If we project a photon rightwards along the lower arm of the interferometer, for instance, it may pass through the semi-silvered mirror like the photon in the interference experiment does. But it may not — sometimes it is deflected downwards. Likewise, a photon projected downwards along the right arm may be deflected rightwards, as in the interference experiment, or it may just travel straight down. Thus, whichever path you set a single photon on inside the apparatus, it will emerge randomly. Only when interference occurs between the two paths is the outcome predictable. It follows that what is present in the apparatus just before the end of the interference experiment cannot be a single photon on a single path: it cannot, for instance, be just a photon travelling on the lower arm. There must be something else present, preventing it from bouncing downwards. Nor can there be just a photon travelling on the right arm; again, something else must be there, preventing it from travelling straight down, as it sometimes would if it were there by itself. Just as with shadows, we can construct further experiments to show that the ‘something else’ has all the properties of a photon that travels along the other path and interferes with the photon we see, but with nothing else in our universe.

Since there are only two different kinds of universe in this experiment, the calculation of what will happen takes only about twice as long as it would if the particle obeyed classical laws — say, if we were computing the path of a billard ball. A factor of two will hardly make such computations intractable. However, we have already seen that multiplicity of a much larger degree is fairly easy to achieve. In the shadow experiments, a single photon passes through a barrier in which there are some small holes, and then falls on a screen. Suppose that there are a thousand holes in the barrier. There are places on the screen where the photon can fall ( does fall, in some universes), and places where it cannot fall. To calculate whether a particular point on the screen can or cannot ever receive the photon, we must calculate the mutual interference effects of a thousand parallel-universe versions of the photon. Specifically, we have to calculate one thousand paths from the barrier to the given point on the screen, and then calculate the effects of those photons on each other so as to determine whether or not they are all prevented from reaching that point. Thus we must perform roughly a thousand times as much computation as we would if we were working out whether a classical particle would strike the specified point or not.

The complexity of this sort of computation shows us that there is a lot more happening in a quantum-mechanical environment than — literally — meets the eye. And I have argued, expressing Dr Johnson’s criterion for reality in terms of computational complexity, that this complexity is the core reason why it does not make sense to deny the existence of the rest of the multiverse. But far higher multiplicities are possible when there are two or more interacting particles involved in an interference phenomenon. Suppose that each of two interacting particles has (say) a thousand paths open to it. The pair can then be in a million different states at an intermediate stage of the experiment, so there can be up to a million universes that differ in what this pair of particles is doing. If three particles were interacting, the number of different universes could be a billion; for four, a trillion; and so on. Thus the number of different histories that we have to calculate if we want to predict what will happen in such cases increases exponentially with the number of interacting particles. That is why the task of computing how a typical quantum system will behave is well and truly intractable.

This is the intractability that was exercising Feynman. We see that it has nothing to do with unpredictability: on the contrary, it is most clearly manifested in quantum phenomena that are highly predictable. That is because in such phenomena the same, definite outcome occurs in all universes, but that outcome is the result of interference between vast numbers of universes that were different during the experiment. All this is in principle predictable from quantum theory and is not overly sensitive to the initial conditions. What makes it hard to predict that in such experiments the outcome will always be the same is that doing so requires inordinately large amounts of computation.

Intractability is in principle a greater impediment to universality than unpredictability could ever be. I have already said that a perfectly accurate rendering of a roulette wheel need not — indeed should not — give the same sequence of numbers as the real one. Similarly, we cannot prepare in advance a virtual-reality rendering of tomorrow’s weather. But we can (or shall, one day, be able to) make a rendering of weather which, though not the same as the real weather conditions prevailing on any historical day, is nevertheless so realistic in its behaviour that no user, however expert, will be able to distinguish it from genuine weather. The same is true of any environment that does not show the effects of quantum interference (which means most environments). Rendering such an environment in virtual reality is a tractable computational task. However, it would appear that no practical rendering is possible for environments that do show the effects of quantum interference. Without performing exponentially large amounts of computation, how can we be sure that in those cases our rendered environment will not do things which the real environment strictly never does because of some interference phenomenon?

It might seem natural to conclude that reality does not, after all, display genuine computational universality, because interference phenomena cannot be usefully rendered. Feynman, however, correctly drew the opposite conclusion! Instead of regarding the intractability of the task of rendering quantum phenomena as an obstacle Feynman regarded it as an opportunity. If it requires so much computation to work out what will happen in an interference experiment, then the very act of setting up such an experiment and measuring its outcome is tantamount to performing a complex computation. Thus, Feynman reasoned, it might after all be possible to render quantum environments efficiently, provided the computer were allowed to perform experiments on a real quantum-mechanical object. The computer would choose what measurements to make on an auxiliary piece of quantum hardware as it went along, and would incorporate the results of the measurements into its computations.

The auxiliary quantum hardware would in effect be a computer too. For example, an interferometer could act as such a device and, like any other physical object, it can be thought of as a computer. We would nowadays call it a special-purpose quantum computer. We ‘program’ it by setting up the mirrors in a certain geometry, and then projecting a single photon at the first mirror. In a non-random interference experiment the photon will always emerge in one particular direction, determined by the settings of the mirrors, and we could interpret that direction as indicating the result of the computation. In a more complex experiment, with several interacting particles, such a computation could easily, as I have explained, become ‘intractable’. Yet since we could readily obtain its result just by performing this experiment, it is not really intractable after all. We must now be more careful with our terminology. Evidently there are computational tasks that are ‘intractable’ if we attempt to perform them using any existing computer, but which would be tractable if we were to use quantum-mechanical objects as special-purpose computers. (Notice that the fact that quantum phenomena can be used to perform computations in this way depends on their not being subject to chaos. If the outcome of computations were an inordinately sensitive function of the initial state, ‘programming’ the device by setting it in a suitable initial state would be an impossibly difficult task.)