91av

THEY said it couldn’t be done. They said it would never be practical. They were wrong, says David Deutsch.

He is referring to the quest to build a quantum computer. This machine would exploit the weird properties of quantum mechanics to perform tasks millions of times faster than today’s most powerful supercomputers. Such a device – if we can build one – would overturn the field of cryptography and revolutionise the computer industry. Yet despite this glittering prize, researchers have so far only coaxed quantum systems into solving mathematics problems that children can do in their heads.

Deutsch, a University of Oxford physicist who drew up the first blueprint for a quantum computer in 1985, thought we were still 20 years away from a useful device – until last summer. That was when theorist Simon Benjamin, also at Oxford, told him about cluster states, an approach that Benjamin believed could solve the major hang-ups that have plagued the quantum community. The idea redefines how a quantum computer processes information, and takes care of the trickiest bits of the calculation first. It should also scale up much more easily than previous designs, allowing researchers to perform larger and larger computations. The chat with Benjamin changed Deutsch’s vision; after two decades of pushing back predictions, he now sees a practical quantum computer arriving within 10 years. “He gave me the zeal of a convert,” says Deutsch.

“A practical quantum computer is now less than 10 years away”

The advantage of a quantum computer over its classical counterpart has long put a gleam in the eye of physicists. Conventional computers represent information as bits, which have a value of 1 or 0 at any time. These bits are manifested in the real world as electric charges or voltage levels. Quantum computing, on the other hand, is based on quantum bits, or qubits. Qubits can exist in a “superposition” state of 1 and 0 at the same time. Only when someone attempts to measure the state of a qubit will it settle on one of the two values. Roughly speaking, this means you can get two calculations for the price of one.

That’s not all. Quantum computing also exploits a phenomenon called entanglement. When two or more qubits are entangled, their properties become linked: two qubits can be manipulated such that when one qubit is measured to be 1, the other must be 0. Or they can be forced to give the same value. Using entanglement and superposition, a quantum computer can perform calculations on a great many numbers all at once. With only a few hundred entangled qubits, it is possible to represent simultaneously more numbers than there are atoms in the universe.

In theory, that is. Researchers have dreamed up many ideas for building a quantum computer, and have run simple algorithms on early versions (see “Quantum contenders”). Some have used the energy levels of ions trapped in electric fields to serve as quantum 1s and 0s. Others have sought out qubits in the polarisation of photons. Still others have used the nuclear spins within chloroform molecules and electron spins within nanocrystals known as quantum dots. Whatever the origin of the qubits, the same problem has always come up: doing calculations while maintaining the entanglements is incredibly difficult.

In traditional quantum schemes, a given set of qubits performs a calculation: a row of trapped ions, for instance, might represent the digits of your input. The qubits are held close together and manipulated, typically by a laser pulse, to be assigned data and to be entangled during the calculation. As they get packed closer together, however, it becomes harder to talk to any qubit without disturbing its neighbours. Such a disturbance can break entanglements or else force the qubit to choose its value, 0 or 1. Either outcome will bring the computing task to a halt. Only at the very end of the calculation can you safely peek at each qubit to read the answer.

It all adds up to a giant headache, and researchers have so far only managed to control about 10 qubits simultaneously. “To be honest, progress in this field has been rather small,” says Chris Monroe, a quantum-computer specialist at the University of Michigan in Ann Arbor.

Cluster states could change all that. Proposed in 2001 by Robert Raussendorf and Hans Briegel of the Ludwig Maximilian University in Munich, Germany, it provides a new architecture for quantum computers. The qubits are laid out such that all entanglements necessary for the calculation are set up at the very beginning. This approach, also called one-way computing, brings a great advantage. “If we’re making the entanglement beforehand, we can screw up as many times as we want,” says Benjamin.

Entangle this

The inspiration came from a set-up known as an optical lattice, in which a grid of lasers traps uncharged atoms at their intersection points. Using lasers to move rows of these qubits close together, it is relatively easy to create multiple entanglements. Much harder, however, is moving individual qubits without the rest of the row. That limits the use of the optical lattice in quantum computing, but the idea of doing entanglements en masse has stuck.

In a cluster state, instead of performing multiple operations over time on a given set of qubits, each step of the calculation has its own set of qubits. So whereas past systems might have carried out five operations sequentially using the same set of four qubits, the new computer would use a grid consisting of five columns of four qubits each (see Diagram); the number of operations in the task is reflected in the number of columns. Entanglements within a row represent the time steps of the calculation, while entanglements within a column represent operations between multiple qubits.

Once this grid of entangled qubits is created, the computation begins its march by measuring the state – 1 or 0 – of all the qubits in the first column. Based on those results, physical adjustments are made to the next column, which is measured in turn, and so on until the last column of qubits. The result of that column is the answer to the calculation.

At first glance, cluster states might seem a roundabout way of solving the problem. After all, it takes more qubits and entanglements to do the same operations. The strength of cluster states, says Benjamin, lies in the fact that entangling is such a fickle process, while measurements are easy. Using the cluster idea gets the hardest part out of the way before the number crunching begins.

Flying qubits

It’s more than just an idea, though. Last year a team led by Philip Walther, then at the University of Vienna, Austria, demonstrated cluster states composed of four entangled photons, or “flying” qubits, using a laser beamed through a crystal (91av, 12 March 2005, p 9). The polarisation state of each photon, horizontal or vertical, represented a 1 or 0. The researchers even managed to perform simple calculations with the set-up.

Though it marked a first for cluster states, Walther’s method by itself is probably not suited to performing more complex calculations. Later in 2005, Pieter Kok and Sean Barrett, both then at Hewlett-Packard, published a different way of constructing cluster states, one that they claimed could be scaled up (Physical Review A, vol 71, p 060310). Around the same time, Almut Beige and Yuan Liang Lim of Imperial College London and Leong Chuan Kwek of the National University of Singapore published a similar idea (Physical Review Letters, vol 95, p 030505).

Both teams proposed combining the strengths of atoms, ions and other “stationary” qubits with those of photons. To entangle two stationary qubits, you shine a laser onto them. A qubit in its 0 state will absorb a laser photon and do nothing. A qubit in its 1 state responds by releasing a photon. The qubits can be held in two reflective containers, or cavities, that ensure that any photons are released through the cavities’ openings and not absorbed into their walls. A photon that leaves a cavity passes through a piece of glass, or beam splitter, that directs it to one of a pair of photon detectors (see Diagram).

The scheme exploits the strange superposition states available to quantum objects. The beam splitter is set up such that when a photon hits one of the detectors, there is no way to tell which cavity it came from. If the detectors register two photons, it means both qubits were in their 1 states. If no photons are detected, it means both qubits were in their 0 states. If, however, exactly one photon is detected, it means one qubit was in the 1 state and the other in the 0 state. Because it is impossible to know which qubit emitted the photon, both qubits are effectively in a superposition of 1 and 0 and are ready for action. Only when the qubits are measured will they be forced to choose which is a 1 and which is a 0, thereby moving the cluster-state calculation forward.

A key strength of this method, says Kok, now at the University of Oxford, is that each qubit can be isolated from the others, communicating only by the release of photons. When the time comes, any qubit can be measured or manipulated without disturbing its neighbours. That means the method should scale up to more and more qubits. It also might be able to incorporate different kinds of qubits, be they ions, neutral atoms or quantum dots. Furthermore, the lasers, mirrors and detectors required are simple enough in principle to operate. “There are many possibly crazy ideas out there, but this isn’t one of them,” says Peter Shor, an expert in quantum computation at the Massachusetts Institute of Technology.

For now, though, it’s all theory. The next crucial step is to prove experimentally that cluster states are even feasible with the new method. “That’s not to subtract anything from these really lovely papers,” says Seth Lloyd, a mechanical engineer and quantum specialist at MIT. “But actually building a device and making it work has been shown to be significantly harder than theorists like me have envisioned.” At the moment, he says, “there are more proposals than there are to do them”. Monroe points out that getting research groups to commit to experiments with cluster states may take a while. “It’s a big conceptual change,” he says. “It requires a whole different toolbox.”

The new experiments will have their share of technical hurdles. Each pair of qubits, for example, will need to emit photons that are synchronised and indistinguishable from one another. If they arrive at slightly different times or have different frequencies, the entanglement won’t happen. Individual photons must also be reliably produced and detected, without getting lost in cavities and fibre-optic cables. Deutsch, for one, is not daunted by all this. Putting these ideas together will an immense challenge, he says. “But it’s not the kind where we have to discover new science to do it.”

“We do not have to discover new science to put this together”

That is key to the prospects of cluster states. For too long, researchers have championed the science behind other approaches to quantum computing but have not been able to scale up to practical systems. If experiments show that a few qubits can be entangled in cluster states with the new method, proponents think that increasing the number of qubits to make a useful machine will be more straightforward than ever.

The results could pave the way to miniaturise the set-up onto a chip, which might use small diamond crystals with nitrogen atoms suspended within them to act as qubits. It would be loaded with micro-mirrors and other optical components similar to those used in telecommunications today.

It is an optimistic view. Nevertheless, Benjamin says, three years of hard work by willing experimentalists should be enough to convince fellow physicists that a practical quantum computer is finally on the way.