An efficient quantum algorithm for simulating polynomial differential equations

DOI10.1007/S11128-024-04311-2arXiv2212.10775OpenAlexW4392760271MaRDI QIDQ6421178FDOQ6421178

Authors: Amit Surana, Abeynaya Gnanasekaran, Tuhin Sahai 

Publication date: 21 December 2022

Abstract: We present an efficient quantum algorithm to simulate nonlinear differential equations with polynomial vector fields of arbitrary degree on quantum platforms. Models of physical systems that are governed by ordinary differential equations (ODEs) or partial differential equation (PDEs) can be challenging to solve on classical computers due to high dimensionality, stiffness, nonlinearities, and sensitive dependence to initial conditions. For sparse $n$-dimensional linear ODEs, quantum algorithms have been developed which can produce a quantum state proportional to the solution in poly(log(nx)) time using the quantum linear systems algorithm (QLSA). Recently, this framework was extended to systems of nonlinear ODEs with quadratic polynomial vector fields by applying Carleman linearization that enables the embedding of the quadratic system into an approximate linear form. A detailed complexity analysis was conducted which showed significant computational advantage under certain conditions. We present an extension of this algorithm to deal with systems of nonlinear ODEs with $k$-th degree polynomial vector fields for arbitrary (finite) values of $k$. The steps involve: 1) mapping the $k$-th degree polynomial ODE to a higher dimensional quadratic polynomial ODE; 2) applying Carleman linearization to transform the quadratic ODE to an infinite-dimensional system of linear ODEs; 3) truncating and discretizing the linear ODE and solving using the forward Euler method and QLSA. Alternatively, one could apply Carleman linearization directly to the $k$-th degree polynomial ODE, resulting in a system of infinite-dimensional linear ODEs, and then apply step 3. This solution route can be computationally more efficient. We present detailed complexity analysis of the proposed algorithms, prove polynomial scaling of runtime on $k$ and demonstrate the framework on an example.

Full work available at URL: https://doi.org/10.1007/s11128-024-04311-2

Recommendations

• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation
• High-order quantum algorithm for solving linear differential equations
• Quantum spectral methods for differential equations

Mathematics Subject Classification ID

Quantum computation (81P68)

Cited In (5)

• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• Quantum simulation for partial differential equations with physical boundary or interface conditions
• Dense outputs from quantum simulations
• Algorithms for perturbative analysis and simulation of quantum dynamics
• Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation

This page was built for publication: An efficient quantum algorithm for simulating polynomial differential equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421178)