Warp-Speed Algebra; January 2010; Scientific American Magazine; by Davide Castelvecchi; 2 Page(s)

Quantum computers can do wondrous things: too bad they do not exist yet. That has not stopped physicists from devising new algorithms for the devices, which can calculate a lot faster than ordinary computers—in fact, exponentially faster, in quite a literal sense. Once quantum computers do become available, the algorithms could become a key part of applications that require number crunching, from engineering to video games.

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.