David Deutch - The Fabric of Reality

Thus the race is on to engineer sub-microscopic systems in which information-carrying variables interact among themselves, but affect their environment as little as possible. Another novel simplification, unique to the quantum theory of computation, partly offsets the difficulties caused by decoherence. It turns out that, unlike classical computation, where one needs to engineer specific classical logic elements such as and, or and not, the precise form of the interactions hardly matters in the quantum case. Virtually any atomic-scale system of interacting bits, so long as it does not decohere, could be made to perform useful quantum computations.

Interference phenomena involving vast numbers of particles, such I as superconductivity and superfluidity, are known, but it seems that none of them can be used to perform any interesting computations. At the time of writing, only single-bit quantum computations can be easily performed in the laboratory. Experimentalists are confident, however, that two- and higher-bit quantum gates (the quantum equivalent of the classical logical elements) will be constructed within the next few years. These are the basic components of quantum computers. Some physicists, notably Rolf Landauer of IBM Research, are pessimistic about the prospects for further advances after that. They believe that decoherence will never be reduced to the point where more than a few consecutive quantum-computational steps can be performed. Most researcher in the field are much more optimistic (though perhaps that is because only optimistic researchers choose to work on quantum computation!). Some special-purpose quantum computers have already been built (see below), and my own opinion is that more complex ones will appear in a matter of years rather than decades. As for the universal quantum computer, I expect that its construction too is only a matter of time, though I should not like to predict whether that time will be decades or centuries.

The fact that the repertoire of the universal quantum computer contains environments whose rendering is classically intractable implies that new classes of purely mathematical computations must have become tractable too. For the laws of physics are, as Galileo said, expressed in mathematical language, and rendering an environment is tantamount to evaluating certain mathematical functions. And indeed, many mathematical tasks have now been discovered which could be efficiently performed by quantum computation where all known classical methods are intractable. The most spectacular of these is the task of factorizing large numbers. The method, known as Shor’s algorithm, was discovered in 1994 by Peter Shor of Bell Laboratories. (While this book was in proof further spectacular quantum algorithms have been discovered, including Graver’s algorithm for searching long lists very rapidly.)

Shor’s algorithm is extraordinarily simple and requires far more modest hardware than would be needed for a universal quantum computer. It is likely, therefore, that a quantum factorization engine will be built long before the full range of quantum computations is technologically feasible. This is a prospect of great significance for cryptography (the science of securely communicating and authenticating information). Realistic communication networks may be global and have large, constantly changing sets of participants with unpredictable patterns of communication. It is impractical to require every pair of participants, physically and in advance, to exchange secret cryptographic keys that would allow them later to communicate without fear of eavesdroppers. Public-key cryptography is any method of sending secret information where the sender and recipient do not already share any secret information. The most secure known method of public-key cryptography depends on the intractability of the problem of factorizing large numbers. This method is known as the RSA cryptosystem, named after Ronald Rivest, Adi Shamir and Leonard Adelman, who first proposed it in 1978. It depends on a mathematical procedure whereby a message can be encoded using a large (say, 250-digit) number as a key. The recipient can freely make this key public, because any message encoded with it can only be decoded given a knowledge of the factors of that number. Thus I can choose two 125-digit prime numbers and keep them secret, but multiply them together and make their 250-digit product public. Anyone can send me a message using that number as the key, but only I can read the messages because only I know the secret factors.

As I have said, there is no practical prospect of factorizing 250-digit numbers by classical means. But a quantum factorization engine running Shor’s algorithm could do it using only a few thousand arithmetic operations, which might well take only a matter of minutes. So anyone with access to such a machine would easily be able to read any intercepted message that had been encrypted using the RSA cryptosystem.

It would do the cryptographers no good to choose larger numbers as keys because the resources required by Shor’s algorithm increase only slowly with the size of the number being factorized. In the quantum theory of computation, factorization is a very tractable task. It is thought that, in the presence of a given level of decoherence, there would again be a practical limit on the size of number that could be factorized, but there is no known lower limit on the rate of decoherence that can be technologically achieved. So we must conclude that one day in the future, at a time that cannot now be predicted, the RSA cryptosystem with any given length of key may become insecure. In a certain sense, that makes it insecure even today. For anyone, or any organization, that records an RSA-encrypted message today, and waits until they can buy a quantum factorization engine with low enough decoherence, will be able to decode the message. That may not happen for centuries, or it may be only decades — perhaps less, who can tell? But the likelihood that it will be rather a long time is all that now remains of the former complete security of the RSA system.

When a quantum factorization engine is factorizing a 250-digit number, the number of interfering universes will be of the order of 10 500— that is, ten to the power of 500. This staggeringly large number is the reason why Shor’s algorithm makes factorization tractable. I said that the algorithm requires only a few thousand arithmetic operations. I meant, of course, a few thousand operations in each universe that contributes to the answer. All those computations are performed in parallel, in different universes, and share their results through interference.

You may be wondering how we can persuade our counterparts in 10 500-odd universes to start working on our factorization task. Will they not have their own agendas for the use of their computers? No — and no persuasion is necessary. Shor’s algorithm operates initially only on a set of universes that are identical to one another, and it causes them to become differentiated only within the confines of the factorization engine. So we, who specified the number to be factorized, and who wait while the answer is computed, are identical in all the interfering universes. There are, no doubt, many other universes in which we programmed different numbers or never built the factorization engine at all. But those universes differ from ours in too many variables — or more precisely, in variables that are not made to interact in the right way by the programming of Shor’s algorithm — and so do not interfere with our universe.

The argument of Chapter 2, applied to any interference phenomenon destroys the classical idea that there is only one universe. Logically, the possibility of complex quantum computations adds nothing to a case that is already unanswerable. But it does add psychological impact. With Shor’s algorithm, the argument has been writ very large. To those who still cling to a single-universe world-view, I issue this challenge: explain how Shor’s algorithm works. I do not merely mean predict that it will work, which is merely a matter of solving a few uncontroversial equations. I mean provide an explanation. When Shor’s algorithm has factorized a number, using 10 500or so times the computational resources that can be seen to be present, where was the number factorized? There are only about 10 80atoms in the entire visible universe, an utterly miniscule number compared with 10 500. So if the visible universe were the extent of physical reality, physical reality would not even remotely contain the resources required to factorize such a large number. Who did factorize it, then? How, and where, was the computation performed?