Quantum computing may actually be useful, after all
In recent years, quantum computers have lost some of their luster. In the 1990s, it seemed that they might be able to solve a class of difficult but common problems — the so-called NP-complete problems — exponentially faster than classical computers. Now, it seems that they probably can't. In fact, until this week, the only common calculation where quantum computation promised exponential gains was the factoring of large numbers, which isn't that useful outside cryptography. In a paper appearing today in Physical Review Letters, however, MIT researchers present a new algorithm that could bring the same type of efficiency to systems of linear equations — whose solution is crucial to image processing, video processing, signal processing, robot control, weather modeling, genetic analysis and population analysis, to name just a few applications. Quantum computers are computers that exploit the weird properties of matter at extremely small scales. Where a bit...