Quantum Computers May Solve Gigantic Linear Equations

 November 10, 2009

A new algorithm developed by researchers at Massachusetts Institute of Technology (MIT) may allow quantum computers to process huge systems of linear equations. This potential for increased efficiency has been completely theoretical until now. Researchers included Seth Lloyd, a mechanical engineering professor at MIT, Avinatan Hassidim, a postdoctoral candidate in the Research Lab of Electronics at MIT, and the University of Bristol's Aram Harrow '01, PhD '05.

Quantum computing gained popularity in the 1990s. These computers take advantage of the odd behavior of matter on extremely small scales. Compared to a bit in a classical computer, which can hold only one value—a one or a zero—a quantum bit (qubit) can hold two values simultaneously. On a large scale, computations performed with qubits can be equivalent to several simultaneous computations on a classical computer, making quantum computers exponentially more efficient.  

As Lloyd explained in an MIT press release, "A supercomputer's going to take trillions of steps and this algorithm will take a few hundred." This sort of linear equation processing has applications in "image processing, video processing, signal processing, robot control, weather modeling, genetic analysis and population analysis."

Despite its potential, quantum computing creates problems even as it solves them. The increased capacity of qubits complicates the process of entering and extracting data. As Greg Kuperberg, a mathematician at University of California, Davis, said, "If you have to spend a year loading in the data, it doesn't matter that you can then do this linear-algebra step in 10 seconds."

An application for the MIT algorithm has not yet been developed. However, researchers at a variety of universities continue to investigate new approaches to quantum computing. Already, mathematicians at the University of London have created a method of solving differential equations based on the MIT algorithm.

The researchers published their findings, "Quantum Algorithm for Linear Systems of Equations," in the Oct.7, 2009 issue of Physical Review Letters.

Source: MIT, Oct. 9, 2009.