We present substantially generalized and improved quantum algorithms over prior work for inhomogeneous linear and nonlinear ordinary differential equations (ODE). In Berry et al., (2017), a quantum algorithm for a certain class of linear ODEs is given, where the matrix involved needs to be diagonalizable. The quantum algorithm for linear ODEs presented here extends to many classes of non-diagonalizable matrices. The algorithm here can also be exponentially faster for certain classes of diagonalizable matrices. Our linear ODE algorithm is then applied to nonlinear differential equations using Carleman linearization (an approach taken recently by us in Liu et al., (2021)). The improvement over that result is two-fold. First, we obtain an exponentially better dependence on error. This kind of logarithmic dependence on error has also been achieved by Xue et al., (2021), but only for homogeneous nonlinear equations. Second, the present algorithm can handle any sparse, invertible matrix (that models dissipation) if it has a negative log-norm (including non-diagonalizable matrices), whereas Liu et al., (2021) and Xue et al., (2021) additionally require normality.
翻译:在Berry 等人(2017年) 中,给出了某类线性分子数的量子算法,其中所涉及的矩阵需要对等。此处提出的线性分子数的量子算法扩大到许多非对等化矩阵类别。这里的算法对于某些可分解的矩阵类别也可以快速增长。然后,我们的线性ODE算法应用到非线性差异方程式(我们最近在刘等人(2021年)中采用的一种方法) 。这一结果的改进是双重的。首先,我们对错误的依赖性极大提高。这种对误的对数依赖性也由薛等人(2021年)实现,但只针对同质的非线性方程方程。第二,目前的算法可以处理任何稀疏、不可逆的矩阵(如果模型分解),如果它具有负式的日志(包括非对等式矩阵),那么Liuxi et al. (2021年) 和 Liscial. al. (2021年) 和Liel. al. (2021年) 。