Quantum Computer Algorithms for Exponentially Speeding the Solution of Linear and Differential Equations

In a paper appearing today in Physical Review Letters, however, MIT researchers present a new algorithm that could exponential speed solutions of 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.

Researchers at the University of London have already expanded on the MIT researchers’ approach to develop a new quantum algorithm for solving differential equations. Early in their paper, they describe the MIT algorithm, then say, “This promises to allow the solution of, e.g., vast engineering problems. This result is inspirational in many ways and suggests that quantum computers may be good at solving more than linear equations.”

Quantum Algorithm for Linear Systems of Equations by Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd

Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector , find a vector such that A=. We consider the case where one does not need to know the solution itself, but rather an approximation of the expectation value of some operator associated with , e.g., †M for some matrix M. In this case, when A is sparse, N×N and has condition number , the fastest known classical algorithms can find and estimate †M in time scaling roughly as N. Here, we exhibit a quantum algorithm for estimating †M whose runtime is a polynomial of log(N) and . Indeed, for small values of [i.e., polylog(N)], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.

11 pages of supplemental information

In this supplementary material, we describe and analyze our algorithm in full detail. While the main paper attempted to convey the spirit of the procedure and left out various improvements, here we take the opposite approach and describe everything, albeit possibly in a less intuitive way. We also describe in more detail our reductions from non-Hermitian matrix inversion to Hermitian matrix inversion and from a general quantum computation to matrix inversion.




Greg Kuperberg, a mathematician at the University of California, Davis, who works on quantum algebra, says that the MIT algorithm “could be important,” but that he’s “not sure yet how important it will be or when.” Kuperberg cautions that in applications that process empirical data, loading the data into quantum memory could be just as time consuming as extracting it would be. “If you have to spend a year loading in the data,” he says, “it doesn’t matter that you can then do this linear-algebra step in 10 seconds.”

But Hassidim argues that there could be applications that allow time for data gathering but still require rapid calculation. For instance, to yield accurate results, a weather prediction model might require data from millions of sensors transmitted continuously over high-speed optical fibers for hours. Such quantities of data would have to be loaded into quantum memory, since they would overwhelm all the conventional storage in the world. Once all the data are in, however, the resulting forecast needs to be calculated immediately to be of any use.

Still, Hassidim concedes that no one has yet come up with a “killer app” for the algorithm

Other Quantum Computer Research

Six Qubits Have Stable Entanglement

An entangled state of six photons could potentially carry quantum information over large distances and between different reference frames.

RELATED

Quantum Computer Algorithm Review

A Quantum algorithm for quantum simulation

Understanding the nature of quantum computer algorithms

A list of the efficient (a lot better than algorithms for regular computers)
Shor’s algorithm, an algorithm for factoring numbers, which is key to decryption
Solving pell’s equation Pell’s equation is useful for approximating things like the square root of 2
Estimating certain Gauss sums
Solving hidden shift problems
solving certain hidden subgroup problems

Every quantum algorithm is fourier transforms and classical computation.

A summary of Quantum computers