Until
next week,Let Your Coffee Do the Computing. An overview of quantum computing
Dateline: June 15, 1997
"IT'LL never fly," say its critics. "Neat physics, but not practical." And maybe they are right. Purblind people were also right about Leonardo da Vinci's flying machines and Leibniz's 17th Century digital computer.
The point is: If not it, then something like it that will achieve the same end, and if not now, then soon enough. I am talking about a quantum jump in computer processing power, and I do mean quantum.
Quantum computing uses the extraordinary properties of quanta (subatomic particles) to perform difficult calculations conventional computers would take literally for ever to compute. The American Association for the Advancement of Science calls it "the Mount Everest of computing," noting that "a quantum computer . . . in a few seconds could perform calculations that would take billions of years on an ordinary supercomputer." What sort of calculation could possibly take so long?
What times what equals 15? Five times three, right? You probably didn't even have to calculate that—you memorized the solution long ago. How about:
? x ? = 29083
Using the "trial division" method you were taught in school, it would take you about an hour to "factor," as the procedure is called, this 5-digit number down to two whole numbers which, multipled together, would give you 29083. Quantum researcher A. Barenco adds the mesmerizing fact that "factoring a 30-digit number using trial division is about 1013 times more time or memory consuming than factoring a three digit number."
The largest number ever known to have been factorized had 129 digits. It took a network of supercomputers working in parallel eight months to find the answer! To factorize a 1,000-digit number would take our most powerful conventional supercomputers more than the estimated 100 billion years the universe has left to run.
How often do we need to factorize enormous numbers, you ask. More often than you might think. The most modern method of cryptography, used to secure email and financial transactions and secret government communications, relies on the fact that factoring big numbers is time-consuming. When quantum computing arrives, we can throw that method of secure transactions in the garbage can—a quantum computer would break the most sophisticated code in no time flat.
We also need, often and increasingly, to search through ever-growing amounts of data accumulating in our databases and on the Web. Searching for patterns is the same order of calculation we face with factoring, where the calculation takes exponentially longer as the search space gets bigger.
How does it work?
All binary computing use switches, gates, and registers to manipulate and store bits (binary digits: 0 and 1), represented physically (electronically) by low or high voltage, respectively. A conventional processor can only handle one of the two possible states of each bit at a time. A quantum computer uses the fact that subatomic particles can be in two opposite states simultaneously. A particle is both on and off, up and down, left and right, 0 and 1, true and false . . . until we look at it. As soon as we do, it only then decides whether to be on or off, up or down, true or false, etc.
A writer for The Economist explains it very well: "The switches inside a computer can also be interpreted as the trues and falses of a form of logic known as Boolean algebra. Indeed, they are organised into `logic gates' that do calculations using this algebra. A digital computer is mainly a machine for altering bits by running them through logic gates. The gate known as AND, for example, compares two bits. If both have a value of `one', it creates an output of one; otherwise it creates a zero. With the next tick of its internal clock, the computer then passes this output bit to another gate for further processing. Each tick, then, corresponds to one step of the calculation.
In the quantum world, however, the rules are different. A quantum computer's switches would not have to be either on or off. Like any quantum object which can come in several distinct states, a quantum switch can carry on indefinitely as a combination of all those states. It is not merely stuck halfway between on and off; it is actually on and off simultaneously, as if it existed in two parallel worlds.
The bits in a `quantum computer' would not, therefore, be ones or zeros. They would be quantum combinations of one and zero. Such vacillating pieces of information are known as `qubits' (pronounced as `cubits', though they are usually rather smaller than the ancient Hebrew unit of length).
It is this simultaneous existence in many states that would give quantum computing its power. An ordinary computer having (say) ten bits could exist in only one of 1,024 states (all the ten-digit sequences that can be made from ones and zeros) available to it, at each instant. A quantum computer with ten qubits could exist in all 1,024 states at the same time. It could therefore work on 1,024 calculations at once."
So if we could use particles to compute using qubits, we'd square the base power of the processing. But how can we do that without looking at the particles?
"The problem with building a quantum computer is that the . . . qubits simultaneously need to be protected from the environment so that they retain their quantum phase," explain Neil Gershenfeld and Isaac Chuang, quantum scientists with a taste for coffee, "but they need to be coupled to the environment so that initial conditions can be loaded, the calculation applied, and the results read out. Because of these apparently contradictory constraints, it's taken a heroic experimental effort to make just a 2 bit quantum computer. This has been done in systems such as trapped ions, or cavity quantum electrodynamics, that carefully isolate the qubits and cool them to their ground state."
These "heroic" techniques require rooms full of very delicate and expensive equipment. Just cooling a particle to its "ground state" means getting down to a fraction above absolute zero. And imagine trying to isolate or "trap" a single photon and keep it "alive" long enough for it to perform some operation, while all the time being careful not to let anything—not even your glance—touch it.
It has been done, but easy, it is not. So Gershenfeld and Chuang have developed "an entirely new approach to quantum computation that promises to solve many of these problems. Instead of carefully isolating a small number of qubits, we use a large thermal ensemble (such as a cup of coffee). Such a system has ~10^23 degrees of freedom; by applying RF pulses that excite nuclear magnetic resonances, we can create a tiny deviation from equilibrium that acts just like a much smaller number of pure qubits.
The nuclear spin is beautifully isolated from the environment; its spin coherence can last for thousands of seconds. By representing the effective computational qubits in such an ensemble, we get these very long coherence times permitting thousands of logical operations before coherence is lost. Further, because the bits are represented in an ensemble, it is possible to continuously read out the quantum state (something that is of course impossible for individual quantum degrees of freedom). Best of all, the most important part of the experimental apparatus is built by nature in the form of ordinary molecules.
Implementing such a quantum computer requires the mature techniques of multiple pulse spin resonance. Using existing NMR spectrometers it will be straightforward to reach about 10 qubits, enough to demonstrate for the first time quantum superfast algorithms and quantum error correction, and to prepare a range of unusual quantum states that have never been realized before . . . . The required instrumentation even promises to scale down to the desktop, so that everyone could have a quantum co-processor." (Emphasis added.)
By manipulating the spins in three distinct types of quantum systems that exist within the liquid, one research group has already constructed a three-qubit system that has successfully executed the mathematical calculation 1+1=2. Well, hey, we all had to start somewhere! The point is, the quantum computing concept has been proved experimentally, and in my opinion it's only a matter of (not much) time before a quantum computer can lick Deep Blue hands down at chess.
Quantum Computing and AI
Is quantum computing vital to AI? I suspect it may prove to be, although a single machine with as much processing power as a single human brain seems possible just on the basis of Moore's Law (by Intel's Gordon Moore) which says that "The number of elements in advanced integrated circuits doubles every year."
But in about two decades, integrated circuit ("chip") manufacturing is going to bump up against physical limits: a transistor will be just one atom wide, for example, and you can't go smaller than that—unless you go subatomic, or quantum. Gershenfeld and Chuang predict that the cost of the fabrication plant for conventional chips just a few atoms in size will be "the GNP of the planet."
Nevertheless, David J. Kuck, holder of the Charles Babbage Outstanding Scientist Award (among many other honors for distinguished contributions to supercomputing), notes that "Following Moore's Law, even at a decreased growth rate, future computers are likely, in terms of physical capacity, to match the human brain."
What is the "physical capacity" of the human brain, in terms of memory storage and processing power?
Nobody's quite sure, but estimates are that the brain stores somewhere between 1013 and 1017 bits. That's roughly between 1,000,000 and 10,000,000,000 megabytes of memory, or quite a lot. But we already have computer storage capacity within that range.
Estimates of brain processing power are even less precise: between 10 and 100,000 teraflops (billions of floating point operations per second). "The general consensus of the experts," wrote Frank Tipler in 1994, "is that our fastest supercomputers should be in the 1,000 teraflop range by 2002," but that if the higher estimate of 100,000 teraflops turns out to be correct then it will take—wait for it—a whole seven years more before we have a single conventional supercomputer equal to a single brain in processing power.
Of course, memory and processing power won't stand still in the year 2002 (or 2009), but will continue to grow within the limits of the technology of the day. It may well be that current silicon architectures will indeed pose limitations, but optical, molecular, atomic, and quantum computing are waiting in the wings.
We should stop thinking and talking about an intelligent machine in terms of a single machine sitting in one spot, and think of it instead in the manner discussed in last week's article, as the collection of millions of machines that constitute the Internet. Sun Microsystems' tagline has for years been: "The network is the computer," and Sun is right. Add up the memory and processing power of all the machines on the Internet, and it's probably already far beyond the capacity of any single human brain.
Let's not forget also that neither you nor I nor Machina sapiens is just a brain. As discussed in an earlier article, we and it also have a body which does a huge amount of processing, some of it without even consulting the brain. So it takes massive computing power—memory storage and information processing—to run an entire organism; more than just a brain.
On June 11, the Institute of Child Health in London, UK announced the discovery that "sociability" in women (which is self-evidently stronger than in men) is coded in the genes. (Curiously, the gene is contributed to the daughter by the father, not the mother.) Dr. David Skuse told a news conference: ``What we hypothesise is that females are genetically programmed to pick up socially appropriate behaviours. What we call feminine intuition—the ability to suss out social situation based on cues—has a genetic origin which has nothing to do with hormones.''
This is more than just another indicator that we, too, are code-driven machines: It is evidence that amorphous aspects of our behavior, such as sociability and intuition, are programmable.
This may imply that the processing power needed to run code that does so much must be enormous, perhaps much greater than 100,000 teraflops. If that turns out to be the case, then quantum computing may prove to be essential for Machina sapiens. Even if it does not prove to be essential, it is certain that Machina sapiens will one day run at quantum speeds, and be that much smarter for it.
Until
next week,
NEXT WEEK: The Weakening Case Against Machina sapiens. Penrose & Searle.