by Seth Lloyd
Not only can atoms emit light, they can also absorb it. Just as an atom can jump from a higher energy state to a lower one, emitting a photon in the process, an atom can absorb a photon and jump from a lower energy state to a higher one. Take an atom in its ground state and bathe it with a beam of laser light made up of photons whose energy is equal to the difference in energy between the ground state and the next-lowest energy state (called the first “excited state”) of the atom. The atom will absorb a photon from the beam and jump from the ground state to the first excited state.
If the atom is bathed by photons whose energy is not equal to the energy difference between the state it’s in and some higher energy state, then it will not absorb the photons. Atoms can absorb energy only in specific chunks (quanta). This feature is useful for controlling the state of atoms. If the atom is bathed with photons of the wrong energy, it refuses to absorb any photons and will just stay where it is, whereas if an atom is bathed with photons whose energy equals the difference in energy between its current state and some higher state, the atom will happily absorb a photon and jump to that state. The fact that atoms respond to light only at frequencies corresponding to their spectrum is useful if you want to send instructions to one kind of atom but not to another, as we will see.
Going from state to state by emitting or absorbing a photon takes a characteristic amount of time that depends on the intensity of the laser beam. In particular, it is possible to subject an atom to a pulse of laser light with the following result: if the atom is in its ground state, it jumps to the first excited state, absorbing a photon in the process; and if the atom is in its first excited state, it jumps to the ground state, emitting a photon in the process. The ground and first excited state of an atom correspond to a bit. We can take the ground state to correspond to 0 and the first excited state to correspond to 1. But the atom is not just a bit; it is a qubit. The atom’s states correspond to waves, just like the states of the nuclear spins described earlier. So in keeping with our practice of bracketing quantum-mechanical things, we call the ground state |0> and the first excited state |1>. Applying a laser pulse to the atom takes |0> to |1> and takes |1> to |0>. In the language of atoms, the atom is simply going from state to state; in the language of zeros and ones, this is the famous logic operation called NOT. By speaking the language of atoms, we can make an atom flip its bit.
How do we get the atom to talk back to us? Just as we can address the atom using light, the atom can talk back to us using light. Imagine a third state, |2>, higher in energy than the qubit states |0> and |1>. Suppose that whenever the atom is in state |2>, it tends to jump back to |0>, the ground state, spontaneously emitting a photon in the process. Spontaneous emission of photons is responsible for the phenomenon known as fluorescence. A fluorescent light works by exciting atoms out of their ground state and letting them jump back, emitting light in the process. The energy of the emitted photon is equal to the difference in energy between the state |2> and the state |0>. If you look closely—through a microscope, for instance—you can sometimes see the emitted photon as a flash of light. The atom is talking to you.
Figure 11. Flipping Qubits
a
b
c
To flip a quantum bit, simply shine light on it. Figure 11a shows a qubit—a nuclear spin—in the state spin-up, or 0. In figure 11b a particle of light, or photon, arrives. It is absorbed by the nuclear spin, flipping it to the state spin-down, or 1, in the process (figure 11c).
The ability to see spontaneously emitted photons allows us to determine whether or not the atom is in the ground state. Bathe the atom with light made up of photons each of whose energy is equal to the energy difference between the states |0> and |2>. If the atom is in the ground state, then because the photons in which it is bathed have just the right energy, it will absorb a photon and go to state |2>. Shortly afterward, it will emit a photon and jump back to the ground state. Then it will absorb another photon and jump back up to state |2>. Then it will emit a photon and jump back to the ground state. Such a process, in which an atom keeps on absorbing and emitting photons, is called a “cycling transition,” because the atom cycles back and forth between two well-defined states.
If the atom starts out in the state |1>, by contrast, then it can’t absorb a photon and go to the state |2>, because the photons available have the wrong energy. An atom starting in the state |1> will simply stay there, impervious to the bath of photons, not fluorescing. An atom that fluoresces is saying, in effect, “I’m 0! I’m 0! I’m 0! I’m 0!”
Now look more closely at how atoms jump from state to state when zapped by a laser. Start an atom off in its ground state and bathe it in light made of photons whose energy is equal to the difference in energy between the ground and the first excited states. What happens during the jump? During the jump, the atom and the light are in a state that is a superposition of the ground state of the atom, with no photon absorbed from the bath, and the first excited state of the atom, with one photon absorbed. That is, the state of the atom is a superposition of two waves. The first wave is the ground state and the second wave is the first excited state. Just after the atom begins its bath and starts its jump, the superposition is made up mostly of the ground state, with only a little bit of the excited state mixed in. Halfway through the jump, the atom and bath are in the equal superposition state |0, no photon absorbed> + |1, photon absorbed>. Near the end of the jump, the superposition is mostly the excited state, with only a little bit of the ground state remaining.
An atom does not instantaneously jump from its ground state to its excited state. Rather, it glides through a continuous intermediate sequence of superpositions. The same continuous gliding occurs when an atom goes from the first excited state back down to the ground state, emitting a photon in the process. The atom and the bath of photons start out in the state |1, no photon emitted> and end up in the state |0, photon emitted>. Halfway through the jump, the atom and the bath are in the superposition state |1, no photon emitted> + |0, photon emitted>.
This description of an atom rotating from one state to another while absorbing and emitting photons is reminiscent of the earlier description of a nuclear spin rotating from one state to another while interacting with a magnetic field. And in fact, these two processes are essentially the same. As a nuclear spin rotates, it, too, absorbs a photon—from the magnetic field—and emits a photon as it returns to its original state.
Now you know how to talk to atoms. By zapping an atom with a laser, you can control its state. You can continuously rotate the atom through a sequence of superposition states; you can excite it, causing it to absorb a photon, and de-excite it, causing it to emit a photon. You also know how to make the atom talk back. By driving cycling transitions, you can ask an atom whether it registers 0 or 1, and you can get a response. All of this means that you now have the power to create new bits.
Take an atom and zap it with a laser to put it in the superposition state |0> + |1>. Now drive a cycling transition to see if it is in the state 0 or the state 1. If it is 0, the atom will fluoresce; if it is 1, it will remain dark. You have tossed the quantum coin to create a brand-new bit.
Talking to an atom by driving a cycling transition measures the state of the atom and creates information. Of course, just as in the last chapter, what happens during the measurement is open to interpretation. In the wave-function-collapse interpretation of measurement, the wave function of the atom taken together with the photons has collapsed to either the state |0, fluorescence> or to the state |1, no fluorescence>.
In the decoherent-histories interpretation, the state of the atom together with the photons is in the superposition state |0, fluorescence> + |1, no fluorescence>. Each of the states in the superposition corresponds to a decoherent history. In this case, the histories are highly decoherent. To make them cohere would require that you collect all the photons emitted by the atom, reflect them back, and force the atom to reabsorb them. You would need a kind of Losc
hmidt’s demon, capable of reversing the sequence of events in time. But reversing photons that are scattering all over the universe is hard (if you doubt it, then go ahead, reverse them). So, because the two states in the superposition decohere, the atom and photon behave as though they are in one state or the other, and you do indeed generate a brand-new bit, one that never existed before.
Quantum Computation
If you zap an atom with light whose photons have the right energy, you can make the atom flip its state from |0> to |1> and back again. You are flipping the atom’s bit. In other words, you are performing the logical operation known as NOT. In a 1993 article in Science entitled “A Potentially Realizable Quantum Computer,” I showed how a slightly more involved set of laser pulse sequences than those used to perform NOT operations allows atoms to perform the logic operations AND, OR, and COPY, as in conventional digital computations. Each atom stores one bit, and a collection of atoms can compute anything an ordinary PC or Macintosh can compute.
But they can do much more than an ordinary PC or Macintosh. Atoms register more than bits; they register qubits. Unlike classical bits, qubits can be in quantum superpositions of |0> and |1>; that is, they can register 0 and 1 at the same time. Is there any way these quantum superpositions can be used to compute in ways that classical computers cannot? This question was first raised by David Deutsch in the mid-1980s, but it was not until the early 1990s that the question was definitively answered. The answer is Yes.
To see why quantum computers and quantum bits can do more than classical computers and classical bits, think about what bits do in a computer. Some bits, like those in the computer’s hard drive or memory, just store information. For example, bits in my computer’s memory receive and store this text as I type it. Other bits, like those in computer programs, are instructions or commands. They tell the computer to do one thing or another. Whether a bit functions as a memory bit or a command bit depends on the context in which it is used.
Consider a bit the computer interprets as a command: 0 means “Do this!” and 1 means “Do that!” “This” could mean, say, “Add 2 plus 2” and “that” could mean “Add 3 plus 1.” Or “this” could mean “Send an e-mail” and “that” could mean “Fire up the Web browser.”
Unlike a classical bit, a quantum bit can register 0 and 1 at the same time. What does a quantum computer do when it tries to interpret such a qubit as a command? The 0 part of the superposition is telling the quantum computer to “Do this” while the 1 part of the superposition is telling the quantum computer to “Do that.” How does the quantum computer decide? It doesn’t. Instead, it does “this” and “that” at the same time! Just as a quantum bit can register two values at once, a quantum computer can perform two computations simultaneously.
David Deutsch called this strange ability of a quantum computer to do two things at once “quantum parallelism.” Quantum parallelism is quite different from ordinary classical parallel computation. A classical parallel computer consists of several processors linked together. In a classical parallel computation, one processor performs one task while the other processors perform other tasks. In quantum parallelism, a single quantum processor performs several tasks at once.
This ability to do two things at once is intrinsic to quantum mechanics. The photon in the double-slit experiment can go through both slits at once; a qubit can register 0 and 1 at the same time; and a quantum computer can perform two distinct tasks simultaneously. The ability to do two things at once arises from the wave nature of quantum mechanics. Each possible state of a quantum system corresponds to a wave, and waves can be superposed.
We’re all familiar with situations in which superposing waves results in qualitatively new and richer phenomena. Consider sound waves. A wave wiggling up and down at a particular frequency corresponds to a pure tone. A sound wave wiggling up and down 440 times per second is the sound of the note A above middle C. A sound wave wiggling up and down 330 times per second is the sound of the note E above middle C. The superposition of these two waves corresponds to a chord, which is qualitatively different from and richer than the sound of either pure tone taken by itself. The richness of the sound arises from the way in which the two pure notes interfere with each other.
A classical computation is like a solo voice—one line of pure tones succeeding each other. A quantum computation is like a symphony—many lines of tones interfering with one another. This interference phenomenon is what gives quantum computation its special qualities and added power.
Quantum computations are not restricted to just two “voices.” Like a symphony, a quantum computation gains its power by building up intricate sequences of chords. For example, suppose the computer is given as input a “qutrit,” with three possible states, 0, 1, and 2. The 0 state instructs the quantum computer to “do this,” the 1 state instructs it to “do that,” and the 2 state instructs it to “do the other thing.” In the example in which “this” means “Add 2 plus 2” and “that” means “Add 3 plus 1,” “the other thing” might be “Add 4 plus 0.” When the quantum computer is given a superposition of all three instructions as input, it does “this,” “that,” and “the other thing” all at once. In our example, the computer is simultaneously exploring all ways of constructing 4 as the sum of non-negative integers. Such a quantum computation is like a trio, in which three waves interfere with each other and three computational “voices” cooperate to deconstruct the number 4 faster than one computational voice could on its own.
The number of things a quantum computer can do at once—the number of voices in the symphony of quantum computation—grows rapidly as the number of bits of input increases. Even a small number of qubits allow an extraordinarily rich texture of interfering waves as they compute. A quantum computer given 10 input qubits can do 1,024 things at once. A quantum computer given 20 qubits can do 1,048,576 things at once. One with 300 qubits of input can do more things at once than there are elementary particles in the universe. Quantum parallelism allows even a relatively small quantum computer, containing only a few hundred qubits, to explore a vast number of possibilities simultaneously.
The Measurement Problem, Again
What happens when you take a quantum computer that is doing several things at once and ask it what it’s doing? Is it possible to take a measurement to determine if it is doing this, that, or the other thing? As with any quantum system, when you take a measurement in a superposition of several possible states, the result of the measurement yields one of those possibilities at random. So if the quantum computer is exploring all the ways of constructing 4 as the sum of positive integers, when you measure it, it will tell you, for example, “Oh, I was adding 3 plus 1,” or “I was adding 2 plus 2.”
To pursue the metaphor of quantum computation as symphony: If you measure the quantum computer while it is computing, you don’t hear the full effect of the orchestration; rather, you hear one of the voices selected at random.
Recall the double-slit experiment. In that model, the electron does two things at once: it goes through both slits simultaneously. When you take a measurement to determine which slit the electron has gone through, it will show up at one slit or the other at random. Similarly, when you take a quantum computer that is doing two things at once and measure to see what it’s doing, you will find it doing one or the other of those things at random. If you want to see the interference pattern in the double-slit experiment, you must wait until the electron has hit the screen, so that the two waves—one from one slit, one from the other—can interfere with each other. The interference pattern comes from the “duet” of the two waves. In a quantum computation, if you wish to get the full benefit of the computation, you must not look at the computation while it is occurring. To get the full symphonic effect of a quantum computation, you must let the all the waves in the computation interfere with one another. You must let the “voices” of the computation blend together on their own.
One way of looking at this phenomenon i
s to say that measuring a quantum computer that is doing several things at once “collapses the computer’s wave function,” so that it ends up doing just one thing. Another way of describing the effect of such a measurement, though, is to say that it “decoheres the computation.” As discussed earlier, decoherence does not suppose that the alternate possibilities have entirely gone away, rather that they still exist, but no longer affect the state of the system as we know it.
Note that a full-blown measurement is not necessary to decohere a quantum computation. Any passing electron or atom that interacts with the quantum computer in such a way as to get information about what the quantum computer is doing can decohere the computer as effectively as a full-blown measurement using a macroscopic measuring device. Great care must be taken to insulate quantum computers from their surroundings while they are performing quantum computations.
Factoring
Quantum parallelism makes quantum computers potentially very powerful. A quantum computer can explore all possible solutions to a hard problem at the same time. An example of such a problem is factoring. A number is factorizable if it can be written as the product of two or more integers greater than 1. For example, 15 is factorizable because it can be written as 3 times 5. But 7 is not factorizable, because the only way it can be written as the product of two positive integers is 7 times 1. Numbers that are not factorizable are called prime numbers, or primes. The first few prime numbers are 2, 3, 5, 7, 11, 13 . . . It’s not hard to show that there are an infinite number of primes.
Take two large prime numbers, each with 200 digits, and multiply them. The result is a 400-digit number. Multiplying two 200-digit numbers is tedious, but it’s a straightforward task for a digital computer, classical or quantum. Take the resulting 400-digit number, hand it to someone who doesn’t know the original two prime numbers, and ask him to factor it. The 400-digit number is clearly factorizable, and if you know the two 200-digit factors, it is straightforward to verify that they can be multiplied together to give the proper 400-digit result. But finding those two factors if you don’t know them beforehand proves daunting. In fact, the only known way to find those factors is, essentially, to examine all possible 200-digit numbers in turn until you find one that divides the 400-digit number. (There are tricks allowing you to eliminate some numbers from consideration, but they don’t help that much.) Unfortunately, there are a lot of 200-digit numbers. To use our favorite large number, there are more 200-digit numbers than there are elementary particles in the universe.