Quantum spectral-Galerkin methods for partial differential equations

Abstract: This paper presents a quantum spectral-Galerkin algorithm for constant-coefficient second-order linear elliptic equations. The method employs a boundary-adapted Jacobi tensor-product basis that incorporates the boundary condition into the approximation space and produces Galerkin systems with polynomially bounded condition numbers and sparsity. For analytic solutions satisfying a suitable uniform regularity condition, spectral convergence allows the normalized Galerkin coefficient state to be prepared with complexity $\poly(d,\log(1/\epsilon))$, where $d$ is the spatial dimension and $\epsilon$ is the error tolerance, under standard sparse-access and state-preparation assumptions. At the state-preparation level, this improves the precision dependence over fixed-order finite-difference and finite-element discretizations. We further show how to estimate prescribed linear functionals of the solution, with an additional $O(1/\epsilon)$ factor arising from norm and inner-product estimation.