Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations

Nonlinear differential equations appear in many fields, such as fluid dynamics, biology, finance, etc. In general, the analytical solutions of nonlinear differential equations cannot be obtained effectively. Numerical methods are often used to solve nonlinear differential equations. However, when solving high-dimensional nonlinear differential equations, too many computing resources are required, which may exceed the computing power of classic computers. It is important to develop more efficient algorithms for solving nonlinear differential equations.

Quantum computing provides a promising way to speed up the solution of various equations. In recent years many quantum algorithms have been developed to solve various equations, such as system of linear equations [1–4], Poisson equation [5], Dirac equation [6], heat equation [7], linear ordinary differential equations (ODEs) [8–11], linear partial ODEs [12, 13] and so on [14–16].

However, because of the linearity of quantum mechanics, solving nonlinear equations with quantum computing is challenging, some related algorithms are proposed [17–25]. An early quantum algorithm for solving nonlinear ODEs is proposed in [17], but the complexity of the algorithm increases exponentially with the evolution time. In [19], the authors proposed a variational quantum algorithm for solving nonlinear differential equations and demonstrate the algorithm by solving one-dimensional nonlinear Schrodinger equation. However, when the equations become complicated, whether the parameterized quantum circuit used in their work is capable of expressing the solution of the problem and the optimization problem of the parameterized quantum circuit has not yet been concluded. In [20], a quantum algorithm for solving nonlinear dissipative ODEs is constructed based on Carleman linearization [26, 27]. This approach embeds the nonlinear ODEs into linear ODEs and solves the linear ODEs with quantum algorithm. The complexity of their algorithm is $O(\frac{{T}^{2}q}{{\epsilon}}\enspace \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\mathrm{log}(nT/{\epsilon})))$ and q measures decay of the solution. In [21], nonlinear ODEs are embedded in Hilbert space, and the evolution of nonlinear ODEs is approximated by the evolution of subsystems in large systems.

Homotopy perturbation method [28–30] is a semi-analytical technique for solving linear as well as nonlinear ordinary/partial differential equations. This method, which is a combination of homotopy in topology and classic perturbation techniques, provides us with a convenient way to obtain analytic or approximate solutions for a wide variety of problems arising in different fields, such as Duffing equation [31], nonlinear wave equations [32] and so on.

In our work, we propose a quantum algorithm for solving time-independent quadratic nonlinear dissipative ODEs. The more general nonlinear ODEs can be reduced to the quadratic ODEs by introducing additional variables [33, 34]. Our algorithm uses the homotopy perturbation method to transform the problem into a series of nonlinear ODEs which have a special structure. The transformed nonlinear ODEs can be embedded into linear ODEs with a technique similar to Carleman linearization. Then the linear ODEs are solved with quantum linear ODEs algorithm proposed in [9]. Finally, we measure some qubit registers and obtain a state -close to the normalized exact solution u(T)/||u(T)|| at evolution time T.

Our work is similar with Liu's work [20], here we list some differences: (1) the truncation method is different, our work uses homotopy perturbation method and [20] uses Carleman linearization. The convergence condition of homotopy perturbation method and Carleman linearization are different. Liu et al [20] define $R=\frac{{\Vert}{u}_{\text{in}}{\Vert}{\Vert}{F}_{2}{\Vert}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }$ (here we omit the inhomogeneity term F₀ in their definition) and the convergence condition is R < 1. In our work, we define $K=\frac{4{\Vert}{u}_{\text{in}}{\Vert}{\Vert}{F}_{2}{\Vert}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }=4R$, the convergence condition is K < 1, the factor '4' is caused by the homotopy perturbation method. By corollary 1 in [20] and lemma 9, the truncation errors of Carleman linearization and homotopy perturbation method decrease exponentially with the truncation order c as ${\Vert}{u}_{\text{in}}{\Vert}{R}^{c}{(1-{\text{e}}^{\text{Re}({\lambda }_{1})t})}^{c}$ and $\frac{{K}^{c+2}}{1-K}$, respectively. (2) The dependence of our algorithm on the error and evolution time T in our algorithm is O(T poly(log(1/))), which is O(T²/) in [20]. Therefore the complexity of our algorithm is exponentially improved on compared to [20], the cost of this improvement is a stronger constraint on the problem, i.e. $K< \sqrt{2}/2$ and $\frac{(c+1)\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }{{\Vert}{F}_{2}{\Vert}}\leqslant 1$.

This paper is organized as follows. Section 2 introduces the quadratic ODEs to be solved. Then we show the details of quantum homotopy perturbation method in section 3. Initial state preparation and oracle construction of matrix A are discussed in section 4. In the following three sections we analyze our method from different aspects: section 5 gives an upper bound of the condition number of the linear system to be solved. Section 6 analyzes the solution error of our method. Section 7 gives a lower bound of success probability. Next, the main result of our work is proved in section 8. Finally, we conclude our work with a discussion of the result and some open problems in section 9.

We focus on an initial value problem described by the n-dimensional quadratic ODEs. The problem to be solved is defined as

$$\begin{equation}\frac{\mathrm{d}u}{\mathrm{d}t}={F}_{1}u+{F}_{2}{u}^{\otimes 2},\quad u(0)={u}_{\text{in}},\end{equation} \tag{ 1 }$$

where u, ${u}_{\text{in}}\in {\mathbb{R}}^{n}$, ${F}_{1}\in {\mathbb{R}}^{n\times n}$, ${F}_{2}\in {\mathbb{R}}^{n\times {n}^{2}}$ are time independent sparse matrices. The sparsity of F₁, F₂ is s, which means the number of non-zero elements in each row or column of F₁, F₂ does not exceed s. We assume F₁ is a normal matrix and the eigenvalues λ_i of F₁ satisfy Re(λ_n ) ⩽ ⋯ ⩽ Re(λ₁) < 0. We also assume oracles O_F1, O_F2 and O_u are given, O_F1, O_F2 are used to extract the non-zero position and value of F₁, F₂ respectively, and |u_in⟩ is prepared with O_u . In specific, O_F1, O_F2 and O_u are defined as

$$\begin{equation}\begin{aligned} & {O}_{F11}\vert j\rangle \vert k\rangle =\vert j\rangle \vert {f}_{1}(j,k)\rangle , & 0\leqslant j\leqslant n-1,\enspace 0\leqslant k\leqslant s-1,\\ & {O}_{F12}\vert j\rangle \vert k\rangle \vert z\rangle =\vert j\rangle \vert k\rangle \vert z\oplus {{F}_{1}}_{j,k}\rangle , & 0\leqslant j,\enspace k\leqslant n-1,\\ & {O}_{F13}\vert j\rangle \vert 0\rangle =\vert j\rangle \vert g(j)\rangle , & 0\leqslant j\leqslant n-1,\\ & {O}_{F21}\vert j\rangle \vert k\rangle =\vert j\rangle \vert {f}_{2}(j,k)\rangle , & 0\leqslant j\leqslant n-1,\enspace 0\leqslant k\leqslant s-1,\\ & {O}_{F22}\vert j\rangle \vert k\rangle \vert z\rangle =\vert j\rangle \vert k\rangle \vert z\oplus {{F}_{2}}_{j,k}\rangle , & 0\leqslant j\leqslant n-1,\enspace 0\leqslant k\leqslant {n}^{2}-1,\\ & {O}_{u}\vert 0\rangle =\vert {u}_{\text{in}}/{\Vert}{u}_{\text{in}}{\Vert}\rangle , \end{aligned}\end{equation} \tag{ 2 }$$

where f₁(j, k) and f₂(j, k) represent the column number of the kth non-zero element in jth row of F₁, F₂ respectively, g(j) satisfies f₁(j, g(j)) = j, here we treat the diagonal element of F₁ as a non-zero element. O_F13 is used to construct an oracle of a matrix related to F₁, the details are shown in the proof of lemma 5.

We define a parameter K which characterizes the nonlinearity of equation (1),

$$\begin{equation}K{:=}\frac{4{\Vert}{u}_{\text{in}}{\Vert}{\Vert}{F}_{2}{\Vert}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }.\end{equation} \tag{ 3 }$$

We assume K ⩾ ||u_in||, if this is not satisfied, we rescale u to ζu with a suitable constant ζ which keeps $\frac{4{\Vert}{u}_{\text{in}}{\Vert}{\Vert}{F}_{2}{\Vert}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }$ unchanged and makes K ⩾ ||u_in||. In this paper we use spectral norm, it means ||⋅|| = ||⋅||₂.

In this section, we give the whole process of quantum homotopy perturbation method for solving equation (1). It contains four steps:

• (a)  
  Using homotopy perturbation method to transform equation (1) into equation (6), a series of nonlinear ODEs with variable ν_i .
• (b)  
  Embedding equation (6) into equation (8), linear ODEs with variable $\overrightarrow{y}$.
• (c)  
  Solving equation (8) with quantum algorithm proposed in [9].
• (d)  
  Measurement.

The following four subsections introduce the details of these four steps.

3.1. Homotopy perturbation method

Firstly, we introduce the process of homotopy perturbation method [28–30] for solving equation (1). Using homotopy method, we construct homotopy $\nu (t,p):{\mathbb{R}}^{+}\times [0,1]\to {\mathbb{R}}^{n}$, which satisfies

$$\begin{equation}H(\nu ,p)=\frac{\mathrm{d}\nu }{\mathrm{d}t}-{F}_{1}\nu -p{F}_{2}{\nu }^{\otimes 2}=0,\quad \nu (0,p)={u}_{\text{in}}.\end{equation} \tag{ 4 }$$

Assuming ν is represented as

$$\begin{equation}\nu ={\nu }_{0}+p{\nu }_{1}+{p}^{2}{\nu }_{2}+\cdots +{p}^{c}{\nu }_{c}.\end{equation} \tag{ 5 }$$

Substituting equation (5) into equation (4), then equating the terms with identical powers of p, we have the following equations:

$$\begin{align} & \frac{\mathrm{d}{\nu }_{0}}{\mathrm{d}t}-{F}_{1}{\nu }_{0}=0,\quad {\nu }_{0}(0)={u}_{\text{in}}, \\ & \frac{\mathrm{d}{\nu }_{1}}{\mathrm{d}t}-{F}_{1}{\nu }_{1}-{F}_{2}{\nu }_{0}\otimes {\nu }_{0}=0,\quad {\nu }_{1}(0)=0, \\ & \frac{\mathrm{d}{\nu }_{2}}{\mathrm{d}t}-{F}_{1}{\nu }_{2}-{F}_{2}({\nu }_{0}\otimes {\nu }_{1}+{\nu }_{1}\otimes {\nu }_{0})=0,\quad {\nu }_{2}(0)=0, \\ & \dots \\ & \frac{\mathrm{d}{\nu }_{c}}{\mathrm{d}t}-{F}_{1}{\nu }_{c}-{F}_{2}\sum\limits _{j=0}^{c-1}{\nu }_{j}\otimes {\nu }_{c-1-j}=0,\quad {\nu }_{c}(0)=0. \end{align} \tag{ 6 }$$

When p = 1 in equation (4), we have

$$\begin{equation}\tilde{u}={\nu }_{0}+{\nu }_{1}+{\nu }_{2}+\cdots +{\nu }_{c}.\end{equation} \tag{ 7 }$$

The difference between $\tilde{u}$ and u is analyzed in section 6.1.

3.2. Linear embedding

Secondly, equation (6) is embedded into the linear ODEs defined in equation (8):

$$\begin{equation}\frac{\mathrm{d}\overrightarrow{y}}{\mathrm{d}t}=A\overrightarrow{y},\quad \overrightarrow{y}(0)={y}_{\text{in}},\end{equation} \tag{ 8 }$$

where $\overrightarrow{y}=[{\overrightarrow{y}}_{0},{\overrightarrow{y}}_{1},\dots ,{\overrightarrow{y}}_{c}]$, ${\overrightarrow{y}}_{i}$ satisfies

$$\begin{equation}{\overrightarrow{y}}_{i}=\begin{cases}[{\nu }_{0}+{\nu }_{1}+\cdots +{\nu }_{c}],\quad & i=0, \\ \left[{\overrightarrow{y}}_{i,0},{\overrightarrow{y}}_{i,1},\dots ,{\overrightarrow{y}}_{i,{\beta }_{i}-1}\right],\quad & 1\leqslant i\leqslant c, \end{cases}\end{equation} \tag{ 9 }$$

where β_i represents the number of items in ${\overrightarrow{y}}_{i}$, ${\overrightarrow{y}}_{i,j}$ represents jth item of ${\overrightarrow{y}}_{i}$, it is represented as ${\overrightarrow{y}}_{i,j}={\otimes }_{k=0}^{i}{\nu }_{{a}_{i,j,k}}$, a_i,j,k satisfies

$$\begin{equation}{a}_{i,j,k}\geqslant 0,\quad i+1\leqslant \sum\limits _{k=0}^{i}({a}_{i,j,k}+1)\leqslant c+1.\end{equation} \tag{ 10 }$$

By equation (10), β_i satisfies

$$\begin{equation}{\beta }_{i}=\begin{cases}1,\quad & i=0, \\ \sum\limits _{k=i}^{c}\left(\genfrac{}{}{0.0pt}{}{k}{i}\right),\quad & 1\leqslant i\leqslant c. \end{cases}\end{equation} \tag{ 11 }$$

We set ${\overrightarrow{y}}_{i,0}={\nu }_{0}^{\otimes i+1},\enspace i=1,2,\dots ,c$, then by equation (6), y_in is written as

$$\begin{equation}{y}_{\text{in}}=[[{u}_{\text{in}}],[{u}_{\text{in}}^{\otimes 2},0,\dots ,0],[{u}_{\text{in}}^{\otimes 3},0,\dots ,0]\dots ,[{u}_{\text{in}}^{\otimes c+1}]].\end{equation} \tag{ 12 }$$

We define ${\overrightarrow{a}}_{i,j}=[{a}_{i,j,0},{a}_{i,j,1},\dots ,{a}_{i,j,i}]$, the mapping ${\overrightarrow{a}}_{i,j}{\mapsto}j$ is one-to-one mapping, so we can construct the following two operations

$$\begin{equation}{O}_{a1}\vert {\overrightarrow{a}}_{i,j}\rangle \vert 0\rangle =\vert {\overrightarrow{a}}_{i,j}\rangle \vert j\rangle ,\end{equation} \tag{ 13 }$$

$$\begin{equation}{O}_{a2}\vert i\rangle \vert j\rangle \vert 0\rangle =\vert i\rangle \vert j\rangle \vert {\overrightarrow{a}}_{i,j}\rangle \end{equation} \tag{ 14 }$$

with O(c)-qubit quantum arithmetic circuit, and the gate complexity is O(poly(c)) [35]. O(poly(c)) will not influence the complexity of our algorithm, so the complexity of O_a1 and O_a2 can be ignored in the following analysis. The dimension of ${\overrightarrow{y}}_{i}$ is nⁱ⁺¹ β_i , so the dimension of $\overrightarrow{y}$ is

$$\begin{equation}N=\sum\limits _{i=0}^{c}{n}^{i+1}{\beta }_{i}={(n+1)}^{c+1}-1-cn\approx {(n+1)}^{c+1}.\end{equation} \tag{ 15 }$$

Next we analyze the structure of matrix A. We have

$$\begin{align}\frac{\mathrm{d}{\overrightarrow{y}}_{i,j}}{\mathrm{d}t}& =\left(\sum\limits _{j=0}^{i}{I}_{n}^{\otimes j}\otimes {F}_{1}\otimes {I}_{n}^{\otimes i-j}\right){\overrightarrow{y}}_{i,j}\\ & \quad +\sum\limits _{k=0}^{i}({I}_{n}^{k}\otimes {F}_{2}\otimes {I}_{n}^{\otimes i-k}){\nu }_{{a}_{i,j,0}}\otimes \cdots \otimes {\nu }_{{a}_{i,j,k-1}}\otimes \left(\sum\limits _{l=0}^{{a}_{i,j,k}-1}{\nu }_{l}\otimes {\nu }_{{a}_{i,j,k}-1-l}\right)\otimes {\nu }_{{a}_{i,j,k+1}}\otimes \cdots \otimes {\nu }_{{a}_{i,j,i}},\end{align} \tag{ 16 }$$

where ${\nu }_{{a}_{i,j,0}}\otimes \cdots \otimes {\nu }_{{a}_{i,j,k-1}}\otimes {\nu }_{l}\otimes {\nu }_{{a}_{i,j,k}-1-l}\otimes {\nu }_{{a}_{i,j,k+1}}\otimes \cdots \otimes {\nu }_{{a}_{i,j,i}}\in {\overrightarrow{y}}_{i+1}$, so equation (8) can be written as

$$\begin{equation}\frac{\mathrm{d}}{\mathrm{d}t}\left(\begin{matrix} {\overrightarrow{y}}_{0} \\ {\overrightarrow{y}}_{1} \\ {\vdots} \\ {\overrightarrow{y}}_{c-1} \\ {\overrightarrow{y}}_{c} \end{matrix}\right)=\left(\begin{matrix} {A}_{0,0} & {A}_{0,1} & & & \\ & {A}_{1,1} & {A}_{1,2} & & \\ & & \ddots & \ddots & \\ & & & {A}_{c-1,c-1} & {A}_{c-1,c} \\ & & & & {A}_{c,c} \end{matrix}\right)\left(\begin{matrix} {\overrightarrow{y}}_{0} \\ {\overrightarrow{y}}_{1} \\ {\vdots} \\ {\overrightarrow{y}}_{c-1} \\ {\overrightarrow{y}}_{c} \end{matrix}\right),\end{equation} \tag{ 17 }$$

A_i,i is nⁱ⁺¹ β_i dimensional square matrix, which is represented as

$$\begin{equation}{A}_{i,i}={I}_{{\beta }_{i}}\otimes \left(\sum\limits _{j=0}^{i}{I}_{n}^{j}\otimes {F}_{1}\otimes {I}_{n}^{\otimes i-j}\right),\end{equation} \tag{ 18 }$$

A_i,i+1 is nⁱ⁺¹ β_i × nⁱ⁺² β_i+1 dimensional matrix, its elements are determined by equation (16). |y(t)⟩ is defined to represent $\overrightarrow{y}(t)$:

$$\begin{equation}\vert y(t)\rangle =\sum\limits _{i=0}^{c}\sum\limits _{j=0}^{{\beta }_{i}-1}\vert i,j\rangle \vert {y}_{i,j}(t)\rangle .\end{equation} \tag{ 19 }$$

3.3. Quantum linear ODEs algorithm

Thirdly, equation (8) is solved with the quantum algorithm proposed in [9]. $\overrightarrow{y}(t)$ is written as

$$\begin{equation}\overrightarrow{y}(t)={\text{e}}^{At}\overrightarrow{y}(0).\end{equation} \tag{ 20 }$$

We define ${T}_{k}(z){:=}{\sum }_{j=0}^{k}\frac{{z}^{j}}{j!}$. When k is large enough and the evolution time h is relatively short (for example, h ⩽ 1/||A||), we have $\overrightarrow{y}(h)\approx {T}_{k}(Ah)\overrightarrow{y}(0)$. This approximate solution can be used as the initial condition for the next approximation, repeating this procedure m steps we have the approximation of $\overrightarrow{y}(mh)$.

Next we introduce the details of the algorithm proposed in [9]. Let $m,k,p\in {\mathbb{Z}}^{+}$ and define

$$\begin{equation}\begin{aligned} {C}_{m,k,p}(A){:=}& \sum\limits _{j=0}^{d}\vert j\rangle \langle j\vert \otimes I-\sum\limits _{i=0}^{m-1}\sum\limits _{j=1}^{k}\vert i(k+1)+j\rangle \langle i(k+1)+j-1\vert \otimes A/j \\ & -\sum\limits _{i=0}^{m-1}\sum\limits _{j=0}^{k}\vert (i+1)(k+1)\rangle \langle i(k+1)+j\vert \otimes I-\sum\limits _{j=d-p+1}^{d}\vert j\rangle \langle j-1\vert \otimes I, \end{aligned}\end{equation} \tag{ 21 }$$

where d := m(k + 1) + p, I is an N-dimensional unit matrix. We consider the linear system

$$\begin{equation}{C}_{m,k,p}(Ah)\vert x\rangle =\vert 0\rangle \vert {y}_{\text{in}}\rangle ,\end{equation} \tag{ 22 }$$

where $\vert {y}_{\text{in}}\rangle \in {\mathbb{C}}^{N},h\in {\mathbb{R}}^{+}$. After evolving m steps, the approximate solution of k-order Taylor series is obtained, and the solution remains unchanged at p steps. The solution of equation (22) is represented as $\vert x\rangle ={C}_{m,k,p}{(Ah)}^{-1}\vert 0\rangle \left\vert {y}_{\text{in}}\right.\hspace{1.5pt}\rangle$, it can also be written as

$$\begin{equation}\vert x\rangle =\sum\limits _{i=0}^{m-1}\sum\limits _{j=0}^{k}\vert i(k+1)+j\rangle \left\vert {x}_{i,j}\right.\enspace \rangle +\sum\limits _{j=0}^{p}\vert m(k+1)+j\rangle \left\vert {x}_{m,j}\right.\enspace \rangle .\end{equation} \tag{ 23 }$$

By equation (21), |x_i,j ⟩ satisfies

$$\begin{align} \vert {x}_{0,0}\rangle & =\vert {y}_{\text{in}}\rangle , \\ \vert {x}_{i,0}\rangle & =\sum\limits _{j=0}^{k}\vert {x}_{i-1,j}\rangle ,\quad 1\leqslant i\leqslant m, \\ \vert {x}_{i,1}\rangle & =Ah\vert {x}_{i,0}\rangle ,\quad 0\leqslant i< m, \\ \vert {x}_{i,j}\rangle & =(Ah/j)\vert {x}_{i,j-1}\rangle ,\quad 0\leqslant i< m,2\leqslant j\leqslant k, \\ \vert {x}_{m,j}\rangle & =\vert {x}_{m,j-1}\rangle ,\quad 1\leqslant j\leqslant p. \end{align} \tag{ 24 }$$

Then we have

$$\begin{equation}\begin{aligned} \left\vert {x}_{0,0}\right.\hspace{1.5pt}\rangle & =\left\vert {y}_{\text{in}}\right.\enspace \rangle , \\ \left\vert {x}_{0,j}\right.\hspace{1.5pt}\rangle & =\left({(Ah)}^{j}/j!\right)\left\vert {x}_{0,0}\right.\enspace \rangle ,\quad 1\leqslant j\leqslant k, \\ \left\vert {x}_{1,0}\right.\hspace{1.5pt}\rangle & ={T}_{k}(Ah)\left\vert {x}_{0,0}\right.\enspace \rangle \approx \mathrm{exp}(Ah)\left\vert {y}_{\text{in}}\right.\hspace{1.5pt}\rangle , \\ \left\vert {x}_{1,j}\right.\hspace{1.5pt}\rangle & =\left({(Ah)}^{j}/j!\right)\left\vert {x}_{1,0}\right.\hspace{1.5pt}\rangle ,\quad 1\leqslant j\leqslant k, \\ \left\vert {x}_{2,0}\right.\enspace \rangle & ={T}_{k}(Ah)\left\vert {x}_{1,0}\right.\hspace{1.5pt}\rangle \approx \mathrm{exp}(2Ah)\left\vert {y}_{\text{in}}\right.\hspace{1.5pt}\rangle , \\ & {\vdots} \\ \left\vert {x}_{m-1,0}\right.\hspace{1.5pt}\rangle & ={T}_{k}(Ah)\left\vert {x}_{m-2,0}\right.\hspace{1.5pt}\rangle \approx \mathrm{exp}(Ah(m-1))\left\vert {y}_{\text{in}}\right.\enspace \rangle , \\ \left\vert {x}_{m-1,j}\right.\hspace{1.5pt}\rangle & =\left({(Ah)}^{j}/j!\right)\left\vert {x}_{m-1,0}\right.\hspace{1.5pt}\rangle ,\quad 1\leqslant j\leqslant k, \\ \left\vert {x}_{m,0}\right.\enspace \rangle & ={T}_{k}(Ah)\left\vert {x}_{m-1,0}\right.\hspace{1.5pt}\rangle \approx \mathrm{exp}(Ahm)\left\vert {y}_{\text{in}}\right.\hspace{1.5pt}\rangle , \\ \left\vert {x}_{m,j}\right.\hspace{1.5pt}\rangle & =\left\vert {x}_{m,0}\right.\hspace{1.5pt}\rangle \approx \mathrm{exp}(Ahm)\left\vert {y}_{\text{in}}\right.\hspace{1.5pt}\rangle ,\quad 1\leqslant j\leqslant p, \end{aligned}\end{equation} \tag{ 25 }$$

|x_i,0⟩ is the approximate solution of the system at time ih, i = ∈ {0, 1, 2, ..., m}. |x_m,0⟩ = |x_m,1⟩ = ⋯ = |x_m,p ⟩ is the approximate solution of $\overrightarrow{y}(t)={\text{e}}^{At}{y}_{\text{in}}$ at t = mh.

3.4. Measurement

In this section, we give the preparation of |y_in⟩ and oracle construction of A.

4.1. State preparation

We first discuss the preparation of |y_in⟩, the result is shown in lemma 1.

Lemma 1. By equation (12), |y_in⟩ is defined as

$$\begin{equation}\vert {y}_{\text{in}}\rangle =\frac{1}{\sqrt{M}}\sum\limits _{i=0}^{c}\vert i,0\hspace{1.5pt}\rangle \vert {u}_{\text{in}}^{\otimes i+1}\rangle ,\end{equation} \tag{ 26 }$$

where $M={\sum }_{j=i}^{c}{\Vert}{u}_{in}{{\Vert}}^{2(i+1)}$. Given O_u defined in equation (2), |y_in⟩ can be prepared by querying O_u O(c) times.

Proof. First we prepare

$$\begin{equation}\vert \psi \rangle =\frac{1}{\sqrt{M}}\sum\limits _{i=0}^{c}{\Vert}{u}_{\text{in}}{{\Vert}}^{2(i+1)}\vert i,0\rangle .\end{equation} \tag{ 27 }$$

Then we execute controlled O_u operation $C-{O}_{u}={\sum }_{i=0}^{c}\vert i,0\rangle \langle i,0\vert \otimes {O}_{u}^{\otimes i+1}$ on |ψ⟩,

$$\begin{equation}\vert {y}_{\text{in}}\rangle =\frac{1}{\sqrt{M}}\sum\limits _{i=0}^{c}\vert i,0\rangle \vert {u}_{\text{in}}^{\otimes i+1}\rangle .\end{equation} \tag{ 28 }$$

The query complexity of O_u is O(c).

4.2. Oracle construction of A

Before introducing oracle construction of A, we analyze some features of A, including sparsity, upper bound of ||A|| and eigenvalue of A. The results are shown in lemmas 2–4.

Lemma 2. The sparsity of the matrix A is O(sc²).

Proof. The sparsity A_i,i is (i + 1)sc. The sparsity of A_0,1 is sc(c + 1)/2, when i ⩾ 1, the sparsity of A_i,i+1 is  max{s(c − i), s(i + 1)}. Therefore, the sparsity of matrix A is O(sc²).

Lemma 3. ||A|| satisfies ||A|| ⩽ (c + 1) (||F₁|| + ||F₂||).

Proof. By the definition of A_i,i , we have

$$\begin{equation}{\Vert}{A}_{i,i}{\Vert}\leqslant (c+1){\Vert}{F}_{1}{\Vert},\quad i\in {[c+1]}_{0},\end{equation} \tag{ 29 }$$

[c + 1]₀ = [0, 1, ..., c] and in this paper, for any $i\in \mathbb{N}$, [i + 1]₀ = [0, 1, ..., i]. Then we analyze upper bound of ||A_i,i+1||. We have ${A}_{0,1}{A}_{0,1}^{\text{T}}=\frac{c(c+1)}{2}{F}_{2}{F}_{2}^{\text{T}}$, then ||A_0,1|| satisfies

$$\begin{equation}{\Vert}{A}_{0,1}{\Vert}=\sqrt{\frac{c(c+1)}{2}}{\Vert}{F}_{2}{\Vert}< (c+1){\Vert}{F}_{2}{\Vert}.\end{equation} \tag{ 30 }$$

When i ⩾ 1, A_i,i+1 can be regarded as β_i × β_i+1 dimensional block matrix, each block unit is an nⁱ⁺¹ × nⁱ⁺² dimensional matrix and has the form I^⊗j ⊗ F₂ ⊗ I^⊗i−j , j ∈ [i + 1]₀. From the structure of A_i,i+1, the number of non-zero block unit in each row or column of A_i,i+1 is no more than c, so A_i,i+1 can be divided into at most c matrices which have only one non-zero block unit in each row or column. Therefore,

$$\begin{equation}{\Vert}{A}_{i,i+1}{\Vert}\leqslant c{\Vert}{F}_{2}{\Vert},\quad i\in [1,2,\dots ,c-1].\end{equation} \tag{ 31 }$$

Combining equations (29)–(31), ||A|| satisfies

$$\begin{align} {\Vert}A{\Vert}\leqslant \enspace & {\Vert}\mathrm{diag}({A}_{0,0},{A}_{1,1},\dots ,{A}_{c,c}){\Vert}+{\Vert}\mathrm{diag}({A}_{0,1},{A}_{1,2},\dots ,{A}_{c-1,c}){\Vert} \\ =\enspace & \underset{i=0{}}{\overset{c}{\mathrm{max}}}\left\{{\Vert}{A}_{i,i}{\Vert}\right\}+\underset{i=0{}}{\overset{c-1}{\mathrm{max}}}\left\{{\Vert}{A}_{i,i+1}{\Vert}\right\} \\ \leqslant \enspace & (c+1)({\Vert}{F}_{1}{\Vert}+{\Vert}{F}_{2}{\Vert}). \end{align} \tag{ 32 }$$

Lemma 4. The eigenvalue γ_i of matrix A satisfies Re(γ_i ) < 0, i ∈ [N]₀.

Proof. From the structure of A, the eigenvalues of A are the sets of eigenvalues of A_i,i for i ∈ [c + 1]₀. The eigenvalue of A_i,i is the sum of i + 1 eigenvalues of F₁. For any j ∈ [1, 2, ..., n], eigenvalue of F₁ λ_j satisfies Re(λ_j ) < 0, so the real part of all eigenvalues of A_i,i is less than 0. Therefore, the eigenvalue γ_i of A satisfies Re(γ_i ) < 0, i ∈ [N]₀.

Next, we introduce the way to construct oracle O_A of A. O_A gives the way to extract non-zero element position and value of A. We first give lemma 5.

Lemma 5. Let matrix $B(m)={\sum }_{j=0}^{m}{I}_{n}^{j}\otimes {F}_{1}\otimes {I}_{n}^{\otimes m-j}$. Oracles O_m,1 and O_m,2 are defined as

$$\begin{equation}\begin{aligned} {O}_{m,1}\vert \overrightarrow{j}\hspace{1.5pt}\rangle \vert l\hspace{1.5pt}\rangle & =\vert \overrightarrow{j}\hspace{1.5pt}\rangle \vert {g}_{m}(\overrightarrow{j},l)\rangle , \\ {O}_{m,2}\vert \overrightarrow{j}\hspace{1.5pt}\rangle \vert \overrightarrow{k}\hspace{1.5pt}\rangle \vert z\hspace{1pt}\rangle & =\vert \overrightarrow{j}\hspace{1.5pt}\rangle \vert \overrightarrow{k}\hspace{1.5pt}\rangle \vert z\oplus B{(m)}_{\overrightarrow{j},\overrightarrow{k}}\hspace{1.5pt}\rangle , \end{aligned}\end{equation} \tag{ 33 }$$

where $\overrightarrow{j}={j}_{m}{j}_{m-1}\dots {j}_{1}{j}_{0}$, j_i ∈ [n]₀. ${g}_{m}(\overrightarrow{j},l)$ represents the column number of lth non-zero element in $\overrightarrow{j}$th row of B(m), ${g}_{m}(\overrightarrow{j},l)$ is also written as ${g}_{m}(\overrightarrow{j},l)={k}_{m}{k}_{m-1}\dots {k}_{0}$, k_i ∈ [n]₀. Then O_m,1, O_m,2 can be constructed by querying O_F1 m + 1 times.

Proof. When m = 0, B(0) = F₁, O_0,1, O_0,2 can be constructed by querying O_F1 once. Assuming when m ⩾ 1, Oracles O_m−1,1, O_m−1,2 of B(m − 1) are constructed by querying O_F1 m times. B(m) is also written as

$$\begin{equation}B(m)=I\otimes B(m-1)+{F}_{1}\otimes {I}^{\otimes m}.\end{equation} \tag{ 34 }$$

Generally, we treat the diagonal element of F₁ as a non-zero element, so the sparsity of B(m) is (m + 1)c − m. ${g}_{m}(\overrightarrow{j},k)$ can be represented as

$$\begin{equation}{g}_{m}(\overrightarrow{j},k)=\begin{cases}{f}_{1}({j}_{m},k){j}_{m-1}\dots {j}_{0},\quad & 0\leqslant k< g({j}_{m}), \\ {j}_{m}{g}_{m-1}({j}_{m-1}\dots {j}_{0},k-g({j}_{m})),\quad & 0\leqslant k-g({j}_{m})\leqslant m(c-1)+1, \\ {f}_{1}({j}_{m},k-m(c-1)){j}_{m-1}\dots {j}_{0},\quad & g({j}_{m})+1\leqslant k-m(c-1)\leqslant c-1, \end{cases}\end{equation} \tag{ 35 }$$

where f₁(j, k) and g(j) are defined in equation (2). Then O_m,1 can be constructed with equation (35), the construction process needs to query O_m−1,1, O_F11, O_F13 once each.

On the other hand, the element of B(m) is written as

$$\begin{equation}B{(m)}_{\overrightarrow{j},\overrightarrow{k}}={\delta }_{{j}_{m}{k}_{m}}B{(m-1)}_{{j}_{m-1}\dots {j}_{0},{k}_{m-1}\dots {k}_{0}}+{\delta }_{{j}_{m-1}\dots {j}_{0},{k}_{m-1}\dots {k}_{0}}{B}_{{j}_{m},{k}_{m}}.\end{equation} \tag{ 36 }$$

By equation (36), O_m,2 can be constructed by querying O_m−1,2 and O_F12 once each. Therefore O_m,1 and O_m,2 can be constructed by querying O_m−1,1, O_m−1,2, O_F11, O_F12 and O_F13 once each.

From the above analysis, O_m,1 and O_m,2 can be constructed by querying O_F1 m + 1 times.

Lemma 6. The oracle O_A of A can be constructed by querying O_F1 O(c) times and querying O_F2 O(1) times.

Proof. To construct O_A , we need to construct oracles of A_i,i and A_i,i+1. We first consider A_i,i , we define $B(i)={\sum }_{j=0}^{i}{I}_{n}^{j}\otimes {F}_{1}\otimes {I}_{n}^{\otimes c-i-j}$, by lemma 5, the oracle of B(i) can be constructed by querying O_F1 i + 1 times. By equation (18), the oracle of A_i,i can be constructed by querying oracle of B(i) once.

Next we consider A_i,i+1. When i = 0, A_0,1 = [F₂, F₂, ..., F₂], the oracle of A_0,1 is constructed by querying O_F2 once. When i ⩾ 1, A_i,i+1 is also regarded as β_i × β_i+1 dimensional block matrix D(i), the dimension of each block unit is nⁱ⁺¹ × nⁱ⁺². The number of non-zero block unit in jth row of D(i) is ${\sum }_{k=0}^{i}{a}_{i,j,k}$. Consider the lth non-zero bolck unit in jth row of D(i), l is represented as $l={\sum }_{k=0}^{{i}_{1}}{a}_{i,j,k}+{i}_{2}$, where ${i}_{1}\in {[i]}_{0},{i}_{2}\in \mathbb{N}$, the lth non-zero block unit is ${I}^{\otimes {i}_{1}}\otimes {F}_{2}\otimes {I}^{\otimes i-{i}_{1}}$, and the corresponding ${\overrightarrow{a}}_{i+1,{j}^{\prime }}$ is represented as

$$\begin{equation}{\overrightarrow{a}}_{i+1,{j}^{\prime }}=[{a}_{i,j,0},\dots ,{a}_{i,j,{i}_{1}},{i}_{2},{a}_{i,j,{i}_{1}+1}-1-{i}_{2},{a}_{i,j,i+2},\dots {a}_{i,j,i}],\end{equation} \tag{ 37 }$$

j' can be obtained from ${\overrightarrow{a}}_{i+1,{j}^{\prime }}$ with O_a1. The oracle of the non-zero block unit ${I}^{\otimes {i}_{1}}\otimes {F}_{2}\otimes {I}^{\otimes i-{i}_{1}}$ is constructed by querying O_F2 once. By realizing the above process with quantum circuit, we construct an oracle that extracts the non-zero position of A_i,i+1. The specific implementation process is

$$\begin{align} & \vert j,{b}_{i},{b}_{i-1},\dots ,{b}_{{i}_{1}},\dots ,{b}_{0}\hspace{1.5pt}\rangle \vert l,{l}_{b}\hspace{1.5pt}\rangle \vert 0,0\rangle \\ \stackrel{{O}_{a2}}{\to }& \enspace \vert j,{b}_{i},{b}_{i-1},\dots ,{b}_{{i}_{1}},\dots ,{b}_{0}\hspace{1.5pt}\rangle \vert l,{l}_{b}\hspace{1.5pt}\rangle \vert {i}_{1},{i}_{2}\hspace{1pt}\rangle \\ \stackrel{{O}_{a1}}{\to }& \enspace \vert j,{b}_{i},{b}_{i-1},\dots ,{b}_{{i}_{1}},\dots ,{b}_{0}\hspace{1.5pt}\rangle \vert {j}^{\prime },{l}_{b}\hspace{1.5pt}\rangle \vert {i}_{1},{i}_{2}\rangle \\ \stackrel{{O}_{F21}}{\to }& \enspace \vert j,{b}_{i},{b}_{i-1},\dots ,{b}_{{i}_{1}},\dots ,{b}_{0}\hspace{1.5pt}\rangle \vert {j}^{\prime },{b}_{i},{b}_{i-1},\dots ,{f}_{2}({b}_{{i}_{1}},{l}_{b}),\dots {b}_{0}\hspace{1.5pt}\rangle \vert {i}_{1},{i}_{2}\hspace{1pt}\rangle \\ \stackrel{\text{uncompute}}{\to }& \enspace \vert j,{b}_{i},{b}_{i-1},\dots ,{b}_{{i}_{1}},\dots ,{b}_{0}\hspace{1.5pt}\rangle \vert {j}^{\prime },{b}_{i},{b}_{i-1},\dots ,{f}_{2}({b}_{{i}_{1}},{l}_{b}),\dots {b}_{0}\hspace{1.5pt}\rangle \vert 0,0\hspace{.5pt}\rangle . \end{align} \tag{ 38 }$$

There are some ancilla qubits to represent $\vert {\overrightarrow{a}}_{i,j}\hspace{1.5pt}\rangle$ and $\vert {\overrightarrow{a}}_{i+1,{j}^{\prime }}\hspace{1.5pt}\rangle$ in the process shown in equation (38). For simplicity, we ignore the compute and uncompute process of $\vert {\overrightarrow{a}}_{i,j}\hspace{1.5pt}\rangle$ and $\vert {\overrightarrow{a}}_{i+1,{j}^{\prime }}\hspace{1.5pt}\rangle$.

The oracle that extracts the non-zero value of A_i,i+1 can also be constructed in a similar process. For any $j\in {[{\beta }_{i}]}_{0}$, $k\in {[{\beta }_{i+1}]}_{0}$, we can judge whether D(i)_j,k is a non-zero block unit and use l_j,k to represent the judgement. If D(i)_j,k is a non-zero block unit, we can find i₁ and represent it as ${I}^{\otimes {i}_{1}}\otimes {F}_{2}\otimes {I}^{\otimes i-{i}_{1}}$, then we use O_F22 to extract the elements of the non-zero block unit. The whole process is shown as

$$\begin{align} & \vert \overrightarrow{j}\hspace{1.5pt}\rangle \vert \overrightarrow{k}\hspace{1.5pt}\rangle \vert 0,0\hspace{.5pt}\rangle \vert z\hspace{1.5pt}\rangle =\vert j,{b}_{i},{b}_{i-1},\dots ,{b}_{0}\hspace{1.5pt}\rangle \vert k,{b}_{i}^{\prime },{b}_{i-1}^{\prime },\dots ,{b}_{0}^{\prime }\hspace{1.5pt}\rangle \vert 0,0\hspace{.5pt}\rangle \vert z\rangle \\ \stackrel{{O}_{a1},{O}_{a2}}{\to }& \vert \overrightarrow{j}\rangle \vert \overrightarrow{k}\rangle \vert {l}_{j,k},{i}_{1}\rangle \vert z\rangle \\ \stackrel{{O}_{F22}}{\to }& \vert \overrightarrow{j}\rangle \vert \overrightarrow{k}\rangle \vert {l}_{j,k},{i}_{1}\rangle \vert z\oplus {l}_{j,k}\times {{F}_{2}}_{{b}_{{i}_{1}},{b}_{{i}_{1}}^{\prime }}\prod\limits _{l\in [i],l\ne {i}_{1}}{\delta }_{{b}_{l}{b}_{l}^{\prime }}\rangle \\ \stackrel{\text{uncompute}}{\to }& \vert \overrightarrow{j}\rangle \vert \overrightarrow{k}\rangle \vert 0,0\rangle \vert z\oplus D{(i)}_{\overrightarrow{j},\overrightarrow{k}}\rangle . \end{align} \tag{ 39 }$$

The query complexity of O_F22 in the above process is O(1). Therefore, oracle of A_i,i+1 can be constructed by querying O_F2 O(1) times.

After constructing the oracles of A_i,i and A_i,i+1, the oracle of A can be directly constructed by querying oracles of A_i,i and A_i,i+1 once. So the oracle O_A can be constructed by querying O_F1 O(c) times and querying O_F2 O(1) times.

In this section, we give an upper bound of the condition number of C_m,k,p (Ah) defined in section 3.3. We first analyze the upper bound of ||e^Aht ||, we have the following lemma.

Lemma 7. Consider the matrix A defined in section 3.2, when

$$\begin{equation}\frac{(c+1){\Vert}{F}_{2}{\Vert}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }\leqslant 1,\end{equation} \tag{ 40 }$$

for t ⩾ 0, ||e^At || satisfies

$$\begin{equation}{\Vert}{\text{e}}^{At}{\Vert}\leqslant c+1.\end{equation} \tag{ 41 }$$

Proof. We consider A as a c + 1-dimensional block matrix. A is divided into

$$\begin{equation}A=B+C,\end{equation} \tag{ 42 }$$

B contains A_i,i , i = 0, 1, ..., c and C contains A_i,i+1, i = 0, 1, ..., c − 1. We analyze the upper bound of ||e^At || according to the method introduced in [36], e^At is written as

$$\begin{equation}{\text{e}}^{(B+C)t}={\text{e}}^{Bt}+{\int }_{0}^{t}{\text{e}}^{B(t-{t}_{0})}C{\text{e}}^{(B+C){t}_{0}}\mathrm{d}{t}_{0}.\end{equation} \tag{ 43 }$$

Using this formula to expand ${\text{e}}^{(B+C){t}_{0}}$ we obtain

$$\begin{equation}{\text{e}}^{(B+C)t}={\text{e}}^{Bt}+{\int }_{0}^{t}{\text{e}}^{B(t-{t}_{0})}C{\text{e}}^{B{t}_{0}}\mathrm{d}{t}_{0}+{\int }_{0}^{t}{\int }_{0}^{{t}_{0}}{\text{e}}^{B(t-{t}_{0})}C{\text{e}}^{B({t}_{0}-{t}_{1})}C{\text{e}}^{(B+C){t}_{1}}\mathrm{d}{t}_{1}\enspace \mathrm{d}{t}_{0}.\end{equation} \tag{ 44 }$$

Clearly, a repetition of this process gives

$$\begin{equation}{\text{e}}^{(B+C)t}={\text{e}}^{Bt}+\sum\limits _{k=0}^{c-1}{A}_{k}(t)+{R}_{c}(t),\end{equation} \tag{ 45 }$$

where

$$\begin{equation}{A}_{k}(t)={\int }_{0}^{t}{\int }_{0}^{{t}_{0}}\cdots {\int }_{0}^{{t}_{k-1}}{\text{e}}^{B\left(t-{t}_{0}\right)}C{\text{e}}^{B\left({t}_{0}-{t}_{1}\right)}C\cdots C{\text{e}}^{B{t}_{k}}\enspace \mathrm{d}{t}_{k}\cdots \mathrm{d}{t}_{0}\end{equation} \tag{ 46 }$$

and

$$\begin{equation}{R}_{c}(t)={\int }_{0}^{t}{\int }_{0}^{{t}_{0}}\cdots {\int }_{0}^{{t}_{c-1}}{\text{e}}^{B\left(t-{t}_{0}\right)}C\cdots C{\text{e}}^{B\left({t}_{c-1}-{t}_{c}\right)}C{\text{e}}^{(B+C){t}_{c}}\mathrm{d}{t}_{c}\cdots \mathrm{d}{t}_{0}.\end{equation} \tag{ 47 }$$

Noting that

$$\begin{equation}{\Vert}{A}_{k}(t){\Vert}\leqslant {\Vert}{\text{e}}^{Bt}{\Vert}{\Vert}C{{\Vert}}^{k+1}\times \frac{{t}^{k+1}}{(k+1)!}={\Vert}{\text{e}}^{Bt}{\Vert}\frac{{({\Vert}Ct{\Vert})}^{k+1}}{(k+1)!},\quad k=0,1,\dots ,c-1,\end{equation} \tag{ 48 }$$

$$\begin{equation}{\Vert}{\text{e}}^{Bt}{\Vert}={\text{e}}^{\text{Re}({\lambda }_{1})t},\quad {\Vert}C{\Vert}\leqslant (c+1){\Vert}{F}_{2}{\Vert},\end{equation} \tag{ 49 }$$

and the matrix $[{\text{e}}^{B(t-{t}_{0})}C]\dots [{\text{e}}^{B({t}_{c-1}-{t}_{c})}C]$ is zero because it is the product of c + 1, (c + 1) × (c + 1) strictly upper triangular block matrices and thus, R_c (t) = 0. Hence,

$$\begin{equation}{\Vert}{\text{e}}^{At}{\Vert}={\Vert}{\text{e}}^{(B+C)t}{\Vert}\leqslant {\text{e}}^{\text{Re}({\lambda }_{1})t}\sum\limits _{k=0}^{c}\frac{{((c+1){\Vert}{F}_{2}{\Vert}t)}^{k}}{k!}.\end{equation} \tag{ 50 }$$

By lemma 14, equations (40) and (50),

$$\begin{equation}{\Vert}{\text{e}}^{At}{\Vert}\leqslant c+1.\end{equation} \tag{ 51 }$$

Then the upper bound of the condition number κ_C of C_m,k,p (Ah) is analyzed in lemma 8.

Lemma 8. Consider the matrix C_m,k,p (Ah) defined in section 3.3. Let $h\in {\mathbb{R}}^{+}$ and satisfies ||Ah|| ⩽ 1, $c,m,k,p\in {\mathbb{Z}}^{+}$. When $\frac{(c+1){\Vert}{F}_{2}{\Vert}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }\leqslant 1$, k ⩾ 5 and $\frac{2}{(k+1)!}m(c+1)(c+2)\leqslant 1$, the condition number κ_C of C_m,k,p (Ah) satisfies

$$\begin{equation}{\kappa }_{\text{C}}\leqslant 2e\sqrt{k}(m(k+1)+p)(c+2),\end{equation} \tag{ 52 }$$

where e is mathematical constant.

Proof. First we analyze the upper bound of ||C_m,k,p (Ah)⁻¹||, we have

$$\begin{equation}{C}_{m,k,p}(Ah)\vert x\rangle =\vert B\rangle ,\end{equation} \tag{ 53 }$$

where $\vert B\rangle ={\sum }_{l=0}^{d}{b}_{l}\vert l\rangle$, |l⟩ represents an N-dimensional state. We define |b^l ⟩ := b_l |l⟩,

$$\begin{equation}\sum\limits _{l=0}^{d}{\Vert}\vert {b}^{l}\rangle {{\Vert}}^{2}={\Vert}\vert B\rangle {{\Vert}}^{2}.\end{equation} \tag{ 54 }$$

For any l ∈ [d]₀, we define

$$\begin{equation}\vert {x}^{l}\rangle {:=}{C}_{m,k,p}{(Ah)}^{-1}\vert {b}^{l}\rangle =\sum\limits _{n=0}^{d}\vert {x}_{n}^{l}\rangle .\end{equation} \tag{ 55 }$$

We consider two cases: 0 ⩽ l < m(k + 1) and m(k + 1) ⩽ l ⩽ d.

When 0 ⩽ l < m(k + 1), assuming l = a(k + 1) + b, 0 ⩽ a < m, 0 ⩽ b ⩽ k. Then based on definition of x, we have

$$\begin{equation}\begin{aligned} \vert {x}_{i,j}^{l}\rangle & =0, & 0\leqslant i< a,0\leqslant j\leqslant k,\\ \vert {x}_{a,j}^{l}\rangle & =0, & 0\leqslant j< b,\\ \vert {x}_{a,j}^{l}\rangle & =b!{(Ah)}^{j-b}/j!\vert {b}^{l}\rangle , & b\leqslant j\leqslant k\\ \vert {x}_{a+1,0}^{l}\rangle & ={T}_{b,k}(Ah)\vert {b}^{l}\rangle , & \\ \vert {x}_{a+1,j}^{l}\rangle & ={(Ah)}^{j}/j!\vert {x}_{a+1,0}^{l}\rangle , & \\ \vert {x}_{a+2,0}^{l}\rangle & ={T}_{k}(Ah)\vert {x}_{a+1,0}^{l}\rangle ={T}_{k}(Ah){T}_{b,k}(Ah)\vert {b}^{l}\rangle , & \\ & {\vdots} & \\ \vert {x}_{m,0}^{l}\rangle & ={T}_{k}(Ah)\vert {x}_{m-1,0}^{l}\rangle ={\left({T}_{k}(Ah)\right)}^{m-a-1}{T}_{b,k}(Ah)\vert {b}^{l}\rangle , & \\ \vert {x}_{m,j}^{l}\rangle & =\vert {x}_{m,0}\rangle ={\left({T}_{k}(Ah)\right)}^{m-a-1}{T}_{b,k}(Ah)\vert {b}^{l}\rangle , & 1\leqslant j\leqslant p,\end{aligned}\end{equation} \tag{ 56 }$$

where $\vert {x}_{i,j}^{l}\rangle =\vert {x}_{i(k+1)+j}^{l}\rangle$ and ${T}_{b,k}(Ah){:=}{\sum }_{j=b}^{k}\frac{b!{(Ah)}^{j-b}}{j!}$. By lemma 15, we have

$$\begin{equation}{\Vert}{\text{e}}^{Ah(m-a-1)}-{T}_{k}^{m-a-1}(Ah){\Vert}\leqslant \frac{2}{(k+1)!}(m-a-1)(c+1)(c+2),\end{equation} \tag{ 57 }$$

by lemma 7, ||e^{Ah(m−a−1)}|| ⩽ c + 1, then we have

$$\begin{equation}{\Vert}{\left({T}_{k}(Ah)\right)}^{m-a-1}{\Vert}\leqslant c+2.\end{equation} \tag{ 58 }$$

Therefore,

$$\begin{equation}\begin{aligned} {\Vert}{(Ah)}^{j-b}{\Vert}& \leqslant {\Vert}(Ah){{\Vert}}^{j-b}\leqslant 1,\quad \quad \quad \quad b\leqslant j\leqslant k, \\ {\Vert}{T}_{b,k}(Ah){\Vert}& \leqslant {T}_{b,k}({\Vert}Ah{\Vert})\leqslant {\text{e}}^{{\Vert}Ah{\Vert}}\leqslant e, \\ {\Vert}{T}_{k}(Ah){\Vert}& \leqslant {T}_{k}({\Vert}Ah{\Vert})\leqslant {\text{e}}^{{\Vert}Ah{\Vert}}\leqslant e, \\ {\Vert}{\left({T}_{k}(Ah)\right)}^{m-a-1}{T}_{b,k}(Ah){\Vert}& \leqslant {\Vert}{\left({T}_{k}(Ah)\right)}^{m-a-1}{\Vert}{\Vert}{T}_{b,k}(Ah){\Vert}\leqslant e(c+2). \end{aligned}\end{equation} \tag{ 59 }$$

By equations (56) and (59), ${\Vert}{x}_{i,j}^{l}{\Vert}$ satisfies

$$\begin{equation}\begin{aligned} {\Vert}\vert {x}_{a,j}^{l}\rangle {\Vert}& \leqslant \frac{b!}{j!}{\Vert}{(Ah)}^{j-b}{\Vert}{\Vert}\vert {b}^{l}\rangle {\Vert}\leqslant {\Vert}\vert {b}^{l}\rangle {\Vert}, & b\leqslant j\leqslant k\\ {\Vert}\vert {x}_{a+1,0}^{l}\rangle {\Vert}& \leqslant {\Vert}{T}_{b,k}(Ah){\Vert}{\Vert}\vert {b}^{l}\rangle {\Vert}\leqslant e{\Vert}\vert {b}^{l}\rangle {\Vert}, & \\ {\Vert}\vert {x}_{i,j}^{l}\rangle {\Vert}& \leqslant e(c+2){\Vert}\vert {b}^{l}\rangle {\Vert}, & a+1\leqslant i\leqslant m-1,0\leqslant j\leqslant k\\ {\Vert}\vert {x}_{m,j}^{l}\rangle {\Vert}& \leqslant e(c+2){\Vert}\vert {b}^{l}\rangle {\Vert}, & 0\leqslant j\leqslant p\end{aligned}\end{equation} \tag{ 60 }$$

therefore,

$$\begin{equation}{\Vert}{C}_{m,k,p}{(Ah)}^{-1}\vert {b}^{l}\rangle {{\Vert}}^{2}\leqslant (m(k+1)+p)(e(c+2)){\left.\right)}^{2}{\Vert}\vert {b}^{l}\rangle {{\Vert}}^{2}.\end{equation} \tag{ 61 }$$

When m(k + 1) ⩽ l ⩽ d, assuming l = m(k + 1) + b, 0 ⩽ b ⩽ p, x_i,j satisfies

$$\begin{equation}\begin{aligned} \vert {x}_{i,j}^{l}\rangle & =0, & 0\leqslant i< m,0\leqslant j\leqslant k,\\ \vert {x}_{m,j}^{l}\rangle & =0, & 0\leqslant j< b,\\ \vert {x}_{m,j}^{l}\rangle & =\vert {b}^{l}\rangle , & b\leqslant j\leqslant p,\end{aligned}\end{equation} \tag{ 62 }$$

then

$$\begin{equation}{\Vert}{C}_{m,k,p}{(Ah)}^{-1}\vert {b}^{l}\rangle {{\Vert}}^{2}\leqslant p{\Vert}\vert {b}^{l}\rangle {{\Vert}}^{2}.\end{equation} \tag{ 63 }$$

From equations (61) and (63), for any |B⟩, ||C_m,k,p (Ah)⁻¹|B⟩|| satisfies

$$\begin{align} {\Vert}{C}_{m,k,p}{(Ah)}^{-1}\vert B\rangle {{\Vert}}^{2}\leqslant \enspace & (m(k+1)+p)\sum\limits _{l=0}^{d}{\Vert}{C}_{m,k,p}{(Ah)}^{-1}\vert {b}^{l}\rangle {{\Vert}}^{2} \\ \leqslant \enspace & {(m(k+1)+p)}^{2}{(e(c+2))}^{2}{\Vert}\vert B\rangle {{\Vert}}^{2}, \end{align} \tag{ 64 }$$

then

$$\begin{equation}{\Vert}{C}_{m,k,p}{(Ah)}^{-1}{\Vert}\leqslant (m(k+1)+p)e(c+2).\end{equation} \tag{ 65 }$$

From lemma 4 in [9], we have

$$\begin{equation}{\Vert}{C}_{m,k,p}(Ah){\Vert}\leqslant 2\sqrt{k}.\end{equation} \tag{ 66 }$$

Therefore, by equations (66) and (65), we have ${\kappa }_{C}\leqslant 2e\sqrt{k}(m(k+1)+p)(c+2)$.

In this section, we analyze the solution error of our algorithm. The error mainly comes from two aspects: (1) homotopy perturbation method truncation error. The solution $\tilde{u}(t)$ defined in equation (7) is an approximate solution of equation (1), the error bound is determined by the truncation order c, in section 6.1, we analyze the convergence condition of equation (7) and give the error bound. (2) Linear ODEs solution error. We solve the linear ODEs defined in equation (8) with the quantum algorithm proposed in [9]. This algorithm also generates intermediate error, we analyze the error bound in section 6.2.

6.1. Homotopy perturbation method truncation error

We first analyze homotopy perturbation method truncation error, the result is shown in lemma 9.

Lemma 9. Consider the nonlinear ODEs defined in equation (1), the solution of equation (1) obtained by homotopy perturbation method is written as $\tilde{u}(t)={\sum }_{i=0}^{c}{\nu }_{i}(t)$, u(t) represents the exact solution of equation (1). When K < 1 and $c > {\mathrm{log}}_{1/K}\frac{1}{{\epsilon}(1-K)}$, $\tilde{u}(t)$ satisfies

$$\begin{equation}{\Vert}u(t)-\tilde{u}(t){\Vert}\leqslant {\epsilon}.\end{equation} \tag{ 67 }$$

Proof.  u(t) can be represented as $u(t)={\sum }_{i=0}^{\infty }{\nu }_{i}(t)$, equation (67) is transformed into

$$\begin{equation}{\Vert}\sum\limits _{j=c+1}^{\infty }{\nu }_{j}(t){\Vert}< {\epsilon}.\end{equation} \tag{ 68 }$$

To prove equation (68), we analyze the upper bound of ||ν_i || defined in equation (6). ${\nu }_{0}(t)={\text{e}}^{{F}_{1}t}{u}_{\text{in}}$, we have

$$\begin{equation}{\Vert}{\nu }_{0}(t){\Vert}\leqslant {\Vert}{\text{e}}^{{F}_{1}t}{\Vert}\times {\Vert}{u}_{\text{in}}{\Vert}\leqslant {\Vert}{u}_{\text{in}}{\Vert}.\end{equation} \tag{ 69 }$$

We define ${K}_{1}=\frac{{\Vert}{u}_{\text{in}}{\Vert}{\Vert}{F}_{2}{\Vert}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }$ and assume when j ⩽ i, ||ν_j || satisfies

$$\begin{equation}{\Vert}{\nu }_{j}{\Vert}\leqslant {\alpha }_{j}{K}_{1}^{j}{\Vert}{u}_{\text{in}}{\Vert},\quad j=0,1,\dots ,i.\end{equation} \tag{ 70 }$$

Then ||ν_i+1(t)|| satisfies

$$\begin{align} {\Vert}{\nu }_{i+1}(t){\Vert}& ={\Vert}{\int }_{0}^{t}{\text{e}}^{{F}_{1}(t-\tau )}{F}_{2}\sum\limits _{j=0}^{i}{\nu }_{j}(\tau )\otimes {\nu }_{i-j}(\tau )\mathrm{d}\tau {\Vert} \\ & \leqslant {\int }_{0}^{t}{\Vert}{\text{e}}^{{F}_{1}(t-\tau )}{F}_{2}{\Vert}\times \left(\sum\limits _{j=0}^{i}{\alpha }_{j}{\alpha }_{i-j}\right){K}_{1}^{i}{\Vert}{u}_{\text{in}}{{\Vert}}^{2}\mathrm{d}\tau \\ & \leqslant \left(\sum\limits _{j=0}^{i}{\alpha }_{j}{\alpha }_{i-j}\right){K}_{1}^{i}{\Vert}{u}_{\text{in}}{{\Vert}}^{2}{\Vert}{F}_{2}{\Vert}{\int }_{0}^{t}{\Vert}{\text{e}}^{\text{Re}({\lambda }_{1})(t-\tau )}{\Vert}\mathrm{d}\tau \\ & \leqslant \left(\sum\limits _{j=0}^{i}{\alpha }_{j}{\alpha }_{i-j}\right){K}_{1}^{i}{\Vert}{u}_{\text{in}}{{\Vert}}^{2}{\Vert}{F}_{2}{\Vert}\frac{1-{\text{e}}^{\text{Re}({\lambda }_{1})t}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert } \\ & \leqslant \left(\sum\limits _{j=0}^{i}{\alpha }_{j}{\alpha }_{i-j}\right){K}_{1}^{i+1}{\Vert}{u}_{\text{in}}{\Vert}. \end{align} \tag{ 71 }$$

By equations (70) and (71), α_i can be defined as

$$\begin{equation}{\alpha }_{i+1}=\sum\limits _{j=0}^{i}{\alpha }_{j}{\alpha }_{i-j},\quad {\alpha }_{0}=1.\end{equation} \tag{ 72 }$$

Equation (72) is the Catalan sequence [37] and satisfies

$$\begin{equation}{\alpha }_{i}=\frac{1}{i+1}\left(\genfrac{}{}{0.0pt}{}{2i}{i}\right)\approx \frac{{4}^{i}}{{i}^{3/2}\sqrt{\pi }}< {4}^{i}.\end{equation} \tag{ 73 }$$

Combining equations (3) and (70)–(73), for any $i\in \mathbb{N}$, ||ν_i (t)|| has the upper bound

$$\begin{equation}{\Vert}{\nu }_{i}(t){\Vert}< {(4{K}_{1})}^{i}{\Vert}{u}_{\text{in}}{\Vert}\leqslant {K}^{i+1}.\end{equation} \tag{ 74 }$$

Substituting equation (74) into equation (68), we have

$$\begin{equation}\sum\limits _{i=c+1}^{\infty }{K}^{i+1}< {\epsilon}.\end{equation} \tag{ 75 }$$

Therefore, when K < 1 and $c > {\mathrm{log}}_{1/K}\frac{1}{{\epsilon}(1-K)}$, we have ${\Vert}u(t)-\tilde{u}(t){\Vert}\leqslant {\epsilon}$.

6.2. Linear ODEs solution error

Then we analyze the error of solving the linear ODEs defined in equation (8), we have a similar conclusion with theorem 6 in [9], the difference comes from the upper bound of ||e^Aj || or ${\Vert}{T}_{k}^{j}(A){\Vert}$ in our work is different from their work. Our result is shown in lemma 10.

Lemma 10. Consider the linear ODEs defined in equation (8) and the system of linear equations defined in equation (22). Let $h\in {\mathbb{R}}^{+}$ satisfies ||Ah|| ⩽ 1. When $\frac{2}{(k+1)!}m(c+1)(c+2)\leqslant 1$, we have

$$\begin{equation}{\Vert}\vert y(jh)\rangle -\vert {x}_{j,0}\rangle {\Vert}\leqslant \frac{2j(c+1)(c+2){\Vert}{y}_{\text{in}}{\Vert}}{(k+1)!},\quad j=0,1,\dots ,m.\end{equation} \tag{ 76 }$$

Proof. The exact solution of equation (8) at t = jh is |y(jh)⟩, it is written as

$$\begin{equation}\vert y(jh)\rangle ={\text{e}}^{Ajh}\vert y(0)\rangle .\end{equation} \tag{ 77 }$$

The solution of equation (22) |x_j,0⟩ satisfies

$$\begin{equation}\vert {x}_{j,0}\rangle ={T}_{k}^{j}(Ah)\vert {x}_{0,0}\rangle ,\end{equation} \tag{ 78 }$$

where ${T}_{k}(Ah)={\sum }_{l=0}^{k}\frac{{(Ah)}^{l}}{l!}$, the initial value satisfies |y(0)⟩ = |x_0,0⟩ = |y_in⟩. By lemmas 7 and 15, |||y(jh)⟩ − |x_j,0⟩|| satisfies

$$\begin{equation}{\Vert}\vert y(jh)\rangle -\vert {x}_{j,0}\rangle {\Vert}\leqslant {\Vert}{\text{e}}^{Ajh}-{T}_{k}^{j}(Ah){\Vert}{\Vert}{y}_{\text{in}}{\Vert}\leqslant \frac{2j(c+1)(c+2){\Vert}{y}_{\text{in}}{\Vert}}{(k+1)!},\quad j=0,1,\dots ,m.\end{equation} \tag{ 79 }$$

As introduced in section 3.4, there are two probabilistic steps in our method. This section gives a lower bound of the success probability of these two steps. The results are shown in lemmas 11 and 12.

Firstly, we analyze the success probability of getting |x_m,i ⟩, i = 0, 1, ..., p when measuring |x⟩. By setting appropriate conditions, lemma 11 gives the same conclusion as theorem 7 in [9].

Lemma 11. Consider the system of linear equations defined in equation (22). Let $h\in {\mathbb{R}}^{+}$ satisfies ||Ah|| ⩽ 1. g = max_t∈[0,mh]|||y(t)⟩||/|||y(mh)⟩||, $m,k,p\in {\mathbb{Z}}^{+}$. When (k + 1)! ⩾ 50m(c + 1) (c + 2)g, we have

$$\begin{equation}\frac{{\Vert}\vert {x}_{m,0}\rangle {{\Vert}}^{2}}{{\Vert}\vert x\rangle {{\Vert}}^{2}}\geqslant \frac{1}{p+77m{g}^{2}}.\end{equation} \tag{ 80 }$$

Proof. As introduced before, |x_m,j ⟩ = |x_m,0⟩ for j ∈ [p]₀, we define

$$\begin{equation}\vert {x}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\rangle {:=}\sum\limits _{j=0}^{p}\vert m(k+1)+j\rangle \vert {x}_{m,j}\rangle \end{equation} \tag{ 81 }$$

and

$$\begin{equation}\vert {x}_{\mathrm{b}\mathrm{a}\mathrm{d}}\rangle {:=}\sum\limits _{i=0}^{m-1}\sum\limits _{j=0}^{k}\vert i(k+1)+j\rangle \vert {x}_{i,j}\rangle .\end{equation} \tag{ 82 }$$

We see |x⟩ = |x_good⟩ + |x_bad⟩ and ⟨x_good|x_bad⟩ = 0, then

$$\begin{align} {\Vert}\vert x\rangle {{\Vert}}^{2}=\enspace & {\Vert}\vert {x}_{\mathrm{g}\mathrm{o}\mathrm{o}\mathrm{d}}\rangle {{\Vert}}^{2}+{\Vert}\vert {x}_{\mathrm{b}\mathrm{a}\mathrm{d}}\rangle {{\Vert}}^{2} \\ =\enspace & (p+1){\Vert}\vert {x}_{m,0}\rangle {{\Vert}}^{2}+{\Vert}\vert {x}_{\mathrm{b}\mathrm{a}\mathrm{d}}\rangle {{\Vert}}^{2}. \end{align} \tag{ 83 }$$

Next we give a lower bound of |||x_m,0⟩|| and an upper bound of |||x_bad⟩||. We define q = |||y(mh)⟩||, by lemma 10 and (k + 1)! ⩾ 50m(c + 1) (c + 2)g, we have

$$\begin{equation}{\Vert}\vert {x}_{i,0}\rangle -\vert y(ih)\rangle {\Vert}\leqslant 0.04q,\quad 0\leqslant l\leqslant m.\end{equation} \tag{ 84 }$$

By the definition of g, |||y(ih)⟩|| ⩽ gq for any i ∈ [m − 1]₀, then we have

$$\begin{equation}{\Vert}\vert {x}_{i,0}\rangle {\Vert}\leqslant (g+0.04)q\leqslant 1.04gq,\quad 0\leqslant i\leqslant m-1,\end{equation} \tag{ 85 }$$

and

$$\begin{equation}0.96q\leqslant {\Vert}\vert {x}_{m,0}\rangle {\Vert}\leqslant 1.04q.\end{equation} \tag{ 86 }$$

For any i ∈ [m]₀, |x_i,j ⟩ = (Ah/j)|x_i,j−1⟩, we have

$$\begin{equation}\vert {x}_{i,j}\rangle =\frac{{(Ah)}^{j-1}}{j!}\vert {x}_{i,1}\rangle ,\quad 2\leqslant j\leqslant k.\end{equation} \tag{ 87 }$$

We have ||Ah|| ⩽ 1, therefore,

$$\begin{equation}{\Vert}\vert {x}_{i,j}\rangle {\Vert}\leqslant \frac{{\Vert}\vert {x}_{i,1}\rangle {\Vert}}{j!},\quad 2\leqslant j\leqslant k.\end{equation} \tag{ 88 }$$

Next, based on $\vert {x}_{i+1,0}\rangle =\vert {x}_{i,0}\rangle +{\sum }_{j=1}^{k}\vert {x}_{i,j}\rangle$, we have

$$\begin{align} 2.08gq\geqslant \enspace & {\Vert}\vert {x}_{i+1,0}\rangle {\Vert}+{\Vert}\vert {x}_{i,0}\rangle {\Vert} \\ \geqslant \enspace & {\Vert}\vert {x}_{i+1,0}\rangle -\vert {x}_{i,0}\rangle {\Vert} \\ \geqslant \enspace & {\Vert}\vert {x}_{i,1}\rangle {\Vert}-\sum\limits _{j=2}^{k}{\Vert}\vert {x}_{i,j}\rangle {\Vert} \\ \geqslant \enspace & \left(1-\sum\limits _{j=2}^{k}\frac{1}{j!}\right){\Vert}\vert {x}_{i,1}\rangle {\Vert} \\ \geqslant \enspace & (3-e){\Vert}\vert {x}_{i,1}\rangle {\Vert}, \end{align} \tag{ 89 }$$

then

$$\begin{equation}{\Vert}\vert {x}_{i,1}\rangle {\Vert}\leqslant \frac{2.08gq}{3-e},\quad 0\leqslant i\leqslant m-1.\end{equation} \tag{ 90 }$$

and

$$\begin{equation}{\Vert}\vert {x}_{i,j}\rangle {\Vert}\leqslant \frac{2.08gq}{j!(3-e)},\quad 0\leqslant i\leqslant m-1,\enspace 1\leqslant j\leqslant k.\end{equation} \tag{ 91 }$$

|||x_bad⟩|| satisfies

$$\begin{align} {\Vert}\vert {x}_{\mathrm{b}\mathrm{a}\mathrm{d}}\rangle {{\Vert}}^{2}& =\sum\limits _{i=0}^{m-1}{\Vert}\vert {x}_{i,0}\rangle {{\Vert}}^{2}+\sum\limits _{i=0}^{m-1}\sum\limits _{j=1}^{k}{\Vert}\vert {x}_{i,j}\rangle {{\Vert}}^{2} \\ & \leqslant 1.0{4}^{2}m{g}^{2}{q}^{2}+m\sum\limits _{j=1}^{k}\frac{{(2.08gq)}^{2}}{{(j!)}^{2}{(3-e)}^{2}} \\ & \leqslant 70.9m{g}^{2}{q}^{2}. \end{align} \tag{ 92 }$$

The last step of equation (92) is derived from the inequality ${\sum }_{j=1}^{k}\frac{1}{{(j!)}^{2}}\leqslant {I}_{0}(2)-1< 1.28$, where I₀(2) < 2.28 a modified Bessel function of the first kind [9]. Combining equations (86) and (92), we have

$$\begin{align} \frac{{\Vert}\vert {x}_{m,0}\rangle {{\Vert}}^{2}}{{\Vert}\vert x\rangle {{\Vert}}^{2}}& \geqslant \frac{{(0.96q)}^{2}}{p{(0.96q)}^{2}+70.9m{g}^{2}{q}^{2}} \\ & \geqslant \frac{1}{p+77m{g}^{2}}. \end{align} \tag{ 93 }$$

Secondly, we analyze the success probability of the second probabilistic step. After the first measurement, the desired state is the state |y(T)⟩ defined in equation (19). Then we measure the first qubit register of |y(T)⟩, if the result is |0, 0⟩, we have a state -close to |u(T)/||u(T)||⟩ in the second qubit register of |y(T)⟩. The lower bound of the success probability in this measurement is analyzed in lemma 12.

Lemma 12. Let $T\in {\mathbb{R}}^{+}$, ${\eta }^{\prime }=K/{\Vert}\tilde{u}(T){\Vert}$. When $K< \sqrt{2}/2$, we have

$$\begin{equation}\frac{{\Vert}\vert {y}_{0}(T)\rangle {{\Vert}}^{2}}{{\Vert}\vert y(T)\rangle {{\Vert}}^{2}}\geqslant \frac{1-2{K}^{2}}{1-2{K}^{2}+2{({\eta }^{\prime })}^{2}}.\end{equation} \tag{ 94 }$$

Proof. We rearrange the components of $\overrightarrow{y}$,

$$\begin{equation}\overrightarrow{y}=[{\overrightarrow{y}}_{0}^{\prime },{\overrightarrow{y}}_{1}^{\prime },\dots ,{\overrightarrow{y}}_{c}^{\prime }],\end{equation} \tag{ 95 }$$

where ${\overrightarrow{y}}_{0}^{\prime }={\overrightarrow{y}}_{0}={\sum }_{j=0}^{c}{\nu }_{j}$, when i ⩾ 1, the component of ${\overrightarrow{y}}_{i}^{\prime }$ is represented as ${\nu }_{{a}_{i,0}^{\prime }}\otimes {\nu }_{{a}_{i,1}^{\prime }}\otimes \cdots \otimes {\nu }_{{a}_{i,k}^{\prime }}$, ${a}_{i,j}^{\prime }$ satisfies

$$\begin{equation}k\geqslant 1,\enspace {a}_{i,j}^{\prime }\geqslant 0,\quad \sum\limits _{j=0}^{k}({a}_{i,j}^{\prime }+1)=i+1.\end{equation} \tag{ 96 }$$

By equation (96), the number of elements in ${\overrightarrow{y}}_{i}^{\prime }$ is 2ⁱ − 1. By equations (74) and (96), for any $j\in {[{2}^{i}-1]}_{0}$, we have ${\Vert}{\overrightarrow{y}}_{i,j}^{\prime }{\Vert}\leqslant {K}^{i+1}$. Therefore,

$$\begin{equation}{\Vert}{\overrightarrow{y}}_{i}^{\prime }{{\Vert}}^{2}\leqslant ({2}^{i}-1){K}^{2(i+1)}< {(2{K}^{2})}^{i}.\end{equation} \tag{ 97 }$$

By equation (97) and ${\Vert}{\overrightarrow{y}}_{0}{\Vert}={\Vert}{\overrightarrow{y}}_{0}^{\prime }{\Vert}={\Vert}\tilde{u}(T){\Vert}=K/{\eta }^{\prime }$, we have

$$\begin{equation}\frac{{\Vert}\vert {y}_{0}\rangle {{\Vert}}^{2}}{{\Vert}\vert y\rangle {{\Vert}}^{2}}=\frac{{(K/{\eta }^{\prime })}^{2}}{{(K/{\eta }^{\prime })}^{2}+{\sum }_{i=1}^{c}{(2{K}^{2})}^{i}}\end{equation} \tag{ 98 }$$

$$\begin{equation}\geqslant \frac{{(K/{\eta }^{\prime })}^{2}}{{(K/{\eta }^{\prime })}^{2}+\frac{2{K}^{2}}{1-2{K}^{2}}}\end{equation} \tag{ 99 }$$

$$\begin{equation}=\frac{1-2{K}^{2}}{1-2{K}^{2}+2{({\eta }^{\prime })}^{2}}.\end{equation} \tag{ 100 }$$

In this section, we give the main result of our work.

Theorem 1. Given n-dimensional nonlinear dissipative ODEs $\frac{\mathrm{d}u}{\mathrm{d}t}={F}_{1}u+{F}_{2}{u}^{\otimes 2}$ defined in equation (1) and construct the linear ODEs $\frac{\mathrm{d}\overrightarrow{y}}{\mathrm{d}t}=A\overrightarrow{y}$ defined in equation (8). Let T > 0, g = max_t∈[0,T]|||y(t)⟩||/|||y(T)⟩||, η = ||u_in||/||u(T)||, $c=\lceil {\mathrm{log}}_{1/K}\frac{4{\Vert}{u}_{\text{in}}{\Vert}}{(1-K){\epsilon}\eta }\rceil$. When $K< \sqrt{2}/2$ and $\frac{(c+1){\Vert}{F}_{2}{\Vert}}{\vert \mathrm{R}\mathrm{e}({\lambda }_{1})\vert }\leqslant 1$, there exists a quantum algorithm to produce |u_out(T)⟩ which satisfies ||u_out(T) − u(T)/||u(T)|||| ⩽ with Ω(1) success probability. The query complexity of the algorithm for O_F1, O_F2, O_u is

$$\begin{equation}O\left(\frac{g\eta sT({\Vert}{F}_{1}{\Vert}+{\Vert}{F}_{2}{\Vert})}{\sqrt{1-2{K}^{2}}{\Vert}{u}_{\text{in}}{\Vert}}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\left(\mathrm{log}\left(\frac{g\eta sT{\Vert}{F}_{1}{\Vert}{\Vert}{F}_{2}{\Vert}}{{\epsilon}(1-2{K}^{2}){\Vert}{u}_{\text{in}}{\Vert}}\right)\right)\right).\end{equation} \tag{ 101 }$$

The gate complexity of this algorithm is larger than its query complexity by a factor of

$$\begin{equation}O\left(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\left(\mathrm{log}\left(\frac{ng\eta sT{\Vert}{F}_{1}{\Vert}{\Vert}{F}_{2}{\Vert}}{{\epsilon}(1-2{K}^{2}){\Vert}{u}_{\text{in}}{\Vert}}\right)\right)\right).\end{equation} \tag{ 102 }$$

Proof.  Whole process. First we show the whole process of our algorithm. We define η' = ηK/||u_in|| and set

$$\begin{equation}{\epsilon}\leqslant 0.1\sqrt{1-2{K}^{2}}/{\eta }^{\prime },\quad {{\epsilon}}_{1}=\frac{{\epsilon}K}{4{\eta }^{\prime }},\quad \delta ={\epsilon}\frac{\sqrt{1-2{K}^{2}}}{30\sqrt{78m}g{\eta }^{\prime }},\end{equation} \tag{ 103 }$$

and construct the N-dimensional linear ODEs defined in equation (8)

$$\begin{equation}\mathrm{d}\overrightarrow{y}/\mathrm{d}t=A\overrightarrow{y},\quad \overrightarrow{y}(0)={y}_{\text{in}}.\end{equation} \tag{ 104 }$$

We also set h = T/⌈T||A||⌉, m = p = T/h = ⌈T||A||⌉, $k=\lfloor \frac{2\enspace \mathrm{log}({\Omega})}{\mathrm{log}(\mathrm{log}({\Omega}))}\rfloor$, where Ω = 50m(c + 1) (c + 2)g/δ, so k satisfies (k + 1)! ⩾ Ω. Then we construct the linear system defined in equation (22) and solve the linear system with the algorithm proposed in [2]. The normalized solution of equation (22) is represented as

$$\begin{equation}\vert x\rangle =\sum\limits _{l=0}^{d}\vert l\rangle \vert {x}_{l}\rangle ,\end{equation} \tag{ 105 }$$

where d = m(k + 1) + p. |x⟩ can also be represented as

$$\begin{equation}\vert \bar{x}\rangle =\sum\limits _{l=0}^{d}{\alpha }_{l}\vert l\rangle \vert {\bar{x}}_{l}\rangle ,\end{equation} \tag{ 106 }$$

where $\vert {\bar{x}}_{l}\rangle$ is a normalized state. Assuming the output state of quantum linear system algorithm [2] is

$$\begin{equation}\vert {\bar{x}}^{\prime }\rangle =\sum\limits _{l=0}^{d}{\alpha }_{l}^{\prime }\vert l\rangle \vert {\bar{x}}_{l}^{\prime }\rangle .\end{equation} \tag{ 107 }$$

By theorem 5 in [2], we make $\vert {\bar{x}}^{\prime }\rangle$ satisfies

$$\begin{equation}{\Vert}\vert \bar{x}\rangle -\vert {\bar{x}}^{\prime }\rangle {\Vert}\leqslant \delta .\end{equation} \tag{ 108 }$$

Then we execute measurement step discussed in section 3.4 and get a state -close to |u(T)/||u(T)||⟩ with success probability O((1 − 2K²)/(gη')²). We can amplify the success probability to Ω(1) with quantum amplitude amplification algorithm [38] by running quantum linear system algorithm $O(g{\eta }^{\prime }/\sqrt{1-2{K}^{2}})$ times.

Proof of correctness. Then we analyze the error bound and the impact of error on success probability.

Assuming u(T) represents the exact solution. We define $\vert \tilde{u}(T)\rangle$ as

$$\begin{equation}\vert \tilde{u}(T)\rangle =\vert \sum\limits _{i=0}^{c}{\nu }_{i}(T)\rangle =\vert {y}_{0,0}(T)\rangle .\end{equation} \tag{ 109 }$$

By lemma 9 and our choice of parameter c, we have

$$\begin{equation}{\Vert}\vert u(T)\rangle -\vert \tilde{u}(T)\rangle {\Vert}\leqslant {{\epsilon}}_{1}.\end{equation} \tag{ 110 }$$

Then by lemma 16 and |||u(T)⟩|| = K/η', we have

$$\begin{equation}{\Vert}\vert \bar{u}(T)\rangle -\vert {\bar{\overrightarrow{y}}}_{0,0}(T)\rangle {\Vert}\leqslant \frac{2{\eta }^{\prime }{{\epsilon}}_{1}}{K}={\epsilon}/2.\end{equation} \tag{ 111 }$$

Let S := {m(k + 1), m(k + 1) + 1, ..., m(k + 1) + p}. By lemma 10 and our choice of parameter k, for any l ∈ S, we have

$$\begin{equation}{\Vert}\vert {x}_{l}\rangle -\vert y(T)\rangle {\Vert}\leqslant \delta {\Vert}\vert y(T)\rangle {\Vert}.\end{equation} \tag{ 112 }$$

By equation (112) and lemma 16, we have

$$\begin{equation}{\Vert}\vert {\bar{x}}_{l}\rangle -\vert \bar{y}(T)\rangle {\Vert}\leqslant 2\delta .\end{equation} \tag{ 113 }$$

By lemma 11, for any l ∈ S, we have

$$\begin{equation}{\alpha }_{l}=\frac{{\Vert}\vert {x}_{l}\rangle {\Vert}}{{\Vert}\vert x\rangle {\Vert}}\geqslant \frac{1}{\sqrt{78m}g}\geqslant \delta .\end{equation} \tag{ 114 }$$

By equations (108) and (114) and lemma 17, we have

$$\begin{equation}{\Vert}\vert {\bar{x}}_{l}\rangle -\vert {\bar{x}}_{l}^{\prime }\rangle {\Vert}\leqslant \frac{2\delta }{{\alpha }_{l}-\delta }.\end{equation} \tag{ 115 }$$

Then, combine equations (113) and (115), we have

$$\begin{align} {\Vert}\vert {\bar{x}}_{l}^{\prime }\rangle -\vert \bar{y}(T)\rangle {\Vert}& \leqslant {\Vert}\vert {\bar{x}}_{l}^{\prime }\rangle -\vert {\bar{x}}_{l}\rangle {\Vert}+{\Vert}\vert {\bar{x}}_{l}\rangle -\vert \bar{y}(T)\rangle {\Vert} \\ & \leqslant 2\delta \left(1+\frac{1}{{\alpha }_{l}-\delta }\right). \end{align} \tag{ 116 }$$

We default α_l is small enough, such as α_l < 0.5, then by equation (114) and $\delta ={\epsilon}\frac{\sqrt{1-2{K}^{2}}}{30\sqrt{78m}g{\eta }^{\prime }}$, we have

$$\begin{equation}2\delta \left(1+\frac{1}{{\alpha }_{l}-\delta }\right)\leqslant 2\delta \frac{\sqrt{3}}{{\alpha }_{l}}\leqslant \frac{{\epsilon}\sqrt{1-2{K}^{2}}}{5\sqrt{3}{\eta }^{\prime }}.\end{equation} \tag{ 117 }$$

|y(T)⟩ and $\vert {\bar{x}}_{l}^{\prime }\rangle$ are also written as

$$\begin{equation}\vert \bar{y}(T)\rangle =\sum\limits _{w=0}^{c}{\chi }_{w}\vert {\bar{y}}_{w}(T)\rangle \end{equation} \tag{ 118 }$$

and

$$\begin{equation}\vert {\bar{x}}_{l}^{\prime }\rangle =\sum\limits _{w=0}^{c}{\chi }_{w}^{\prime }\vert {\bar{x}}_{l,w}^{\prime }\rangle .\end{equation} \tag{ 119 }$$

By lemma 12, we have

$$\begin{equation}{\chi }_{0}=\frac{{\Vert}\vert {y}_{0}(T)\rangle {\Vert}}{{\Vert}\vert y(T)\rangle {\Vert}}\geqslant \sqrt{\frac{1-2{K}^{2}}{(1-2{K}^{2})+2{({\eta }^{\prime })}^{2}}}\geqslant \frac{\sqrt{1-2{K}^{2}}}{\sqrt{3}{\eta }^{\prime }}.\end{equation} \tag{ 120 }$$

By equations (116), (117), (120) and lemma 17, we have

$$\begin{equation}{\Vert}\vert {\bar{x}}_{l,0}^{\prime }\rangle -\vert {\bar{y}}_{0,0}(T)\rangle {\Vert}\leqslant \frac{2({\Vert}\vert {\bar{x}}_{l}^{\prime }\rangle -\vert \bar{y}(T)\rangle {\Vert})}{{\chi }_{0}-({\Vert}\vert {\bar{x}}_{l}^{\prime }\rangle -\vert \bar{y}(T)\rangle {\Vert})}\leqslant \frac{2{\epsilon}}{5-{\epsilon}}\leqslant {\epsilon}/2.\end{equation} \tag{ 121 }$$

We notice $\vert {\bar{x}}_{l,0}^{\prime }\rangle$ is the output state of our algorithm, we have $\vert {u}_{\mathrm{o}\mathrm{u}\mathrm{t}}(T)\rangle =\vert {\bar{x}}_{l,0}^{\prime }\rangle$. Combining equations (111) and (121), we have

$$\begin{equation}{\Vert}\vert \bar{u}(T)\rangle -\vert {u}_{\text{out}}(T)\rangle {\Vert}\leqslant {\Vert}\vert \bar{u}(T)\rangle -\vert {\bar{y}}_{0,0}(T)\rangle {\Vert}+{\Vert}\vert {\bar{x}}_{l,0}^{\prime }\rangle -\vert {\bar{y}}_{0,0}(T)\rangle {\Vert}\leqslant {\epsilon}.\end{equation} \tag{ 122 }$$

On the other hand, caused by solution error, the success probability also changes. By lemma 18, equation (120) and ${\epsilon}\leqslant 0.1\sqrt{1-2{K}^{2}}/{\eta }^{\prime }$, we have

$$\begin{equation}{\chi }_{0}^{\prime }\geqslant {\chi }_{0}-\frac{1}{\sqrt{3}{\eta }^{\prime }}\sqrt{1-2{K}^{2}}\times \frac{1}{5}{\epsilon}\geqslant {\chi }_{0}-{\epsilon}/2\geqslant \frac{\sqrt{1-2{K}^{2}}}{2{\eta }^{\prime }}\end{equation} \tag{ 123 }$$

and

$$\begin{equation}{\alpha }_{l}^{\prime }\geqslant {\alpha }_{l}-\delta \geqslant \left(\frac{1}{\sqrt{78}}-\frac{1}{30\sqrt{78}}\right)\frac{1}{\sqrt{m}g}\geqslant \frac{1}{10\sqrt{m}g},\end{equation} \tag{ 124 }$$

then

$$\begin{equation}\sum\limits _{l\in S}\vert {\alpha }_{l}^{\prime }{\vert }^{2}\geqslant \frac{p}{100m{g}^{2}}=\frac{1}{100{g}^{2}}.\end{equation} \tag{ 125 }$$

Therefore, the success probability of our algorithm is

$$\begin{equation}p={({\chi }_{0}^{\prime })}^{2}\times \left(\sum\limits _{l\in S}\vert {\alpha }_{l}^{\prime }{\vert }^{2}\right)\geqslant \frac{1-2{K}^{2}}{400{(g{\eta }^{\prime })}^{2}}.\end{equation} \tag{ 126 }$$

Complexity analysis. Finally, we analyze the complexity of our algorithm.

By lemmas 2 and 3, the sparsity of A is c² s and ||A|| ⩽ (c + 1) (||F₁|| + ||F₂||). The sparsity s_C of C_m,k,p (Ah) satisfies

$$\begin{equation}{s}_{\text{C}}< k+{c}^{2}s.\end{equation} \tag{ 127 }$$

By lemma 8, the condition number κ_C of C_m,k,p (Ah) satisfies

$$\begin{equation}{\kappa }_{\text{C}}\leqslant 2e\sqrt{k}((m(k+1)+p))(c+2).\end{equation} \tag{ 128 }$$

By theorem 5 in [2] and equation (108), the query complexity of quantum linear system algorithm to oracle of C_m,k,p (Ah) and |0⟩|y_in⟩ is

$$\begin{equation}O({s}_{\text{C}}{\kappa }_{\text{C}}\enspace \mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\mathrm{log}({s}_{\text{C}}{\kappa }_{\text{C}}/\delta ))).\end{equation} \tag{ 129 }$$

By the definition of C_m,k,p (Ah), the oracle of C_m,k,p (Ah) can be constructed by querying oracle O_A once, by lemma 6, O_A is constructed by querying O_F1 O(c) times and O_F2 O(1) times. By lemma 1, |0⟩|y_in⟩ can be prepared by querying O_u O(c) times.

Substituting equations (127)–(129) and considering the choice of all parameters, the query complexity of solving equation (22) for O_F1, O_F2 and O_u is

$$\begin{equation}O\left(sT({\Vert}{F}_{1}{\Vert}+{\Vert}{F}_{2}{\Vert})\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\left(\mathrm{log}\left(\frac{g\eta sT{\Vert}{F}_{1}{\Vert}{\Vert}{F}_{2}{\Vert}}{{\epsilon}(1-2{K}^{2}){\Vert}{u}_{\text{in}}{\Vert}}\right)\right)\right).\end{equation} \tag{ 130 }$$

Using amplitude amplification algorithm [38], we repeat the above process $O(1/\sqrt{p})$ times and get $\vert {u}_{\mathrm{o}\mathrm{u}\mathrm{t}}(T)\rangle =\vert {\bar{x}}_{l,0}^{\prime }(T)\rangle$ which satisfies |||u_out(T)⟩ − u(T)/||u(T)|||| ⩽ with Ω(1) success probability.

The query complexity of the whole process for O_F1, O_F2 and O_u is

$$\begin{equation}O\left(\frac{g\eta sT({\Vert}{F}_{1}{\Vert}+{\Vert}{F}_{2}{\Vert})}{\sqrt{1-2{K}^{2}}{\Vert}{u}_{in}{\Vert}}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\left(\mathrm{log}\left(\frac{g\eta sT{\Vert}{F}_{1}{\Vert}{\Vert}{F}_{2}{\Vert}}{{\epsilon}(1-2{K}^{2}){\Vert}{u}_{in}{\Vert}}\right)\right)\right).\end{equation} \tag{ 131 }$$

The gate complexity of this algorithm is larger than its query complexity by a factor of

$$\begin{equation}O\left(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\left(\mathrm{log}\left(\frac{ng\eta sT{\Vert}{F}_{1}{\Vert}{\Vert}{F}_{2}{\Vert}}{{\epsilon}(1-2{K}^{2}){\Vert}{u}_{\text{in}}{\Vert}}\right)\right)\right).\end{equation} \tag{ 132 }$$

In this paper, we presented a quantum homotopy perturbation method for solving nonlinear dissipative ODEs. The gate complexity of our algorithm is O(gηT poly(log(nT/))). The complexity of the optimal classical algorithm for solving equation (1) is at least linear with n, the complexity of the algorithm proposed in [20] is linear with 1/, so our algorithm provides exponential improvement over the best classical algorithms or previous quantum algorithms in n or . η and g also affect the complexity of our algorithm, η measures the decay of u(T) and increases exponentially as T increases, g measures the decay of $\overrightarrow{y}(T)$ defined in equation (8) and also increases exponentially as T increases. Our algorithm is effective when T is relatively small which makes η and g small enough. η and g are also affected by F₂, when T is relatively small, the trend of η and g increasing exponentially with T may not be obvious due to the influence of F₂, this case makes our algorithm perform better. Our algorithm has the potential to accelerate the solution of various nonlinear equations, and can be applied to nonlinear problems in various fields, such as fluid dynamics, biology, finance, etc, thereby accelerating the research progress of nonlinear science.

Our algorithm only discusses time-independent homogeneous quadratic nonlinear ODEs. When solving time-dependent nonlinear ODEs, the algorithm proposed in [9] is not suitable, an alternative way is to use the algorithm proposed in [8] to solve the linear ODEs, then the dependence of complexity on error becomes O(poly(1/)). Is it possible to optimize the complexity of time-dependent quadratic nonlinear ODEs to O(poly(log(1/))) is an open question.

On the other hand, homotopy analysis method [39] and its derivatives [40–42] are similar to homotopy perturbation method. Whether we can use quantum computing to accelerate the execution process of homotopy analysis method and thus construct a quantum homotopy analysis method is also a question to be investigated further.

Furthermore, how to induce nonlinearity in quantum computing is a basic problem when solving nonlinear equations with quantum algorithm. A common method is producing multiple copies of the original system, some nonlinear quantum algorithms contain copy process [17, 19, 21]. In [43], a linearization technique of nonlinear classical dynamics based on Koopman–von Neumann method is proposed. [44] summarizes three classical linear embedding techniques, including Carleman embedding(Carleman linearization is also called Carleman embedding) [26, 27], coherent states embedding [27, 45] and position-space embedding [46], and then puts forward the prospects of these linear embedding techniques to construct effective quantum algorithms. An open question is whether there are other ways to induce nonlinearity in quantum computing.

This work was supported by the National Key Research and Development Program of China (Grant No. 2016YFA0301700), the National Natural Science Foundation of China (Grants No. 11 625 419), the Strategic Priority Research Program of the Chinese Academy of Sciences (Grant No. XDB24030600), and the Anhui Initiative in Quantum Information Technologies (Grants No. AHY080000).

No new data were created or analyzed in this study.

In this appendix, we give some lemmas used in proving some conclusions of our work. Lemmas 16–18 are given in [9], we just list them again.

Lemma 13. Let γ ⩾ 1, m ∈ N⁺, when t ⩾ 0, we have

$$\begin{equation}\sum\limits _{j=0}^{m-1}\frac{{t}^{j}}{j!}{\text{e}}^{-\gamma t}\leqslant m.\end{equation} \tag{ 133 }$$

Proof. We consider two cases: (1) 0 < t ⩽ m − 1; (2) t ⩾ m.

When 0 < t ⩽ m − 1, we can find i ∈ [m − 1]₀ which satisfies t ∈ (i, i + 1], then we have

$$\begin{equation}\sum\limits _{j=0}^{m-1}\frac{{t}^{j}}{j!}{\text{e}}^{-\gamma t}< m\frac{{t}^{i}}{i!}{\text{e}}^{-\gamma t}.\end{equation} \tag{ 134 }$$

We define

$$\begin{equation}g(t)=m\frac{{t}^{i}}{i!}{\text{e}}^{-\gamma t},\quad 0< t\leqslant m-1.\end{equation} \tag{ 135 }$$

It is obvious that $g(t)\leqslant g(\frac{i}{\gamma })$ for 0 < t ⩽ m − 1. Using Stirling's formula $i!\approx \sqrt{2\pi i}{(\frac{i}{e})}^{i}$, we have

$$\begin{equation}g(t)\leqslant m\frac{{\left(\frac{i}{\gamma }\right)}^{i}}{\sqrt{2\pi i}{\left(\frac{i}{e}\right)}^{i}}{\text{e}}^{-\text{i}}\leqslant m{\left(\frac{1}{\gamma }\right)}^{i}\leqslant m.\end{equation} \tag{ 136 }$$

Therefore,

$$\begin{equation}\sum\limits _{j=0}^{m-1}\frac{{t}^{j}}{j!}{\text{e}}^{-\gamma t}\leqslant m.\end{equation} \tag{ 137 }$$

When t ⩾ m, we have

$$\begin{equation}\sum\limits _{j=0}^{m-1}\frac{{t}^{j}}{j!}{\text{e}}^{-\gamma t}< m\frac{{t}^{m-1}}{(m-1)!}{\text{e}}^{-\gamma t}.\end{equation} \tag{ 138 }$$

Similar with the case 0 < t ⩽ m − 1, we also have

$$\begin{equation}m\frac{{t}^{m-1}}{(m-1)!}{\text{e}}^{-\gamma t}\leqslant m\frac{{\left(\frac{m-1}{\gamma }\right)}^{m-1}}{\sqrt{2\pi (m-1)}{\left(\frac{m-1}{e}\right)}^{m-1}}{\text{e}}^{-(m-1)}\leqslant m{\left(\frac{1}{\gamma }\right)}^{m-1}\leqslant m.\end{equation} \tag{ 139 }$$

Therefore, for any t ⩾ 0, we have ${\sum }_{j=0}^{m-1}\frac{{t}^{j}}{j!}{\text{e}}^{-\gamma t}\leqslant m$.

Lemma 14. Let $\gamma ,\beta \in {\mathbb{R}}^{+}$, m ∈ N⁺, when t ⩾ 0 and γ/β ⩾ 1, we have

$$\begin{equation}\sum\limits _{j=0}^{m-1}\frac{{(\beta t)}^{j}}{j!}{\text{e}}^{-\gamma t}\leqslant m.\end{equation} \tag{ 140 }$$

Proof. We define t' = βt, γ' = γ/β, then equation (140) is written as

$$\begin{equation}\sum\limits _{j=0}^{m-1}\frac{{({t}^{\prime })}^{j}}{j!}{\text{e}}^{-{\gamma }^{\prime }{t}^{\prime }}\leqslant m.\end{equation} \tag{ 141 }$$

By lemma 13, we directly obtain equation (141).

Lemma 15. Given a matrix M satisfies ||M|| ⩽ 1 and ||e^Mt || ⩽ Δ for any t ⩾ 0. Let k, m ∈ N⁺ and satisfy $\frac{2}{(k+1)!}m{\Delta}({\Delta}+1)\leqslant 1$, ${T}_{k}(M)={\sum }_{l=0}^{k}\frac{{(Ah)}^{l}}{l!}$. Then for any l ∈ [m]₀, we have

$$\begin{equation}{\Vert}{\text{e}}^{Ml}-{T}_{k}^{l}(M){\Vert}\leqslant \frac{2l{\Delta}({\Delta}+1)}{(k+1)!}.\end{equation} \tag{ 142 }$$

Proof. When l = 0, ${\Vert}{\text{e}}^{Ml}-{T}_{k}^{l}(M){\Vert}=0$. When l = 1,

$$\begin{equation}{\Vert}{\text{e}}^{M}-{T}_{k}(M){\Vert}={\Vert}\sum\limits _{j=k+1}^{\infty }\frac{{M}^{j}}{j!}{\Vert}\leqslant \sum\limits _{j=k+1}^{\infty }\frac{{\Vert}M{{\Vert}}^{j}}{j!}\leqslant \sum\limits _{j=k+1}^{\infty }\frac{1}{j!}\leqslant \frac{2}{(k+1)!}\leqslant \frac{2}{(k+1)!}{\Delta}({\Delta}+1).\end{equation} \tag{ 143 }$$

Assuming when l ⩽ l', we have

$$\begin{equation}{\Vert}{\text{e}}^{Ml}-{T}_{k}^{l}(M){\Vert}\leqslant \frac{2}{(k+1)!}l{\Delta}({\Delta}+1),\end{equation} \tag{ 144 }$$

then by ||e^Ml || ⩽ Δ, we have

$$\begin{equation}{\Vert}{T}_{k}^{l}(M){\Vert}\leqslant {\Delta}+\frac{2}{(k+1)!}l{\Delta}({\Delta}+1)\leqslant {\Delta}+1.\end{equation} \tag{ 145 }$$

When l = l' + 1,

$$\begin{align} {\Vert}{\text{e}}^{M({l}^{\prime }+1)}-{T}_{k}^{{l}^{\prime }+1}(M){\Vert}=\enspace & {\Vert}({\text{e}}^{M}-{T}_{k}(M))\left(\sum\limits _{j=0}^{{l}^{\prime }}{\text{e}}^{Mj}{T}_{k}^{l-j}(M)\right){\Vert} \\ \leqslant \enspace & \frac{2{\Delta}}{(k+1)!}\times \left(\sum\limits _{j=0}^{{l}^{\prime }}{\Vert}{T}_{k}^{l-j}(M){\Vert}\right) \\ \leqslant \enspace & \frac{2}{(k+1)!}({l}^{\prime }+1){\Delta}({\Delta}+1). \end{align} \tag{ 146 }$$

Therefore, for any l ∈ [m]₀, we have ${\Vert}{\text{e}}^{Ml}-{T}_{k}^{l}(M){\Vert}\leqslant \frac{2}{(k+1)!}l{\Delta}({\Delta}+1)$.

Lemma 16 ([9]). Let |ψ⟩ and |φ⟩ be two vectors such that |||ψ⟩|| ⩾ α > 0 and |||ψ⟩ − |φ⟩|| ⩽ β. Then

$$\begin{equation}{\Vert}\frac{\vert \psi \rangle }{{\Vert}\vert \psi \rangle {\Vert}}-\frac{\vert \varphi \rangle }{{\Vert}\vert \varphi \rangle {\Vert}}{\Vert}\leqslant \frac{2\beta }{\alpha }.\end{equation} \tag{ 147 }$$

Lemma 17 ([9]). Let $\vert \psi \rangle =\alpha \vert 0\rangle \vert {\psi }_{0}\rangle +\sqrt{1-{\alpha }^{2}}\vert 1\rangle \vert {\psi }_{1}\rangle$ and $\vert \varphi \rangle =\beta \vert 0\rangle \vert {\varphi }_{0}\rangle +\sqrt{1-{\beta }^{2}}\vert 1\rangle \vert {\varphi }_{1}\rangle$, where |ψ₀⟩, ψ₁⟩, |φ₀⟩, |φ₁⟩ are unit vectors, and α, β ∈ [0, 1]. Suppose |||ψ⟩ − |φ⟩|| ⩽ δ < α. Then ${\Vert}\vert {\psi }_{0}\rangle -\vert {\varphi }_{0}\rangle {\Vert}\leqslant \frac{2\delta }{\alpha -\delta }$.

Lemma 18 ([9]). Let $\vert \psi \rangle =\alpha \vert 0\rangle \vert {\psi }_{0}\rangle +\sqrt{1-{\alpha }^{2}}\vert 1\rangle \vert {\psi }_{1}\rangle$ and $\vert \varphi \rangle =\beta \vert 0\rangle \vert {\varphi }_{0}\rangle +\sqrt{1-{\beta }^{2}}\vert 1\rangle \vert {\varphi }_{1}\rangle$, where |ψ₀⟩, ψ₁⟩, |φ₀⟩, |φ₁⟩ are unit vectors, and α, β ∈ [0, 1]. Suppose |||ψ⟩ − |φ⟩|| ⩽ δ < α. Then β ⩾ α − δ.