Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
Joint Center for Quantum Information and Computer Science · Massachusetts Institute of Technology · +2 more institutions
Abstract
Harrow, Hassidim, and Lloyd [Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified $N \times N$ matrix $A$ and an $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 time ${poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general…
Citation impact
- FWCI
- 23.52
- Percentile
- 100%
- References
- 27
Authors
3Topics & keywords
- Quantum algorithm
- Quantum phase estimation algorithm
- Mathematics
- Quantum algorithm for linear systems of equations
- Algorithm
- State (computer science)
- Operator (biology)
- Quantum