



@article {1605,
	title = {Quantum algorithm for systems of linear equations with exponentially improved dependence on precision},
	journal = {SIAM Journal on Computing},
	volume = {46},
	year = {2017},
	month = {2017/12/21},
	pages = {1920-1950},
	abstract = {<p>Harrow, Hassidim, and Lloyd showed that for a suitably specified N\&times;N matrix A and N-dimensional vector b⃗ , there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax⃗ =b⃗ . If A is sparse and well-conditioned, their algorithm runs in time poly(logN,1/ϵ), where ϵ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/ϵ), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on ϵ is prohibitive.</p>},
	doi = {10.1137/16M1087072},
	url = {http://epubs.siam.org/doi/10.1137/16M1087072},
	author = {Andrew M. Childs and Robin Kothari and Rolando D. Somma}
}
