by John Gribbin
Which brings us back to the quantum computer, where, as I explained in the Introduction, processing involves qubits, not bits, of information. The key feature of a qubit is that it can exist not only in the state 0 or the state 1, but in a superposition of both states. But they have another important property. Qubits, like other quantum entities, can be entangled with one another. In carrying out a calculation using a quantum computer, the set of instructions—the program, or algorithm—initially sets out the “problem” by putting some of an array of qubits (the input register) into a superposition of states. If each qubit is regarded as a register for a number then it stores two (or more) numbers simultaneously. During the next stage, a computation is carried out which spreads information to other qubits in the array (the output register), but not into the outside world (stopping the information leaking out too soon and being destroyed by entanglement is one of the key practical problems involved in building quantum computers). Crudely speaking, each component of the input register is entangled with a corresponding component of the output register, like the photons in the EPR experiment. The information has been processed simultaneously in all the histories represented by the superposition of states—in all the parallel universes, in everyday language. Finally, the qubits are allowed to interfere in a controlled fashion that provides a combination of the information from all those histories—an “answer.” The computer has carried out separate parts of the calculation in separate histories (separate universes) and produced an answer based on the interference between those histories.
But quantum computers are not magic. Like all tools, they have their limitations. There are some kinds of problems that they can solve with ease that classical computers cannot begin to tackle on any timescale relevant to human activities; but there are other problems that are not susceptible to this approach. When quantum computers are good, they are very, very good; but when they are out of their depth, they are not so much bad as no better than classical computers. To explain this, I'll start with the good.
THE GOOD: CRACKING CODES CONVENIENTLY
The best example of the power of quantum computation is the one that has inspired (if that is the right word) large amounts of money to be spent on making it a practical reality—codebreaking. There is a pleasing resonance with the reason why so much effort was devoted to building Colossus, the first computer, but this time the impetus comes as much from big business as from the military.
Cryptography has, of course, moved on a long way since the days of Colossus and Enigma. Modern codes are devised specifically to be difficult, if not impossible, to break using classical computers. The classic example of an unbreakable code is the “one time pad” system, where two protagonists (usually known as Alice and Bob) each have a pad made up of sheets of paper each listing a coding system—the first sheet might begin A codes as D, B codes as A, C codes as Z, and so on.14 Alice encodes her message using the first sheet on the pad, then rips it out and destroys it. Bob receives the message and decodes it using the first sheet on his pad, then rips it out and destroys it. The next message uses sheet two of the code pad, and so on. The “one time” aspect is vital, because if the same code is used more than once an eavesdropper (Eve) can crack the code using the kind of techniques pioneered at Bletchley Park. This method is utterly secure as long as Eve doesn't get hold of a copy of the pad, but suffers from the difficulty of getting fresh pads to Alice and Bob as required. This used to involve trusted couriers carrying locked briefcases between embassies or the offices of global businesses in different parts of the world (and Enigma was essentially based on this kind of idea, generating its own “pads” as it went along). But the system has been superseded by so-called public key cryptography.
This technique uses a freely available system—the public key—to encode messages, which can only be decoded by the intended recipient using a private key unknown to anyone else, including the sender of the message. Anybody can encrypt messages using Alice's public key, but only Bob can decrypt them. The mathematics behind this technique was first published in 1974, by Ralph Merkle, a graduate student at the University of California, Berkeley, and developed by Whitfield Diffie and Martin Hellman at Stanford University. The system depends on generating a public key using a combination of two numbers (M and N) which are openly published and a third “secret” number (actually a third and a fourth number, since each cryptographer—sender and receiver—also has their own secret number). It is very difficult (though not actually impossible) to work out what the secret numbers are from M, N and the public key. The system was developed further in 1977 by a team at MIT: Ronald Rivest, Adi Shamir and Len Adleman. In this form, the cryptographic technique is known as the RSA algorithm, from their initials. Using RSA, all Alice has to do is publish a public key, which anyone can use to send her a message that she alone can read.
The names of all of the people mentioned in the previous paragraph are enshrined in the history of cryptography. It was only in 1997 that the British government released previously secret records revealing that the whole package of ideas had been developed earlier by mathematicians working at GCHQ, the heirs to the Bletchley Park codebreakers, and kept under wraps for obvious reasons.
Without delving deeply into the full mathematical details, the secrecy of codes based on the RSA algorithm depends on the difficulty of finding the factors of a very large number. Factors are something we all learned in school—the factors of the number 15, for example, are 3 and 5, because they are both primes and 3 × 5 = 15. Numbers can have more than two factors—3 × 5 × 2 = 30—but in the present context we are interested only in numbers which are obtained by multiplying two large prime numbers together. These numbers are the factors of the resulting very large number. It's easy to find the factors of 15 by trial and error, but the difficulty grows exponentially as the size of the number increases. The reason—the only reason—Eve cannot crack Alice's code is because she does not know the factors of the large number used in Alice's public key. A key of 1,024 bits (one kilobit) would represent a decimal number with more than 300 digits; while such a number is simple to work with for coding purposes, finding its factors using a classical computer would take longer than the time that has elapsed since the Big Bang in which the Universe as we know it was born.15 No wonder big business and the military make use of the RSA algorithm—which is also the basis (using much shorter keys) of the secure systems used to preserve your privacy when you use your credit card over the World Wide Web. So imagine the mixture of horror and delight when it was realized that even a very simple quantum computer could factorize this kind of 300-digit number—thereby cracking the code—in about four minutes. More advanced machines could do it in milliseconds. Horror, because “our” secrets might be revealed; delight because “their” secrets might be revealed to us.
If a quantum computer is asked the question “What are the factors of 15?” after performing the calculation its output register contains information which can be processed using classical techniques to give answers corresponding to 3 and 5. When the output is read, it will give one of these numbers—and if you know one, you know the other. Even with large numbers, by repeating the process it is easy to find all the factors. But how does it perform the calculation?
The breakthrough came from Peter Shor, of Bell Labs, in 1994. In his landmark paper of 1985, David Deutsch himself had given an example of a kind of problem susceptible to parallel processing that could be solved twice as fast by a quantum computer using an algorithm he devised (the Deutsch algorithm) as by a classical computer; but this was not impressive enough to encourage efforts to build a working quantum computer, since it would be easier and cheaper to build two classical computers and use them working in parallel to solve such problems twice as fast. Deutsch himself was only interested in this example as proof of the reality of parallel universes. But the Shor algorithm was a whole new ball game.
The essence of Shor's algorithm is that long strings of numbers contain periodicit
ies—patterns of repetition—which may not be obvious at first sight but can be teased out by mathematical analysis. The details are fascinating, and if you want them the best place to look is in Julian Brown's book Minds, Machines and the Multiverse, but what matters here is that periodic patterns can be probed using a technique known as Fourier analysis, which unpacks complicated wave patterns into their component parts. For example, the complicated sound wave corresponding to the sound of a group of musical instruments playing a chord together could be unraveled by Fourier analysis into a wave corresponding to a violin note, a wave corresponding to the cello, a wave corresponding to a clarinet and so on. Astronomers use the same sort of technique to do such things as, for example, analyze the variations in the output of light from a star and find underlying patterns of periodic variation which reveal details of the structure of the star.16 Using a classical computer, it would be possible in principle to search for periodicities by considering each possibility in turn—looking for a pattern that repeats every two digits, then for one that repeats every three digits, then for one that repeats every four digits, and so on. But for numbers containing hundreds of digits this could take longer than the age of the Universe. A quantum computer using Shor's algorithm could set up a superposition with all the possible periods (waves) being examined simultaneously, and select the one that actually fit the number in question—which would take only a few minutes. The periodicity found in this way could then be used by a classical computer to reveal the factors of that number.
One particularly attractive feature of this procedure is that you know at once if you have gotten the right answer—you just multiply the factors together to see if they give you the right number. If there has been a glitch inside the computer and you got the wrong answer (and the first quantum computers are likely to be at least as temperamental as the first classical computers were), you just run the problem again. Even if the quantum computer only works properly one time in a hundred, you can still solve the problem in a few hundred minutes: nothing compared with the age of the Universe.
Deutsch explains this in terms of a myriad identical computers in a myriad almost identical universes, each of which tests one of the possible periodicities, which then interfere so that each of them outputs the one correct answer. You might ask why the myriad codebreakers in all those universes bother to run their computers for our benefit. But FAPP those codebreakers are us; they also want to crack the code!
All of this provides Deutsch with his most powerful argument for the reality of the Multiverse. Bear in mind that a single 250-qubit “memory” contains more bits of information than there are atoms in the observed Universe. As Deutsch writes in The Fabric of Reality:
To those who still cling to a single universe world-view, I issue this challenge: explain how Shor's algorithm works.17 I do not merely mean predict that it will work, which is simply a matter of solving a few uncontroversial equations. I mean provide an explanation. When Shor's algorithm has factorized a number, using 10500 or so times the computational resources that can be seen to be present, where was the number factorized? There are only about 1080 atoms in the entire visible universe, an utterly minuscule number compared with 10500. 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?
“I have never,” Deutsch told me, “received a satisfactory answer to this question.” Or, as his colleague Artur Ekert, also of Oxford University, put it at that time: “The Many Worlds Interpretation of quantum mechanics is the least weird of all the weird interpretations of quantum mechanics.” These days, however, Ekert has told me, “I do not refer to the Many Worlds as an interpretation, for it is just quantum theory in its bare essentials.”18
On its own, the codebreaking potential of the Shor algorithm would justify the effort now going into attempts to build quantum computers. It isn't just future codes that will be broken. You can be sure that government agencies, doubtless including GCHQ, are already stockpiling intercepted coded messages they suspect of being of long-term political significance in the hope and expectation of being able to read them in ten or twenty years’ time.
There is another extremely useful algorithm that will enable quantum computers to perform rapidly a class of tasks that would take an interminably long time on classical computers. This is the seemingly mundane job of searching through large numbers of pieces of information to find the one that is required. The usual example is the problem of searching a printed telephone directory to find the name of somebody when you only have their telephone number. Starting at either end of the alphabet, you have to check each number against the corresponding name; since the name could be anywhere in the list, on average if N is the number of numbers in the list it will take N/2 steps to find it. In 1996 Lov Grover, another Bell Labs researcher, found an algorithm which reduces this number to roughly the square root of N, by starting with a superposition of all the pieces of information and carrying out a series of operations which magnify (in a quantum sense) the one we are looking for. This is impressive, but not as impressive as Shor's algorithm, and not sufficient to displace classical computers as long as they remain cheap. The real importance of the discovery lay in providing evidence that quantum computing could be used for more than one thing, encouraging further investigation.
Remember, though, that “classical physics is false.” Perhaps the most important, and certainly the most profound, feature of a quantum computer is that it would be able to simulate physics precisely, not just approximately. No matter how good the approximations involved in simulating the Universe in a classical computer may be, they can never be perfect because the Universe is not classical. And remember how Deutsch got interested in quantum physics originally—through the search for a quantum theory of gravity. If we are ever to have a satisfactory “theory of everything” incorporating both quantum theory and gravity, it is almost certain that it will only be found with the aid of quantum computers to simulate the behavior of the Universe.19
But if that is the long-term dream, we also have to face a harsher short-term reality. When they are good, quantum computers are very, very good. But…
THE BAD: LIMITS OF QUANTUM COMPUTATION
Ironically, Grover's algorithm, which stimulated interest in quantum computation in the late 1990s, also provides a neat example of the limitations of quantum computing. In 1997, the year after Grover published his discovery, the computer Deep Blue made headlines by defeating the human world chess champion, Gary Kasparov. This encouraged speculation about how good a chess-playing quantum computer might be, if it were able to use Grover's algorithm to search for the best moves.
The argument is persuasively, but deceptively, simple. It goes like this. The computer chess program works by exploring all the possible moves as far ahead as possible in a set time. For each move by white, it considers each possible response by black, then for each possible response by black it considers each possible next move by white, and so on. From all these moves, it selects the first move that leads, assuming perfect play, to the most favorable situation for whichever color it is playing. There are about 10120 possible variations in a chess game, and if a computer could analyze a trillion (1012) possibilities every second, it would take 10100 years to analyze a whole game. For comparison, the time since the Big Bang is a few times 109 years, which is roughly a decimal point followed by 90 zeroes and a 1 times the time needed to analyze the number of possible variations in a chess game. In 1997, using 256 processors working in parallel, Deep Blue examined a mere 60 billion possibilities in the three minutes allowed between moves in the Kasparov game. Each of the processors considered about 25 million possibilities. So a naive understanding of Grover's algorithm suggests that a single quantum processor equivalent to one of Deep Blue's processors could handle 25 million squared possibilities in the same time, making the whole comp
uter 600 million times more powerful than Deep Blue, and able to probe that much further into the web of chess possibilities in the time allowed.
Alas, this naive understanding is wrong. Richard Cleve, of the University of Calgary, pointed out that games like chess, in which there is a relatively small number of fixed choices available at each move, do not lend themselves to speedup by Grover searching, and at best the process would be made slightly faster by a fixed amount. Don't just take my word for it—in a footnote to an article in Frontiers magazine in December 1998, David Deutsch said that “algorithms based on Grover-accelerated brute-force searching” are not suitable for speeding up chess-playing computers significantly—although, of course, there may be other algorithms that are more suited to the game.20
As this example demonstrates, there may be limitations on quantum computing that are quite separate from the practical problems of building a quantum computer. To see those limits, it is helpful to look in more general terms at the things computers (not just quantum computers) can do well, and the things they can't do. The key question that has to be considered is how quickly the time needed to solve a problem grows as the size of the problem increases. The time taken for factoring, our classic example, grows exponentially with the number of digits in the number; such problems can be solved efficiently if we have an algorithm that involves a number of steps that grows only by a fixed power, not exponentially, as the number increases, which is why Shor's algorithm works. Such algorithms are said to be “efficient,” and problems which can be solved by efficient algorithms belong to a category mathematicians call “complexity class P,”21 or are said to be “in P.” Another class of problem, known as NP,22 are very difficult to solve but easy to check once you have the answer—such as the factorization problem. All problems in P are, of course, also in NP.
