Because quantum cryptography depends on manipulating individual photons, it suffers from a major limitation. Each photon that is successfully received, carrying one bit of the message, must somehow have been transmitted intact from the transmitter to the receiver. But every method of transmission involves losses, and if these are too heavy the message will never arrive. Setting up relay stations (which is the remedy for this problem in existing communication systems) would compromise the security because an eavesdropper could, without being detected, monitor what goes on inside the relay station. The best existing quantum-cryptographic systems use fibre-optic cables and have a range of about ten kilometres. This would suffice to provide, say, the financial district of a city with absolutely secure internal communications. Marketable systems may not be far away, but to solve the problem of public-key cryptography in general — say, for global communication — further advances in quantum cryptography are required.
Experimental and theoretical research in the field of quantum computation is accelerating world-wide. Ever more promising new technologies for realizing quantum computers are being proposed, and new types of quantum computation with various advantages over classical computation are continually being discovered and analysed. I find all these developments very exciting, and I believe that some of them will bear technological fruit. But as far as this book is concerned, that is a side-issue. From a fundamental standpoint it does not matter how useful quantum computation turns out to be, nor does it matter whether we build the first universal quantum computer next week, or centuries from now, or never. The quantum theory of computation must in any case be an integral part of the world-view of anyone who seeks a fundamental understanding of reality. What quantum computers tell us about connections between the laws of physics, universality, and apparently unrelated strands of explanation of the fabric of reality, we can discover — and are already discovering — by studying them theoretically.
quantum computation Computation that requires quantum-mechanical processes, especially interference. In other words, computation that is performed in collaboration between parallel universes.
exponential computation A computation whose resource requirements (such as the time required) increase by a roughly constant factor for each additional digit in the input.
tractable/intractable (Rough-and-ready rule) A computational task is deemed tractable if the resources required to perform it do not increase exponentially with the number of digits in the input.
chaos The instability in the motion of most classical systems. A small difference between two initial states gives rise to exponentially growing deviations between the two resulting trajectories. But reality obeys quantum and not classical physics. Unpredictability caused by chaos is in general swamped by quantum indeterminacy caused by identical universes becoming different.
universal quantum computer A computer that could perform any computation that any other quantum computer could perform, and render any finite, physically possible environment in virtual reality.
quantum cryptography Any form of cryptography that can be performed by quantum computers but not by classical computers.
special-purpose quantum computer A quantum computer, such as a quantum cryptographic device or quantum factorization engine, that is not a universal quantum computer.
decoherence If different branches of a quantum computation, in different universes, affect the environment differently, then interference is reduced and the computation may fail. Decoherence is the principal obstacle to the practical realization of more powerful quantum computers.
The laws of physics permit computers that can render every physically possible environment without using impractically large resources. So universal computation is not merely possible, as required by the Turing principle, it is also tractable. Quantum phenomena may involve vast numbers of parallel universes and therefore may not be capable of being efficiently simulated within one universe. However, this strong form of universality still holds because quantum computers can efficiently render every physically possible quantum environment, even when vast numbers of universes are interacting. Quantum computers can also efficiently solve certain mathematical problems, such as factorization, which are classically intractable, and can implement types of cryptography which are classically impossible. Quantum computation is a qualitatively new way of harnessing nature.
The next chapter is likely to provoke many mathematicians. This can’t be helped. Mathematics is not what they think it is.
(Readers who are unfamiliar with traditional assumptions about the certainty of mathematical knowledge may consider the chapter’s main conclusion — that our knowledge of mathematical truth depends on, and is no more reliable than, our knowledge of the physical world — to be obvious. Such readers may prefer to skim this chapter and hurry on to the discussion of time in Chapter 11.)
10
The Nature of Mathematics
The ‘fabric of reality’ that I have been describing so far has been the fabric of physical reality. Yet I have also referred freely to entities that are nowhere to be found in the physical world — abstractions such as numbers and infinite sets of computer programs. Nor are the laws of physics themselves physical entities in the sense that rocks and planets are. As I have said, Galileo’s ‘Book of Nature’ is only a metaphor. And then there are the fictions of virtual reality, the non-existent environments whose laws differ from the real laws of physics. Beyond those are what I have called the ‘Cantgotu’ environments, which cannot even be rendered in virtual reality. I have said that there exist infinitely many of those for every environment that can be rendered. But what does it mean to say that such environments ‘exist’? If they do not exist in reality, or even in virtual reality, where do they exist?