quantum computer

a quantum computer is a computing device that makes use of the fact that, in terms of quantum mechanics, physical systems can be in a superposition of several states at the same time. Using a number of 2-state systems (qubits), binary information can be encoded just the way as in classical computation - with the difference, that all possible binary states can be encoded in the q-register simultaniously. the quantum computer carries out the computation by means of reversible operations on the qubits and processes the whole superposition of inputs at once - that's where the quantum parallelism comes in.

Quantum computers have first been proposed by Richard Feynman in the early 80's. When David Deutsch wrote his famous paper "Quantum theory, the Church-Turing principle and the universal quantum computer" in 1985 the hype started. He formulated the notion of the quantum-Turing machine and made quantum computers accessible to both computer scientists and physisists. In 1994 Peter Shor finally presenented his prime-factorizing algorithm which factorizes products of large primenumbers efficiently on a quantum computer while no efficient algorithm for the classical computer has yet been found. This algorithm is of particular interest for the cryptography-industry as the security of most of the common cryptoalgorithms (as RSA) relies on the fact that large numbers can not be factorized efficiently.

The implementation of quantum computers still lies in the far future (it is y2k now). For computation in a quantum computer it is crucial to maintain the coherence of the superposition of the qubits in order to keep q-parallelism and do reversible computation. As physical systems tend to interact with their environment they are subject to decoherence (they entangle themselves with the environment and turn into mixed states). The main task therefore lies in completely shielding the qubits from their environment which is as yet impossible for more than 7 qubits.

There are three major areas that are being pursued in the creation of the actual computing machines (as opposed to quantum algorithms). The most successful in numbers of qubits has been the NMR quantum computer. Another major thrust has been with the linear ion array, and finally a less developed, but still attractive method is called quantum QED.

The idea of Quantum Computing was first proposed by Feynman based on the idea that simulating a quantum system would be a hard problem for a classical computer. The logic goes somewhat like this. Consider N quantum particles. At the next time step there are approximately N possibilities. After N time steps the number of possibilities has gone up to N^N. Thus simply storing all possible alternatives requires memory which goes up exponentially.

On the other hand a quantum system could easily simulate another quantum system. This idea was put in a more concrete form by Peter Shor in 1995 with Shor's algorithm which showed that it would be possible for a quantum computer to factorize a large number using a polynomial time algorithm.

As the fact that factorizing a large number is a "hard problem" for a classical computer is the basis of RSAencryption, this discovery spurned off a lot of research on Quantum Computing.

A lot of research is being done both in trying to realize a quantum computer using technologies such as NMR and in developing new algorithms. More information and links may be found at http://www.qubit.org.

This node looks like it needs updating on the current state of play with quantum computing. For a start, of course, we still don't have one. There are no useful quantum computers. Quantum software is coming along nicely, so if we create one, it won't just sit there unused for years.

You'd know if we had a full-scale one. Oh yes. As mentioned above, the RSA encyption algorithm is dependent upon factorization being very hard to do. Quantum computers make it quick and easy. There is quantum encyption, of course, but that's a seperate problem and is not likely to be implemented any sooner than quantum computing renders our current codes redundant.

So, how is quantum computing actually coming along?

Slowly.

Physicists hijacked a medical method called nuclear magnetic resonance, which allows nuclei to be given a certain spin representing a qubit using electromagnetic fields - typically from radio waves. Nuclei cunningly dodge the decoherence problem described above because they don't interact with their environment much.

This seemed promising for a while. IBM built a 7-qubit device, and successfully factored 15 with it. There have been talks of a 10-qubit computer, but sadly that's nearing the upper limit for NMR. Scientists don't believe that a machine of more than fifteen qubits is possible with this method.

The reasons for this are two-fold. For a start, the computer's return is recorded by measuring the magnetic field of the nuclei. These are so weak that you need a lot of molecules with the same spin to make it measurable. This could be theoretically overcome, but the real problem is that, unlike traditional computing, you don't know the initial spin of the molecules involved. This noise completely overcomes the signal once you have enough molecules to represent more than fifteen or so qubits.

Recent efforts have turned to that great bastion of engineering, solid state technology. Promoted by David DeVincenzo, this method uses so-called "quantum dots" on a silicon chip, controlled by electrodes. So far, only one qubit devices have been constructed, but importantly, there's no obvious signs of an upper limit so far. We could have several qubits on one chip in a few years. One to watch.

A second possibility is a superconducting circuit, which uses superposition to make the current flow both ways. These could be small and easily placed onto chips, creating large-scale circuits like those of a traditional computer. So far, there's been no success in linking these chips together, but again, there's no suggestion as yet that this is a dead-end.

So far then, we have a few avenues for research, and numerous other contenders by the way side. There's no theoretical reason why a useful quantum computer can't be created, as far as we know. This puts physicists in a "win-win" situation; if a quantum computer is built, all well and good. If they can find some reason why it cannot, as a matter of principle, ever be built, they have a whole new area of theory to explore. Most physicists are nevertheless hopeful that it can be achieved. With any luck, it's just a matter of time.