David Deutch - The Fabric of Reality

Quantum computation is more than just a faster, more miniaturized technology for implementing Turing machines. A quantum computer is a machine that uses uniquely quantum-mechanical effects, especially interference, to perform wholly new types of computation that would be impossible, even in principle, on any Turing machine and hence on any classical computer. Quantum computation is therefore nothing less than a distinctively new way of harnessing nature.

Let me elaborate that claim. The earliest inventions for harnessing nature were tools powered by human muscles. They revolutionized our ancestors’ situation, but they suffered from the limitation that they required continuous human attention and effort during every moment of their use. Subsequent technology overcame that limitation: human beings managed to domesticate certain animals and plants, turning the biological adaptations in those organisms to human ends. Thus the crops could grow, and the guard dogs could watch, even while their owners slept. Another new type of technology began when human beings went beyond merely exploiting existing adaptations (and existing non-biological phenomena such as fire), and created completely new adaptations in the world, in the form of pottery, bricks, wheels, metal artefacts and machines. To do this they had to think about, and understand, the natural laws governing the world — including, as I have explained, not only its superficial aspects but the underlying fabric of reality. There followed thousands of years of progress in this type of technology — harnessing some of the materials, forces and energies of physics. In the twentieth century information was added to this list when the invention of computers allowed complex information processing to be performed outside human brains. Quantum computation, which is now in its early infancy, is a distinct further step in this progression. It will be the first technology that allows useful tasks to be performed in collaboration between parallel universes. A quantum computer would be capable of distributing components of a complex task among vast numbers of parallel universes, and then sharing the results.

I have already mentioned the significance of computational universality — the fact that a single physically possible computer can, given enough time and memory, perform any computation that any other physically possible computer can perform. The laws of physics as we currently know them do admit computational universality. However, to be at all useful or significant in the overall scheme of things, universality as I have defined it up to now is not sufficient. It merely means that the universal computer can eventually do what any other computer can. In other words, given enough time it is universal. But what if it is not given enough time? Imagine a universal computer that could execute only one computational step in the whole lifetime of the universe. Would its universality still be a profound property of reality? Presumably not. To put that more generally, one can criticize this narrow notion of universality because it classifies a task as being in a computer’s repertoire regardless of the physical resources that the computer would expend in performing the task. Thus, for instance, we have considered a virtual-reality user who is prepared to go into suspended animation for billions of years, while the computer calculates what to show next. In discussing the ultimate limits of virtual reality, that is the appropriate attitude for us to take. But when we are considering the usefulness of virtual reality — or what is even more important, the fundamental role that it plays in the fabric of reality — we must be more discriminating. Evolution would never have got off the ground if the task of rendering certain properties of the earliest, simplest habitats had not been tractable (that is, computable in a reasonable time) using readily available molecules as computers. Likewise, science and technology would never have got off the ground if designing a stone tool had required a thousand years of thinking. Moreover, what was true at the beginning has remained an absolute condition for progress at every step. Computational universality would not be much use to genes, no matter how much knowledge they contained, if rendering their organism were an intractable task — say, if one reproductive cycle took billions of years.

Thus the fact that there are complex organisms, and that there has been a succession of gradually improving inventions and scientific theories (such as Galilean mechanics, Newtonian mechanics, Einsteinian mechanics, quantum mechanics,…) tells us something more about what sort of computational universality exists in reality. It tells us that the actual laws of physics are, thus far at least, capable of being successively approximated by theories that give ever better explanations and predictions, and that the task of discovering each theory, given the previous one, has been computationally tractable, given the previously known laws and the previously available technology. The fabric of reality must be, as it were, layered, for easy self-access. Likewise, if we think of evolution itself as a computation, it tells us that there have been sufficiently many viable organisms, coded for by DNA, to allow better-adapted ones to be computed (i.e. to evolve) using the resources provided by their worse-adapted predecessors. So we can infer that the laws of physics, in addition to mandating their own comprehensibility through the Turing principle, ensure that the corresponding evolutionary processes, such as life and thought, are neither too time-consuming nor require too many resources of any other kind to occur in reality.

So, the laws of physics not only permit (or, as I have argued, require) the existence of life and thought, they require them to be, in some appropriate sense, efficient. To express this crucial property of reality, modern analyses of universality usually postulate computers that are universal in an even stronger sense than the Turing principle would, on the face of it, require: not only are universal virtual-reality generators possible, it is possible to build them so that they do not require impracticably large resources to render simple aspects of reality. From now on, when I refer to universality I shall mean it in this sense, unless otherwise stated.

Just how efficiently can given aspects of reality be rendered? What computations, in other words, are practicable in a given time and under a given budget? This is the basic question of computational complexity theory which, as I have said, is the study of the resources that are required to perform given computational tasks. Complexity theory has not yet been sufficiently well integrated with physics to give many quantitative answers. However, it has made a fair amount of headway in defining a useful, rough-and-ready distinction between tractable and intractable computational tasks. The general approach is best illustrated by an example. Consider the task of multiplying together two rather large numbers, say 4,220,851 and 2,594,209. Many of us remember the method we learned in childhood for performing such multiplications. It involves multiplying each digit of one number in turn by each digit of the other, while shifting and adding the results together in a standard way to give the final answer, in this case 10,949,769,651,859. Many might be loath to concede that this wearisome procedure makes multiplication ‘tractable’ in any ordinary sense of the word. (Actually there are more efficient methods for multiplying large numbers, but this one provides a good enough illustration.) But from the point of view of complexity theory, which deals in massive tasks carried out by computers that are not subject to boredom and almost never make mistakes, this method certainly does fall into the ‘tractable’ category.