A new algorithm researchers hope may help make quantum computing useful

From MIT news late last week:

Quantum computers are computers that exploit the weird properties of matter at extremely small scales. Where a bit in a classical computer can represent either a “1” or a “0,” a quantum bit, or qubit, can represent “1” and “0” at the same time. Two qubits can represent four values simultaneously, three qubits eight, and so on. Under the right circumstances, computations performed with qubits are thus the equivalent of multiple classical computations performed in parallel. But those circumstances are much rarer than was first anticipated.

In fact, it turns out that quantum computers are so weird that researchers are still developing the theoretical framework for even thinking about the calculations. But a new algorithm developed at MIT shows how quantum computers might be used to solve something we know a little bit about: systems of linear equations

Computer models of weather systems or of complex chemical reactions, however, might have to solve millions of equations with millions of variables. Under the right circumstances, a classical computer can solve such equations relatively efficiently: the solution time is proportional to the number of variables. But under the same circumstances, the time required by the new quantum algorithm would be proportional to the logarithm of the number of variables.

That means that for a calculation involving a trillion variables, “a supercomputer’s going to take trillions of steps, and this algorithm will take a few hundred,” says mechanical engineering professor Seth Lloyd…

There are still significant, and interesting, challenges, such as getting the data in and out in such as way that the total time to solution has any advantage over conventional computing

Because the result of the calculation would be stored on qubits, however, “you’re not going to have the full functionality of an algorithm that just solves everything and writes it all out,” Lloyd says. To see why, consider the way in which each added qubit doubles the capacity of quantum memory. Eight qubits can represent 256 values simultaneously, nine qubits 512 values, and so on. This doubling rapidly yields astronomical numbers. The trillion solutions to a trillion-variable problem would be stored on only about 40 qubits. But extracting all trillion solutions from the qubits would take a trillion steps, eating up all the time that the quantum algorithm saved.

More in the article and, if you’re are feeling really froggy, a lot more in the paper itself (PDF).