Choose a time discretization or propagator approximation

Why this is a layer

The choice fixes both the $\varepsilon$-scaling and the condition number the downstream solver must pay. The same ODE encoded by a finite-difference scheme and by a truncated Taylor expansion of the propagator differs exponentially in its $\varepsilon$-dependence. Treating discretization as an implementation detail hides the dominant cost term.

Ways to do this

6 methods recorded

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

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

Routes that skip this layer

These do not fill the slot. They replace the span it belongs to, so this layer is not on their path at all.

• Quantum simulation of the KvN representation

  Because the Koopman-von Neumann generator is Hermitian and its propagator unitary, the lifted evolution can be run by Hamiltonian simulation directly. No linear system is assembled and no linear solver is called.

• LCHS — linear combination of Hamiltonian simulation

  Express a general non-unitary evolution operator as a linear combination of unitary evolution operators, each of which solves a Hamiltonian simulation problem, rather than converting the problem into a dilated linear system. An, Liu and Lin state that the method can achieve optimal cost in terms of state preparation.

• LCHS with the improved kernel a narrower version of LCHS — linear combination of Hamiltonian simulation

  A family of identities expressing non-unitary evolution as a linear combination of unitary evolutions, built on the kernel $f(z) = 1/(C_β e^{(1+iz)^β})$ with $β ∈ (0,1)$ and $C_β = 2π e^{-2^β}$. The kernel decays at a near-exponential rate $e^{-c|k|^β}$, replacing the original Cauchy kernel's quadratic decay and exponentially enhancing accuracy.

• Schrödingerisation (linear PDEs as Schrödinger equations)

  A simple change of variable — the warped phase transformation, which introduces one extra variable — recasts any linear PDE or ODE system into a system of Schrödinger equations in real time, which ordinary Hamiltonian simulation then runs. The original solution is recovered from the auxiliary dimension.

This is a step inside

• Quantum Carleman linearization algorithm

  Carleman-linearize the quadratic ODE, discretize with forward Euler, assemble the whole history into one large sparse linear system, and solve that system with a quantum linear system algorithm. This is the route that made dissipative nonlinear ODEs tractable in evolution time.

• Linear multistep method, all-at-once encoding

  The first quantum algorithm for general linear ODEs. Discretize with a high-order linear multistep method, lay every time step out at once against a clock register so that one state $\sum_j |t_j\rangle|x_j\rangle$ holds the whole history, and solve the resulting sparse linear system with a quantum linear system algorithm. Going high-order is what buys the $\Delta t$ scaling: plain Euler costs at least $O(\Delta t^4)$ here.

• Taylor propagator, all-at-once encoding

  Encode a truncated Taylor series of the propagator into a single sparse linear system approximating the whole evolution, then solve it with a quantum linear system algorithm. This is what brought the precision dependence down to polynomial in $\log(1/\varepsilon)$.

• Chebyshev spectral method, global collocation

  The route that brought $\mathrm{poly}(\log(1/\varepsilon))$ precision to linear ODEs with **time-dependent** coefficients, which is what its abstract says was missing: "no such algorithm was previously known for differential equations with time-dependent coefficients". It does it by not stepping. The solution is approximated globally by a truncated Chebyshev series, the coefficients are fixed by collocating the differential equation at Chebyshev nodes, and the resulting sparse system goes to a high-precision quantum linear system algorithm. The exponential precision is bought by smoothness rather than by the solver: it is the $C^{\infty}$ convergence of the Chebyshev series that makes the series length logarithmic in $1/\varepsilon$.

• Krovi's reanalysis of the all-at-once encoding a narrower version of Taylor propagator, all-at-once encoding

  Reanalyses the all-at-once propagator encoding and shows that the norm of the matrix exponential, rather than the eigenvector condition number, characterizes the run time. It still forms a global linear system and still calls a quantum linear solver.

• Dyson propagator, all-at-once encoding

  Encode the Dyson series in a system of linear equations and solve it via the optimal quantum linear equation solver, extending the all-at-once approach to genuinely time-dependent generators.

• Time-marching with uniform singular value amplification

  Propagate the solution one step at a time and defeat the exponentially vanishing success probability by repeatedly invoking uniform singular value amplification, improved further by a compression gadget lemma. Fang, Lin and Tong present it explicitly as a design path alternative to solvers based on quantum linear systems algorithms.

Routes that run this slot many times

For these routes this slot is inside a loop, so its cost is multiplied rather than paid once. That multiplier is usually the largest single term in what the route costs.

• Time-marching with uniform singular value amplification runs once per time step, with an amplification at every one

  The loop stays coherent: nothing is measured between turns. The preparation may still be reapplied every turn — what the loop never pays is a readout and a restart from classical data. The price is depth, and a success probability that multiplies down the chain.

No multiplicity recorded

These routes take this step and no source we have read says how often. That is an absence, not a claim that they take it once.

• Quantum Carleman linearization algorithm

  Carleman-linearize the quadratic ODE, discretize with forward Euler, assemble the whole history into one large sparse linear system, and solve that system with a quantum linear system algorithm. This is the route that made dissipative nonlinear ODEs tractable in evolution time.

• Linear multistep method, all-at-once encoding

  The first quantum algorithm for general linear ODEs. Discretize with a high-order linear multistep method, lay every time step out at once against a clock register so that one state $\sum_j |t_j\rangle|x_j\rangle$ holds the whole history, and solve the resulting sparse linear system with a quantum linear system algorithm. Going high-order is what buys the $\Delta t$ scaling: plain Euler costs at least $O(\Delta t^4)$ here.

• Taylor propagator, all-at-once encoding

  Encode a truncated Taylor series of the propagator into a single sparse linear system approximating the whole evolution, then solve it with a quantum linear system algorithm. This is what brought the precision dependence down to polynomial in $\log(1/\varepsilon)$.

• Chebyshev spectral method, global collocation

  The route that brought $\mathrm{poly}(\log(1/\varepsilon))$ precision to linear ODEs with **time-dependent** coefficients, which is what its abstract says was missing: "no such algorithm was previously known for differential equations with time-dependent coefficients". It does it by not stepping. The solution is approximated globally by a truncated Chebyshev series, the coefficients are fixed by collocating the differential equation at Chebyshev nodes, and the resulting sparse system goes to a high-precision quantum linear system algorithm. The exponential precision is bought by smoothness rather than by the solver: it is the $C^{\infty}$ convergence of the Chebyshev series that makes the series length logarithmic in $1/\varepsilon$.

• Krovi's reanalysis of the all-at-once encoding a narrower version of Taylor propagator, all-at-once encoding

  Reanalyses the all-at-once propagator encoding and shows that the norm of the matrix exponential, rather than the eigenvector condition number, characterizes the run time. It still forms a global linear system and still calls a quantum linear solver.

• Dyson propagator, all-at-once encoding

  Encode the Dyson series in a system of linear equations and solve it via the optimal quantum linear equation solver, extending the all-at-once approach to genuinely time-dependent generators.

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.