An efficient quantum algorithm for simulating polynomial dynamical systems

Abstract

In this paper, we present an efficient quantum algorithm to simulate nonlinear differential equations with polynomial vector fields of arbitrary (finite) degree on quantum platforms. Ordinary differential equations (ODEs) and partial differential equations (PDEs) arise extensively in science and engineering applications. Examples of ODE models include mechanics of rigid bodies, molecular dynamics, chemical kinetics, and epidemiology. Nonlinear PDEs arise in fluid dynamics, combustion, weather forecasting, structural mechanics, plasma dynamics, and finance to name a few. In practice, it is challenging to simulate such equations on classical computers due to high dimensionality, stiffness arising from multiple spatial/temporal scales, nonlinearities, and chaotic dynamics. Typically, high performance computing is used to mitigate computational challenges and involves approximations for tractability. For sparse n-dimensional linear ODEs, quantum algorithms have been developed which can produce a quantum state proportional to the solution in $\textsf {poly}(\log (n))$) 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 and prove polynomial scaling of runtime on k. We demonstrate the computational framework on a numerical example.

Appendix A: Carleman linearization equivalence

Lemma 6

The CL of the transformed quadratic form (18) with truncation level $N$ is equivalent to the CL of k-th order polynomial system (8) with truncation level $N^\prime =N(k-1)$.

Proof

First note that the system (18) can be expressed as,

$$\begin{aligned} \dot{\tilde{\textbf{x}}}_1&= \textbf{A}_1^1\tilde{\textbf{x}}_1+\textbf{A}^1_2\tilde{\textbf{x}}_2+\cdots +\textbf{A}^1_{k-1}\tilde{\textbf{x}}_{k-1}+\textbf{A}^1_k\tilde{\textbf{x}}_1\otimes \tilde{\textbf{x}}_{k-1}+\textbf{A}^1_0, \nonumber \\ \dot{\tilde{\textbf{x}}}_2&= \textbf{A}_1^2\tilde{\textbf{x}}_1+\textbf{A}^2_2\tilde{\textbf{x}}_2+\cdots +\textbf{A}^2_{k-1}\tilde{\textbf{x}}_{k-1}+\textbf{A}^2_k\tilde{\textbf{x}}_1\otimes \tilde{\textbf{x}}_{k-1}+\textbf{A}^2_{k+1}\tilde{\textbf{x}}_2\otimes \tilde{\textbf{x}}_{k-1}, \nonumber \\&\quad \vdots \nonumber \\ \dot{\tilde{\textbf{x}}}_{k-1}&= \textbf{A}^{k-1}_{k-2}\tilde{\textbf{x}}_{k-2}+\textbf{A}^{k-1}_{k-1}\tilde{\textbf{x}}_{k-1}+\textbf{A}^{k-1}_{k}\tilde{\textbf{x}}_1\otimes \tilde{\textbf{x}}_{k-1}+\cdots +\textbf{A}^{k-1}_{2(k-1)}\tilde{\textbf{x}}_{k-1}\otimes \tilde{\textbf{x}}_{k-1}, \end{aligned}$$

(A1)

where $\tilde{\textbf{x}}_i={\textbf{x}}^{[i]}$. Let $\tilde{\textbf{x}}=(\tilde{\textbf{x}}_1^\prime ,\ldots ,(\tilde{\textbf{x}}_{k-1})^\prime )^\prime$ and $\tilde{\textbf{z}}_i=\tilde{\textbf{x}}^{[i]}$ be the variables introduced for the CL of the above system, and satisfy equations of the form

$$\begin{aligned} \dot{\tilde{\textbf{z}}}_{i+1}=\tilde{\textbf{A}}^{i+1}_{i}\tilde{\textbf{z}}_{i}+\tilde{\textbf{A}}^{i+1}_{i+1} \tilde{\textbf{z}}_{i+1}+\tilde{\textbf{A}}^{i+1}_{i+2}\tilde{\textbf{z}}_{i+2}, \end{aligned}$$

(A2)

for appropriate, $\tilde{\textbf{A}}^{i+1}_{i},\tilde{\textbf{A}}^{i+1}_{i+1}$ and $\tilde{\textbf{A}}^{i+1}_{i+2}$.

To prove the result, we next show that every unique equation of the form (A2), appearing in the CL of (A1), also appears in the CL of (8). Firstly, note that, the above system of equations (A1) is equivalent to the system of equations (9) for $i=1,\hdots ,k-1$ which is the first set of equations, i.e., for $\tilde{\textbf{z}}_{1}$, appearing in the CL (A2). Secondly, in going from $\tilde{\textbf{z}}_{i}$ to $\tilde{\textbf{z}}_{i+1}=\tilde{\textbf{x}}\otimes \tilde{\textbf{z}}_{i}$, the only new powers of ${\textbf{x}}$ introduced in the vector $\tilde{\textbf{z}}_{i+1}$ are ${\textbf{x}}^{[{i(k-1)+p}]}(\equiv \tilde{\textbf{x}}_{i(k-1)+p}), \text {where}\,\,p=1,\hdots ,k-1$. From (9), these variables satisfy,

$$\begin{aligned} \dot{\tilde{\textbf{x}}}_{i(k-1)+1}&= \textbf{A}^{i(k-1)+1}_{i(k-1)}\tilde{\textbf{x}}_{i(k-1)}+\textbf{A}^{i(k-1)+1}_{i(k-1)+1}\tilde{\textbf{x}}_{i(k-1)+1}+\cdots \nonumber \\&\quad +\textbf{A}^{i(k-1)+1}_{i(k-1)+k-1}\tilde{\textbf{x}}_{i(k-1)+k-1}+\textbf{A}^{i(k-1)+1}_{i(k-1)+k}\tilde{\textbf{x}}_{1}\otimes \tilde{\textbf{x}}_{(i+1)(k-1)}, \nonumber \\ \dot{\tilde{\textbf{x}}}_{i(k-1)+2}&= \textbf{A}^{i(k-1)+2}_{i(k-1)+1}\tilde{\textbf{x}}_{i(k-1)+1}+\textbf{A}^{i(k-1)+2}_{i(k-1)+2}\tilde{\textbf{x}}_{i(k-1)+2}+\cdots \nonumber \\&\quad +\textbf{A}^{i(k-1)+2}_{i(k-1)+k-1}\tilde{\textbf{x}}_{i(k-1)+k-1}+\textbf{A}^{i(k-1)+2}_{i(k-1)+k}\tilde{\textbf{x}}_1\otimes \tilde{\textbf{x}}_{(i+1)(k-1)}\nonumber \\&\quad +\textbf{A}^{i(k-1)+2}_{i(k-1)+k+1}\tilde{\textbf{x}}_2\otimes \tilde{\textbf{x}}_{(i+1)(k-1)}, \nonumber \\&\quad \vdots \nonumber \\ \dot{\tilde{\textbf{x}}}_{i(k-1)+k-1}&= \textbf{A}^{i(k-1)+k-1}_{i(k-1)+k-2}\tilde{\textbf{x}}_{i(k-1)+k-2}+\textbf{A}^{i(k-1)+k-1}_{i(k-1)+k-1}\tilde{\textbf{x}}_{i(k-1)+k-1}+\cdots \nonumber \\&\quad +\textbf{A}^{i(k-1)+k-1}_{i(k-1)+2(k-1)}\tilde{\textbf{x}}_{k-1}\otimes \tilde{\textbf{x}}_{(i+1)(k-1)}. \end{aligned}$$

(A3)

Note that the term $\tilde{\textbf{x}}_{i(k-1)}$ appears in $\tilde{\textbf{z}}_{i}$, the terms $\tilde{\textbf{x}}_{i(k-1)+p},p=1,\hdots ,k-1$ appear in $\tilde{\textbf{z}}_{i+1}$, and the terms $\tilde{\textbf{x}}_{p}\otimes \tilde{\textbf{x}}_{(i+1)(k-1)},p=1,\hdots ,k-1$ appear in $\tilde{\textbf{z}}_{i+2}=\tilde{\textbf{x}}\otimes \tilde{\textbf{z}}_{i+1}$. Hence, the system (A3) can be written in the form,

$$\begin{aligned} \left( \begin{array}{c} \dot{\tilde{\textbf{x}}}_{i(k-1)+1} \\ \dot{\tilde{\textbf{x}}}_{i(k-1)+2} \\ \vdots \\ \dot{\tilde{\textbf{x}}}_{i(k-1)+k-1} \end{array}\right) =\tilde{\textbf{B}}^{i+1}_{i}\tilde{\textbf{z}}_{i}+\tilde{\textbf{B}}^{i+1}_{i+1}\tilde{\textbf{z}}_{i+1}+\tilde{\textbf{B}}^{i+1}_{i+2}\tilde{\textbf{z}}_{i+2}, \end{aligned}$$

(A4)

for appropriate $\tilde{\textbf{B}}^{i+1}_{i},\tilde{\textbf{B}}^{i+1}_{i+1}$ and $\tilde{\textbf{B}}^{i+1}_{i+2}$. For example, $\tilde{\textbf{B}}^{i+1}_{i+1}$, will take the form,

$$\begin{aligned} \tilde{\textbf{B}}^{i+1}_{i+1}=\left( \begin{array}{cccccc} \textbf{0}_1 &{}\quad \textbf{A}^{i(k-1)+1}_{i(k-1)+1} &{}\quad \textbf{A}^{i(k-1)+1}_{i(k-1)+2}&{}\quad \textbf{A}^{i(k-1)+1}_{i(k-1)+3} &{}\quad \cdots &{}\quad \textbf{A}^{i(k-1)+1}_{i(k-1)+k-1} \\ \textbf{0}_2 &{}\quad \textbf{A}^{i(k-1)+2}_{i(k-1)+1} &{}\quad \textbf{A}^{i(k-1)+2}_{i(k-1)+2} &{}\quad \textbf{A}^{i(k-1)+2}_{i(k-1)+3} &{}\quad \cdots &{}\quad \textbf{A}^{i(k-1)+2}_{i(k-1)+k-1} \\ \textbf{0}_3 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad \cdots &{}\quad \cdot \\ \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots &{}\quad \vdots \\ \textbf{0}_{k-1} &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad \textbf{A}^{i(k-1)+k-1}_{i(k-1)+k-2}&{}\quad \textbf{A}^{i(k-1)+k-1}_{i(k-1)+k-1} \\ \end{array} \right) , \end{aligned}$$

(A5)

where $\textbf{0}_p$ are zero matrices of size $n^{i(k-1)+p}\times (n_k^{i+1}-(k-1))$ for $p=1,\ldots ,k-1$. Expressions for $\tilde{\textbf{B}}^{i+1}_{i}$ and $\tilde{\textbf{B}}^{i+1}_{i+2}$ take a similar form, which we omit here for brevity. Finally, note that $\tilde{\textbf{B}}^{i+1}_{i},\tilde{\textbf{B}}^{i+1}_{i+1}$ and $\tilde{\textbf{B}}^{i+1}_{i+2}$ are sub-matrices defining $\tilde{\textbf{A}}^{i+1}_{i},\tilde{\textbf{A}}^{i+1}_{i+1}$ and $\tilde{\textbf{A}}^{i+1}_{i+2}$, respectively, since the vectors on the LHS of Eq. (A4) are elements of the vector $\dot{\tilde{\textbf{z}}}_{i+1}$ appearing in (A2). The system of equations (A4), thus, represents a subsystem of equations appearing in the CL (A2). Hence, by choosing $N^\prime =N(k-1)$ for truncation level of the CL of (8), we will obtain a system of equations representing a set of all unique equations appearing in the CL of (18) with the truncation level $N$. $\square$