by Seth Lloyd
Contents
Title Page
Dedication
Prologue: The Apple and the Universe
PART ONE: THE BIG PICTURE
CHAPTER ONE: Introduction
CHAPTER TWO: Computation
CHAPTER THREE: The Computational Universe
PART TWO: A CLOSER LOOK
CHAPTER FOUR: Information and Physical Systems
CHAPTER FIVE: Quantum Mechanics
CHAPTER SIX: Atoms at Work
CHAPTER SEVEN: The Universal Computer
CHAPTER EIGHT: Complexity Simplified
Personal Note: The Consolation of Information
Acknowledgments
Further Reading
A Note About the Author
Copyright
To Eve
PROLOGUE
The Apple and the Universe
“In the beginning was the bit,” I began. The chapel in the seventeenth-century convent that housed the Santa Fe Institute for the study of complex systems was filled with the usual collection of physicists, biologists, economists, and mathematicians, with a leavening of Nobel laureates. The grand old man of astrophysics and quantum gravity, John Archibald Wheeler, had challenged me to give a talk on the subject “It from Bit.” I had accepted the challenge. I was beginning to wonder if that had been a good idea, but it was too late to back down now. I held an apple in my hand.
“Things, or ‘its,’ arise out of information, or ‘bits,’” I continued, nervously tossing the apple in the air. “This apple is a good ‘it.’ Apples have long been associated with information. First of all, the apple is the fruit of knowledge ‘whose mortal taste brought death into the world, and all our woe.’ It conveys information about good and evil. Down the line, it was in the trajectory of a falling apple that Newton traced the universal laws of gravitation, and the curved surface of the apple is a metaphor for Einstein’s curved spacetime. More directly, the genetic code locked in the seeds of an apple programs the structure of future apple trees. And last, but not least, an apple contains free energy—the calories of bit-rich energy that our bodies need to function.” I took a bite of the apple.
“Clearly, there are many types of information contained in this apple. But how much information does the apple embody? How many bits are there in an apple?” I placed the apple on the table and turned to the board to perform a short calculation. “Interestingly, the number of bits in an apple has been known since the beginning of the twentieth century, since before the word ‘bit.’ At first, one might think that an apple embodies an infinite number of bits, but this is not so. In fact, the laws of quantum mechanics, which govern all physical systems, make finite the number of bits required to specify the microscopic state of the apple and its atoms. Each atom, by its position and velocity, registers only a few bits; each nuclear spin in an atom’s core registers but a single bit. As a result, the apple contains only a few times more bits than atoms—a few million billion billion zeros and ones.”
I turned back to face the audience. The apple was gone. Not good. Who had taken it? I glanced at the benign face of Wheeler and the impassive expression of Murray Gell-Mann, Nobel laureate, inventor of the quark and wearer of one of the world’s physics heavyweight title belts.
“I can’t continue without the apple. No it, no bit,” I declared, and sat down.
The hunger strike lasted only a few moments before an impish engineer from Bell Labs produced the apple. I took it from him and held it on high, issuing a challenge to anyone who might attempt another theft. This was a mistake. For the moment, though, all seemed well. I continued:
“All bits are equal in terms of the amount of information they can register. A bit, short for ‘binary digit,’ is registered by two distinguishable states—0 or 1, yes or no, heads or tails. Any physical system with two such states registers exactly one bit. A system with more states registers more bits. A system with four states—for example, 00, 01, 10, 11—registers two bits; a system with eight states—for example, 000, 001, 010, 011, 100, 101, 110, 111—registers three bits, and so on. As mentioned before, quantum mechanics guarantees that any physical system with finite energy confined to a finite volume of space has a finite number of distinguishable states and therefore will register a finite number of bits. All physical systems register information. In the words of IBM’s Rolf Landauer, ‘Information is physical.’”
Here Gell-Mann interrupted: “But are all bits truly equal? What about the bit that tells us whether some famous unsolved mathematical conjecture is true or not? Compare that with a bit derived from a random coin toss. Some bits are more important than others.”
True, I agreed. Different bits play different roles in the universe. All bits can register the same amount of information, but the quality and importance of that information varies from bit to bit. The significance of “yes” depends on the question asked. The two bits of information that determine the identity of a base pair in the apple’s DNA are far more important for generations of future apples than the bits of information registered by the thermal jiggling of a carbon atom in one of the apple’s molecules. Only a few molecules and their attendant bits are required to convey the smell of the apple, whereas billions of billions of bits are needed to provide the apple with its nutritional value.
“But,” Gell-Mann interjected, “is there a mathematically precise way of quantifying the significance of a bit?”
I did not have a complete answer to this question, I replied, still holding the apple. The significance of a bit of information depends on how that information is processed. All physical systems register information, and when they evolve dynamically in time, they transform and process that information. If an electron “here” registers a 0 and an electron “there” registers a 1, then when the electron goes from here to there, it flips its bit. The natural dynamics of a physical system can be thought of as a computation in which a bit not only registers a 0 or 1 but acts as an instruction: 0 can mean “do this” and 1 can mean “do that.” The significance of a bit depends not just on its value but on how that value affects other bits over time, as part of the continued information processing that makes up the dynamical evolution of the universe.
I continued to identify the bits from which the apple arises and to elaborate the roles those bits play in the processes that make up the apple’s characteristics. Things were going well. I had addressed the problem of “it from bit” and had survived the questioning. Or so I thought.
As I finished the talk and stepped away from the board, someone tackled me from behind. One of the audience members had taken seriously my challenge to steal the apple. Doyne Farmer was one of the founders of chaos theory—a tall, athletic man. He grabbed my arms to make me drop the apple. To break his grasp, I slammed him back against the wall. Pictures of fractals and photos of pueblos fell. But before I could wriggle free, Farmer wrestled me to the ground. We rolled around the floor, overturning chairs. By now, the apple was gone. It had been reduced to bits.
Part 1
THE BIG PICTURE
CHAPTER 1
Introduction
This book is the story of the universe and the bit. The universe is the biggest thing there is and the bit is the smallest possible chunk of information. The universe is made of bits. Every molecule, atom, and elementary particle registers bits of information. Every interaction between those pieces of the universe processes that information by altering those bits. That is, the universe computes, and because the universe is governed by the laws of quantum mechanics, it computes in an intrinsically quantum-mechanical fashion; its bits are quantum bits. The history of the universe is, in effect, a huge and ongoing quantum computation. The universe is a quantum computer.
Allow me to introduce myself. The first thing I remember is living in a chicken house. My father was apprenticed to a furniture maker in Lincoln, Massachusetts, and the chicken house was in back of her barn. My father turned the place into a two-room apartment; the space where the chickens had roosted became bunks for my older brother and me. (My younger brother was allowed a cradle.) At night, my mother would sing to us, tuck us in, and close the wooden doors to the roosts, leaving us to lie snug and stare out the windows at the world outside.
My first memory is of seeing a fire leap up in a wire trash basket with an overlapping diamond pattern. Then I remember holding tight to my mother’s blue-jeaned leg just above the knee and my father flying a Japanese fighter kite. After that, memories crowd on thick and fast. Each living being’s perception of the world is unique and crowded with detail and structure. Yet we all inhabit the same space and are governed by the same physical laws. In school, I learned that the physical laws governing the universe are surprisingly simple. How could it be, I wondered, that the intricacy and complexity I saw outside my bedroom window was the result of these simple physical laws? I decided to study this question and spent years learning about the laws of nature.
Heinz Pagels, who died tragically in a mountaineering accident in Colorado in the summer of 1988, was a brilliant and unconventional thinker who believed in transgressing the conventional boundaries of science. He encouraged me to develop physically precise techniques for characterizing and measuring complexity. Later, under the guidance of Murray Gell-Mann at Caltech, I learned how the laws of quantum mechanics and elementary-particle physics effectively “program” the universe, planting the seeds of complexity.
These days, I am a professor of mechanical engineering at the Massachusetts Institute of Technology. Or, because I have no formal training in mechanical engineering, it might be more accurate to call me a professor of quantum-mechanical engineering. Quantum mechanics is the branch of physics that deals with matter and energy at its smallest scales. Quantum mechanics is to atoms what classical mechanics is to engines. In essence: I engineer atoms.
In 1993, I discovered a way to build a quantum computer. Quantum computers are devices that harness the information-processing ability of individual atoms, photons, and other elementary particles. They compute in ways that classical computers, such as a Macintosh or a PC, cannot. In the process of learning how to make atoms and molecules—the smallest pieces of the universe—compute, I grew to appreciate the intrinsic information-processing ability of the universe as a whole. The complex world we see around us is the manifestation of the universe’s underlying quantum computation.
The digital revolution under way today is merely the latest in a long line of information-processing revolutions stretching back through the development of language, the evolution of sex, and the creation of life, to the beginning of the universe itself. Each revolution has laid the groundwork for the next, and all information-processing revolutions since the Big Bang stem from the intrinsic information-processing ability of the universe. The computational universe necessarily generates complexity. Life, sex, the brain, and human civilization did not come about by mere accident.
The Quantum Computer
Quantum mechanics is famously weird. Waves act like particles, and particles act like waves. Things can be in two places at once. It is perhaps not surprising that, at small scales, things behave in strange and counterintuitive ways; after all, our intuitions have developed for dealing with objects much larger than individual atoms. Quantum weirdness is still disconcerting, though. Niels Bohr, the father of quantum mechanics, once said that anyone who thinks he can contemplate quantum mechanics without getting dizzy hasn’t properly understood it.
Quantum computers exploit “quantum weirdness” to perform tasks too complex for classical computers. Because a quantum bit, or “qubit,” can register both 0 and 1 at the same time (a classical bit can register only one or the other), a quantum computer can perform millions of computations simultaneously.
Quantum computers process the information stored on individual atoms, electrons, and photons. A quantum computer is a democracy of information: every atom, electron, and photon participates equally in registering and processing information. And this fundamental democracy of information is not confined to quantum computers. All physical systems are at bottom quantum-mechanical, and all physical systems register and process information. The world is composed of elementary particles—electrons, photons, quarks—and each elementary piece of a physical system registers a chunk of information: one particle, one bit. When these pieces interact, they transform and process that information, bit by bit. Each collision between elementary particles acts as a simple logical operation, or “op.”
To understand any physical system in terms of its bits, we need to understand in detail the mechanism by which each and every piece of that system registers and processes information. If we can understand how a quantum computer does this, then we can understand how a physical system does.
The idea of such a computer was proposed in the early 1980s by Paul Benioff, Richard Feynman, David Deutsch, and others. When they were first discussed, quantum computers were a wholly abstract concept: Nobody had a clue how to build them. In the early 1990s, I showed how they could be built using existing experimental techniques. Over the past ten years, I have worked with some of the world’s greatest scientists and engineers to design, build, and operate quantum computers.
There are a number of good reasons to build quantum computers. The first is that we can. Quantum technologies—technologies for manipulating matter at the atomic scale—have undergone remarkable advances in recent years. We now possess lasers stable enough, fabrication techniques accurate enough, and electronics fast enough to perform computation at the atomic scale.
The second reason is that we have to—at least if we want to keep building ever faster and more powerful computers. Over the past half century, the power of computers has doubled every year and a half. This explosion of computer power is known as “Moore’s law,” after Gordon Moore, subsequently the chief executive of Intel, who noted its exponential advance in the 1960s. Moore’s law is a law not of nature, but of human ingenuity. Computers have gotten two times faster every eighteen months because every eighteen months engineers have figured out how to halve the size of the wires and logic gates from which they are constructed. Every time the size of the basic components of a computer goes down by a factor of two, twice as many of them will fit on the same size chip. The resulting computer is twice as powerful as its predecessor of a year and half earlier.
If you project Moore’s law into the future, you find that the size of the wires and logic gates from which computers are constructed should reach the atomic scale in about forty years; thus, if Moore’s law is to be sustained, we must learn to build computers that operate at the quantum scale. Quantum computers represent the ultimate level of miniaturizati
on.
The quantum computers my colleagues and I have constructed already attain this goal: each atom registers a bit. But the quantum computers we can build today are small, not only in size but also in power. The largest general-purpose quantum computers available at the time of this writing have seven to ten quantum bits and can perform thousands of quantum logic operations per second. (By contrast, a conventional desktop computer can register trillions of bits and can perform billions of conventional, classical logic operations per second.) We’re already good at making computers with atomic-scale components; we’re just not good at making big computers with atomic-scale components. Since the first quantum computers were constructed a decade ago, however, the number of bits they register has doubled almost every two years. Even if this exponential rate of progress can be sustained, it will still take forty years before quantum computers can match the number of bits registered by today’s classical computers. Quantum computers are a long way from the desktop.
The third reason to build quantum computers is that they allow us to understand the way in which the universe registers and processes information. One of the best ways to understand a law of nature is to build and operate a machine that illustrates that law. Often, we build the machine first and the law comes later. The wheel and the top had existed for millennia before the establishment of the law of conservation of angular momentum. The thrown rock preceded Galileo’s laws of motion; the prism and the telescope came before Newton’s optics; the steam engine preceded James Watt’s governor and Sadi Carnot’s second law of thermodynamics. Since quantum mechanics is so hard to grasp, wouldn’t it be nice to build a machine that embodies the laws of quantum mechanics? By playing with that machine, one could acquire a working understanding of quantum mechanics, just as a baby who plays with a top grasps the principles of angular momentum embodied by the toy. Without direct experience of how atoms actually behave, our understanding remains shallow. The “toy” quantum computers we build today are machines that will allow us to learn more and more about how physical systems register and process information at the quantum-mechanical level.