Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x}=\vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in …