According to Wall Street Journal columnist Lee Gomes, you know an idea's time has come when it "starts to be taught to undergraduates as though it is old hat." Gomes says that's what led him to sit in on a session of UC Berkeley's senior-level course in "Qubits, Quantum Mechanics, and Computers" last spring, C/CS/Physics 191 — a course otherwise known as quantum computing.

Two people the columnist heard speak that day, teacher Michael Crommie and guest Thomas Schenkel, are both staff scientists at Berkeley Lab, Crommie in the Materials Sciences Division and Schenkel in the Accelerator and Fusion Research Division (AFRD). Crommie, who is also a professor of physics at UC Berkeley, studies atomic and molecular structures on surfaces. Schenkel is heading a project at Berkeley Lab to demonstrate hardware for a quantum computer.

"In our class we start with a foundation in quantum mechanics and only later build up to the machinery we might use," says Crommie. Crommie teams with Umesh Vazirani, an associate professor in UC Berkeley's Department of Electrical Engineering and Computer Sciences; the two created the course in concert with K. Birgitta Whaley, a UCB professor of chemistry.

Asked about the genesis of the class, Vazirani says that for him the motives were twofold. One was a straightforward desire to give undergraduates a jump-start in the field of quantum computing, a subject otherwise taught only at the graduate level. His other motive is more basic:

"Like others, I have thought for a long time that quantum computing is the right way to introduce students to quantum mechanics," Vazirani says. "If you begin with the basic concepts that make quantum computing work, you can grasp the fundamentals of the theory of quantum mechanics itself."

Superposing the question

Perhaps the most fundamental of all is the concept of the superposition of states, made infamous by the parable of Schrödinger's cat. Schrödinger's cat is a creature who exists in a superposition of dead and alive, until the moment an observer opens the box and peers in (death may or may not have been triggered by the radioactive decay of a single atom, an unpredictable quantum event with a calculable probability). In the vocabulary of quantum mechanics, looking into the box is a measurement. When a system with superposed states is measured, probabilities collapse to certainties, in this case life or death.

Quantum superposition and measurement are customarily confined to the microworld, however, where their defiance of common sense is less obvious. Like Schrödinger's macroscopic cat, a typical microscopic system has two (or more) discrete states, which may be the spin — up or down — of a particle or atomic nucleus, or the polarization — call it horizontal or vertical — of a photon. So long as the system hasn't been measured, both states might be equally probable; they are superposed. Practically speaking, the quantum-mechanical system can be in both states at once, until it is measured.

A two-state system is also the basis of classical computing, in which bits of information are manipulated through binary arithmetic. Each bit is either a 0 or 1 — but not, in a classical system, both at once. In a quantum computer a bit (a "qubit") is different: it represents 0 and 1, both at the same time.

In a classical system a register consisting of three bits, say, can occupy just one of eight states, with no uncertainty about it: the eight possible numbers are written in binary as 000, 001, 010, 011, 100, 101, 110, or 111. Because of superposition, however, a three-qubit register can store all eight numbers at once. In fact whatever the number of qubits in a quantum computer's register — say, 50 — it can store two (states) to the power of that number. Two to the power of 50 is well over a quadrillion.

Because of this scaling it was long thought that a quantum computer, if one could be constructed, would have vast memory capacity. But although superposition opens a "huge space in which a relativity small amount of information can be spread out, operated upon, and collapsed at will," Vazirani says, most of it is unavailable for ordinary data storage.

"Operations in this enormous space allow us to peek at the private world of Nature, which is extremely complex but pretends to be otherwise," he says. As a result, it may be possible to perform some kinds of mathematical operations with a quantum computer that can't be done in any other way.

Thomas Schenkel of AFRD describes one of the most spectacular: "In 1994, Peter Shor of Bell Labs came up with an algorithm for factoring very large numbers with a quantum computer," Schenkel says. "The difficulty of factoring is at the core of modern methods of encryption."

Using paper and pencil, it would take most people about an hour of trial-and-error long division to find the only two numbers, or factors, that when multiplied together equal the five-digit number 29,083 (they are 127 and 129, a unique solution except for 1 and 29,083 itself) — although it takes only a minute to go the other way, that is, to arrive at 29,083 by multiplication. (This example is taken from an article by Adriano Barenco et al; see Additional information below.) Likewise, classical computers are good at multiplying large numbers rapidly, but bog down trying to factor large numbers.

"When Shor suggested that with his algorithm and a quantum computer you could factor a very large number in a very short time, he let loose a storm of activity," says Schenkel. Soon, finding a practical way to realize what had until then seemed like a purely mental exercise had assumed new importance in research labs around the world.

A tangled web of calculation

Crommie says, "Beginning with understanding a qubit, the quantum mechanical behavior of a two-state or two-level system" — electrons orbiting an atom can have many energy levels, with an electron jumping between two of them serving as a qubit — "we ask how does a qubit evolve in time? How do we measure it? What is a measurement?"

(This last is a question that particularly troubled Albert Einstein, who asked, "Is it enough that a mouse observes that the moon exists?")

Here's the best part: if qubits are prepared in the right way, the computer can perform a calculation on all of them virtually at once. Crucial to this capacity is the concept of entanglement, an intimate relationship that may exist between two or more separate quantum systems. Quantum entanglement is almost as well known as Schrödinger's cat, in the form of the so-called Einstein-Podolsky-Rosen paradox, or EPR (which was an expression of Einstein's unhappiness with the implications of the quantum theory he helped create).

One version of EPR goes this way: suppose two photons are prepared together so that they have opposed polarization, so if one is horizontal, the other is vertical. The states of each are superposed, so initially there is no way to distinguish them by polarization. The two photons are allowed to separate to an arbitrary distance — one could fly to the moon, even "to infinity and beyond" — but because the systems are entangled, when a measurement is performed on one, the state of the other is instantly determined as well.

Einstein's objections to quantum-mechanical explanations of this scenario were many, including the apparent violation of relativity when information appears to travel from one place to another faster than the speed of light. But the effect is real; it has been measured over many kilometers and forms the basis for a number of communication and "teleportation" schemes. In quantum computing, entanglement is what allows the states of many qubits to be related so that measurement of one instantaneously measures them all.

"Once the students understand the theory of two-state systems, we look at how we might use it to embody qubits in the real world," Crommie says. "There are lots of possibilities, but we picked just a few: spin is one, of an electron or an atom — what do you need to do to really put an electron into a superposition? How do you entangle it? The energy levels of atoms are another: how to take a real atom, measure its levels, superpose them, evolve the system in time. Another is polarization of photons: how to manipulate and use it."

Is it really possible?

The nitty-gritty of practical hardware is where classroom guests like Schenkel come in. As a member of AFRD's Ion Beam Technology Program, Schenkel has devoted much of his research to devices called electron-beam ion traps, which produce low-energy, highly charged ions — atoms that have shed many of their orbiting electrons.

Of the several uses for highly charged ions, one in particular fires Schenkel's imagination. In 1998 he read a paper by Bruce Kane in Nature proposing a silicon-based quantum computer . "Kane said 'I can do it in silicon!' and everybody said 'Wow,' because that meant, unlike other schemes, these quantum devices would be scalable."

Schenkel says, "One project is a prototype single-electron transistor," which would encode information in the electron spin of a dopant atom embedded in silicon. "We want to make the current through the transistor depend on the spin of a single electron in a single atom. The expectation is that if we can make one transistor, we can make millions."

Like any quantum phenomenon, electron spins eventually become entangled with their environment, leading to "decoherence" that can obliterate quantum effects. "The time for coherence of a single atom of phosphorus or antimony implanted in silicon is quite long, about 60 milliseconds" — which may not seem all that long until one considers the possibility of virtually instantaneous computation. "Maintaining coherence could be done with controlled pulse interactions, like a juggler keeping a bunch of plates spinning on poles. Except in quantum computing you have to do it without looking at the plates. Once you look at them — make a measurement — they all collapse."

The goal is to plant single atoms in very precise positions in silicon that will be sculpted lithographically. Single atoms are hard to detect unless highly ionized, but the electron-beam ion trap readily makes phosphorus plus-13 (lacking 13 of its 15 electrons), bismuth plus-45 (lacking 45 of its 83 electrons), and other highly charged ions suitable for use with silicon. These are implanted by drilling a extraordinarily narrow passage through or near the tip of a scanning microscope; the tip images the surface of the wafer and positions the ion beam at the desired location

Schenkel's group has used the implanter to spell out the letters "LBL" with dots in resist on a silicon substrate, each dot aligned to within 10 nanometers (billionths of a meter) inside a rectangle 6 by 14 micrometers (millionths of a meter) on a side. This placement resolution is at the upper limit for qubits based on electron spin, but while isolated single ions are easily detected within the dots, single ions haven't yet been implanted at will.

"Our ion implanter is a unique way to implant atoms," says Schenkel. "We want to implant just one, but we haven't done the killer experiment yet." Nevertheless he expects to achieve the goal of demonstrating a layered single-electron transistor, with metal gates on the surface to control input and output, by August 2005. Not long thereafter he expects to demonstrate a full-blown single-electron MOSFET (metal-oxide semiconductor field-effect transistor), a qubit as down to earth as the workhorse transistors in a desktop PC.

But it may take a thousand qubits for a quantum computer to perform dramatically better than classical supercomputers, and the obstacles are formidable. The more qubits that must interact with one another, the faster irreversible decoherence is likely to set in.

Schenkel says, "Some people say quantum computing is impossible, the problems are just too hard. Others, like myself, say quantum computing is inevitable. If you let loose the rules of quantum mechanics on information, you get a far more general theory of information than the classical theory. We have lots of time to figure out how to get there."

It's a faith he shares with Mike Crommie, Umesh Vazirani, and Birgitta Whaley, and their students in C/CS/Phys 191 — who at semester's end made presentations on such topics as quantum error-correction in fault-tolerant memory hierarchies, how to realize Josephson-junction qubits, and a host of other practical schemes. It's a faith that even the Wall Street Journal seems to share.

Additional information

• More about the spring 2005 semester of Qubits, Quantum Mechanics, and Computing , including lecture notes
• More about Michael Crommie's Research
• Access Umesh Vazirani's papers on quantum computing
• More about Thomas Schenkel's Electron Beam Ion Trap
• " A Short Introduction to Quantum Computation ," by Adriano Barenco et al
• Read about how entanglement leads to "information at a distance"
• Lee Gomes wrote about UC Berkeley's quantum computing course in the Wall Street Journal , April 25, 2005, page B1, available online to subscribers .