Quantum Algorithm for Linear Systems of Equations

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 $\overrightarrow{b}$, find a vector $\overrightarrow{x}$ such that $A\overrightarrow{x}=\overrightarrow{b}$. We consider the case where one does not need to know the solution $\overrightarrow{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\overrightarrow{x}$, e.g., ${\overrightarrow{x}}^{†}M\overrightarrow{x}$ for some matrix $M$. In this case, when $A$ is sparse, $N\times N$ and has condition number $\kappa$, the fastest known classical algorithms can find $\overrightarrow{x}$ and estimate ${\overrightarrow{x}}^{†}M\overrightarrow{x}$ in time scaling roughly as $N\sqrt{\kappa }$. Here, we exhibit a quantum algorithm for estimating ${\overrightarrow{x}}^{†}M\overrightarrow{x}$ whose runtime is a polynomial of $\log (N)$ and $\kappa$. Indeed, for small values of $\kappa$ [i.e., $\mathrm{poly}\log (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.