Computing with Quantum Cats Read online

  This is more or less where things stood when Feynman wrote up his thesis and went off to Los Alamos. After the war, he was able to pick up the threads and develop his ideas into a complete theory of quantum electrodynamics (QED) including relativistic effects, the work for which he received a share of the Nobel Prize; but this is not the place to tell that story.

  What I hope you will take away from all this is the idea that at the quantum level the world is in a sense timeless, and that in describing interactions between quantum entities everything has to be considered at once, not sequentially. It is not necessary to say that an electron shakes and sends a wave moving out across space to shake another electron; it is equally valid to say that the first electron shakes and the second one shakes a certain time later as a result of a direct, but delayed, interaction. And the trajectory “sniffed out” when an electron moves from A to B is the one that corresponds to the least action for the journey. Nature is lazy.

  Nobody said this more clearly than Feynman, as another quote from his Nobel Lecture shows:

  We have a thing [the action] that describes the character of the path through all of space and time. The behavior of nature is determined by saying her whole space–time path has a certain character…if you wish to use as variables only the coordinates of particles, then you can talk about the property of the paths—but the path of one particle at a given time is affected by the path of another at a different time.

  This is the essence of the path integral formulation of quantum mechanics.

  Intriguingly, Schrödinger's quantum wave function has built into it exactly the same time symmetry as Maxwell's equations, which Schrödinger himself had commented on in 1931, but had been unable to interpret, simply remarking: “I cannot foresee whether [this] will prove useful for the explanation of quantum mechanical concepts.” Feynman doesn't seem to have been influenced by this, and may not have been aware, in 1942, of Schrödinger's remark, which was made in a paper published in German by the Prussian Academy of Science. Schrödinger was also ahead of Feynman, although in an almost equally understated way, in appreciating that all quantum “paths” are equally valid (but not necessarily equally probable). A convenient way into his version of this idea is through Schrödinger's famous cat puzzle (sometimes called a “paradox,” although it isn't one).

  CATS DON'T COLLAPSE

  The point of Schrödinger's “thought experiment,” published in 1935, was to demonstrate the absurdity of the Copenhagen Interpretation, and in particular the idea of the collapse of the wave function. His hypothetical cat12 was imagined to be living happily in a sealed chamber, on its own with plenty to eat and drink, but accompanied by what Schrödinger called a “diabolical device.” This device could involve any one of several quantum systems, but the example Schrödinger chose was a combination of a sample of radioactive material and a detector. If the sample decays, spitting out an energetic particle, the detector triggers a piece of machinery which releases poison and kills the cat. The point is that the device can be set up in such a way that after a certain interval of time there is a 50:50 chance that the radioactive material has or has not decayed. If the sample has decayed, the cat dies; if not, the cat lives. But the Copenhagen Interpretation says that the choice is not made until someone observes what is going on. Until then, the radioactive sample exists in a “superposition of states,” a mixture of the two possible wave functions. Only when it is observed does this mixture collapse one way or the other. This is equivalent to the way the wave associated with an electron going through the experiment with two holes goes both ways at once through the slits when we are not looking, but collapses onto one or the other of the slits when we put a detector in place to monitor its behavior.

  This is all very well for electrons, and even radioactive atoms. But if we take the Copenhagen Interpretation literally it means that the cat is also in a mixture of states, a superposition of dead and alive, and collapses into one or the other state only when someone looks to see what is going on inside the room. But we never see a cat that is dead and alive (or neither dead nor alive) at the same time. This is the so-called paradox.

  It is possible to extend this idea beyond Schrödinger's original formulation to bring out another aspect of quantum reality that is crucial in understanding quantum computation. Instead of one cat, imagine two (perhaps brother and sister), each in its own chamber, both connected to a diabolical device which determines, with 50:50 precision, that as a result of the radioactive decay one cat dies and the other lives. Now, after the mixture of states has been set up, the two chambers, still sealed, are separated and taken far apart from each other (in principle, to opposite sides of the Galaxy). The Copenhagen Interpretation says that each chamber contains a superposition of dead and alive cat states, until someone looks in either one of the chambers. As soon as that happens, the wave function collapses for both cats, instantaneously. If you look in just one chamber and see a dead cat, it means that the wave function for the other cat has collapsed at that precise instant to form a live cat, and vice versa. But the quantum rules do not say that the collapse happened before the chambers were separated and that there “always was” a dead cat in one chamber and a live cat in the other. Like the way a measurement at one slit in the experiment with two holes seems to affect what is going on at the other slit, this is an example of what is known as “quantum non-locality,” of which more shortly. But Schrödinger's resolution of all these puzzles was to say that there is no such thing as the collapse of the wave function. As early as 1927, at a major scientific meeting known as a Solvay Congress, he said: “The real system is a composite of the classical system in all its possible states.” At the time, this remark was largely ignored, and the Copenhagen Interpretation, which worked For All Practical Purposes, even if it doesn't make sense, held sway for the next half-century. I will explain the importance of his alternative view of quantum reality later; but Schrödinger was way ahead of his time, and it is worth mentioning now that in 2012, eighty-five years after he made that remark, two separate teams offered evidence that wave functions are indeed real states that do not collapse. Before coming up to date, though, we should take stock of what Feynman and his contemporaries had to say about quantum computation.

  THE GATEWAY TO QUANTUM COMPUTATION

  In order to understand their contribution, we need just a passing acquaintance with the logic of computation. This is based on the idea of logic “gates”: components of computers which receive strings of 1s and 0s and modify them in accordance with certain rules. These are the rules of so-called Boolean logic (or Boolean algebra), developed by the mathematician George Boole in the 1840s. Boolean algebra can be applied to any two-valued system, and is familiar to logicians in the form of application to true/false systems; but in our context it applies to the familiar binary language of computation. When we talk blithely about computers carrying out the instructions coded in their programs, we are really talking about logic gates taking 1s and 0s and manipulating them in accordance with the rules of Boolean algebra.

  These rules are very simple, but not quite the same as those used in everyday arithmetic. For example, in everyday arithmetic 1 + 0 is always equal to 1. But using Boolean algebra a so-called AND gate will take an input of 1 + 0 and give the output 0. It will do the same for 0 + 0 and for 0 + 1 (which is different from 1 + 0 in the Boolean world). It will only give the output 1 if both inputs are 1; in other words if input A and input B are both 1, which is where it gets its name. Another gate, called the NOT gate, will always give the opposite output from its input. Put in 1 and out comes 0; put in 0 and out comes 1. The output is not the same as the input. Don't worry about how the possible kinds of gates combine to carry out the instructions in a computer program; I just want you to be aware that such gates exist and give you the simplest idea of what is actually going on inside your smartphone or other computer. An important part of developing computers is to devise gates which do interesting things in a reliable way, and in th
e mid-1970s this endeavor led to a major rethinking of the possibilities of machine computation.

  One of the questions that computer scientists working at the more esoteric end of their specialty asked in the 1950s and 1960s was whether it was possible, in principle, to build a computer that could simulate precisely (not just approximately; no matter how good an approximation is, it is never perfect) the workings of “classical” physics—the physics of colliding billiard balls and orbital motion of planets described so beautifully by Newton's laws. This brought them up against one of the most intriguing features of the world. Newton's laws are reversible. If we ignore things like friction, a collision between two individual pool balls, for example, looks the same going forwards in time or backwards in time. If we made a movie of the collision, and cut out the player making the shot, it would make as much sense backwards as it does forwards. But although each individual collision is reversible, if we made a similar movie showing the break in a game of pool, it would be obvious which was the future and which the past. The future is the situation where there is more disorder. This is a simple example of one of the most fundamental laws in science, the second law of thermodynamics. This says that, left to its own devices, the amount of disorder in a system (measured by a quantity called entropy) always increases, in spite of the reversibility of Newton's laws. The relevance of these ideas to computation comes about because entropy can be measured in terms of information. Another very simple example helps. If we have a glass containing water and some ice cubes, it takes more information to describe than if we have a glass that contains just water, even if it is the same glass but the ice has now melted—and once again, the direction of the “arrow of time” is clear. The greater the entropy of a system, the more disordered it is, and the less information it contains.

  The relationship between information (more specifically, information transmission) and thermodynamics was put on a mathematical basis by Claude Shannon, working at the Bell Telephone Laboratories in the 1940s. As this affiliation suggests, the idea was developed in the context of telephone communications, rather than computation, but it was soon taken up by the computer scientists. In this context, information is always a measure of the decrease of uncertainty provided by a message or a computation, and the direct motivation for Shannon's work was to find out how many calls could be sent simultaneously down a telephone cable without unacceptable loss of information. Incidentally, Shannon, who had been born in 1916, made his name developing telephone switching relay systems; during the Second World War he had worked at Bell Labs on cryptography and gunnery control systems, and met Alan Turing when he visited the labs in 1943. Shannon moved to MIT in 1956 and spent the rest of his career there.

  Now, it is important to appreciate in what follows that we are talking about only those entropy changes involved in the act of computation itself, not the ones involved in the process of producing electricity for the computer to run on, or air conditioning for the room in which it operates. In doing so we are following the same convention physicists use in discussing the movements of frictionless pool balls to get insight into Newton's laws, and it leads to equally deep truths. But at first computer scientists were led in the wrong direction—ironically, by Johnny von Neumann, who gave a lecture in 1949 in which he calculated that there must be a minimum amount of energy required in the basic act of computation, that is, switching a 0 into a 1 or vice versa. And this would make it impossible to simulate the world of classical physics precisely, because not only would it take energy (and increase entropy) to run a calculation in a computer, energy would be required and entropy would increase still more if the computer were run backwards. The operation would not be reversible—at least, not in entropy/information terms.

  The first hint that this was not the whole story came in 1961, when IBM researcher Rolf Landauer pointed out that at least some aspects of computation need not involve dissipating energy at all. Landauer was one of the first people to appreciate that, as he put it, “information is physical,” and that the unspoken assumption that there was some abstract, “pure” form of computation that exists regardless of the machinery used is wrong. As he later said:

  Information is inevitably tied to a physical representation. It can be engraved on stone tablets, denoted by a spin up or spin down, a charge present or absent, a hole punched in a card, or many other physical phenomena. It is not just an abstract entity; it does not exist except through physical embodiment. It is, therefore, tied to the laws of physics.13

  It is in that spirit that we can understand Landauer's insight of 1961. Imagine that the state of a single bit of information is represented by the presence of a ball in one of two holes, of equal depth, separated by a small hill. If the ball is in hole A, the bit is 1; if it is in hole B, the bit is 0. To change the state of the bit, the ball has to be rolled up the hill and down the other side. But the energy needed to raise the ball up one side of the hill is exactly equal to the amount of energy released when it is lowered down the other side. So, in principle, a computation can be carried out without using any energy at all! Another way of visualizing a change which does not use up energy is to think of a skateboarder at the top of a (frictionless) half-pipe. Starting out with zero speed, the skateboarder accelerates down to the bottom of the pipe then decelerates up the other side, arriving at the top with zero speed. He or she has changed position without using any energy.

  This, though, is not the end of the story. Imagine that we started with a whole array of balls each in its equivalent of hole A, like a computer starting out from a state with every bit registering 1, then performed a computation (using zero energy) which left it with some balls in “A” holes and some in “B” holes. Landauer also showed that reversing the process of computation to erase the information (in computer jargon, resetting the register to its initial state) sometimes does require energy. This is a little more tricky to understand, but depends on the fact that the computer has to operate some process which will restore it to an original situation regardless of the present state. In the example I have used, the original starting situation involves all the balls being in their starting positions. Clearly, the ball in hole B can be put back into hole A by using energy which pushes it back over the hill—energy which can again be reclaimed as it falls down the other side. But the computer does not “know” whether the ball is in hole B, so even if the ball is not there, the energy needed to reset the bit has to be applied, just in case it was there. Sometimes, this energy is wasted. This is the key insight provided by Landauer: that the computation itself need not involve any dissipation of energy (and so is, in principle, reversible), but that, paradoxical though it may seem, energy is dissipated every time that information is discarded!

  Another way of looking at this, in terms of reversibility of information rather than dissipation of energy, is that if there is more than one way in which a state can be reached; that is, if it can be reached by different routes, the computer does not “know” which is the right path to follow in order to reset the register—and this brings us back to the logic of gates. The AND gate is a good example. If we are trying to reset the registers and come across an AND gate in the state 1, we know for sure that the original input to the gate was 1 + 1. But if we find the AND gate in the state 0, we have no idea whether the input was 0 + 0, 1 + 0, or 0 + 1. A reversible computer, one which can simulate classical physics perfectly, has to be built entirely out of reversible gates. And such gates do exist.

  FREDKIN, FEYNMAN AND FRIENDS

  The next step in the theory of reversible computation came from Charles Bennett, another IBM researcher, in 1973. Inspired by reading Landauer's paper and hearing him talk a few years earlier, he wrote some very simple computer programs which were indeed reversible—that is, in carrying out the exercise he realized that in every case the computation consisted of two halves, the second half almost exactly undoing the work of the first half. As he later explained:

  The first half would generate the des
ired answer…. as well as, typically, some other information…. The second half would dispose of the extraneous information by reversing the process that generated it, but would keep the desired answer. This led me to realize that any computation could be rendered into this reversible format by accumulating a history of all information that would normally be thrown away, then disposing of this history by the reverse of the process that generated it. To prevent the reverse stage from destroying the desired output along with the undesired history, it suffices, before beginning the reverse stage, to copy the output on blank tape. [This] copying onto blank tape is already logically reversible.14

  This is as if you had a tablet (in his 1973 paper Bennett called it a “logically reversible Turing machine”) on which you could write, with a special pen, all the working for a problem, including the final answer. Then, you copy the answer onto a sheet of paper, and retrace all the writing on the tablet, using the pen as an eraser, removing the working as you go. You are left with the answer, and a blank tablet ready to use again.