THE dream of the mechanics who design quantum computers is to take a problem--the increasingly spooky behaviour of electronic components as they grow smaller, due to the effects predicted by quantum theory--and turn it into advantage. These quantum mechanics hope to use one of that theory's main planks, the uncertainty principle, to allow them to design machines that can do "massively parallel" calculations which are beyond even the theoretical capabilities of conventional computers. That, in turn, would allow currently insoluble problems (including some in the field of cryptography) to be crunched reasonably conveniently.
Building a practical quantum computer will be hard. But another step towards one has just been announced in Nature. Stephan Gulde, of the University of Innsbruck, in Austria, and his colleagues have built a prototype machine whose chief working part is a single atom of calcium, and they have run a program on it.
Conventional computers manipulate binary digits (bits). Quantum computers manipulate "qubits" (quantum bits). A bit represents a numerical value of one or zero. However, owing to the uncertainty principle (which says that you can never have perfect information about the behaviour of a very small object) a qubit can represent a one and a zero simultaneously. This allows each qubit to participate in more than one calculation at once, which is why a quantum computer can run a large number of computations in parallel. The problem is manipulating the qubits. Setting their initial values is hard. So is reading the results. And while the computation is performed, different qubits must interact with each other in carefully controlled ways--aptly known as entanglement--while being kept isolated from the environment outside the computer.
Dr Gulde begins by trapping an electrically charged calcium atom (ion) into what is called a "linear Paul trap", which uses an oscillating electric field to hold the ion in place. It is then zapped by light from a titanium-sapphire laser. Instead of heating it up, as might be expected, this zapping stimulates the ion to give up energy in the form of further light, thus cooling it. This cooling reduces outside influences on the properties of the ion that are used to encode the qubits. One of these properties is the ion's electronic state (the energy levels of its electrons). The other is its vibrational state (how it is resonating in the trap).
The computation itself is performed by a further series of laser pulses. These act on both the electronic state and the vibrational state, and the answer is left encoded in the electronic state. It can be read by a further laser pulse, which stimulates the ion to spit it out in the form of light.
The test to which Dr Gulde put his computer was running the "Deutsch-Jozsa" algorithm. This algorithm, named after David Deutsch and Richard Jozsa, two of the pioneers of quantum computing, is a way to check if a coin is fair or not. A coin is considered to be fair if it has heads on one side and tails on the other. If it has heads or tails on both sides, it is deemed unfair.
In the non-quantum world, checking a coin involves two steps: look at one side of the coin, and then look at the other. Dr Deutsch and Dr Jozsa, however, have worked out a way to use a quantum computer to test an (imaginary) coin in a single step. It involves measuring, after the coin is tossed, a qubit that is an equal mixture of heads and tails. It turns out that an arithmetical sign (plus or minus) in this qubit depends on whether the coin is fair or not--minus is fair, plus is unfair. Measuring the qubit is a one-step process, in effect looking at both sides of the coin at once.
This might not be thought the sort of thing that would make the CIA nervous about the safety of its secret codes. But it is an important proof of principle. Other quantum computers have solved the coin-flipping test, but they were clunky affairs with the qubits encoded in great gobs of atoms. That restricts the number of qubits that can be entangled to ten at most. With this new approach, the limit will be nearer 100. And, since the power of a quantum computer should rise exponentially with the number of entangled qubits, that tenfold leap would have enormous consequences. Many obstacles remain, but computing's quantum mechanics may one day be more concerned with counting coins than with flipping them.
--The Economist, 1/2/03