Backward (implicit) 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

On a quantum computer the trade differs from the classical one: each implicit step is itself a linear solve, so implicit stepping does not remove the quantum-linear-solve layer below — it invokes it repeatedly, or folds the whole trajectory into one larger block system and hands that over instead. Written out step by step it is one solve per time step, $T/h$ of them to reach time $T$, and each step's solve consumes the previous step's output as its right-hand side, so the chain is a quantum state passed forward and never a number read out. That is what makes the repetition expensive rather than merely long: a quantum linear solve succeeds only on a flagged branch, and the flags multiply down the chain, so the amplification bill compounds with the number of steps. Folding the trajectory into one banded system — which is what the all-at-once encodings do, and what the deliverable of this layer is — is how the published treatments spend that once instead of $T/h$ times. Still first order, so the precision dependence stays polynomial in $1/\varepsilon$. The nearest published quantum treatment, by Dong, Li and Xue, encodes diagonal Padé approximations of the matrix exponential into a large, block-sparse linear system solved via a quantum linear system algorithm; backward Euler is the subdiagonal $(0,1)$ approximant and is not among the schemes they analyse. No primary quantum source verified here gives an end-to-end complexity or conditioning bound for a pure backward-Euler encoding.

Requires

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

Example

Dong, Li and Xue (arXiv:2504.06948) set the off-diagonal Padé cases aside in one sentence of Section 3.1 — "we consider the case p = q = k in the rest of the paper" — and backward Euler is the (0,1) member. Everything they then measure is diagonal, so the paper's experiments are about schemes this record is not.

given  A, b, u_0, step size h, horizon T

for k = 0 … T/h − 1:
    # one quantum linear solve; being implicit does not remove the layer
    solve (I − hA) u_{k+1} = u_k + h b_{k+1}
    # u_{k+1} is a quantum state handed to the next step, never read out

return u_{T/h}

Cost, as the source states it

No verified source states an end-to-end cost for a pure backward-Euler encoding, and the field says so. The nearest treatment, Dong, Li and Xue, proves its complexity theorems for diagonal Padé approximants of order $k \ge 3$; backward Euler is the $(0,1)$ subdiagonal approximant, outside them. What the repetition itself charges — one flagged linear solve per step, $T/h$ of them — is in conditions.

Implementations

Dong, Li and Xue implement diagonal Pade approximants and nothing else. Their Section 3.1 sets the off-diagonal cases aside in one sentence — "Since the diagonal Pade approximation ($p = q$) is usually preferred over the off-diagonal cases ($p \\ne q$), we consider the case $p = q = k$ in the rest of the paper" — two sections before the first experiment, and backward Euler is the $(0,1)$ approximant. The words "backward Euler" appear nowhere in the paper. So there is no implementation of THIS scheme to write up, which is the same sentence that stops `cost` quoting a complexity here.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Forward (explicit) Euler

  First-order explicit stepping, $u_{k+1} = (I + hA)u_k + h b_k$, assembled into a banded all-at-once linear system. Liu et al. use it inside the Carleman route because its structure is simple enough to bound explicitly.

• 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

• A quantum algorithm for linear autonomous differential equations via Padé approximation↗Dekuan Dong, Yingzhou Li, Jungong Xue · 2025theory yes · simulation yes · hardware no