Title | Quantum linear systems algorithm with exponentially improved dependence on precision |

Publication Type | Journal Article |

Year of Publication | 2015 |

Authors | Childs, AM, Kothari, R, Somma, RD |

Date Published | 2015/11/07 |

Abstract | Harrow, Hassidim, and Lloyd showed that for a suitably specified N×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. |

URL | http://arxiv.org/abs/1511.02306 |