Parallel power

With their multiple personalities, quantum states could form the heart of a massively parallel computer

What would you get if you crossed a Bose-Einstein condensate with Schroedinger's cat? One big, chilly cat? A litter of identical but indeterminate kittens? In fact, no: you would get a quantum computer. But let's take that a little more slowly.

A conventional computer is a decidedly classical machine. It relies on electric currents acting as the 0s and 1s of a binary arithmetic system, and those 0s and 1s have to influence each other in absolutely predictable and dependable ways if they are to generate all manner of complex calculations and manipulations. If some of those 0s and 1s started behaving in an indeterminate, probabilistic way, what you would have, as a rule, is a computer that makes random mistakes.

But quantum theory is not wholly random. It does obey rules. When quantum states interact, they do so in an entirely predictable way. It's only in the outcome of a measurement that unpredictability crops up. Imagine a quantum computer in which the internal calculations and operations take place through a series of entirely predictable interactions of quantum rather than classical states. If no measurements disrupt the system - and that's a big if, since any kind of random, uncontrolled disturbance amounts to a measurement - nothing unpredictable happens. The quantum computer can carry out a calculation in a reliable way, just as a classical computer does.

The logic elements of a quantum computer could be, for example, the "half-up, half-down" Schroedinger cat-state rather than the definite up and down states a classical computer would use. And the computer would resemble a Bose-Einstein condensate because you would need an awful lot of these quantum states acting together coherently to perform any sort of useful or interesting calculation.

Why go to all this trouble? The answer, as was most clearly pointed out by David Deutsch of Oxford University in the mid-1980s, is that quantum computing allows a kind of parallelism a classical computer can't hope to match. In standard computing, any part of the internal logic, whether a single 0 or 1 or a whole string of such bits, represents a specific numerical state. But in quantum computing, an electron spin or a photon polarisation - a "qubit" - can represent two states simultaneously. A "half-up, half-down" state is both 0 and 1 at the same time. What's more, when this state interacts with other states, both parts of its dual identity participate in the interaction. A quantum calculation lets 0 and 1 take part in the same step, and at the same time.

With two "half-up, half-down" electron spins, for example, you can have four different states - representing 00, 01, 10 and 11. Similarly, with a string of 10 states you could simultaneously represent all the numbers from 0 to 1024 (210). Two such states might then interact in such a way as to produce an even more complex final state which contains - again, all at once - representations of all the numbers in the 1024 x 1024 multiplication table.

A conventional computer has to march through more than a million individual calculations to work out all the numbers in this table. Because a quantum computer explores all the possibilities simultaneously, it reaches the same result in a single effortless step.

So quantum computers could be enormously powerful. However, there are two difficulties with exploiting their capacity for massively parallel calculations. First, decoherence is hard to beat. It takes enormous care and effort to create Bose-Einstein condensates and Schroedinger cat atomic states in the lab. Any kind of random disturbance or interaction will destroy the exquisitely delicate mix of coexisting quantum states, forcing a single classical state to emerge instead. Maintaining the integrity of a quantum computer would therefore be incredibly hard. A whole array of complex and, importantly, different states would have to be created, sustained, and made to interact in a prescribed manner. (In a Bose-Einstein condensate, by contrast, all the states are identical, which would be like having a quantum computer whose bits are all permanently fixed at zero.)

The second problem is more subtle. How do you extract the result of any calculation from a quantum computer? As soon as any measurement is made on the quantum "multiplication table" state, for example, the computer will respond with just a single answer out of the 1024 ¥ 1024 possible answers that could have emerged. All the rest are lost. Which seems to defeat the purpose of doing the simultaneous quantum calculation in the first place.

What this really shows is that quantum computers are likely to be better at some kinds of calculations than others. The problem of finding the prime factors of a large number, for example, has acquired considerable urgency in the realm of code-making and breaking. The security of many encryption systems hinges on how hard it is for a conventional computer to find prime factors. It has to check all the possibilities laboriously until it hits on the right combination. But a quantum computer, in principle, could check on all possibilities at once. What's more, this is a problem where the whole point is to have a single answer emerge out of all possible (but wrong) answers - something that a suitably defined measurement of the state could achieve.

In a similar vein, Lov Grover of Bell Labs recently devised an algorithm that would pick out a desired entry from a list of scrambled entries in a time proportional to the square root of the number of items in the list. Conventional searches would take a time proportional to the number itself.

But how would you actually build a quantum computer? A number of researchers have recently hit upon the idea of using the individual atomic spin states within molecules. Single protons, the nuclei of hydrogen atoms, have spins that can point up or down relative to the spin of some other nucleus in a molecule. Pulses of radio waves with the right frequency can flip these spins up and down, and the spins of different nuclei on the same molecule interact in predictable ways. This could form the basis of a quantum computer: the spins would store the information and the radio waves would make them flip according to plan, to carry out your calculations.

We already have some of the necessary technology. Nuclear magnetic resonance imaging, now routine in medicine, maps out the position of atoms by measuring their spins. A quantum computer's central processor, its Pentium chip, could conceivably be nothing more than a beaker of some suitable liquid, whose molecules would include a variety of atomic spin states specially chosen to perform a set task. Another possibility is to use a silicon chip etched with dots and doped with atoms whose spins would be the computer's qubits. No electric currents would flow in this chip: instead spins would nudge each other along, dot to dot, passing along their message according to the dictates of quantum logic.