A research team in Japan says it has successfully demonstrated for the first time in the world in a solid-state device one of the two basic building blocks that will be needed to construct a viable quantum computer.

The team has built a controlled NOT (CNOT) gate, a fundamental building block for quantum computing in the same way that a NAND gate is for classical computing.

Research into quantum computers is still in its early days and experts predict it will be at least 10 years before a viable quantum computer is developed. But if they can be developed, quantum computers hold the potential to revolutionize some aspects of computing because of their ability to calculate in a few seconds what might take a classical supercomputer millions of years to accomplish.

The team reporting the breakthrough is headed by Tsai Jaw-Shen and jointly funded by NEC Corp. and Japan's Institute of Physical and Chemical Research (RIKEN). Tsai said his team has successfully demonstrated a CNOT gate in a two-qubit (quantum bit) solid-state device.

The CNOT gate is one of two gates used with quantum bits (qubits) that are the basic building blocks required for a quantum computer. The other, a one-qubit rotation gate, was demonstrated by Tsai's team in 1999. Now that both have been demonstrated, Tsai says one of his goals is to combine them to create something called a universal gate which is a basic unit of a quantum computer.

"Another goal is to do some quantum algorithms based on this," he said.

One of the biggest tasks Tsai says he faces is extending the time for which the two qubits are coupled together in a state known as quantum entanglement. In this state, which is one of several exotic properties associated with qubits and crucial to quantum computing, the two qubits act together even though they are not physically connected.

Tsai announced in February this year that his team has succeeded in entangling a pair of qubits.

Among the startling properties of qubits is that they do not just hold either binary 1 or binary 0, but can hold a superposition of the two states simultaneously. As the number of qubits grows, so does the number of distinct states which can be represented by entangled qubits. Two qubits can hold four distinct states which can be processed simultaneously, three qubits can hold eight states, and so on in an exponential progression.

So a system with just 10 qubits could carry out 1,024 operations simultaneously as though it were a massively parallel processing system. A 40-qubit system could carry out one trillion simultaneous operations. A 100-qubit system could carry out one trillion trillion simultaneous operations.

That means calculations, such as working out the factors of prime numbers, which present problems for even the fastest supercomputers could be trivialized by a quantum computer. As an example Tsai estimated that using the Shor Algorithm to factor a 256-bit binary number, a task that would take 10 million years using something like IBM Corp.'s Blue Gene supercomputer, could be accomplished by a quantum computer in about 10 seconds.

However, there are numerous hurdles which need to be overcome before anything like that becomes possible. The largest problem Tsai faces at present is keeping the qubit pair in entanglement for as long as possible before decoherence sets in.

"Fighting the decoherence time is the largest problem," he said. "For other problems there are some solutions and lots of possibilities but the decoherence is more difficult."

"The decoherence time (observed in the experiment) is rather short," he said. "We didn't optimize it so its roughly a few hundred picoseconds. (A picosecond is a trillionth of a second) A CNOT time pulse is about 15 picoseconds so within that time we can do a few operations, maybe two or something."

Despite the hurdles, Tsai's research is going well, said Eiichi Maruyama, director of the Frontier Research System at RIKEN. He said its still hard to estimate when a viable quantum computer might be developed however. "Our guess is anywhere between 10 years and 100 years from now," he said.

Full details of Tsai's experiment are included in the Oct. 30 edition of the British scientific journal Nature.