HISTORY OF QUANTUM COMPUTING
In the classical model of a computer, the most fundamental building block, the bit, can only exist in one of two distinct states, a 0 or a 1. In a quantum computer the rules are changed. Not only can a 'quantum bit', usually referred to as a 'qubit', exist in the classical 0 and 1 states, it can also be in a coherent superposition of both. When a qubit is in this state it can be thought of as existing in two universes, as a 0 in one universe and as a 1 in the other. An operation on such a qubit effectively acts on both values at the same time. The significant point being that by performing the single operation on the qubit, we have performed the operation on two different values. Likewise, a two-qubit system would perform the operation on 4 values, and a three-qubit system on eight. Increasing the number of qubits therefore exponentially increases the 'quantum parallelism' we can obtain with the system. With the correct type of algorithm it is possible to use this parallelism to solve certain problems in a fraction of the time taken by a classical computer.
A number of key advances have been made in the theory of quantum computation, the first being the discovery that a simple class of 'universal simulator' can mimic the behavior of any finite physical object, by Richard Feynman in 1982. David Albert made the second discovery in 1984 when he described a 'self measuring quantum automaton' that could perform tasks that no classical computer can simulate. By instructing the automaton to measure itself, it can obtain 'subjective' information that is absolutely inaccessible by measurement from the outside. The final and perhaps most important discovery was made by David Deutsch in 1989, he proved that all the computational capabilities of any finite machine obeying the laws of quantum computation are contained in a single machine, a 'universal quantum computer'. Such a computer could be built from the quantum equivalent of the Toffoli gate and by adding a few extra operations that can bring about linear superpositions of 0 and 1 states; the universal quantum computer is complete. This discovery requires a slight alteration to the Church-Turing principle - "There exists or can be built a universal quantum computer that can be programmed to perform any computational task that can be performed by any physical object".
Building a quantum computer
A quantum computer is nothing like a classical computer in design; you can't for instance build one from transistors and diodes. In order to build one, a new type of technology is needed, a technology that enables 'qubits' to exist as coherent super positions of 0 and 1 states. The best method of achieving this goal is still unknown, but many methods are being experimented with and are proving to have varying degrees of success.
Quantum dots
An example of an implementation of the qubit is the 'quantum dot' which is basically a single electron trapped inside a cage of atoms. When the dot is exposed to a pulse of laser light of precisely the right wavelength and duration, the electron is raised to an excited state: a second burst of laser light causes the electron to fall back to its ground state. The ground and excited states of the electron can be thought of as the 0 and 1 states of the qubit and the application of the laser light can be regarded as a controlled NOT function as it knocks the qubit from 0 to 1 or from ' to 0.
If the pulse of laser light is only half the duration of that required for the NOT function, the electron is placed in a superposition of both ground and excited states simultaneously, this being the equivalent of the coherent state of the qubit. More complex logic functions can be modeled using quantum dots arranged in pairs. It would therefore seem that quantum dots are a suitable candidate for building a quantum computer. Unfortunately there are a number of practical problems that are preventing this from happening:
* The electron only remains in its excited state for about a microsecond before it falls to the ground state. Bearing in mind that the required duration of each laser pulse is around 1 nanosecond, there is a limit to the number of computational steps that can be made before information is lost.
* Constructing quantum dots is a very difficult process because they are so small. A typical quantum dot measures just 10 atoms (1 nanometer) across. The technology needed to build a computer from these dots doesn't yet exist.
* To avoid cramming thousands of lasers into a tiny space, quantum dots could be manufactured so that they respond to different frequencies of light. A laser that could reliably retune itself would thus selectively target different groups of quantum dots with different frequencies of light. This again, is another technology that doesn't yet exist.
Computing liquids
Quantum dots are not the only implementation of qubits that have been experimented with. Other techniques have attempted to use individual atoms or the polarization of laser light as the information medium. The common problem with these techniques is decoherence. Attempts at shielding the experiments from their surroundings, by for instance cooling them to within a thousandth of a degree of absolute zero, have proven to have had limited success at reducing the effects of this problem.
The latest development in quantum computing takes a radical new approach. It drops the assumption that the quantum medium has to be tiny and isolated from its surroundings and instead uses a sea of molecules to store the information. When held in a magnetic field, each nucleus within a molecule spins in a certain direction, which can be used to describe its state; spinning upwards can signify a 1 and spinning down, a 0. Nuclear Magnetic Resonance (NMR) techniques can be used to detect these spin states and bursts of specific radio waves can flip the nuclei from spinning up (1) to spinning down (0) and vice-versa.
The quantum computer in this technique is the molecule itself and its qubits are the nuclei within the molecule. This technique does not however use a single molecule to perform the computations; it instead uses a whole 'mug' of liquid molecules. The advantage of this is that even though the molecules of the liquid bump into one another, the spin states of the nuclei within each molecule remain unchanged. Decoherence is still a problem, but the time before the decoherence sets in is much longer than in any other technique so far. Researchers believe a few thousand primitive logic operations should be possible within time it takes the qubits to deco here.
Dr. Gershenfield from the Massachusetts Institute of Technology is one of the pioneers of the computing liquid technique. His research team has already been able to add one and one together, a simple task which is way beyond any of the other techniques being investigated. The key to being able to perform more complex tasks is to have more qubits but this requires more complex molecules with a greater number of nuclei, the caffeine molecule being a possible candidate. Whatever the molecule, the advancement to 10 qubit systems is apparently straightforward. Such a system, Dr. Gershenfield hopes, will be possible by the end of this year, and should be capable of factoring the number 15.
Advancing beyond a 10-qubit system may prove to be more difficult. In a given sample of 'computing liquid' there will be a roughly even number of up and down spin states but a small excess of spin in one direction will exist. It is the signal from this small amount of extra spin, behaving as if it were a single molecule that can be detected and manipulated to perform calculations while the rest of the spins will effectively cancel each other out. This signal is extremely weak and grows weaker by a factor of roughly 2 for every qubit that is added. This imposes a limit on the number of qubits a system may have as the readable output will be harder to detect.
