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 192 = 361 and 193 = 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 692 = 4,761 and 693 = 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 1075 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 1075 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 pure
ly 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.
The story of quantum cryptography dates back to a curious idea developed in the late 1960s by Stephen Wiesner, then a graduate student at Columbia University. Sadly, it was Wiesner’s misfortune to invent an idea so ahead of its time that nobody took it seriously. He still recalls the reaction of his seniors: “I didn’t get any support from my thesis adviser-he showed no interest in it at all. I showed it to several other people, and they all pulled a strange face, and went straight back to what they were already doing.” Wiesner was proposing the bizarre concept of quantum money, which had the great advantage of being impossible to counterfeit.
Wiesner’s quantum money relied heavily on the physics of photons. When a photon travels through space it vibrates, as shown in Figure 73(a). All four photons are traveling in the same direction, but the angle of vibration is different in each case. The angle of vibration is known as the polarization of the photon, and a lightbulb generates photons of all polarizations, which means that some photons will vibrate up and down, some from side to side, and others at all angles in between. To simplify matters, we shall assume that photons have only four possible polarizations, which we label and .
By placing a filter known as a Polaroid in the path of the photons, it is possible to ensure that the emerging beam of light consists of photons that vibrate in one particular direction; in other words, the photons all have the same polarization. To some extent, we can think of the Polaroid filter as a grating, and photons as matchsticks randomly scattered onto the grating. The matchsticks will slip through the grating only if they are at the correct angle. Any photon that is already polarized in the same direction as the Polaroid filter will automatically pass through it unchanged, and photons that are polarized perpendicular to the filter will be blocked.
Unfortunately, the matchstick analogy breaks down when we think about diagonally polarized photons approaching a vertical Polaroid filter. Although matchsticks oriented diagonally would be blocked by a vertical grating, this is not necessarily the case with diagonally polarized photons approaching a vertical Polaroid filter. In fact, diagonally polarized photons are in a quantum quandary when confronted by a vertical Polaroid filter. What happens is that, half of them at random will be blocked, and half will pass through, and those that do pass through will be reoriented with a vertical polarization. Figure 73(b) shows eight photons approaching a vertical Polaroid filter, and Figure 73(c) shows that only four of them successfully pass through it. All the vertically polarized photons have passed through, all the horizontally polarized photons have been blocked, and half of the diagonally polarized photons have passed through.
Figure 73 (a) Although photons of light vibrate in all directions, we assume for simplicity that there are just four distinct directions, as shown in this diagram. (b) The lamp has emitted eight photons, which are vibrating in various directions. Each photon is said to have a polarization. The photons are heading toward a vertical Polaroid filter. (c) On the other side of the filter, only half the photons have survived. The vertically polarized photons have passed through, and the horizontally polarized photons have not. Half the diagonally polarized photons have passed through, and are thereafter vertically polarized.
It is this ability to block certain photons that explains how Polaroid sunglasses work. In fact, you can demonstrate the effect of Polaroid filters by experimenting with a pair of Polaroid sunglasses. First remove one lens, and close that eye so that you are looking with just the other eye through the remaining lens. Not surprisingly, the world looks quite dark because the lens blocks many of the photons that would otherwise have reached your eye. At this point, all the photons reaching your eye have the same polarization. Next, hold the other lens in front of the lens you are looking through, and rotate it slowly. At one point in the rotation, the loose lens will have no effect on the amount of light reaching your eye because its orientation is the same as the fixed lens-all the photons that get through the loose lens also pass through the fixed lens. If you now rotate the loose lens through 90°, it will turn completely black. In this configuration, the polarization of the loose lens is perpendicular to the polarization of the fixed lens, so that any photons that get through the loose lens are blocked by the fixed lens. If you now rotate the loose lens by 45°, then you reach an intermediate stage in which the lenses are partially misaligned, and half of the photons that pass through the loose lens manage to get through the fixed lens.
Wiesner planned to use the polarization of photons as a way of creating dollar bills that can never be forged. His idea was that dollar bills should each contain 20 light traps, tiny devices that are capable of capturing and retaining a photon. He suggested that banks could use four Polaroid filters oriented in four different ways () to fill the 20 light traps with a sequence of 20 polarized photons, using a different sequence for each dollar bill. For example, Figure 74 shows a bill with the polarization sequence
() Although the polarizations are explicitly shown in Figure 74, in reality they would be hidden from view. Each note also carries a traditional serial number, which is B2801695E for the dollar bill shown. The issuing bank can identify each dollar bill according to its polarization sequence and its printed serial number, and would keep a master list of serial numbers and the corresponding polarization sequences.
A counterfeiter is now faced with a problem-he cannot merely forge a dollar bill which carries an arbitrary serial number and a random polarization sequence in the light traps, because this pairing will not appear on the bank’s master list, and the bank will spot that the dollar bill is a fake. To create an effective forgery, the counterfeiter must use a genuine bill as a sample, somehow measure its 20 polarizations, and then make a duplicate dollar bill, copying across the serial number and loading the light traps in the appropriate way. However, measuring photon polarizations is a notoriously tricky task, and if the counterfeiter cannot accurately measure them in the genuine sample bill, then he cannot hope to make a duplicate.
To understand the difficulty of measuring the polarization of photons, we need to consider how we would go about trying to perform such a measurement. The only way to learn anything about the polarization of a photon is by using a Polaroid filter. To measure the polarization of the photon in a particular light trap, the counterfeiter selects a Polaroid filter and orients it in a particular way, say vertically, . If the photon emerging from the light trap happens to be vertically polarized, it will pass through the vertical Polaroid filter and the counterfeiter will correctly assume that it is a vertically polarized photon. If the emerging photon is horizontally polarized, it will not pass through the vertical Polaroid filter, and the counterfeiter will correctly assume that it is a horizontally polarized photon. However, if the emerging photon happens to be diagonally polarized ( or ), it might or might not pass through the filter, and in either case the counterfeiter will fail to identify its true nature. A photon might pass through the vertical Polaroid filter, in which case the counterfeiter will wrongly assume that it is a vertically polarized photon, or the same photon might not pass through the filter, in which case he will wrongly assume that it is a horizontally polarized photon. Alternatively, if the counterfeiter chooses to measure the photon in another light trap by orientating the filter diagonally, say , then this would correctly identify the nature of a diagonally polarized photon, but it would fail to accurately identify a vertically or horizontally polarized photon.