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.

The generator $A(t)$, the interval $[0,T]$, an error tolerance $\varepsilon$, and a target algebraic form.

1. Linear ODE system → Linear system Ax = bstep explicitly, one row per step

   The steps are $u_{k+1} = (I + hA)u_k + h b_k$, assembled into a banded all-at-once linear system. approximation: First-order local accuracy, which is what leaves the surrounding algorithm with $1/\varepsilon$ rather than $\log(1/\varepsilon)$ precision dependence. assumption: Explicit, and therefore conditionally stable — a stiff generator forces a small step $h$ and hence many steps, inflating the dimension of the assembled system.

   approximationassumption

The discrete object, its truncation-error bound, and its conditioning bound.

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

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).

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

  • 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 · 2020

  About

  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.

  Methods

  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.

  Data

  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}$.

  Code

  None found yet.

  Results

  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

    Jin-Peng Liu, Herman Øie Kolden, Hari K. Krovi, Nuno F. Loureiro, Konstantina Trivisa, Andrew M. Childs · 2020

  About

  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$".

  Methods

  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.

  Data

  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$.

  Code

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

  Results

  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.