SECOND IN A 2-PART SERIES ON QUANTUM COMPUTING
Three and five! The result was correct. After spending long nights in the lab during the spring of 2001 tweaking and fixing a roomful of equipment, my colleagues and I at Stanford University and the IBM Almaden Research Center had built a computer that could successfully calculate the prime factors of 15. To be sure, you don’t need a computer for that--a fifth-grader could give you the answer. What was so remarkable about our machine was that it computed not by toggling a bunch of transistors but by manipulating deep quantum-mechanical properties of individual atomic nuclei. In doing so, this quantum computer prototype factored 15 in a fundamentally different way, and in fewer steps, than any conventional computer was capable of doing.
Six years later, we’re still hunkered down in labs--albeit different labs, having dispersed to various research institutions throughout the world--and we’re now seeking to build bigger and better quantum computers. We want a computer that can factor not 15 or 21 or 35 but 300-digit-plus numbers. Such a system would in principle be able to break today’s most advanced cryptographic codes and could be used to engineer new ways of protecting data. A quantum computer would also easily simulate physical models that today’s top supercomputers can’t handle--calculating the quantum energy levels of atoms, for example, or simulating the behavior of conventional transistors as they shrink to diminutive dimensions where the laws of quantum mechanics rule. Quantum computers may also speed up key types of search problems in which the correct solution must be found among a vast number of trial solutions [see " Connecting the Quantum Dots."
As we look forward to such possibilities, we often look back to that first Stanford-IBM machine. It taught us a couple of important lessons. The first was that the quantum-mechanical property we used to store the computer’s data proved an excellent choice. This property is spin, a kind of intrinsic angular momentum exhibited by atomic nuclei, electrons, and other particles.
The second lesson was that the way we used spin posed some big challenges. The core of our quantum computer consisted of a custom-synthesized organic molecule in a solution. It had five fluorine and two carbon nuclei whose spins we used to store seven units of information, called quantum bits, or qubits. We blasted the molecule with radio-frequency pulses to alter the spins according to the computational steps of the factoring algorithm. To read out the qubits, we used nuclear magnetic resonance, or NMR, to generate a frequency spectrum of each spin. It worked beautifully for seven qubits, and in fact that system remains the only one to have factored a number to this day. But designing molecules suitable for more complex calculations became just too hard.
If we wanted a quantum computer that we could scale up, we needed a system that would let us precisely manipulate tiny bits of energy, that could be effectively shielded from external interference, and--most important--that could be built by replicating tiny identical building blocks within a small area. We needed something less like a test tube--and more like a microchip.
A semiconductor quantum computer is now the goal of dozens of research groups worldwide. In the last few years, these groups, including my own at Delft University of Technology, in the Netherlands, have made rapid progress in creating qubits based on materials and processes similar to those used in the microelectronics industry to manufacture standard processors and memory chips. [See ”The Trap Technique,” IEEE Spectrum, August, for the first part of this report.]
The advantage of a solid-state design over the NMR approach is the ability to fabricate large arrays of miniature electronic devices that can be individually addressed and interconnected--just as we do with transistors in an integrated circuit. One promising approach to such a solid-state system was put forward by Daniel Loss of the University of Basel, in Switzerland, and David DiVincenzo of the IBM T.J. Watson Research Center, in Yorktown Heights, N.Y. In their January 1998 paper, ”Quantum Computation with Quantum Dots,” in Physical Review A, they proposed trapping individual electrons in semiconductor structures called quantum dots and then using the electrons’ spins as qubits.
With typical dimensions from a few nanometers to a few micrometers--about the size of a virus--a quantum dot is a tiny area in a semiconductor that can hold anything from a single electron to several thousand. To make a quantum dot that’s suitable for a quantum computer, you start with a half-millimeter-thick wafer of gallium arsenide and cover it with an even thinner, 100''nm-thick layer of silicon-doped aluminum-gallium-arsenide. Free electrons will concentrate at the interface between the two materials, forming a thin electron sheet. Next, you attach a set of gold electrodes to the top layer and apply negative voltages to them. The electrodes will repel electrons in the sheet underneath and create small islands of electrons isolated from the rest.
Creating such electron puddles is relatively straightforward, but manipulating electron spin is a different matter. Like charge and mass, spin is considered an intrinsic property of electrons, and yet it remains somewhat mysterious. We can measure spin because it interacts with an external magnetic field, much as an ultrasmall magnet rotating about its own axis would. But unlike with a real magnet, when we measure an electron’s spin orientation, there will be only two possible outcomes: the spin and the external field are pointing in the same direction, or they are pointing in opposite directions. These two possibilities are also referred to as spin up and spin down, respectively.
More interesting--and bizarre--is that spin can also exist in a combined state of up and down. This superposition state is one of the things that set quantum computers apart from classical ones. A three-bit conventional memory, for example, can hold any combination of three bits at a time: 000, 001, 010, 011, 100, 110, 101, or 111. But using qubits, and representing spin up as 0 and spin down as 1, you can do much better: a three-qubit memory can hold all those eight states simultaneously. As a result, if you perform a calculation using those three qubits, you in effect perform a calculation on all eight states at once. As you add more qubits, this quantum parallel processing increases exponentially.
To perform quantum computations, however, you need to link the qubits somehow. The way researchers do that is by using the quantum phenomenon of entanglement. Two entangled spins can exist in a superposition of, say, up-down and down''up. You don’t know which electron has which spin until you measure it. But as soon as you measure one spin, that means the other spin must have the opposite value. How do they ”know” which way to point? Scientists devised ingenious experiments to test entanglement and concluded that entangled particles don’t carry a ”preprogrammed” behavior. Instead, according to quantum mechanics, the pair of electrons forms a single entity. Each electron’s spin by itself has no definite orientation until one of them is measured, no matter how far apart they are. Einstein rejected this notion and famously called it ”spooky action at a distance.”
Spooky indeed. But those are the rules of quantum mechanics, and we might as well use them to our advantage. Quantum researchers not only accept spin’s weirdness, but they also embrace it. They think of spin as a vector in a mathematical domain called a Hilbert space. Basically, this vector describes the probabilities of obtaining spin up or down when a particle’s spin is measured. The researchers perform a host of mathematical transformations to those vectors to concoct quantum computing algorithms. But as physicist Asher Peres has put it, ”Quantum phenomena do not occur in a Hilbert space, they occur in a laboratory.” And it’s in the lab that our group and many others set out to build a practical quantum computer.