A Shortcut Through Time: The Path to the Quantum Computer

A Shortcut Through Time: The Path to the Quantum Computer

by George Johnson


$14.33 $15.00 Save 4% Current price is $14.33, Original price is $15. You Save 4%.
View All Available Formats & Editions
Choose Expedited Shipping at checkout for guaranteed delivery by Wednesday, October 16


In this remarkably illustrative and thoroughly accessible look at one of the most intriguing frontiers in science and computers, award-winning New York Times writer George Johnson reveals the fascinating world of quantum computing—the holy grail of super computers where the computing power of single atoms is harnassed to create machines capable of almost unimaginable calculations in the blink of an eye.

As computer chips continue to shrink in size, scientists anticipate the end of the road: A computer in which each switch is comprised of a single atom. Such a device would operate under a different set of physical laws: The laws of quantum mechanics. Johnson gently leads the curious outsider through the surprisingly simple ideas needed to understand this dream, discussing the current state of the revolution, and ultimately assessing the awesome power these machines could have to change our world.

Product Details

ISBN-13: 9780375726187
Publisher: Knopf Doubleday Publishing Group
Publication date: 02/10/2004
Edition description: Reprint
Pages: 224
Sales rank: 612,905
Product dimensions: 5.20(w) x 8.00(h) x 0.60(d)

About the Author

George Johnson writes about science for The New York Times. His most recent books, Strange Beauty: Murray Gell-Mann and the Revolution in Twentieth-Century Physics and Fire in the Mind: Science, Faith, and the Search for Order, were finalists for the Aventis and Rhone-Poulenc science book prizes. He has also won the AAAS Science Journalism Award. He is codirector of the Santa Fe Science-Writing Workshop and a former Alicia Patterson fellow. Mr. Johnson lives in Santa Fe. He can be reached on the World Wide Web at talaya.net.

Read an Excerpt

Chapter 1

"Simple Electric Brain Machines and How to Make Them"

I don't know where I first saw the advertisement for the Geniac Electric Brain construction kit, but I knew I had to have one for Christmas. It was the early 1960s, and like a lot of science-crazed kids I was obsessed with the wonderfully outrageous idea of "thinking machines." I devoured the picture stories in Life magazine and the Saturday Evening Post about the electronic behemoths manufactured by companies like International Business Machines, Univac, and Remington Rand. The spinning tape drives and banks of blinking lights were as exciting to me as the idea of space travel. Two of my favorite books were Tom Swift and His Giant Robot and Danny Dunn and the Homework Machine-testaments to the eerie fantasy of automating human thought. One day, flipping through one of my favorite magazines-probably Boys' Life or Popular Science-I stumbled upon an unbelievably tantalizing ad.

"Can you think faster than this Machine?"

Below the provocative headline was a picture of the Geniac with its sloping panel bedecked with six large dials and a row of ten bulbs. Who knew what kind of mysterious circuitry was hidden inside?

"GENIAC, the first electrical brain construction kit, is equipped to play tic-tac-toe, cipher and decipher codes, convert from binary to decimal, reason in syllogisms, as well as add, subtract, multiply and divide. . . . You create from over 400 specially designed and manufactured components a machine that solves problems faster than you can express them." Such was the promise of the Oliver Garfield Co., 126 Lexington Avenue, New York 16, N.Y. (This was before zip codes replaced the old numbered postal zones.) To a boy growing up in Albuquerque, the location of this modern Frankenstein laboratory seemed promisingly exotic and far away.

"Send for your GENIAC kit now. Only $19.95. . . . We guarantee that if you do not want to keep GENIAC after two weeks you can return it for full refund plus shipping costs."

There was nothing to lose. I began my lobbying effort, making it clear to my parents that receiving a Geniac was all that mattered to me. Then I waited, my brain charged with the kind of high-voltage anticipation that can only accumulate in someone still in the first decade of life.

Christmas morning I sat on the floor anxiously opening presents, keeping my eye out for one large enough to hold the pieces of an electronic computer. Finally a likely box emerged from behind the tree. I tore off the wrapping.

Decades later I still remember the disappointment I felt as I explored the contents of the cardboard package. The title of the instruction manual was intriguing enough: "Simple Electric Brain Machines and How to Make Them." But how was anyone to carry out such an ambitious project with the meager, humdrum parts that had been supplied?

Digging through the pile, I was crestfallen to find that the bulk of the kit consisted of some decidedly low-tech pieces of particle board called Masonite: a big square one and six smaller round disks, each drilled with concentric patterns of little holes. This was complemented by an assortment of hardware you might find in a kitchen junk drawer or a toolbox in the garage: ten flashlight bulbs and sockets, a battery and battery clamp, a spool of insulated wire, several dozen nuts, bolts, and washers, a bunch of small brass-plated staples (referred to in the typewritten instructions as "jumpers"), and the tools for assembling this detritus into what would supposedly function as a digital computer-a hexagonal wrench for gripping bolts (a "spintite") and a screwdriver.

Finally there was a simple on-off switch, described rather melodramatically in the manual: "This is the switch that enables you to put suspense and drama into your machine; for you set everything the way it should be, then talk about it and explain it, and finally when you have your listener all keyed up and ready, you (or he) throw the switch . . ."

I'd been had. There were no vacuum tubes, no transistors, or capacitors, or resistors-the colorful components I'd found from eviscerating dead radios and TV sets. All I'd gotten for Christmas was a handy-dandy kit for stringing together mindlessly simple circuits of switches and bulbs. The nuts and bolts were to be placed in various holes on the square wooden panel and connected one to the other by wires running underneath. The little metal jumpers were to be inserted into holes in the Masonite disks, the ends bent over to keep them in place. When the disks were attached to the panel, with more bolts and washers, they could be turned to and fro so that the jumpers touched the heads of the bolts, forming connections that caused the lightbulbs to flash on and off. It was all just switches-simple enough for a child to understand.

Reluctantly I opened the manual, published, disconcertingly, in 1955, and saw that it contained the familiar explanations of the wonders of electricity. ("You can think of a battery as a pump, which is able to push electrons, or little marbles of electricity, away from the plus end of the battery and towards the minus end of the battery . . . A flow of electrons is an electric current.")

The instructions went on to show how to assemble circuits and switches into various question-answering machines.

1.Whom do you prefer: (a) Marilyn Monroe? or

(b) Liberace?

2.How would you put a thread in a small hole: (a) wet it? or (b) tap it?

3.Would you rather spend a day: (a) shopping on Fifth Avenue? or (b) hunting in the woods?

Depending on how you answered these and three other questions (rotating the six circular switches so that they pointed to A or B), the current in the wiring would flow to one of two bulbs, M or F. The result was called a "Masculine-Feminine Testing Machine."

Never mind the musty Eisenhower-era philosophy. Scientifically, the whole thing seemed obvious and dumb. Just changing the paper labels would turn the machine into a tester for, say, whether you were a Jock or a Brain (the 1960s version of "nerd"): "Would you rather spend a rainy afternoon: (a) building a crystal radio? or (b) working out in the gym?" The meaning was all in the eye of the beholder.

As I paged through the manual, other projects appeared slightly more interesting. The switches could be wired to make machines that added numbers. Turn dial A to indicate the first number, turn dial B to indicate the second, and if the copper paths behind the panel had been correctly platted, the lightbulb that came on would be the very one labeled with the proper answer. (And if you made a mistake and didn't feel like redoing the wires, you could just move around the tags.)

Rig the machine another way and you could subtract or multiply. Wire up the "Reasoning Machine" described on page 25 of the guide and turning switch A to indicate "All fighter pilots are bomber pilots" and switch B to "No bomber pilots are jet pilots" would light the bulb for "No fighter pilots are jet pilots." QED. A syllogism (and a reminder that something can be logical but not true).

It was all terribly anticlimactic. Only years later would I realize that an utterly profound idea was slowly insinuating itself into my head: a computer is indeed just a box with a bunch of switches. The Geniac was "semiautomatic," as the manual put it: You had to turn the dials by hand to light the lights. And to "reprogram" the machine, you had to unscrew nuts with the "spintite" and shift the wires around. But suppose that some of the bulbs were replaced with little motors. When activated by the proper combination of settings, the motors could turn switches on other Geniacs, which would cause the dials on still other Geniacs to spin.

All kinds of elaborations were possible. Data could be fed into a glorified Geniac not with clunky wooden rotary dials but with cards or paper tape punched with holes arranged in the proper patterns. Read like Braille by metallic fingers, the holes would cause electrical connections to be made. Instead of flashlight bulbs, the circuits could ignite phosphorescent dots on a video screen-which is really just an array of thousands of tiny lights.

In the computer's modern incarnation, mechanical parts have been replaced by millions of microscopic transistors, minuscule switches etched onto the surfaces of silicon chips. Data are stored as invisible magnetic spots on spinning disks. But the basic idea is the same.

Only remnants of my Geniac survive. Going through a closet recently, I found a box of old electronic junk. There, sitting atop a partially dissected radio chassis and other relics of the vacuum-tube age, were three of the old dials. Two still had labels-"Candidate A: Popularity," "Candidate A: Campaign Effort"-handwritten in black ink on strips of surgical adhesive tape. I had apparently tried to make a machine to predict election outcomes.

I couldn't find the old manual anywhere. The reason I can quote from it (and the advertisement), reigniting old memories, is because I found the information in minutes on the World Wide Web. (I also found a Geniac kit on eBay, which was auctioned off for more than $400, twenty times its original price.) I'm still astonished by the speed with which data course through the great skein of computers called the Internet. But it is comforting to know that for all its complexity, the Net is just a bunch of Geniacs chattering at each other, twisting each other's dials.

On page 37 of "Simple Electric Brain Machines and How to Make Them" came what was intended to be the climax: instructions for how to make a Geniac that played tic-tac-toe. But looking back years later, it's clear to me that the real meat of the book was an innocent-sounding statement way back on page 3: "The kit, though inexpensive and convenient for constructing Geniacs, is however not necessary; and some persons will prefer to construct their Geniacs using other materials."

This was the crowning lesson: It was the form of the machine, not its substance, that mattered. If you wanted to really strip the idea of a computer to its essence, you didn't necessarily have to make it electrical. One could even be constructed from Tinkertoys.

Chapter 2

Tinkertoy Logic

In the lobby of the Boston Science Museum, protected by a Plexiglas case, stands a whimsical monument to this most incisive of ideas: the power of a computer arises not from the nature of its parts-be they transistors, microchips, vacuum tubes, wooden wheels, or pulleys and string-but from its architecture, how the parts are arranged. Flip open the side door of, say, a Macintosh G4 and the electronic innards look like a space-age city viewed from the sky. Copper-colored avenues shuttle electronic traffic between squat black structures reminiscent of suburban office buildings: the computer chips that, if magnified many times, look like little cities in themselves, populated by billions of microscopic structures laced together by wires whose thickness is measured in millionths of an inch. This image has become so familiar that people now habitually reverse the metaphor, describing a suburban view from an airplane as looking like the layout of a chip.

This cartographic complexity seems to be the quintessence of computing. But for all the apparent differences, there is nothing going on inside the mightiest Macintosh or Dell or Compaq-or for that matter in the supercomputers like Blue Mountain and Q-that cannot be done, in principle, with a stadium full of Geniacs, or even a sprawling contraption made from Tinkertoys, like the one in the Boston museum. In the mid-1970s, a group of computer-science students (including Daniel Hillis, who went on to start a company called Thinking Machines) gathered together more than a hundred Giant Engineer Tinkertoy sets, assembling the thousands of wooden spokes and spools into a computer that played a mean game of tic-tac-toe.

Anyone who cracks open the most basic high-school text on computer theory almost immediately learns two comfortingly simple truths: Any kind of data, from moves on a checkerboard to streaming videos, can be translated into a code consisting of just two symbols, 1 and 0. And the data can be manipulated using basic operations called AND, OR, and NOT, trivial functions that can be carried out with simple little switches called gates.

If an "AND gate" receives a 1 signal at both of its inputs, A and B, then the device responds with a 1: Yes. Otherwise it says No: 0. An OR gate is less restrictive: it will fire if it receives a 1 at either A or B. And a NOT gate does nothing more than invert its input: If it receives a 1 it will say 0, if it receives a 0 it will say 1. Weave together millions of these elements and the result is a digital chain reaction. Ones and zeroes, representing words, numbers, pictures, sounds, or positions on a game board, ricochet through the circuitry like pachinko balls. A computation is performed.

It's easy to see how such simple things could be made from ordinary switches and wire, as they were with the Geniac. In an AND gate, two switches are connected one after the other so that both must be closed for current to flow and the bulb to light. In an OR gate, the switches are in parallel; closing either one will complete the circuit. But it is merely incidental that the gates just described are electrical. The students, studying at the Massachusetts Institute of Technology, took on the challenge of making them from the sticks and spoked wheels in a child's set of Tinkertoys.

Suppose you have a Tinkertoy OR gate (as shown on the next page). If either of the input shafts, A or B, is pushed to the right, the output shaft will move too. NOT and AND gates can also be constructed with Tinkertoys. By combining hundreds of gates, the MIT students built a complex mechanical contraption that would respond to any of its opponent's moves. Clicking and clacking, the wooden pieces, each positioned just so, would process the information, finally coming back with the best countermove.

Tic-tac-toe is particularly easy to code into the all-or-nothing diction of the binary tongue. Every round of the game leaves the board in a different state, with each of the nine cells of the crisscross pattern containing an X or an O or remaining unoccupied. After studying the game, the students made a list of the best way for a player to react to every situation. Suppose the human opponent is playing O and the board looks like this:

Obviously the computer can stave off defeat only by putting its X in the right-hand position of the middle row.

Without worrying about the details, one can imagine how this situation might be captured by a combination of rackety Tinkertoy gates manipulating Xs and Os instead of 1s and 0s. First, number the cells of the board starting in the upper-left corner. If cell 4 AND cell 5 are marked O, then put an X in cell 6. One can almost hear the wooden shafts sliding into place.

Table of Contents

Preface: Inside the Black Boxix
Prologue: The Road to Blue Mountain3
1"Simple Electric Brain Machines and How to Make Them"12
2Tinkertoy Logic19
3Playing with Mirrors32
4A Shortcut Through Time51
5Shor's Algorithm66
6Breaking the Code83
7Invisible Machines105
8Counting with Atoms122
9Quantum Secrecy141
10The Hardest Problem in the Universe155
Epilogue: The Nine Billion Names of God168
The Fine Print: Notes and Sources175


A Conversation with George Johnson author of

Q: Why did you want to write about quantum computing?
A few years ago, a fellow science writer complimented me on a piece I'd just written for the New York Times science section. He said it was the clearest explanation he'd ever read of the mind-bending peculiarities of quantum theory. Then he went on to say that what the world needs is a short book (emphasis on "short") that would explain an emerging new technology called quantum computing. I decided to take up the challenge.

Q: Can you briefly explain what a quantum computer would be like?
All computers that now exist—from the Mac or PC on your desktop to gargantuan supercomputers like Q in Los Alamos, New Mexico—speak the same language, called binary logic. Everything is either 1 or 0, on or off. It is this simplicity that allows computers to process data —numbers, words, sounds, pictures—at such rapid speeds. A quantum computer works according to a very different set of rules. Everything is 1, 0, or 1 and 0 at the same time. That sounds ridiculous, but the laws of quantum theory allow it. And the result—this is what I try to explain in the book—would be computers that can solve problems now considered impossible.

Q: What is an example of one of these "impossible" problems?
Finding a number's smallest factors. We know that 12 can be broken down into 2 x 2 x 3. But how about 1,347,012,645,886,345,555,097? (I just made that up by randomly hitting keys on my word processor.) First you would have to try dividing it by 2, then 3, then 5, then 7. . . and on and on.It's been estimated that factoring a number hundreds of digits long would take the fastest supercomputers billions of years. A quantum computer could do it in seconds.

Q: That sounds exciting for mathematicians, but what are the practical benefits?
Every time you use a credit card to buy something from Amazon or Ebay, the information is encrypted using a system that is based on the difficulty of factoring very long numbers. Military and corporate secrets are often encrypted the same way. (They just use longer numbers.) The system works because of the inherent limitations of today's computers. But an electronic thief armed with a quantum computer would be able to break the hardest codes with ease.

Q: Besides encryption technologies, what other sorts of breakthroughs are possible?
For many scientists the most exciting thing is that quantum computers—even the experimental ones that now exist in the labs—are deepening their understanding of how the universe works. We already know that electrons, protons, photons—all the subatomic particles— obey the strange dictums of quantum theory. (Remember "Heisenberg's uncertainly principle" or "Schrödinger's cat"—the one that is dead and alive simultaneously?) By making computers that behave in the same manner, scientists are getting a hands-on feel for how very weird reality can be.

Q: How close are we to the creation of a quantum computer?
They are already here, in very simple form. And every year they are becoming more powerful. But how long will it be before someone makes a quantum computer powerful enough to crack the world's hardest codes—10 years, 30, 100? That is the billion dollar question.

Q: Do you foresee this technology ever being made available to the public?
Much as I'd love to have a quantum computer on my desk, right now that seems like a far-off dream. But consider: In 1949, an article in Popular Mechanics, describing a state-of-the-art supercomputer called the Eniac, made this prediction: "Where a calculator like the Eniac today is equipped with 18,000 vacuum tubes and weighs 30 tons, computers in the future may have only 1,000 vacuum tubes and perhaps weigh only 1/2 tons.'' Recently a group of electrical engineering students at the University of Pennsylvania duplicated the entire circuitry of the Eniac
on a silicon chip smaller than a fingernail. That leaves me feeling rather optimistic.

Q: How might a working quantum computer conceivably effect our daily lives?
The good:
• Searching vast databases in a matter of seconds. (Imagine being able to do a full-text search of every word in the Library of Congress.)
• Solving mathematical problems that have stumped scientists for centuries.
The bad:
• The breakdown of secret codes used to guard credit card transactions and other
personal financial information.
• The compromise of sensitive classified military information.

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews