"Every other computer in the world takes several steps to solve the order-finding problem, but our quantum computer solved it in a single step," said Stanford University researcher Lieven Vandersypen. The quantum computer was invented by IBM Almaden Research Center researcher Isaac Chuang, who led a team of scientists that included fellow researchers Gregory Breyta and Costantino Yannoni of IBM Almaden, professor Richard Cleve of the University of Calgary, and researchers Matthias Steffen and Lieven Vandersypen from Stanford University.

Long way to go
Since the late 1980s Chuang has been pursuing ever-more-sophisticated realizations of quantum computers. His last effort was a 3-qubit machine. While the latest version represents a rapid advance for the field, quantum computing still has a long way to go before it will compete with leading-edge supercomputers. But researchers in the field are optimistic that machines of competitive size will appear in this decade.

That optimism was reflected in a statement by IBM's Chuang. "This result gives us a great deal of confidence in understanding how quantum computing can evolve into a future technology," Chuang said. "It reinforces the growing realization that quantum computers may someday be able to live up to their potential of solving, in remarkably short times, problems that are so complex that the most powerful supercomputers couldn't calculate the answers even if they worked on them for millions of years."

The order-finding problem determines the period of a function. In digital computers, that requires a step-by-step iterative solution of the function's values until they begin to repeat. The quantum computer, however, solved the order-finding problem without any iteration steps.

Its ability to obtain a single-step solution can be traced to the nature of qubits. Because quantum bits simultaneously represent all possible values of the input variables, the single step of a quantum computer considers every possible input value at once. Hence, the single step can solve problems of any size. That represents the ultimate in parallel processing: parallelism at the bit level.

While a quantum computation starts and ends with information encoded in binary bits, the computation itself is performed in the mysterious realm of quantum mechanics, where a physical system can be in what is known as a superposition of states.

Using nuclear magnetic resonance, it is possible to measure whether the constituent particles of an atom — the protons and neutrons in its nucleus — are spinning in one direction or another. Such a measurement represents the output stage of the computation, since once observed, an elementary particle's spin becomes fixed in one of its binary states: spin up or spin down.

One spin direction is designated "0" and the other designated "1," but both are only probabilities during the course of a computation. IBM's 5-bit quantum computer used the spin configuration in fluorine atoms to represent qubits, but other experiments have employed the spin of carbon or oxygen atoms.

Logic is performed in any quantum computer when its qubit atoms affect the spin of neighboring qubit atoms. When structured properly, the quantum-computer atom can perform a number of mathematical operations in parallel.

In short, quantum operations are the reversible generalizations of standard digital operations. A quantum computer's basic operations are often compared with probabalistic algorithms.

Many probabalistic algorithms can be sped up by random search methods. For instance, the occasional multiplying of intermediate results by a random number and checking for performance gains can uncover shortcuts in gradient descent algorithms that would otherwise have to be discovered one by one via exhaustive searches. Such probabalistic circuits can always be transformed into larger, slower deterministic circuits.

For the two-element order-finding problem here, a deterministic circuit requires an exponential number of steps (four), while a probabalistic circuit only requires a polynomial number of steps (less than four, but more than one). The quantum circuit required only a single step.

Quantum circuits extend the probabilistic notion by generalizing the one-way operations of both deterministic and probabilistic operations into reversible operations. Qubits enable reversible procedures by taking on not only the 1 and 0 symbolized by all bits but also holding a vector length expressed as a complex number. Thus, a qubit encodes both a spin direction — expressed as 1 or 0 — and a complex amplitude.

The resulting qubit vector is angled into a multidimensional space equal in dimension to the number of qubits stored in a system. A 2-bit qubit computer thus can solve, in a single step, problems represented in two-dimensional space. In IBM's 5-qubit quantum computer, only two qubits could be used, since three had to be reserved for calculating the result. Consequently, IBM's 5-qubit quantum computer was only able to solve 2-bit problems. However, future multibit quantum computers should in theory scale up to higher dimensional spaces merely by adding qubits.

The biggest problem with quantum computers is that the quantum states must remain unobserved, or "decoherence" will spoil their ability to take on different values simultaneously and therefore disable them from solving problems in a single step. That problem stymied the first attempts to build quantum computers, since any isolated particle, such as an electron or photon, could be too easily disturbed by environmental effects. The first successes at Harvard, MIT and IBM's Almaden Research Center were based on the use of atoms as stable environments for particle states.

IBM's answer here, suggested earlier this year in a paper by Cleve, was to tack on a quantum Fourier transform of the results and then decode the answer from its spectrum. A quantum Fourier transform essentially performs a discrete Fourier transform on the amplitude part of the qubit vector, allowing the final quantum state of the computer to be inferred by humans after their examination of the qubit atom's frequency spectrum, rather than through direct observation of the probabilistic state.

The specific problem IBM's 5-qubit computer tackled was the ordering problem, a precursor to the integer-factoring algorithm used to decode encyphered data. Traditional deterministic algorithms must exponentially expand computing resources as problems get bigger, but with a quantum computer it takes the same number of steps to solve any size problem, as long as there are enough qubits to encode the variables and the algorithm. Thus, the CPU's power scales up exponentially with the number of bits in its "registers."

That fact, and a practical quantum-based algorithm for factoring large numbers, was first published in 1994 by Peter Shor of AT&T Research. Since encryption plays a central role in national security, Shor's result stimulated a round of government funding in quantum-computer research.

Two bits, four ways
The order-finding problem used in IBM's demonstration essentially found the period of a 2-bit function. Here, that amounted to repeatedly permuting a 2-bit string with the same function — four possible ways for two bits — until returning to the original 2-bit value. The number of permutations needed is equal to the period of the "ordering" function. According to a statement by IBM, this is the most complex algorithm yet solved by an actual quantum computer. For the five-qubit quantum computer, a two-element ordering problem was encoded by putting the starting state in the first two qubits. Radio frequency pulses were used to put the five atoms into the correct starting state, then a second set of pulses induced a single permutation of the function in the two "input atoms," and the interactions among the spins caused the answer to be calculated.

"In essence, the quantum computer simultaneously answers what happens after one, two, three and four permutations; then we take the quantum Fourier transform to find the period," said Vandersypen. The quantum Fourier transform was measured with standard laboratory magnetic resonance equipment, permitting the results to be read out from the spectrum of three qubit atoms.

Once these molecular methods mature, they may actually represent an advance over silicon-circuit fabrication processes. Instead of having to define complex circuits from the ground up using photographically reduced drawings, quantum circuits could be fabricated using automatic controlled chemical reactions. Current research indicates that the use of internal nuclear states is a stable environment for the representation and modification of qubits.