by Seth Lloyd
The final reason to build quantum computers is that it’s fun. In the pages to come, you’ll meet some of the world’s foremost scientists and engineers: Jeff Kimble of Caltech, constructor of the world’s first photonic quantum logic gate; Dave Wineland of the National Institute of Standards and Technology, who built the first simple quantum computer; Hans Mooij of the Delft University of Technology, whose group gave some of the earliest demonstrations of quantum bits in superconducting circuits; David Cory of MIT, who built the first molecular quantum computer, and whose quantum analog computers can perform computations that would require a classical computer larger than the universe itself. Once we have seen how quantum computers work, we will be able to put bounds on the computational capacity of the universe.
The Language of Nature
As it computes, the universe effortlessly spins out intricate and complex structures. To understand how the universe computes—and thus to understand better those complex structures—we must learn how it registers and processes information. That is, we must learn the underlying language of nature.
Think of me as a kind of atomic masseur. As a professor of quantum-mechanical engineering at MIT, my job is to massage electrons, photons, atoms, and molecules into those special states in which they become quantum computers and quantum communication systems. Atoms are tiny but strong, resilient but sensitive. They are easy to talk to (just hit the table and you’ve talked to billions upon billions of them) but hard to listen to (I bet you can’t tell me what the table had to say beyond “thump”). They don’t care about you, and they go about their business doing what they have always done. But if you massage them in just the right way, you can charm them. They will compute for you.
Atoms are not alone in their ability to process information. Photons (particles of light), phonons (particles of sound), quantum dots (artificial atoms), superconducting circuits—all these microscopic systems can register information. And if you speak their language and ask them nicely, they will process that information for you. What language do such systems speak? Like all physical systems, they respond to energy, force, and momentum, to light and sound, to electricity and gravity. Physical systems speak a language whose grammar consists of the laws of physics. Over the last ten years, we have learned this language well enough to talk to atoms—to convince them to perform computations and report the results.
How hard is it to “speak Atom”? To learn to converse fluently takes a lifetime. I myself am a poor atomic conversationalist, compared with other scientists and quantum-mechanical engineers you will meet in this book. To learn enough to carry on a simple conversation, however, is not hard.
Like all languages, Atom is easier to learn when you’re younger. With Paul Penfield, I co-teach a freshman course at MIT called Information and Entropy. The goal of this course, like the goal of this book, is to reveal the fundamental role that information plays in the universe. Fifty years ago, MIT freshmen used to arrive full of knowledge about internal-combustion engines, gears and levers, drivetrains and pulleys. Twenty-five years ago, they arrived full of knowledge of vacuum tubes, transistors, ham radios, and electronic circuits. Now they arrive chock-a-block full of knowledge about computers, disk drives, fiber optics, bandwidth, and music- and image-compression codes. Their predecessors lived in worlds dominated by mechanical and electrical technologies; today’s freshmen come from a world dominated by information. Their predecessors already knew lots about force and energy, voltage and charge; today’s freshmen already know lots about bits and bytes. The freshmen in our course already know so much about information technology that we can teach them subjects—including quantum computation—that previously could be taught only to graduate students. (My senior colleagues in the Mechanical Engineering Department complain that the incoming freshmen have never used a screwdriver. This is untrue. Fully half of them have used a screwdriver to install more memory in their computers.)
As part of a research project supported by the National Science Foundation, I have developed a class to teach first- and second-graders about how information is processed at the microscopic scale. Six- and seven-year-olds these days also come equipped with scarily extensive knowledge of computers. They, too, seem to have no trouble learning about bits and bytes. When asked to play a game in which each student represents an atom in a quantum computer, they do so readily and accurately.
Those of us who grew up before the current information-processing revolution, though, have no less appreciation for the variety and significance of information than do our bit-saturated juniors. Old or young, by the time you finish reading this book, you will know how to ask atoms to perform simple computations, employing machines that are available throughout the world, along with the grammar of the language of nature.
Information-Processing Revolutions
The underlying ability of the universe to process information has given rise, through history, to a series of information-processing revolutions. We are in the midst of such a revolution now, one driven by the rapid advance of the electronic computing technology embodied by Moore’s law. Quantum computers represent the avant-garde of this revolution. But exciting and tumultuous as it is, ours is neither the first nor the greatest revolution in information processing.
Just as great a revolution was the invention of zero. The number zero was invented by the ancient Babylonians and passed down through the Arab world. The use of zero to represent powers of ten (10, 100, 1,000, etc.) distinguishes our Arabic number system from number systems such as that of the Romans, which used distinct symbols for powers of 10 (X = 10; C = 100; M = 1,000). Though it might seem only a slight change in the form of numerical representation, the invention of Arabic numbers has had a significant impact on mathematical information processing. (Not the least of which was the improvement in ease and transparency of commercial transactions. If the folks at Enron had been able to do their shady accounting in Roman numerals, they might have gotten away with it!) The origins of the Arabic number system are indistinguishable from the origins of its accompanying technology, the abacus—a simple, robust, and powerful calculating machine that consists of rows of movable beads mounted on sticks. The first row corresponds to ones, the second to tens, the third to hundreds, and so on. An abacus with just ten rows can perform calculations ranging into the billions.
Even more powerful than the ability of the abacus to deal easily with large numbers is its embodiment of the concept of zero. In fact, it seems likely that the machine predated the word. The word “zero” is Italian, short for zefiro, from the Low Latin zephirum, Old French cifre, Arabic sifr, Sanskrit shunya—“an empty thing.” In the Arabic number system, zero acts as a placeholder, allowing ever larger numbers (10, 100, 1,000, . . . ) to be expressed with ease. An empty thing is a powerful device. In spite of—or possibly because of—its power, zero as a number arouses suspicion. It is somehow unnatural. Indeed, it is not one of the natural numbers (1, 2, 3, . . . ). Zero in the abstract is a thorny concept, but an abacus with all beads down is a simple, concrete thing: zero.
Figure 1a. The Ascent of Bits
The history of the universe can be thought of as a sequence of information processing revolutions, each of which builds on the technology of the previous ones.
Figure 1b. The Ascent of Bits
The abacus shows how a revolution in information processing cannot be separated from the underlying mechanism or technology that governs how the information is represented and processed. The information-processing technology (e.g., the abacus) is typically inseparable from the conceptual breakthrough (e.g., zero).
Going thousands of years farther back, we find an even greater revolution: writing. The original technology consisted of scratching marks on clay or rock. Writing was, almost literally, language made concrete. It enabled large-scale social organization, contracts, scriptures, and books like this one. Over the years, the technologies of writing have progressed from rock to paper to electrons. Each manifestation of writing, from comm
andment to poem to neon sign, possesses its own variation on the technology for representing words.
The development of human language itself, 100,000 years ago or more, was (to flatter our own species) an information-processing revolution of the first rank. The fossil record suggests that the development of language was accompanied and furthered by the relatively rapid evolution of parts of the brain that specialize in language processing. We can think of this new neural circuitry, together with the accompanying development of the vocal cords, as a naturally evolved “technology,” or mechanism, that makes language possible. This additional neural technology is apparently what gave rise to the remarkable universality of human speech—the ability to express in one language more or less what has been said in another. At the very least, language allowed the uniquely human forms of social organization that have made our species so successful thus far.
The farther back we go, the more momentous the information-processing revolutions we uncover. The development of the brain and the central nervous system was a triumph of naturally evolved technology, well suited for the transformation of information from the outside in, and for communication between parts of an organism. The development of multicellular organisms in the first place arose from numerous breakthroughs in intra- and intercellular communication. Every successful mutation, every instance of speciation, constitutes an advance in information processing. But for an even greater revolution, dwarfing all that followed, we turn the clock back a billion years, to the invention of sex.
The original sexual revolution was a tour de force, a huge success that came from what at first glance looks like a bad idea. Why bad? Because it risked losing valuable information. A successful bacterium, reproducing asexually, passes on its exact genetic makeup (absent the occasional mutation) to its offspring. But if an organism reproduces sexually, its genes are scrambled with those of its mate in order to produce the offspring’s genes, a process called recombination. Because each half of this offspring’s genes came from a different parent, and because of the scrambling process, no matter how successful either parent’s unique combination of genes, the offspring’s genome will not be the same as that parent’s. Sexual reproduction has never passed on a full winning combination intact. Sex messes with success.
So why is sex good? From the point of view of natural selection, it allows for greater genetic variation at the same time as it faithfully reproduces individual genes. Suppose the world were to get hotter. A heretofore successful, but asexual, bacterium would suddenly find itself in a hostile environment. Its previously well-adapted, almost perfectly identical offspring would now be poorly adapted.
Without sex, the only way for bacteria to adapt is through mutation, which is caused by reproductive error or environmental damage. Most mutations are hurtful; they make for even less successful bacteria—though eventually, with luck, a mutation would arise that made for a more heat-resistant bacterium. Asexual adaptation is problematic because the dictate of the world, “Change or die,” runs directly counter to one of the primary dictates of life: “Maintain the integrity of the genome.” In engineering, this type of clash is called a coupled design. Two functions of a system clash so that it is not possible to adjust one without negatively affecting the other. In sexual reproduction, by contrast, the inherent scrambling, or recombination, affords a vast scope for change, yet still maintains genetic integrity.
Consider a small town with 1,000 inhabitants. Count up all the possible mating combinations (judging from daytime TV, there are quite a few), and then the number of possible ways their genes can be scrambled up and recombined in their kids. The result: the town is a genetic powerhouse, capable of generating as much diversity as billions of bacteria. This diversity is good: if an epidemic hits the town, there are likely to be survivors, who will then pass on their resistant genes to their children. Moreover, the capacity for diversity that sex conveys now comes without damage to the genome. By separating the function of adaptation from the function of maintaining the integrity of individual genes, sex allows much greater diversity while still keeping genes whole. Sex is not only fun, it is good engineering practice.
Moving even farther back in time, we come to the grandmother of all information-processing revolutions, life itself. About one-third of the way back to the beginning of the universe, life began on Earth. (When or whether it happened elsewhere is not known.) Living organisms possess genes, sequences of atoms in molecules such as DNA that encode information. The amount of information in a gene can be measured: the human genome possesses some 6 billion bits of information. Organisms pass their genetic information on to their offspring, sometimes in a mutated form. The organisms that are good at passing on genetic information are by definition successful; the organisms that fail to pass on their genes die out. Genetic information that conveys a reproductive advantage to its host tends to persist over generations, even as the organisms that carry it are born, reproduce, and die.
As it is passed down, genetic information is transmitted through natural selection. Genes and the mechanisms for copying and reproducing them are the key information-processing technology of life. Not surprisingly, the sum total of all genetic information processing performed by living organisms dwarfs the information processing performed by manmade computers, and should continue to do so for quite some time.
Surely, life is the big one. What revolution could top the origins of life in sheer power and beauty? But there was indeed an earlier information-processing revolution, one whose consequences encompass everything. The original information processor is the universe itself. Every atom, every elementary particle registers information. Every collision between atoms, every dynamic change in the universe, no matter how small, processes that information in a systematic fashion.
This computational capacity of the universe underlies all subsequent information-processing revolutions. Once a physical system possesses the ability to process information at a rudimentary level—performing simple operations on a few bits at a time—arbitrarily complicated forms of information processing can be built up from these basic operations. The laws of physics allow simple information processing at the quantum-mechanical level: one particle, one bit; one bump, one op. The complex forms of information processing we see around us—life, reproduction, language, society, video games—are all built up from simple operations governed by the laws of physics and performed on a few quantum bits at a time. Every information-processing revolution is associated with a new technology—the computer, the book, the brain, DNA. These technologies allow information to be registered and processed according to a set of rules. What is the technology associated with the Big Bang’s information processing? What machine processes information in the computational universe? To see this universal information-processing technology in action, one need only open one’s eyes and look around. The machine performing the “universal” computation is the universe itself.
CHAPTER 2
Computation
Information
I began the initial meeting of my MIT graduate course on information in the manner I begin all of my courses: “First,” I said to the twenty-odd students, “you ask questions and I’ll try to answer them. Second, if you don’t ask questions, I’ll ask you questions. Third, if you don’t answer my questions, I’ll tell you something I think you ought to know. Any questions?”
I waited. No response.
Something was wrong. Normally, MIT students are more than happy to try to stump the professor, particularly if the alternative is that the professor will try to stump them.
I moved on to step two: “No questions? Then here’s one for you: What is information?”
Nothing. This was even worse. After all, these students had been stuffing themselves full of information since freshman year. If they didn’t regurgitate some of it, I was going to have to resort to step three.
“OK. How about this one: What is the unit of information?”
At once, the class responded,
“The bit!”
What do my students’ answers, or lack thereof, reveal? That it is far easier to measure a quantity of information than to say what information is. And more broadly, “How much?” is frequently an easier question to answer than “What is . . . ?” What is energy? What is money? These are hard questions. How much energy does it take to . . . ? How much money does it take to . . . ? These questions have precise and available answers.
“What is a bit?” I asked. Now replies came thick and overlapping: “0 or 1!” “Heads or tails!” “Yes or no!” “True or false!” “The choice between two alternatives!”
All of these answers were correct. The word “bit” stands for “binary digit.” “Binary” means consisting of two parts, and a bit represents one of these two alternatives. Traditionally, these alternatives are referred to as 0 and 1, but any two distinct alternatives (hot/cold, black/white, in/out) register a bit.
A bit is the smallest unit of information. A coin toss yields one bit: heads or tails. Two bits represent a slightly larger chunk of information. Two coin tosses yield one of four (or two times two) alternative outcomes: heads-heads, heads-tails, tails-heads, tails-tails. Similarly, three coin tosses yield one of eight (or two times two times two) alternatives.
As you can see from even these few examples, as you keep on tossing coins, the number of total alternatives—total possible outcomes of the series of tosses—grows rapidly. In fact, with each subsequent toss (remember: each toss yields one bit), the number of total alternatives doubles. So, to calculate the number of alternative outcomes in a given scenario, you simply multiply two by itself a number of times equal to the number of bits. For example, ten bits gives two multiplied by itself ten times, or 1,024 alternatives (2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 210 = 1,024 - 103).