Another step forward: Quantum algorithm for solving linear systems of equations

Harrow, Hassidim, and Lloyd have recently published a paper titled "Quantum algorithm for solving linear systems of equations" [1]. You can find the paper here on ArXiv and there is a pretty good summary article here from MIT news. (Lloyd is pretty big in the pop sci world of quantum computing too, he's written Programming the Universe and a recent Scientific American article for instance.)

As the title says, they outline a quantum algorithm for solving linear systems of equations. In other words given:
The algorithm solves for the vector x, when matrix A and b are known. So why is this useful? Linear systems of equations show up all the time. Some diverse examples include: oil exploration, electrical networks, and flight crew scheduling [2] just to name a few. Of course, as they point out even in the abstract, they aren't actually solving for x, but "...an
approximation of the expectation value of some operator associated with x..." [1]. Another highlight is that this algorithm is an exponential speed up over the best known classical value! I recommend the MIT article from above if you want a general overview, or the entire paper (obviously) for all the details.

This is another important step forward we've had recently in addition to the steps forward in physical implementations I've written about here and here. Up until now there are really only two practical quantum algorithms, and they get cited quite a bit: Shor's algorithm for factoring [3] and Grover's fast database search [4]. Both of these where developed in the mid 1990s. Furthermore both of these algorithms have pretty narrow applications, while linear systems of equations are everywhere. We'll see how things pan out, but it could arguably be considered the most important development to date in the currently sparse universe of quantum algorithms.

References

[1] A. W. Harrow, A. Hassidim, and S. Lloyd, "Quantum algorithm for solving linear systems of equations," Phys. Rev. Lett, vol. 15, p. 15, 07Oct2009 2009.

[2] D. C. Lay, Linear Algebra and Its Applications, 1 ed. Reading, MA: Addison-Wesley, 1997.

[3] P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM Journal on Computing, vol. 26, p. 25, October 1997 1997.

[4] L. K. Grover, "A fast quantum mechanical algorithm for database search," Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.