Programming the Universe

by Seth Lloyd

  The Heisenberg uncertainty principle expresses a trade-off between the degree of certainty about the value of one physical quantity, such as position, and a complementary quantity, such as speed. The more certain the value of one quantity, the less certain the value of the other. As a consequence, any procedure (such as measurement, or observation) that makes the value of some physical quantity more precise inherently makes the value of the complementary quantity less precise. Again, measurement tends to disturb the system measured.

  This perturbing aspect of the Heisenberg uncertainty principle has become deeply embedded in popular lore. For example, the uncertainty principle is sometimes invoked, incorrectly, to explain why anthropologists intrinsically alter the societies they set out to investigate. (As in the expression, “When the anthropologist comes in the door, the truth flies out the window.”) In fact, the Heisenberg uncertainty principle typically makes a difference only at very small scales, such as the atomic scale. Even the most probing investigations by anthropologists occur in a realm much too large to allow the uncertainty principle to kick in.

  Flipping Qubits

  It’s not hard to flip a quantum bit, or qubit. Recall from the example of the spin-echo effect that when you put a nuclear spin in a magnetic field, the spin precesses about that field. Take a spin that’s initially spin-up (or |0>) and apply a field facing toward you. After half the time it takes for the spin to precess all the way around, it has precessed to the spin-down state, |1>. (Likewise, if the spin starts out down, or |1>, after the same amount of time it will precess to the spin-up state, |0>.) By applying the magnetic field, you flip the qubit.

  By varying the amount of time for which you apply the magnetic field, you can also put the spin in a variety of superpositions. For example, start with the spin in the state spin-up and apply the field for one-quarter of the time it takes to precess all the way around; the spin is now in the state spin sideways to the right, or |0> + |1>. Or start with the spin-up state and apply the field for three-quarters of the time it takes to precess all the way around; the spin is now in the state spin sideways to the left, or |0> - |1>. By applying the magnetic field for different amounts of time, you can rotate the spin into any desired superposition of states.

  These single-qubit rotations are the quantum analogs of single classical bit transformations, such as bit-flip, or NOT. Because of the existence of superpositions, there are many more transformations that can be applied to a quantum bit than to a classical bit. One thing classical and qubit transformations have in common, though, is that each is a one-to-one transformation. It’s straightforward to reverse the action: just rotate the qubit back along the same axis in the opposite direction. Like the transformations allowed by classical physics, the rotations of a qubit preserve information.

  Now look at interactions between qubits. Consider a two-qubit transformation that is a quantum analog of the controlled-NOT logic operation described earlier. Recall that the controlled-NOT operation flips one bit if and only if the other bit is 1. That is, the controlled-NOT takes 00 to 00, 01 to 01, 10 to 11, and 11 to 10. The controlled-NOT operation is one-to-one and can be reversed simply by applying it twice. The quantum controlled-NOT takes the quantum states |00> to |00>, |01> to |01>, |10> to |11>, and |11> to |10>. Here, the state |00> corresponds to the “joint wave” of the two quantum bits taken together, in which the first qubit is in the state |0> and the second qubit is also in the state |0>.

  The preceding paragraphs form the basis for quantum computation. Later, we’ll see that rotations of individual quantum bits, together with controlled-NOT operations, constitute a universal set of quantum logic operations. Recall that AND, OR, NOT, and COPY make up a universal set of classical logic operations; any desired logical transformation can be built up from these basic elements. Similarly, any desired transformation of a set of quantum bits can be built up out of single-qubit rotations and controlled-NOTs. This universal feature can be used to perform arbitrarily complicated quantum computations. But first, let’s use the universal character of rotations and controlled-NOTs to investigate how processes such as measurement and decoherence actually work.

  Qubits and Decoherence

  The state |0> + |1> is a qubit analog of the state of the particle in the double-slit experiment in which it is going through both slits at once. The state of the particle going through the slits also corresponds to a quantum bit. If |left> corresponds to the state in which the particle goes through the left-hand slit and |right> corresponds to the state in which the particle goes through the right-hand slit, then |left> + |right> is the state in which the particle goes through both slits at once.

  A qubit such as a nuclear spin can be placed in the state |0> + |1> (corresponding to the particle going through both slits at once) by preparing a spin in the state spin-up (|0>) and rotating it one-quarter of a turn, into the state |0> + |1>. Similarly, you can verify that the qubit is in the desired state by rotating the spin back one-quarter of a turn and measuring its state (e.g., with a Stern-Gerlach apparatus) to verify that it has been returned to its original state.

  Now take a second qubit, initially in the state |0>. Just as the first qubit is an analog to the position of the particle, this second qubit is an analog to the detector. Perform a controlled-NOT op on this qubit, using the particle bit as the control. The controlled-NOT flips the detector qubit if and only if the particle qubit is in the state |1>, corresponding to the particle going through the right-hand slit. But this particle qubit is in the superposition state |0> + |1>. The quantum controlled-NOT operation acts like a classical controlled-NOT on each component of this superposition. In the part of the superposition in which the particle qubit is in the state |0>, corresponding to the particle going through the left-hand slit, the detector qubit remains in the state |0>. In the part of the superposition in which the particle qubit is in the state |1>, the detector qubit is flipped from |0> to |1>. Taken together, after the controlled-NOT, the two quantum bits are now in the state |00> + |11>. In one component of the superposition, particle and detector qubits are both |0>. In the other component, they are both |1>. The controlled-NOT operation correlates the two quantum bits.

  In the course of the controlled-NOT operation, information in the first qubit has spread to and “infected” the second qubit; that is, the controlled-NOT operation has created mutual information between the two qubits. The second qubit now possesses information about whether the first qubit is |0> or |1>.

  The controlled-NOT operation has also disturbed the first qubit. Suppose you try to verify that the first qubit is still in the state |0> + |1> by rotating the nuclear spin back a quarter of a turn and measuring to see if it is in the state spin-up. When you make this measurement, you find that half the time the spin is in the correct state, spin-up, and half the time it is in the incorrect state, spin-down. The particle qubit is no longer in the state |0> + |1>. In the process of correlating the particle qubit with the detector qubit, the controlled-NOT operation has completely randomized the state of the particle qubit.

  Like its classical counterpart, the quantum controlled-NOT allows one bit to obtain information about another. But unlike its classical counterpart, the quantum controlled-NOT typically disturbs the bit about which information is obtained. This disturbance is intrinsic to processes in which one quantum system gets information about another; in particular, the quantum measurement process typically disturbs the system measured.

  In the example given here, the disturbance can be undone simply by repeating the controlled-NOT operation. Like the classical controlled-NOT, the quantum controlled-NOT is its own inverse. If you perform it twice, you return the qubits to their original state. In particular, a quantum controlled-NOT performed on the state |00> + |11>, with the first qubit as control, does nothing to the |00> component of the superposition and takes the |11> component to |10>. The second (detector) qubit is now in the state |0> and the first (particle) qubit is now in the state |0> + |1>. Rotating the particle
qubit back by a quarter of a turn and measuring gives the result spin-up, verifying that the particle qubit was indeed returned to the proper state.

  Historically, though, the quantum measurement process is taken to be irreversible. Unlike the simple controlled-NOT model of quantum detection given here, conventional interpretations of quantum mechanics, such as Bohr’s Copenhagen interpretation, assume that once a macroscopic measuring apparatus has become correlated with a microscopic system such as a particle, that correlation cannot be undone. In this purported irreversibility of measurement, the reader probably detects an echo of the second law of thermodynamics. In Boltzmann’s H-theorem, you’ll recall, the apparent irreversibility of entropy increase holds only as long as atoms don’t interact in such a way as to undo their correlations and thus decrease their entropies. Similarly, in the quantum measurement process, irreversibility can only be apparent.

  In particular, the underlying dynamics of quantum systems preserve information, just as the dynamics of classical systems do. Because these dynamics preserve information, they can in principle be reversed. Thus there is a quantum-measurement analog of Loschmidt’s objection. Simply reverse the dynamics of the measurement process and the quantum system will be returned to its pristine, undisturbed state. As with the classical controlled-NOT discussed earlier, the second application of the quantum controlled-NOT operation is a realization of Loschmidt’s objection. Analogs of the spin-echo experiment can effectively reverse the dynamics of millions of qubits at once.

  To the (correct) objection to the notion of irreversibility in the measurement process, Bohr might well have replied, like Boltzmann, “Go ahead, reverse it.” Niels Bohr, however, was a gentle person. His response to these objections was instead to obscure the problem of irreversibility by veiling the traditional Copenhagen interpretation in a semantic fog, wisps of which persist to the present day.

  In fact, the idea of the irreversibility of quantum measurement is just as safe as the second law of thermodynamics, true or otherwise. Recall that with the second law, you identify an increase in the entropy of a system by, in effect, betting that the newly made correlations will not be reversed, thus undoing this apparent increase in entropy. If in fact those correlations are reversed, decreasing the entropy of the parts, then you lose your bet: entropy did not, in fact, increase.

  Similarly, in the quantum-measurement process, you provisionally identify the spread of information from the system to the measurement apparatus as irreversible. If it turns out later that the dynamics of the measurement process undo themselves to restore the original state, you simply rescind your identification of the spread of information as an irreversible process. Since most of the time entropy continues to increase and information continues to spread, you rarely have to recant. Occasionally, however, because the laws of physics are reversible, an apparent entropy increase undoes itself and information “unspreads.” Given the underlying reversibility of the known laws of physics, and the existence of phenomena like the spin-echo effect in which entropy does in fact decrease, you may find it conceptually more satisfying to regard the second law of thermodynamics and irreversibility of quantum measurements as probabilistic laws: entropy tends to increase and information is highly likely to spread. But sometimes they don’t.

  Entanglement

  Another difference between the classical and quantum versions of the controlled-NOT is that in the quantum case, information is created, apparently from nothing. Recall the analogous classical process: the particle bit could have been in either the state 0 or the state 1 to begin with; it had one bit of entropy. Here, the qubit is in a well-defined state: its entropy is zero. Of course, the state that the qubit is in, |0> + |1>, is one that has elements of both |0> and |1>: like the corresponding state of the particle in the double-slit experiment, this state is a curious quantum state in which the quantum bit in some sense registers 0 and 1 at the same time.

  When the two classical bits interacted via the controlled-NOT, the entropy in the particle bit infected the detector bit. The two bits were now correlated and the entropy of the detector bit had increased. When the two qubits interact via the quantum controlled-NOT, they also become correlated, and the entropy of the detector qubit increases. But this entropy did not come from the particle qubit. In the quantum case, before the controlled-NOT was applied, the particle qubit was in a well-defined state with zero entropy. Where did the information come from?

  What’s going on is that quantum mechanics, unlike classical mechanics, can create information out of nothing. Take our two qubits in their correlated state, |00> + |11>, with the wave of the first qubit correlated with the wave of the second qubit. This state is a definite quantum state: its entropy is zero. But now each of the qubits on its own is in a completely indefinite state: each could be either |0> or |1>. That is, each quantum bit now has one full bit of entropy.

  This weird type of quantum correlation is called “entanglement.” If a classical system is in a definite state, with zero entropy, then all the pieces of the system are also in a definite state, with zero entropy. If we know the state of the whole, then we also know the state of the pieces. For example, if two bits are in the state 01, then the first bit is in the state 0 and the second bit is in the state 1. But when a quantum system is in a definite state, though, such as the correlated state of our quantum bits, the pieces of the system need not be in a definite state. In entangled states, we can know the state of a quantum system as a whole but not know the state of the individual pieces.

  When the pieces of a quantum system become entangled, their entropies increase. Almost any interaction will entangle the pieces of a quantum system. The universe is a quantum system, and almost all of its pieces are entangled. Later, we’ll see how entanglement allows quantum computers to do things that classical computers can’t do. Here, we see that entanglement is responsible for the generation of information in the universe.

  Spooky Action at a Distance

  Entanglement is responsible for what Einstein called “spooky action at a distance.” Consider the state for two quantum bits |01> - |10>. In this state, if you look at the first qubit and find that it is 0, then the second qubit is 1. Similarly, if you look at the first qubit and find that it is 1, then the second qubit is 0. That is, the two qubits are the opposite of each other. For example, say the two qubits are made up of nuclear spins. When you measure the first spin along some axis and find that it is spin-up, the second spin will be spin-down.

  So far, this doesn’t sound so bad. The two spins rotate in the opposite direction, no matter which axis one chooses to measure their rotation about. The problem is that before the measurement of the first qubit, both qubits are in a completely indefinite state. Measuring the first qubit puts it in a definite state, |0> or |1>. This is not surprising, as measurement is supposed to determine the state of the thing measured. What is surprising is that measuring the spin of the first particle about some axis also puts the second particle in a definite state of spin about that axis; that is, if you choose to measure the first spin about the vertical axis, then after the measurement the second spin is in a definite state of spin about the vertical axis. If you choose to measure the first spin about the sideways axis, then after the measurement the second spin is in a definite state about the sideways axis. Somehow, it appears that measuring the first spin does something to the second spin as well. And the first particle need be nowhere near the second particle. After entanglement, one particle could be kept here on Earth and the other particle sent to Alpha Centauri.

  How can measuring something on Earth simultaneously affect something else at Alpha Centauri, which is some four light-years away from us? No signal can possibly arrive there in less than four years, let alone simultaneously. This is what Einstein meant when he called the effect of entanglement “spooky action at a distance.” With Boris Podolsky and Nathan Rosen, he wrote a famous paper on what is now commonly referred to as the EPR paradox, pointing out the counterintuitive na
ture of entanglement and showing that it implied that there were no underlying “elements of reality” in the world.

  In fact, entanglement does not involve action at a distance, spooky or otherwise. If measuring the spin of the first particle truly affected the spin of the second particle in some observable way, then it would be possible to send information from the first to the second by making measurements on the first. But measuring the first spin has no observable effect on the second spin. True, after the measurement of the first spin along the vertical axis, the second spin is in a definite state of spin about that axis: if the first spin was in the state |0>, the second spin is in the state |1>, and vice versa. But in the absence of information about the result of the measurement on the first spin, the second spin’s state is still completely uncertain, just as it was before the first spin was measured. Measuring the first spin does not change the outcome of measurements made on the second spin; measuring the first spin has no observable effect on the second spin. Measuring the first spin may increase our knowledge of the second one, but it doesn’t really change its state. As a result, it is not possible to send information from the first spin to the second just by making measurements on the first spin. Entanglement does not involve action at a distance.

  Even if entanglement does not involve action at a distance, it is still spooky. Each spin registers one qubit, no more, no less. But the fact that two spins are always spinning in the opposite direction, no matter which axis one chooses to measure them about, seems to involve much more than one bit of information. As a classical analog, consider two brothers who, when given a choice between two alternatives, always pick the opposite choices. One brother walks into the Miracle of Science bar in Cambridge, Massachusetts, at the same moment that the other brother walks into the Free Press pub in Cambridge, England. The bartender in the Miracle of Science asks the first brother, “Beer or whiskey?” “Beer,” he replies. Meanwhile, the bartender in the Free Press asks the same question. “Whiskey,” says the contradictory brother in Britain. If, instead, the bartenders had asked, “Bottled or draft?” one brother would have replied “Bottled” and the other “Draft.” Or if the bartenders had asked, “Red wine or white?” one brother would have replied “Red” and the other “White.” For each bit of information the bartenders might elicit, the brothers would reply with opposite bits.