2019/01/04 by Andrew M. Childs, Jin-Peng Liu · 2 citations
Physics and Astronomy · Computer Science · Mathematics · #quant-ph #cs.NA #math.NA
paper · pdf · doi:10.1007/s00220-020-03699-z
published as Communications in Mathematical Physics 375, 1427-1457 (2020) · 29 pages
arxiv created 2019/01/04 · arxiv updated 2021/10/19
Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a d-dimensional system of linear equations or linear differential equations with complexity poly(log d). While several of these algorithms approximate the solution to within ε with complexity poly(log(1/ε)), no such algorithm was previously known for differential equations with time-dependent coefficients. Here we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity poly(log d, log(1/ε)).