01422nas a2200145 4500008004100000245007300041210006900114260001400183490000600197520097400203100002301177700001801200700002101218856003701239 2021 eng d00aHigh-precision quantum algorithms for partial differential equations0 aHighprecision quantum algorithms for partial differential equati c11/4/20210 v53 a
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity poly(1/ε), where ε is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be poly(d,log(1/ε)), where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.
1 aChilds, Andrew, M.1 aLiu, Jin-Peng1 aOstrander, Aaron uhttps://arxiv.org/abs/2002.07868