The Fabric of Reality: The Science of Parallel Universes--and Its Implications

by David Deutsch

In 1985 I proved that under quantum physics there is a universal quantum computer. The proof was fairly straightforward. All I had to do was mimic Turing’s constructions, but using quantum theory to define the underlying physics instead of the classical mechanics that Turing had implicitly assumed. A universal quantum computer could perform any computation that any other quantum computer (or any Turing-type computer) could perform, and it could render any finite physically possible environment in virtual reality. Moreover, it has since been shown that the time and other resources that it would need to do these things would not increase exponentially with the size or detail of the environment being rendered, so the relevant computations would be tractable by the standards of complexity theory. The classical theory of computation, which was the unchallenged foundation of computing for half a century, is now obsolete except, like the rest of classical physics, as an approximation scheme. The theory of computation is now the quantum theory of computation.