Trapezoidal rule (Crank-Nicolson)

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

Second order at the same stability class as backward Euler, so it is more accurate at equal step size, but the implicit solve does not disappear on a quantum computer — it is the layer below, and what this one hands down to it is the assembled system. Second order buys a larger $h$ at the same accuracy, so written out step by step the loop turns fewer times than backward Euler's; it is the same loop, one linear solve per turn with the previous turn's state as its right-hand side. Being A-stable removes the step-size restriction, not the repetition. Second order still leaves a polynomial dependence on $1/\varepsilon$; only propagator-series or spectral discretizations reach $\log(1/\varepsilon)$. Dong, Li and Xue encode diagonal Padé approximations of the matrix exponential into a large, block-sparse linear system solved via a quantum linear system algorithm, but state no complexity for the $(1,1)$ case specifically.

Requires

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

Example

Crank-Nicolson is the (1,1) member of the family Dong, Li and Xue (arXiv:2504.06948) do encode, but k = 1 is the one order their results never reach: Theorem 3.6 is stated for k ≥ 3, Table 1 begins at k = 5, and every experiment in Section 5.2 runs at k = 9 or higher. The words Crank-Nicolson and trapezoidal appear nowhere in the paper.

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

for k = 0 ... T/h - 1:
    # the generator averaged at the two ends of the step
    # one linear solve per turn, the previous turn's state as its right-hand side
    solve (I - (h/2)A) u_{k+1} = (I + (h/2)A) u_k + (h/2)(b_k + b_{k+1})

return u_{T/h}

# second order at backward Euler's stability class, so a larger h at the same
# accuracy and fewer turns of this loop -- the same loop, not a shorter one.
# A-stability removes the step-size restriction, not the repetition.

Cost, as the source states it

Dong, Li and Xue's complexity theorems require diagonal Padé order $k \ge 3$, and Crank–Nicolson is the $(1,1)$ approximant — so no verified source states its end-to-end cost, and the field says so. What second order buys — a larger $h$, hence fewer turns of the same solve-per-step loop — is an accuracy statement, recorded in conditions, not a stated complexity.

Implementations

The same sentence as `backward-euler`'s: Dong, Li and Xue analyse and implement only diagonal Pade approximants, and Crank-Nicolson is the $(1,1)$ case, which their complexity theorems exclude by requiring $k \\ge 3$. Their four numerical experiments run order nine or an order chosen to meet a precision — never this one.

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.

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

• 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