Quantum computing creeps forward

Sep 27 2007 Published by under Science news

Researchers at Yale have apparently managed to take an important step forward in the development of quantum computers: they've gotten atoms to talk to each other coherently over a long distance.

What is 'quantum computing'? To understand this, we begin by mentioning a classic problem in mathematics: the traveling salesman problem. Suppose a salesman needs to visit N cities during a round-trip sales route. Assuming the costs of travel between all pairs of cities are known, what is the cheapest route possible which visits each city only once?

For a small number of cities, we can readily solve this problem by calculating all the possibilities: for three cities, for instance, we can calculate the travel from home-1-2-3-home, home-1-3-2-home, home-2-1-3-home, home-2-3-1-home, home-3-1-2-home, home-3-2-1-home. As we increase the number of cities, we find that even for a small number of cities we need to make a large number of calculations in order to determine the minimum. In fact, this brute-force approach requires N-factorial (N*(N-1)*(N-2)*...2*1) calculations to determine the minimum. For a large enough number of cities these computations fall outside the range of what any ordinary computer can cope with. For instance, 1000-factorial ~ 4* 10^(2567).

There are many mathematical problems of this type, and modern electronic encryption software is based on choosing encryption keys which are not in principle unbreakable, but would require an impossible amount of computer time to break.

How does quantum mechanics help? Quantum mechanical particles (atoms, electrons) have wavelike properties. In a manner that is still not completely well understood, at least philosophically, an atom does not follow a definite path through an experimental system but simultaneously follows all possible paths through the system. Only at the output, when we measure the results of our experiment, does the atom 'choose' which path it has actually followed.

The relevance to the traveling salesman problem is then straightforward. If we can harness an atom to follow the salesman's route, it could in principle simultaneously follow all routes through the cities. If we can somehow force it to 'tell' us which route is cheapest in the end, we've reduced our N-factorial travels through the system to a single atomic journey.

In practice, things are of course more complicated than this. 'Tricking' the atom into giving us the right answer requires a very carefully designed experiment, and numerous practical experimental considerations make developing such a quantum computer nearly impossible. Quantum computing is one of those topics which seemingly holds great promise but has, up until now, failed to deliver on that promise. In fact, a colleague of mine who specializes in quantum computing once confided to me that he thought it would never work!

This returns us to the new development by the Yale group. One of the big challenges of quantum computing is getting your 'quantum bits' of information (qubits) to talk to one another. Previous experiments only allowed adjacent atoms in a system to communicate with one another, which meant that information could only be transfered in a grapevine-manner (A talks to B, who tells C, who tells D, etc.). The Yale group has developed a technique by which a pair of qubits can communicate over a longer distance via microwave radiation. This opens the door to having multiple qubits interacting with each other, and this was considered one of the major hurdles to developing a quantum microchip.

Again, though, I wouldn't worry about your email encryption just yet. The experiment only allowed communication between two qubits! Making a useful quantum microchip will require a significantly larger number.

No responses yet