The Code Book (55 page)

Ordinary computers operate at a relatively macroscopic level, and at that level quantum laws and classical laws are almost indistinguishable. It did not therefore matter that scientists had generally thought of ordinary computers in terms of classical physics. However, at the microscopic level the two sets of laws diverge, and at this level only the laws of quantum physics hold true. At the microscopic level, quantum laws reveal their true weirdness, and a computer constructed to exploit these laws would behave in a drastically new way. After the conference, Deutsch returned home and began to recast the theory of computers in the light of quantum physics. In a paper published in 1985 he described his vision of a quantum computer operating according to the laws of quantum physics. In particular, he explained how his quantum computer differed from an ordinary computer.

Imagine that you have two versions of a question. To answer both questions using an ordinary computer, you would have to input the first version and wait for the answer, then input the second version and wait for the answer. In other words, an ordinary computer can address only one question at a time, and if there are several questions it has to address them sequentially. However, with a quantum computer, the two questions could be combined as a superposition of two states and inputted simultaneously-the machine itself would then enter a superposition of two states, one for each question. Or, according to the many-worlds interpretation, the machine would enter two different universes, and answer each version of the question in a different universe. Regardless of the interpretation, the quantum computer can address two questions at the same time by exploiting the laws of quantum physics.

Figure 72
David Deutsch. (
photo credit 8.1
)

To get some idea of the power of a quantum computer, we can compare its performance with that of a traditional computer by seeing what happens when each is used to tackle a particular problem. For example, the two types of computer could tackle the problem of finding a number whose square and cube together use all the digits from 0 to 9 once and only once. If we test the number 19, we find that 19
²
= 361 and 19
³
= 6,859. The number 19 does not fit the requirement because its square and cube include only the digits: 1, 3, 5, 6, 6, 8, 9, i.e., the digits 0, 2, 4, 7 are missing and the digit 6 is repeated.

To solve this problem with a traditional computer, the operator would have to adopt the following approach. The operator inputs the number 1 and then allows the computer to test it. Once the computer has done the necessary calculations, it declares whether or not the number fulfills the criterion. The number 1 does not fulfill the criterion, so the operator inputs the number 2 and allows the computer to carry out another test, and so on, until the appropriate number is eventually found. It turns out that the answer is 69, because 69
²
= 4,761 and 69
³
= 328,509, and these numbers do indeed include each of the ten digits once and only once. In fact, 69 is the only number that satisfies this requirement. It is clear that this process is time-consuming, because a traditional computer can test only one number at a time. If the computer takes one second to test each number, then it would have taken 69 seconds to find the answer. In contrast, a quantum computer would find the answer in just 1 second.

The operator begins by representing the numbers in a special way so as to exploit the power of the quantum computer. One way to represent the numbers is in terms of spinning particles-many fundamental particles possess an inherent spin, and they can either spin eastward or westward, rather like a basketball spinning on the end of a finger. When a particle is spinning eastward it represents 1, and when it is spinning westward it represents 0. Hence, a sequence of spinning particles represents a sequence of 1’s and 0’s, or a binary number. For example, seven particles, spinning east, east, west, east, west, west, west respectively, together represent the binary number 1101000, which is equivalent to the decimal number 104. Depending on their spins, a combination of seven particles can represent any number between 0 and 127.

With a traditional computer, the operator would then input one particular sequence of spins, such as west, west, west, west, west, west, east, which represents 0000001, which is simply the decimal number 1. The operator would then wait for the computer to test the number to see whether it fits the criterion mentioned earlier. Next the operator would input 0000010, which would be a sequence of spinning particles representing 2, and so on. As before, the numbers would have to be entered one at a time, which we know to be time-consuming. However, if we are dealing with a quantum computer, the operator has an alternative way of inputting numbers which is much faster. Because each particle is fundamental, it obeys the laws of quantum physics. Hence, when a particle is not being observed it can enter a superposition of states, which means that it is spinning in both directions at the same time, and so is representing both 0 and 1 at the same time. Alternatively, we can think of the particle entering two different universes: in one universe it spins eastward and represents 1, while in the other it spins westward and represents 0.

The superposition is achieved as follows. Imagine that we can observe one of the particles, and it is spinning westward. To change its spin, we would fire a sufficiently powerful pulse of energy, enough to kick the particle into spinning eastward. If we were to fire a weaker pulse, then sometimes we would be lucky and the particle would change its spin, and sometimes we would be unlucky and the particle would keep its westward spin. So far the particle has been in clear view all along, and we have been able to follow its progress. However, if the particle is spinning westward and put in a box out of our view, and we fire a weak pulse of energy at it, then we have no idea whether its spin has been changed. The particle enters a superposition of eastward and westward spins, just as the cat entered a superposition of being dead and alive. By taking seven westward-spinning particles, placing them in a box, and firing seven weak pulses of energy at them, then all seven particles enter a superposition.

With all seven particles in a superposition, they effectively represent all possible combinations of eastward and westward spins. The seven particles simultaneously represent 128 different states, or 128 different numbers. The operator inputs the seven particles, while they are still in a superposition of states, into the quantum computer, which then performs its calculations as if it were testing all 128 numbers simultaneously. After 1 second the computer outputs the number, 69, which fulfills the requested criterion. The operator gets 128 computations for the price of one.

A quantum computer defies common sense. Ignoring the details for a moment, a quantum computer can be thought of in two different ways, depending on which quantum interpretation you prefer. Some physicists view the quantum computer as a single entity that performs the same calculation simultaneously on 128 numbers. Others view it as 128 entities, each in a separate universe, each performing just one calculation. Quantum computing is
Twilight Zone
technology.

When traditional computers operate on 1’s and 0’s, the 1’s and 0’s are called bits, which is short for binary digits. Because a quantum computer deals with 1’s and 0’s that are in a quantum superposition, they are called quantum bits, or
qubits
(pronounced “cubits”). The advantage of qubits becomes even clearer when we consider more particles. With 250 spinning particles, or 250 qubits, it is possible to represent roughly 10
⁷⁵
combinations, which is greater than the number of atoms in the universe. If it were possible to achieve the appropriate superposition with 250 particles, then a quantum computer could perform 10
⁷⁵
simultaneous computations, completing them all in just one second.

The exploitation of quantum effects could give rise to quantum computers of unimaginable power. Unfortunately, when Deutsch created his vision of a quantum computer in the mid-1980s, nobody could quite envisage how to create a solid, practical machine. For example, scientists could not actually build anything that could calculate with spinning particles in a superposition of states. One of the greatest hurdles was maintaining a superposition of states throughout the calculation. A superposition exists only while it is not being observed, but an observation in the most general sense includes any interaction with anything external to the superposition. A single stray atom interacting with one of the spinning particles would cause the superposition to collapse into a single state and cause the quantum calculation to fail.

Another problem was that scientists could not work out how to program a quantum computer, and were therefore not sure what sort of computations it might be capable of doing. However, in 1994 Peter Shor of AT&T Bell Laboratories in New Jersey did succeed in defining a useful program for a quantum computer. The remarkable news for cryptanalysts was that Shor’s program defined a series of steps that could be used by a quantum computer to factor a giant number-just what was required to crack the RSA cipher. When Martin Gardner set his RSA challenge in
Scientific American
, it took six hundred computers several months to factor a 129- digit number. In comparison, Shor’s program could factor a number a million times bigger in one-millionth of the time. Unfortunately, Shor could not demonstrate his factorization program, because there was still no such thing as a quantum computer.

Then, in 1996, Lov Grover, also at Bell Labs, discovered another powerful program. Graver’s program is a way of searching a list at incredibly high speed, which might not sound particularly interesting until you realize that this is exactly what is required to crack a DES cipher. To crack a DES cipher it is necessary to search a list of all possible keys in order to find the correct one. If a conventional computer can check a million keys a second, it would take over a thousand years to crack a DES cipher, whereas a quantum computer using Grover’s program could find the key in less than four minutes.

It is purely coincidental that the first two quantum computer programs to be invented have been exactly what cryptanalysts would have put at the top of their wish lists. Although Shor’s and Grover’s programs generated tremendous optimism among codebreakers, there was also immense frustration, because there was still no such thing as a working quantum computer that could run these programs. Not surprisingly, the potential of the ultimate weapon in decryption technology has whetted the appetite of organizations such as America’s Defense Advanced Research Projects Agency (DARPA) and the Los Alamos National Laboratory, who are desperately trying to build devices that can handle qubits, in the same way that silicon chips handle bits. Although a number of recent breakthroughs have boosted morale among researchers, it is fair to say that the technology remains remarkably primitive. In 1998, Serge Haroche at the University of Paris VI put the hype surrounding the breakthroughs into perspective when he dispelled claims that a real quantum computer is only a few years away. He said this was like painstakingly assembling the first layer of a house of cards, then boasting that the next 15,000 layers were a mere formality.

Only time will tell if and when the problems of building a quantum computer can be overcome. In the meantime, we can merely speculate as to what impact it would have on the world of cryptography. Ever since the 1970s, codemakers have had a clear lead in the race against codebreakers, thanks to ciphers such as DES and RSA. These sorts of ciphers are a precious resource, because we have come to trust them to encrypt our e-mails and guard our privacy. Similarly, as we enter the twenty-first century more and more commerce will be conducted on the Internet, and the electronic marketplace will rely on strong ciphers to protect and verify financial transactions. As information becomes the world’s most valuable commodity, the economic, political and military fate of nations will depend on the strength of ciphers.

Consequently, the development of a fully operational quantum computer would imperil our personal privacy, destroy electronic commerce and demolish the concept of national security. A quantum computer would jeopardize the stability of the world. Whichever country gets there first will have the ability to monitor the communications of its citizens, read the minds of its commercial rivals and eavesdrop on the plans of its enemies. Although it is still in its infancy, quantum computing presents a potential threat to the individual, to international business and to global security.

Quantum Cryptography

While cryptanalysts anticipate the arrival of quantum computers, cryptographers are working on their own technological miracle—an encryption system that would reestablish privacy, even when confronted with the might of a quantum computer. This new form of encryption is fundamentally different from any that we have previously encountered in that it offers the hope of perfect privacy. In other words, this system would be flawless and would guarantee absolute security for eternity. Furthermore, it is based on quantum theory, the same theory that is the foundation for quantum computers. So while quantum theory is the inspiration for a computer that could crack all current ciphers, it is also at the heart of a new unbreakable cipher called
quantum cryptography
.