joe
writes “Aram Harrow and colleagues have just published on the arXiv a
quantum algorithm for solving systems of linear equations (paper, PDF).
Until now, the only quantum algorithms of practical consequence have
been Shor’s algorithm for prime factoring, and Feynman-inspired quantum
simulation algorithms. All other algorithms either solve problems with
no known practical applications, or produce only a polynomial speedup
versus classical algorithms. Harrow et. al.’s algorithm provides an
exponential speedup over the best-known classical algorithms. Since
solving linear equations is such a common task in computational science
and engineering, this algorithm makes many more important problems that
currently use thousands of hours of CPU time on supercomputers amenable
to significant quantum speedup. Now we just need a large-scale quantum
computer. Hurry up, guys!”

Read more of this story at Slashdot.

Advertisements