Forward (explicit) Euler

What it fills

• Choose a time discretization or propagator approximation

  Reduce continuous evolution over $[0,T]$ to a finite algebraic object — a banded linear system, a product of step propagators, or a spectral coefficient system — with a stated truncation error. When a linear system is formed, a conditioning bound is stated with it.

When it applies

Explicit, and therefore conditionally stable: a stiff generator forces a small step $h$ and hence many steps, inflating the dimension of the assembled system. First-order local accuracy is what leaves the surrounding algorithm with $1/\varepsilon$ rather than $\log(1/\varepsilon)$ precision dependence, because the number of steps needed to reach accuracy $\varepsilon$ is fixed by the order of the local truncation error. Liu et al. bound the condition number of the resulting Carleman plus forward-Euler system; the constant is in the paper and is not quoted here.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

Nothing in Liu, Kolden, Krovi, Loureiro, Trivisa and Childs (arXiv:2011.03185) assembles the banded all-at-once system of Eq. (3.8) or hands it to a solver, and no quantum linear system algorithm is executed anywhere in it. Its one piece of numerical work is Figure 1 of Section 6, which the paper itself names "Integration of the forced viscous Burgers equation using Carleman linearization on a classical computer".

given  A, b, u_0, step size h, horizon T,  m = T/h steps

# explicit: each step's recurrence is evaluated, never solved
#     u_{k+1} = (I + hA) u_k + h b_k

assemble the banded all-at-once system over all m steps:
    row 0    :  u_0                        = u_0        # the initial condition
    row k+1  :  u_{k+1} - (I + hA) u_k     = h b_k      # one row per step

# conditionally stable: a stiff generator forces a small h and hence many
# steps, and m is the dimension the assembled system inherits

hand the assembled system to the layer below

Cost, as the source states it

No standalone cost is stated for the Euler step itself — Liu et al.'s accounting is end-to-end for the Carleman route, and is quoted on that route's card. The discretization enters their bill as the $m = T/h$ time steps of the assembled system and the condition-number upper bound they prove for it, whose constant this record deliberately leaves untranscribed (see conditions).

Implementations

• Banded all-at-once Euler system for the Carleman route

  • Efficient quantum algorithm for dissipative nonlinear differential equations

  The encoding the paper's algorithm actually solves, and the one this record describes. The problem it starts from is Problem 1: an $n$-dimensional quadratic ODE $du/dt = F_2 u^{\otimes 2} + F_1 u + F_0(t)$ with $F_2$, $F_1$, $F_0$ $s$-sparse, $F_1$ diagonalizable with $\mathrm{Re}(\lambda_n) \le \cdots \le \mathrm{Re}(\lambda_1) < 0$, and the goal of producing a quantum state proportional to $u(T)$ within a prescribed $\varepsilon$. Carleman linearization truncated at level $N$ turns that into the linear ODE (3.1) of dimension $\Delta = n + n^2 + \cdots + n^N = O(n^N)$, and this entry is how that linear ODE becomes one linear system rather than a march.

  The interval $[0,T]$ is divided into $m = T/h$ time steps and the forward Euler method is applied to the Carleman system, $y^{k+1} = [I + A(kh)h]y^k + b(kh)$ with $y^0 = y_{in} = \hat{y}(0)$, and all $y^k$ are then held equal for $k$ beyond $m$ for a sufficiently large integer $p$ of padding steps. That gives the $(m+p+1)\Delta \times (m+p+1)\Delta$ system $L|Y\rangle = |B\rangle$ with $L = \sum_{k=0}^{m+p}|k\rangle\langle k| \otimes I - \sum_{k=1}^{m}|k\rangle\langle k-1| \otimes [I + A((k-1)h)h] - \sum_{k=m+1}^{m+p}|k\rangle\langle k-1| \otimes I$, which the paper notes is lower triangular, and $|B\rangle$ assembled from $\lVert y_{in} \rVert |0\rangle \otimes |y_{in}\rangle$ and the terms $\lVert b((k-1)h) \rVert |k\rangle \otimes |b((k-1)h)\rangle$ with a normalizing factor $B_m$. The step is not free: (4.46) fixes $h \le \min\{1/(N\lVert F_1 \rVert),\, 2(|\mathrm{Re}(\lambda_1)| - \lVert F_2 \rVert - \lVert F_0 \rVert)/(N(|\mathrm{Re}(\lambda_1)|^2 - (\lVert F_2 \rVert + \lVert F_0 \rVert)^2 + \lVert F_1 \rVert^2))\}$, or $h \le 1/(N\lVert F_1 \rVert)$ when the eigenvalues of $F_1$ are all real, and the discussion says the point of that choice is to ensure $\lVert I + Ah \rVert \le 1$. Under it Lemma 3 bounds the global Euler error by $\lVert \hat{y}(T) - y^m \rVert \le 3N^{2.5}Th[(\lVert F_2 \rVert + \lVert F_1 \rVert + \lVert F_0 \rVert)^2 + \lVert F_0' \rVert]$, linear in $T$ rather than the $e^{LT}$ a general Lipschitz argument would give.

  No dataset. The inputs are the ones Problem 1 assumes: the values $\mathrm{Re}(\lambda_1)$, $\lVert F_2 \rVert$, $\lVert F_1 \rVert$, $\lVert F_0(t) \rVert$, $\lVert F_0 \rVert$, $\lVert F_0' \rVert$ and $\lVert u_{in} \rVert$ taken as known, the sparse-access oracles $O_{F_2}$, $O_{F_1}$, $O_{F_0}$ giving locations and values of nonzero entries for any specified row, column and time, and the oracle $O_x$ mapping $|00\ldots 0\rangle$ to a state proportional to $u_{in}$. Lemma 5 charges the preparation of $|B\rangle$ at $O(N)$ queries to $O_x$ and $O(m)$ queries to $O_{F_0}$.

  None: the paper states no execution of this construction. What it establishes for it is proved rather than measured, namely the global Euler error bound of Lemma 3, an upper bound on the condition number of $L$ whose constant this record deliberately leaves untranscribed, a lower bound on the success probability of the final measurement over the padding outcomes, and the end-to-end complexity quoted on the Carleman route's card. The paper's only computation is the classical Burgers experiment, which is the other entry here and does not assemble this system.

• Classical forward-Euler marching of the truncated Carleman system for Burgers

  • Efficient quantum algorithm for dissipative nonlinear differential equations

  The computation behind Figure 1, and the only one in the paper. Its question is not about the discretization at all: the formal analysis needs $R < 1$, and the discretized Burgers instance has $R = 43.59$, so the experiment asks whether the classical Carleman method converges anyway on a PDE that violates the hypothesis. The paper's own words for it are "we find in one numerical experiment that our proposed approach remains valid for larger $R$".

  The forced viscous Burgers equation (6.9) is semi-discretized by central differences on $n_x = 16$ points, $\partial_t u_i = \nu(u_{i+1} - 2u_i + u_{i-1})/\Delta x^2 - (u_{i+1}^2 - u_{i-1}^2)/(4\Delta x) + f_i$ with $\Delta x = L_0/(n_x - 1)$, which is of the quadratic form (2.1) and so generates the Carleman system (3.2). That linear system is then integrated with the forward Euler method over $n_t = 4000$ temporal intervals, at Carleman truncation levels up to $N = 4$. A second arm integrates the same semi-discrete equation (6.10) directly with the forward Euler method, without Carleman linearization, and serves as the comparison. Both arms run on a classical computer, and the all-at-once system $L|Y\rangle = |B\rangle$ is never formed: this is step-by-step marching, not the encoding of the other entry.

  Nothing from outside the paper. The initial condition is the closed form $u(x,0) = U_0\sin(2\pi x/L_0)$ on $x \in [-L_0/2, L_0/2]$ with Dirichlet conditions $u(-L_0/2,0) = u(L_0/2,0) = 0$, and the forcing is the closed form $f(x,t) = U_0\exp(-(x - L_0/4)^2/(2(L_0/32)^2))\cos(2\pi t)$, a localized off-centre Gaussian with sinusoidal time dependence. The paper's footnote records that this forcing "does not satisfy the general conditions for efficient implementation of our algorithm since it is not sparse". The viscosity is set only through $\mathrm{Re} = U_0L_0/\nu = 20$; $U_0$ and $L_0$ are never given numerically, and the derived convergence parameter is $R = 43.59$.

  The figure caption names the artefact: "source code available at https://github.com/hermankolden/CarlemanBurgers".

  Reported graphically. The top panel shows the initial condition and the solution at a third of the nonlinear time, $T_{nl}/3 = L_0/(3U_0)$; the bottom panels show the $l2$ norm of the absolute error between the Carleman solutions at truncation levels $N$ and the direct forward-Euler integration, and the convergence of the corresponding time-maximum error. The finding is that the time-maximum error decreases exponentially as $N$ is incremented, up to $N = 4$, even though $R \approx 44$ violates the $R < 1$ the algorithm's analysis requires, which the paper calls surprising and reads as evidence that "some property of equation (6.9) makes it more amenable to Carleman linearization than our current analysis predicts". It is a classical computation throughout: no quantum device, no simulator and no quantum linear system algorithm is involved, and no error is reported for the Euler discretization itself, which is identical in both compared arms.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Backward (implicit) Euler

  First-order implicit stepping: each step solves $(I - hA)u_{k+1} = u_k + h b_{k+1}$. $A$-stability is the classical reason to prefer it for stiff generators, since it removes the explicit method's step-size restriction.

• Trapezoidal rule (Crank-Nicolson)

  Second-order implicit stepping that averages the generator at the two ends of each step, and is $A$-stable. As a rational approximation of $e^{hA}$ it is the $(1,1)$ diagonal Padé approximant.

• Truncated Taylor series of the propagator

  Rather than approximating the derivative, approximate the propagator $e^{hA}$ itself by $k$ Taylor terms and encode those terms as extra rows of a sparse linear system. Truncation error falls factorially in $k$, so accuracy is bought by adding rows rather than by shrinking $h$ and lengthening the system.

• Truncated Dyson series of the propagator

  Truncate the Dyson series — the expansion that stands in for the propagator once the generator varies with time — and encode its terms as rows of a system of linear equations. This is what extends the all-at-once approach to genuinely time-dependent generators; solving the system those rows make up is the layer below.

• Chebyshev pseudospectral collocation

  A **global** discretization, and the only one on this slot. Write each component of the solution as a truncated Chebyshev series $x_i(t) = \sum_{k=0}^{n} c_{i,k}T_k(t)$ with the coefficients undetermined, then fix them by demanding that the differential equation hold exactly at the $n+1$ Chebyshev-Gauss-Lobatto nodes $t_l = \cos(l\pi/n)$. What comes out is one linear system in the coefficients. Childs and Liu put the difference from every stepping scheme plainly: "instead of locally approximating the ODE at discretized times, these linear equations use the behavior of the differential equations at the $n+1$ times $\{t_l\}$ to capture their behavior over the entire interval $[-1,1]$".

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• Efficient quantum algorithm for dissipative nonlinear differential equations↗Jin-Peng Liu, Herman Øie Kolden, Hari K. Krovi, Nuno F. Loureiro, Konstantina Trivisa, Andrew M. Childs · 2020theory yes · simulation yes · hardware no