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 Schrödinger'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" Schrödinger 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 (2¹⁰). 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 Schrödinger 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 x 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.

PHYSICS New Strategies Needed to Play Traditional Games in the Quantum World Flip a coin in the quantum realm and the outcome won't be heads or tails. The quantum coin can also settle on heads and tails. The same holds true for a bit in a quantum computer, called a qubit. For this reason, scientists expect that quantum computers will be able to use entirely new algorithms to solve a variety of problems more efficiently than conventional machines. To test what these new approaches might look like, they are studying how the strategies of standard games change under quantum rules. In the September issue of Physical Review A, Patrick Hayden and his colleagues at the University of Oxford describe a quantum version of a typical Dilemma game, in which three players must decide whether to betray each other in the hope of increasing their own chances of winning. Hayden and his team found that the players' strategies needed to be quite different in the quantum dilemma game. The scientists represented each player's approach with a qubit: the player could try to win (given a value of 0); they could settle for not winning (1); or they could try for some combination of the two. Because the qubits were entangled, or interlinked in way unique to quantum laws, the choices of each player heavily affected the others. And Hayden's group discovered that this entanglement actually removed the dilemma. In other words, it eliminated the incentive a player would have in the real world to betray his opponents. —Kristin Leutwyler Scientific American Sep 24,2001

PHYSICS NEWS UPDATE The American Institute of Physics Bulletin of Physics News Number 591 May 29, 2002 by Phillip F. Schewe, Ben Stein, and James Riordon A SINGLE-PHOTON LED, a light-emitting diode that fires one photon at a time, has been created, offering a potentially inexpensive and easy-to-manufacture component for quantum cryptography and a host of other applications. At the CLEO/QELS meeting last weekin Long Beach, scientists at Toshiba Research Europe Limited described a tiny, nanometer-scale indium arsenide quantum dot embedded in a gallium arsenide LED structure. The quantum dot is so small that it can at most capture a few electrons and holes from a pulse of electric current. A single photon is created by the recombination of a single electron and single hole in the dot. The researchers believe this is the first electrically driven single-photon source. Such single-particle-emitting sources are essential for a truly secure form of quantum cryptography. Otherwise, if several photons spill out from a device at a time, the extra ones can be siphoned off by an eavesdropper, who could then intercept a message without being detected. (Paper QTuG1 at meeting; contact Andrew Shields, [email protected]; see also Yuan et al., Science, 4 January 2002.)

Quantum computing making 'tremendous progress' 09:30 29 November 02 Exclusive from New Scientist Print Edition The first element of a device that many believe holds the best hope for quantum information processing has been completed by Australian researchers, while an Austrian team has reported the first truly quantum calculation. The achievements go some way to dispelling the widely-held idea that doing anything useful with quantum computing is decades or even centuries away. The strange properties of the quantum world should allow a quantum computer to outperform any existing computer. While classical computers process binary digits (bits) of information, quantum processors use quantum bits, or qubits, encoded in the quantum states of particles such as atoms, photons and electrons. Since such particles can be in several states at once, qubits would allow huge numbers of computations to be carried out simultaneously. But the practical obstacles are formidable, not least because the quantum properties such devices will exploit are extremely sensitive to disturbance from the outside world. Unless kept completely isolated they leak their quantum information - a phenomenon called "decoherence". Last week, Robert Clark of the University of New South Wales in Sydney unveiled a silicon-chip qubit, complete with a readout mechanism, that seems to solve the problem. "This was thought to be impossible just a few years ago," Clark told a discussion meeting at the Royal Society in London, UK. Precise implant The UNSW device is based on a blueprint drawn up in 1998 by Bruce Kane of the University of Maryland. Kane envisaged using two phosphorus atoms embedded in a silicon crystal. The quantum states of phosphorus atoms are particularly long-lived, so the hope is that they will provide qubits that are resistant to decoherence. A large array of such chips would then allow useful quantum processing. Building Kane's device calls for the atoms to be implanted extremely precisely, and researchers had doubted whether this would be possible. But working with a team at the University of Melbourne, Clark and his colleagues implanted phosphorus atoms within a silicon chip by focusing a high-energy beam of phosphorus ions onto it. They have now verified the atoms' position within the chip, and shown that their quantum state can be read using sensitive single-electron transistors. The only deviation from Kane's blueprint is that the chip uses states of charge rather than spin to process information. Clark believes that his device can be scaled up to make arrays of qubits, and hopes to be carrying out processing tasks by 2007. One of his goals is to run Grover's algorithm, a quantum database search that is much faster than is possible with standard computers. Head and tails Also at the meeting, Rainer Blatt of Innsbruck University in Austria announced that his team has carried out a quantum computation using a single trapped calcium ion. It is the first calculation made on a system proven to be in a quantum state. The Innsbruck researchers used their calcium ion to execute a quantum procedure called the Deutsch-Josza algorithm, which involves working out whether an imaginary coin is the same or different on each side. A quantum computer can check both sides at once, so can answer the problem at least twice as fast as a classical computer. The team has also made progress in using photons to carry quantum information between calcium qubits. This is an important step in linking individual qubits to form larger arrays. The advances made in the field belie the difficulty of manipulating quantum information, according to Peter Knight, a quantum information researcher at Imperial College, London. But he believes there is now cause for optimism about developing a truly useful quantum processor. "There's been tremendously rapid progress in the last year. I was hugely impressed at how things have developed," he says. Michael Brooks [New Scientist]

MAIN INDEX

REFERENCE GUIDE

TRANSCRIPTS

CIPHER-GLOSSARY