2015/11/30 by Andrew M. Childs, Robin Kothari, Rolando D. Somma · 643 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Chebyshev filter #Mathematical analysis #Mathematics #Matrix (chemical analysis) #Numerical Methods and Algorithms #Operator (biology) #Physics #Polynomial #Quantum #Quantum Computing Algorithms and Architecture #Quantum Fourier transform #Quantum Information and Cryptography #Quantum algorithm #Quantum algorithm for linear systems of equations #Quantum dynamics #Quantum error correction #Quantum mechanics #Quantum phase estimation algorithm #Quantum process #Series (stratigraphy) #State (computer science) #State vector #quant-ph
paper · pdf · doi:10.1137/16m1087072
published in SIAM Journal on Computing 46(6), 1920-1950 (Society for Industrial and Applied Mathematics) · v1: 28 pages; v2: 31 pages, minor change to title, various minor changes and clarifications in response to referee comments
openalex publication_date 2017/01/01 · arxiv created 2017/09/29 · openalex created_date 2017/10/20 · arxiv updated 2017/12/27 · openalex updated_date 2026/08/05
Harrow, Hassidim, and Lloyd [Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified N × N matrix A and an 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(log N, 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.