v1.0.2 / chapter 19 of 20 / 01 aug 09 / greg goebel / public domain
* While many physicists long tried to ignore the whole concept of "quantum weirdness", in the 21st century work is being done to actually make practical use of the bizarre aspects of quantum physics for computing and cryptology. This work has highlighted research that has challenged long-held ideas about quantum physics.
* The initial chapters of this document introduced some of the bizarre concepts of "quantum weirdness" and then glossed over the matter, but it's not something that can be swept under the rug. Although quantum weirdness tends to sound like doubletalk -- which, given a certain lack of caution, it quickly becomes -- aspects of it do have practical, or at least potentially practical, applications in the field of "quantum computing".
A normal computer processor essentially performs operations on a single number at a time. A scheme can be imagined with quantum physics that can perform operations on a full range of numbers at a time.
The two-slit interference experiment shows that quantum entities like photons or electrons don't actually exist in a well-defined state until they are observed. Until they are observed, they exist simultaneously in the range of all their possible states, or in a "superposition of states". Once they are observed, the observation causes a "collapse of the wavefunction" or "decoherence".
Superposition of states was discussed earlier in this document and then ignored, partly because it was baffling and it was hard to see what to make of it. John Wheeler was a neighbor of Einstein's in Princeton, New Jersey. Wheeler had a cat that for some reason decided to include Einstein's house in its turf, and Einstein was always bringing the cat back to Wheeler's house. Wheeler, half-jokingly, suggested that this scenario provided a quantum-mechanical parable along the lines of Schroedinger's Cat. Schroedinger's Cat was half-alive, half-dead; Wheeler's Cat was in two places at once -- a neat trick, even for a cat.
However, as it turns out, even though superposition of states is baffling, something can actually be made of it. Up until 1985, superposition of states was generally a puzzle for theorists. In that year, following up on hints provided by Feynman, a British physicist named David Deutsch (born 1953) of the University of Oxford published a paper that suggested that superposition of states could be put to use in a "quantum computer".
A conventional computer encodes a bit, a 1 or 0, as the presence or absence of a voltage. A quantum computer, in contrast, uses a quantum-mechanical property of a particle to encode a 1 or 0, for example the spin value or the polarization of a photon. In either case, calculations will be performed on a group of bits, say 32 bits, at one time. 32 bits can be arranged in a total of 4,294,967,296 different ways, allow them to encode that number of different numbers. Suppose a conventional computer were to perform a calculation requiring a test of all possible values that can be represented by 32 bits. It would have to loop through every single value, one at a time.
In contrast, if a 32-bit value were represented by the spin states of 32 electrons or the polarization states of 32 photons, by the principle of superposition of states, all possible 32-bit values would be present at the same time! A quantum computer operating on these 32 particles could test all 4,294,967,296 values in a single calculation, without going in a loop. While adding another bit doubles the number of loops for a conventional computer, even if another bit is added to the calculation in a quantum computer, the calculation would still be done at one time and would take no longer than before. The hardware would have to get bigger, but the computation time would remain the same.
Since the use of the spin state of an electron or polarization state of a photon to represent a bit has vastly different properties from the use of a voltage level to represent a bit, in a quantum computer the bits are referred to as "quantum bits" or "qubits".
* This was a completely mind-boggling idea. It was also a purely abstract proposal at the time; Deutsch not only did not know how to implement a quantum computer, and he didn't really know what could be specifically done with such a technology even if it existed. All he had was a marvelous "what if?" scenario. For this reason, quantum computing remained little more than an exotic theoretical toy for almost a decade. Researchers figured out examples of tasks that a quantum computer could execute, but these tasks were trivial and of little practical value.
That changed in 1994, when Peter Shor (born 1959) of Bell Labs came up with a practical algorithm that could be implemented with a quantum computer: fast factoring of large numbers. Two years later, his colleague Lov Grover, working from Shor's research, came up with a second practical algorithm: a fast technique for searching for the location of a specific value in an unsorted list of values. Grover announced an even more efficient scheme in the summer of 2000.
Neither of these algorithms actually got a result in a single step using a quantum computer, but they were far more efficient than comparable calculations performed on a conventional computer. For example, while the average number of searches to find a specific entry in a list of N items is no better than N/2 with a conventional sequential search, with Shor's scheme it is SQRT(N). As it turns out, both these algorithms are potentially very useful for "cracking" modern digital encryption schemes in a hurry, and so "black" organizations that work with codes and ciphers are very interested in quantum computing.
Nobody's actually built a real quantum computer yet. Controlling individual particles or small groups of particles is very difficult, and to make matters worse the qubits have to be isolated from the environment to achieve a superposition of states; any interaction with the qubits immediately causes their states to be resolved. The "decoherence" problem gets more troublesome as more qubits are used at one time.
Researchers are painfully nailing down the technological steps pieces needed to build a quantum computer. Much recent research has focused on using atoms or molecules to implement qubit storage. For example, in 2000 a team from IBM and Stanford University announced that they had developed a quantum computer that used a five-atom fluorine molecule to perform a two-qubit quantum calculation. The qubit value was encoded by the spin states of the atoms in the molecule, with the spin states ultimately sensed by nuclear magnetic resonance (NMR) measurements. Two of the atoms were used for qubit storage, while the other three were used to evaluate the operation.
An actual quantum computer will require thousands of qubits to be useful, including a large number of bits simply for error correction. Nobody believes that the approach of sensing the spin states of molecules with NMR is useful for much more than demonstrating that quantum computing is possible, but other schemes are being investigated, based on manipulation of magnetic flux states in superconducting loops; or single photons fed through optical elements; or single-electron transistors.
So far, all demonstrations of quantum computing techniques have been just that, demonstrations, and a long way from practical technology. Some critics have compared quantum computing to cold fusion, suggesting it has very little basis in reality. Others have more generously suggested it's more like hot fusion, meaning that it's clearly possible in principle -- but there's no reason to believe that it will ever be practical.
* At the same time that work was being done to puzzle out quantum computers that might be able to crack existing codes and ciphers, work was being done on technologies also based on quantum physics that could produce an unbreakable cipher.
Actually, unbreakable ciphers have been around since the end of the First
World War. In modern terms, computer data of any sort is transmitted as a
sequence of 1s and 0s, for example:
110010001010100000010101111010 ...
These might be broken into groups to represent letters, or numbers, or color
values of a dot of an image. Now suppose that there are two friends, Alice
and Bob, and Alice wants to send Bob a message that must be kept completely
private. If she toggles the bits in her message -- switching 1s for 0s and
0s for 1s -- in a completely random pattern, then she will have scrambled her
message to complete random noise that is impossible to crack. If she was
careful to write down what bits she toggled and what bits she didn't, using a
0 for no toggle and a 1 for a toggle, then she would be able to send this
"key" to Bob to tell him how to extract the message. For example:
message: 110010001010100000010101111010 ...
key: 111000101001110001011010100010 ...
_______________________________________________________
scrambled message: 001010100011010001001111011000 ...
If an eavesdropper, named say "Eve", gets hold of the scrambled message,
there's nothing she can do with it: it's just complete gibberish. However,
there's two problems with this scheme. The first is obvious: how does Alice
get the key to Bob without Eve getting her hands on it?
The second is not so obvious: every message Alice sends Bob has to have its own unique completely random key. If Alice sends two messages to Bob that have been scrambled with the same key, Eve can then try every possible key on both messages until she gets a key that gives sensible text in both messages. If only one message was sent with one key, Eve would not be able to pull this trick: she could try keys until she got something that made sense, but since she really is trying to read random noise, she would get any number of entirely arbitrary messages out of it.
* In any case, this is known as a "one-time key" cipher. Despite the fact that it's been around for the better part of a century, it tends to be used almost exclusively for very high level communications, because of the difficulty of getting a unique set of cipher keys to recipients. Quantum physics offers a way around this problem.
According to quantum physics, a polarization filter doesn't actually just pass photons with polarization at the same angle as the orientation of the filter. There is a probability of passing a photon at some angle off to the sides of the orientation angle, with this probability falling off to zero as the difference in angle goes to 90 degrees.
In other words, if the filter is oriented vertically, it will always pass a photon with the same vertical polarization and never pass a photon with a horizontal orientation. Similarly, if the filter is oriented horizontally, it will always pass a photon with horizontal polarization and never pass a photon with vertical orientation. Changing the orientation of the filter, then, will always allow distinguishing between a photon with vertical polarization and a photon with horizontal polarization. However, suppose a photon is sent at an angle of 45 degrees between the vertical and horizontal. It will be passed by a vertical filter half the time, and it will be passed by a horizontal filter half the time.
In the early 1980s, a physicist named Charles H. Bennett (born 1943), who was working for IBM at the time, decided that the quantum quirks of the polarization of light might provide a secure way for Alice to send Bob a secure one-time key. He was following ideas produced some years before by a friend named Stephen Weisner who had come up with a quirky theoretical idea for using quantum physics to generate serial numbers for money that couldn't be counterfeited. Bennett chatted up his own ideas with Gilles Brassard (born 1955), a computer scientist at the University of Montreal, and the two decided that the whole mad scheme might actually be implemented.
To explain the idea, let's assume that Alice filters light so that she ends up with photons polarized in only four directions: vertically, horizontally, +45 degrees, and -45 degrees. She designates these four polarizations as "V", "H", "P (plus)", and "M (minus)". In the Bennett-Brassard quantum cryptography scheme, Alice will send single photons to Bob, selecting one of the four polarization schemes at random. Bob will measure the polarization of the photons using a filter set vertically or at 45 degrees, also at random, and write down the results.
After sending an extended sequence of these polarized photons, Alice will phone Bob and tell him what the proper filter orientations should have been to measure the polarizations of individual photons. She doesn't tell him what the actual polarization of a photon was (V or H, or P and M). Bob tells Alice which photon polarizations he measured correctly. When they're done, they agree to ignore all the photons whose polarization was measured incorrectly. For those that were measured correctly, they agree to each assign a value of "1" to V and P photons and a value of "0" to H and M photons. They don't tell each other which photons were assigned which value, but since they both know the actual polarizations of these photons, they will come up with the same values. This sequence of 1s and 0s is then used as the one-time key.
The beauty of this scheme is that if Eve is intercepting the photons, it will do her no good. She will have to set her filter polarizations at random and will get an entirely different set of results from Bob. Eve could relay her results on to Bob, but her results aren't the same as those sent by Alice. If Eve taps into the conversation between Alice and Bob in which the filter polarizations are discussed, it does her no good. If she didn't intercept the photons, they're long gone, and if she did, Alice and Bob won't agree on the one-time key and the result of enciphering will be gibberish.
* The Bennett-Brassard scheme sounded nice on paper, but could it be made to work in practice? In 1988, Bennett and one of his students, John Smolin, managed to send a quantum-encrypted message between two personal computers, appropriately named "Alice" and "Bob", and read it properly. The distance between the two computers was only 30 centimeters (a foot), but other researchers have been steadily increasing the distance between transmitter and receiver, reaching distances of tens of kilometers so far.
So far, these have been strictly demonstrations, and aren't really practical secure quantum-cryptography systems. Sending and receiving single photons is very difficult, so they sent pulses of polarized photons instead. This opens the possibility that Eve could use a half-silvered mirror, set at an angle to the line of transmission of the pulse, to divert part of the pulse and let the rest through. Eve could then test the polarization of the diverted portion of the pulse without disturbing the portion of the pulse that went through the mirror. The probability that Eve can successfully sample the pulse in this way increases with the size of the pulse, and at some size of pulse the security of the system is lost completely. On the other hand, reducing the size of the pulse reduces the range over which it can be sent.
It is unclear how far a single photon might be transmitted, but the length of a system could be multiplied by adding "repeaters" at intervals. The photon itself can't be regenerated by the repeater without measuring it and corrupting the quantum cryptography scheme, but the message could be securely enciphered and deciphered between each set of repeaters, with the full transmission consisting of a chain of such sessions.
* There's another angle on implementing a quantum cryptography scheme, but it requires a substantial conceptual leap into the realm of what is known as the "EPR paradox" or, more or less equivalently, "quantum nonlocality".
As mentioned in the initial chapters of this book, although Einstein eventually agreed that quantum physics was correct, he continued to insist that it wasn't complete, that there was something left out. In 1935 he published a paper co-authored by his assistant, Nathan Rosen (1909:1995), and another physicist, Boris Podolsky (1896:1966). The paper became known as the "EPR paper" after "Einstein-Podolsky-Rosen". The EPR paper imagined the simultaneous generation of two particles that had interlinked properties -- for example, two electrons with opposed spins, or two photons with polarizations at right angles to each other. Entangled photons with a right-angle polarization relationship can be generated, for example, by electron-positron annihilation, which produces gamma-ray photons; or, more practically, by shining a laser beam through certain types of optically-active crystals.
The two particles propagate in opposite directions. Their state is unknown until one is measured, to obtain its spin or polarization as the case may be -- but then the state of the other one is known, no matter how far away it is. Erwin Schroedinger described the photons as "entangled". This "EPR paradox" seemed to violate Einstein's theory of relativity, which stated that nothing can travel faster than the speed of light, or in other words implied "quantum nonlocality". He referred to this notion as "spooky action at a distance."
Einstein said the EPR paradox showed that the photons were not actually undefined before they were measured, with their state specified by "hidden variables". Pauli and Heisenberg were outraged; Niels Bohr was all but in shock, but he rallied to wrote a detailed refutation of the EPR paper. However, at the time the argument was basically philosophical, something of a matter of opinion, a science-fiction notion that couldn't be tested, and that was essentially all it was for three decades.
In 1951 David Bohm (1917:1992), a left-leaning American physicist who had gone to work in Britain because of the Red Scare hysteria back in the US, published a refined version of the EPR paradox, but his work had little impact at the time. However, beginning in the 1970s devious experiments showed that the quantum nonlocality was the way things actually worked.
Quantum nonlocality would seem to suggest schemes of faster-than-light communications, but quantum nonlocality makes no such concession. Suppose that a pair of entangled photons are sent in different directions: one is received by Alice, who uses a filter to determine its polarization, and the other is received by her friend Bob, whose photon's polarization will also be determined when hers is.
As mentioned, before measurement the state of the photons is indeterminate. Alice can do a measurement to determine the photon's state, which will resolve the state of Bob's photon as well, but the catch is: Alice cannot control the outcome of the measurement. There is no way to send Bob any information using this phenomenon. It's as if Bob and Alice are shown a cube of gold and a cube of lead, and the cubes are then put into identical boxes. The two boxes are shuffled around so Alice and Bob can't remember which is in which box, and then each is given a box. If Alice opens her box and finds gold, she then knows that Bob has lead. Big deal. There is no communication of any information between Alice and Bob in this case.
This scenario is not quite the same as the EPR paradox, which adds the, shall we say, fascinating aspect that the contents of the boxes are undefined -- a half probability of gold, a half probability of lead -- until Alice opens her box, in which she finds gold while lead appears in Bob's box, or she finds lead while gold appears for Bob. Of course, while this is a useless scheme for faster-than-light communications, it works out very well, at least in principle, for quantum cryptography.
Suppose Alice and Bob both have "tanks" of entangled photons. Alice can then measure the polarizations of photons in her tank, reporting to Bob over a clear channel which one of the set she measured and how she measured it. Bob can then measure the polarizations of his own photons. The orientation of the polarizations of the photons can then be used to determine a mutually-agreed cipher key without trading any information that could be intercepted by an eavesdropper.
* Incidentally, although using quantum nonlocality for cryptography is a fairly obscure subject, the phenomenon has picked up a lot of publicity because it also implies what is called, somewhat confusingly, "quantum teleportation". Bennett proposed the scheme and it works as follows:
It should be noted that this only transfers the state of Alice's electron as it was at the time of the interaction; the interaction changes its state. It is as though it were "teleported" from Alice to Bob, hence the name of the process.
It should also be noted, as Bennett has insisted, that this scheme doesn't imply faster than light communications. Bob cannot check periodically on his photon without disturbing its state and destroying the entanglement, so he has to be tipped off by Alice after she does her own measurement, and he cannot figure out the state of his electron without knowing the results of Alice's experiment. Alice cannot communicate this information to him faster than the speed of light. Even if she could, quantum teleportation only really works for simple quantum entities, and it is hard to see how it could be scaled up to more complicated things. As some of those working in the field have suggested: "It's teleportation, Jim, but not as we know it."
* The notion of quantum nonlocality leads to challenges to the traditional status quo of quantum physics. As mentioned, for decades nobody thought the EPR paradox could ever be anything more than a thought experiment. One physicist who was interested in testing it said that in his student days he suggested the idea to Dick Feynman. Feynman, in his usual gentle way, bluntly told him to get out of his office.
In 1965, a brilliant physicist from Belfast named John S. Bell (1928:1990) came up with a persuasive if subtle proof that it was possible in principle to test the EPR paradox by analyzing the pattern of correlations of entangled photons or other quantum entities received at two distant locations. If the EPR experiment was true, the statistical results would be clearly different than if it wasn't. Bell saw this as basically an impractical thought experiment, but by the 1970s researchers had actually performed the experiment. Early efforts gave somewhat ambiguous results and were not accepted by all, but by the early 1980s a team led by the French physicist Alain Aspect (born 1947) had conducted experiments that the critics were hard-pressed to ignore.
Einstein would have not necessarily been all that happy at the result. He had been trying to attack quantum physics, and though the results showed that there could well be hidden variables, but that nonlocality had to be accepted along with them.
* In fact, by the 1970s researchers were beginning to conduct experiments that few of the founders of quantum mechanics would have been believed even possible in theory. Nowdays physicists can perform experiments on single atoms, trapped in beams of laser light; or single electrons; or single photons. One of the premises of the statistical interpretation of the wavefunction was that it focused on systems of large numbers of quantum entities. That was, after all, the only thing that could be dealt with at the time. The fact that quantum entities can now be isolated as individuals doesn't necessarily overthrow the probabilistic nature of quantum physics, but it does complicate matters.
One interesting experiment along such lines challenged the long-standing concept of wave-particle duality. The classic two-slit experiment isn't the only way to demonstrate quantum weirdness. Another scheme is to fire photons at a half-silvered mirror set at a 45-degree angle to their path of flight, with the mirror acting as a "beam splitter", sending photons straight through half the time and off at a right angle the other half of the time. If a photon detector is placed at the end of each path, the two detectors will confirm that the photons are acting like particles, counting them up one by one. If mirrors are used to focus the two paths back on a beam splitter, recombining them, then the classic interference pattern will emerge.
This is really just a sideways variation on the two-slit experiment. However, in the early 1990s a group of Indian researchers proposed a devious modification of the experimental setup, factoring in a new test by replacing the half-silvered mirror with two prisms, separated by a very narrow air gap, narrower than a wavelength of the light involved. As a particle, the photon wouldn't be able to jump the gap; as a wave, it would tunnel across the gap. If a photon detector was placed along each of the two paths produced by the prismatic beam-splitter, what would it record?
A Japanese team gave it a try, employing some very tricky techniques to establish the sub-microscopic air gap, and found out that they got the same results as they did if they had a half-silvered mirror, the photon going one way or another. The issue of this result was that if light were strictly acting as a particle, it would only go through one path all the time, the particle not being able to tunnel across the gap; and if it were strictly acting as a wave, it would go through both paths at the same time. The actual results fit neither of these scenarios, meaning the photons were being seen operating as both particle and wave at the same time.
Nobody is very sure what this means, except for the fact that it undermines the classical notion of wave-particle duality. Saying that an experiment designed to detect photons as particles will pick up particles and one designed to pick of photons as waves will pick up waves makes a certain sort of sense. Saying that an experiment designed to detect photons as both particles and waves will detect both really makes matters confusing.
However, the new experiments have done much to break the stranglehold of Bohr's Copenhagen interpretation on quantum physics. The next chapter discusses the alternative concepts now being debated.