Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling

Abstract

The solution of large systems of nonlinear differential equations is needed for many applications in science and engineering. In this study, we present three main improvements to existing quantum algorithms based on the Carleman linearisation technique. First, by using a high-precision technique for the solution of the linearised differential equations, we achieve logarithmic dependence of the complexity on the error and near-linear dependence on time. Second, we demonstrate that a rescaling technique can considerably reduce the cost, which would otherwise be exponential in the Carleman order for a system of ODEs, preventing a quantum speedup for PDEs. Third, we provide improved, tighter bounds on the error of Carleman linearisation. We apply our results to a class of discretised reaction-diffusion equations using higher-order finite differences for spatial resolution. We show that providing a stability criterion independent of the discretisation can conflict with the use of the rescaling due to the difference between the max-norm and 2-norm. An efficient solution may still be provided if the number of discretisation points is limited, as is possible when using higher-order discretisations.

37 pages, 2 figures

References in corpus (13)

• Quantum algorithm for solving linear systems of equations
• Improved quantum algorithms for linear and nonlinear differential equations
• Quantum simulation of partial differential equations via Schrodingerisation: technical details
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Time-marching based quantum solvers for time-dependent linear differential equations
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• Quantum simulation of partial differential equations via Schrodingerisation
• Quantum algorithm for time-dependent differential equations using Dyson series
• Potential quantum advantage for simulation of fluid dynamics
• Quantum algorithm for nonlinear differential equations
• Quantum algorithms for computing observables of nonlinear partial differential equations
• Quantum differential equation solvers: limitations and fast-forwarding
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations

Cited by in corpus (5)

• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Koopman and transfer operator techniques from the perspective of quantum theory
• Vortex Detection from Quantum Data
• Solving the Nonlinear Vlasov Equation on a Quantum Computer
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs