Quest for the Quantum Computer - Couverture souple

Chapter One: Late-Night Quantum Thoughts

Any technology that is sufficiently advanced is indistinguishable from magic.

Arthur C. Clarke

Life in Other Universes

Gaunt, hair unkempt, and skin a ghostly shade, David Deutsch cuts a strange figure even by the standards of the eccentrics and oddballs that so often inhabit the upper reaches of science. Yet appearances can be deceptive. Talk to Deutsch and you won't find the withdrawn, head-in-the-clouds academic you might expect but someone who is articulate, personable, and exceedingly bright. You'll also quickly discover this is an individual whose ideas about life and the universe are bigger and more radical than those of anyone you are ever likely to meet.

As I drove from London to visit him at his home in Oxford, a fatal accident on the road alerted me to the bizarre implications of some of Deutsch's ideas, in particular his resolute belief in the existence of an infinite set of parallel universes -- the multiverse, as he calls it. Within the multiverse there are endless alternate realities in which, supposedly, a huge army of mutant copies of everyone on this and other planets plays out an almost limitless variety of dramas. According to this world view, each time we make the smallest decision the entire assemblage divides along different evolutionary paths like some vast ant colony splitting off in divergent directions. In the process, large numbers of our copies suddenly embark on different lives in different universes.

Presumably, I thought, in some of those fabled other-universes the truck in front hadn't jackknifed, the accident hadn't happened, the crash victims were still alive, and I was now on my way instead of stuck in a jam. But did that mean the victims would therefore feel as though they had survived regardless of the accident because they would only be aware of the universes in which they had continued to live?

A foreshadow of this all-possible-worlds idea was intriguingly captured by Jorge Luis Borges in a short story now often cited by quantum physicists. In "The Garden of Forking Paths," written back in the 1950s, an illustrious Chinese governor is said to have written a strange kind of novel constructed as a kind of labyrinth. "In all fictional works, each time a man is confronted with several alternatives, he chooses one and eliminates the others; in the fiction of Ts'ui Pen, he chooses -- simultaneously -- all of them," Borges wrote. By writing a novel that pursued all possible story lines simultaneously, Borges's fictitious author, Ts'ui Pen, could have been writing a script for the multiverse.

But why, I wondered, should we care about other universes? There's surely enough to worry about in this one without concerning ourselves over the fate of the poor lost souls living in others. With such thoughts running through my mind, I was ready to be briefed by this world's leading advocate for the existence of those other worlds. When I finally arrived and entered Deutsch's house, it took me a moment to persuade myself that I hadn't stepped right into another universe. His place was an unbelievable mess. Papers, books, boxes, computer equipment, mugs, magazines, videos, and numerous other items were strewn everywhere. Even a trip to the bathroom entailed climbing over a mound of cardboard boxes. How does this man function, I wondered?

Okay, so this wasn't exactly a parallel universe, more a parallel mode of living. Yet out of the chaos there were definite, albeit eclectic, signs of order. A whiteboard in the corner of his living room was covered with equations, a reference to Oliver Stone's Natural Born Killers here, and notes about time travel there. On a piano in another corner of the room lay open a score of Beethoven's Waldstein Sonata. On the floor, littered among the detritus, were strange and elaborate drawings of spidery-looking aliens, designs for an animated film that Deutsch was making with some friends.

But it wasn't long before our conversation leapt far beyond the confines of Deutsch's domicile. "Somewhere in the multiverse there are Earths that were not hit by a comet 60 million years ago and on which the dinosaurs evolved into intelligent beings," Deutsch informed me. "Now those dinosaurs might look completely different from us, and their houses might look different from ours, and their cars probably look different from ours -- but if you look at their airplanes and spaceships, they probably look much more similar to ours, and if you look at their microchips, they're going to look very similar to ours. The more knowledge that is embodied in a physical object, the more alike it will look in different universes because the more it will have been subjected to the same tests of efficiency, validity, truth, and so on."

"Do you really think there are such universes, in which dinosaurs have all those things?" I asked incredulously. "Undoubtedly," Deutsch replied without hesitation. "That's what the laws of physics tell us."

Deutsch is a physicist, winner of the 1998 Paul Dirac prize for theoretical physics and a researcher at the Centre for Quantum Computation at Oxford University's Clarendon Laboratory. Owing to his unusual lifestyle, though, he rarely sets foot in the university's buildings, preferring instead to inhabit his own private world. If you call Deutsch on the telephone before 2 p.m., you are unlikely to get an answer. He prefers to sleep during the day and work uninterrupted through the night.

During those long nocturnal hours Deutsch has deliberated on some extraordinary ideas. Among them is one of the biggest ideas in physics and mathematics since the development of quantum theory, a breakthrough that could also lead to the most significant invention since the digital computer. It is the concept of a quantum computer, a machine that has begun a revolution in computing -- and far beyond -- that looks set to be as momentous as the upheaval in Newtonian physics brought about in the early twentieth century. As Discover magazine once put it,4 a quantum computer "would in some sense be the ultimate computer, less a machine than a force of nature."

Why so? Because a quantum computer would make any existing computer -- even the fastest Cray supercomputer -- seem exceedingly puny. It would solve problems that will never be cracked by any conceivable nonquantum successors of current computers. It would make possible virtual-reality simulations of things we know can never be simulated with current technology, even in principle. But perhaps most important, it would throw open doors to a totally new kind of laboratory in which we could explore those alternate universes of which Deutsch is so fond. Imagine living in a small house for many years and then discovering in the basement a trapdoor that opened onto a colossal subterranean world of rooms that appeared to stretch on into infinity. For physicists and computer scientists that, in some sense, is what the arrival of the first quantum computer would be like.

Exciting though the idea of an extraordinary new kind of computing machine might be, the quest for the quantum computer touches upon issues that are much grander than simply a new technology. The study of the ideas involved has already led to remarkable and strange new insights into the nature of our universe.

From the early 1970s to the present day, Deutsch has seen his ideas grow from an apparently small ripple in the world of academic physics to what is now an intellectual maelstrom. By the nineties, the subject of quantum computing had become one of the most exciting and rapidly moving research disciplines in physics and computing. Chaos theory and superstring theory -- the scientific gold rushes of the 1980s -- suddenly seemed far less enticing in the light of the new Klondike: quantum computation. Theoretical and experimental physicists, mathematicians, and computer scientists realized that this subject offered one of the remaining big opportunities within physics to mine the secrets of nature.

Following the announcement of the first experimental demonstrations of simple quantum programs, the media began to catch on. The inevitable headline QUANTUM COMPUTING TAKES A QUANTUM LEAP, in the International Herald Tribune, was occasioned when researchers at MIT, IBM, Oxford University, and the University of California at Berkeley reported in 1998 that they had succeeded in building the first working computers based on quantum mechanics. The story was all the more compelling because these scientists had fashioned their first quantum processors from the unlikeliest of materials. The quantum calculations weren't performed, as you might imagine, by manipulating tiny specks of matter, nor were they the product of elaborate banks of electronic hardware or even huge contraptions the size of particle accelerators. There were no laser beams, no smoke and no mirrors.

No, the quantum logic was all executed within the modest confines of a small flask of liquid. No ordinary liquid, either, but a specially prepared version of the common anesthetic and solvent chloroform. Who would have predicted such a thing a few years before?

Of course, these early demonstrations of experimental quantum computing were very simple, and to be fair, other demonstrations have used the more familiar apparatus of the modern physics lab, such as lasers and mirrors. But none of these hinted at the truly extraordinary powers a fully fledged machine would possess. If you imagine the difference between an abacus and the world's fastest supercomputer, you would still not have the barest inkling of how much more powerful a quantum computer could be compared with the computers we have today. More remarkable yet, this amazing discovery originated not from some breakthrough in electronics or software design but in large measure from pure theory -- from Deutsch's highly individual take on the laws of physics.

The Quantum AI Experiment

The origins of this quantum information revolution are to be found in the pioneering work of Rolf Landauer, a physicist who became an IBM Fel-

low in 1969 and who, until his death in 1999, worked at IBM's Thomas J. Watson Research Center in Yorktown Heights, near New York City. "Back in the 1960s, when I was still in school," Deutsch said, "Landauer was telling everyone that computation is physics and that you can't understand the limits of computation without saying what the physical implementation [i.e. type of hardware] is. He was a lone voice in the wilderness. No one really understood what he was talking about -- and certainly not why."

The prevailing view at the time was that computation was ultimately an abstract process that had more to do with the world of mathematical ideals than with the physics of machines. But Landauer's view began to take hold when he, and subsequently his IBM colleague Charles Bennett, discovered a crucial link between physics and computation, which we'll explore in the next chapter.

"The next thing that happened was in 1977-78," Deutsch continued. "I proposed what today would be called a quantum computer, though I didn't think of it as that. I thought of it as a conventional computer operating by quantum means that had some additional quantum hardware that allowed it to do extra things. But I didn't think of the additional hardware as being part of the computer. The purpose of this was not to do computations, it was to test the many-universes theory. It had been thought that the theory was untestable. I realized that if you had a quantum computer, and the quantum computer could count as an observer, then it could observe things that would distinguish between the many-worlds interpretation of quantum mechanics and other so-called interpretations."

Many worlds, many universes -- or nowadays, "many minds" or "many histories" -- take your pick. All are variants of a particular interpretation of quantum theory, the theory of the subatomic realm. Ever since the development of quantum theory at the beginning of the twentieth century, scientists have known that on the atomic scale matter behaves very differently from what we see on everyday scales. Particles such as electrons and atoms do not behave like the billiard balls of Newton's classical physics but seem to exhibit characteristics more in keeping with fuzzy wavelike entities. These and other properties led to a great deal of puzzlement and angst over how quantum theory should be understood as a description of reality -- or realities. So much so that today there are a multitude of different interpretations of what goes on at the atomic level.

In the early 1980s, Deutsch's proposed experiment (described more fully in Chapter 3) sounded like the stuff of science fiction. To test the existence of multiple universes, he envisaged the construction of a thinking, conscious artificial intelligence whose memory worked "at the quantum level." Such a machine, he claimed, could be asked to conduct a crucial experiment inside its own brain and report back to us whether Deutsch was indeed right to believe in the existence of parallel universes. The idea of assembling a conscious machine took some swallowing, but what exactly did Deutsch have in mind when he talked of "quantum memory"?

Well, nearly 20 years later we have the answer because quantum computer memory is on the verge of becoming an experimental reality. But even if Deutsch's ideas looked far-fetched at first sight, they were compellingly presented and, more important, appeared to be scientifically testable. As the philosopher of science Karl Popper pointed out, only those theories that are open to the possibility of experimental refutation or falsifiability are worthy of being considered good science. The trouble was that Deutsch's test would have to be carried out on a new kind of machine that no one had yet built or knew how to build.

But he was following a well-established tradition in physics: dreaming up thought experiments to question fundamental assumptions about the world. Such experiments, even if they cannot be carried out in practice, have often acted as a powerful spur for creative thinking in physics. Albert Einstein, for example, devised several that were instrumental in the development of relativity and quantum theory. Sure enough, Deutsch's thought experiment, although nearly impossible to carry out then as now, convinced him that the many-universes interpretation had to be correct.

The "experiment" didn't make much of an impression on other scientists, though. This was largely because the work remained unpublished for many years. Deutsch originally described the idea in 1978 in a paper he sent to the journal Physics Review. The editors had a policy of not publishing papers on the interpretation of quantum theory, but Deutsch felt his idea was sufficiently exceptional to warrant the breaking of that rule. The review's editors thought otherwise. Unfortunately, Deutsch did not submit his paper to any other journal and thereby lost his claim to being the first to publish something close to the concept of a quantum computer. Why didn't he publish elsewhere?

Deutsch explained that he was not especially interested in claiming priority for his ideas. "I usually lose interest in a paper when it's about three-quarters finished," he said. "Finishing papers is quite a chore. I've got a whole stack of unfinished papers. If I do finish a paper, I send it off and it's good-bye, I'm already working on other things. It was only when I happened to meet David Finkelstein at the Quantum Gravity II conference [in 1984] that I mentioned this paper to him -- we were all having a riotous argument, as often happens over dinner, about t...

Julian Brown is a science journalist who specializes in physics and computers. He has written extensively about quantum physics for New Scientist magazine, and is the coeditor of The Ghost in the Atom and Superstrings: A Theory of Everything? He lives in San Francisco, California.