New quantum algorithm can solve monster-size equations

[bananas]

http://www.scientificamerican.com/article.cfm?id=warp-speed-algebra

From the January 2010 Scientific American Magazine

Warp-Speed Algebra: New Algorithm Does Algebra in a Snap
New quantum algorithm can solve monster-size equations

By Davide Castelvecchi

<snip>

The latest quantum algorithm is generating excitement among physicists. It tackles linear equations: expressions such as 3x + 2y = 7 and typically written with unknowns on one side and constants on the other. Many high schoolers learn the trite mechanics of solving systems of such equations by eliminating one unknown at a time. Speed becomes crucial when systems contain billions of variables and billions of equations, which are not unusual in modern applications such as simulations of weather and other physical phenomena. Efficient algorithms can solve large, “N by N” systems (systems having N linear equations and N unknowns) by computer. Still, calculation time grows at least as fast as N does: if N gets 1,000 times larger, the problem will take at least 1,000 times longer to solve, often more.

The quantum algorithm now proposed by Aram W. Harrow of the University of Bristol in England and Avinatan Hassidim and Seth Lloyd of the Massachusetts Institute of Technology takes a clever shortcut. It can return the most relevant information about the solution without fully calculating the solution itself, thus trading off the amount of data it produces for speed. (For example, in the case of weather prediction it could return the average temperature over a town rather than the temperatures predicted city block by city block.)

<snip>

The gain in speed is enormous: the time required to produce the universal solution grows only with the number of digits in N. Thus, if N gets 1,000 times larger, the algorithm takes three times as long (because three digits are added to N), as opposed to 1,000 times as long. Even writing down the result for all the variables would involve 1,000 times more steps in the classical case. “It takes exponentially less time to solve the problem than to read the solution,” Lloyd says only half-jokingly.

<snip>

Some applications could be possible sooner, Lloyd says, if they exploit the intrinsically quantum nature of photons. He proposes, for example, that the algorithm could be embodied in a “superimaging device” that would remove optical distortions in a telescope. Each photon measured by the telescope would play the role of the constant terms of the equation, and the distortions would correspond to a linear system of equations. Finding the solutions would mean reversing the distortions, thus improving image quality.