Sign outOpen workspaceSign in

SlotLayer 1

Solve a linear ODE du/dt = A(t)u + b(t)

Given block-encoding access to A(t)A(t) and b(t)b(t) and a preparation unitary for u0u_0, output a normalized state ε\varepsilon-close to u(T)/∣∣u(T)∣∣u(T)/||u(T)||. Matrix-query and state-preparation-query counts are stated separately, because methods here differ in them independently.

Takes

A block-encoding of A(t)A(t) with a normalization αA≥max⁡t∥A(t)∥\alpha_A \ge \max_t \lVert A(t)\rVert, preparation unitaries for u0u_0 and bb, the evolution time TT, and an error tolerance ε\varepsilon.

Returns

A state proportional to u(T)u(T), or a history state, together with separately stated matrix-query and initial-state-query complexity.

This one, drawn

Solve a linear ODE du/dt = A(t)u + b(t)Linear multistep method, all-at-once encoding · 2 parts insideLinear multistep method, all-at-once encoding · 2 parts inside — click the line to open it hereTaylor propagator, all-at-once encoding · 2 parts insideTaylor propagator, all-at-once encoding · 2 parts inside — click the line to open it hereChebyshev spectral method, global collocation · 2 parts insideChebyshev spectral method, global collocation · 2 parts inside — click the line to open it hereDyson propagator, all-at-once encoding · 2 parts insideDyson propagator, all-at-once encoding · 2 parts inside — click the line to open it hereTime-marching with uniform singular value amplification · 2 parts insideTime-marching with uniform singular value amplification · 2 parts inside — click the line to open it hereLCHS — linear combination of Hamiltonian simulation · 3 parts insideLCHS — linear combination of Hamiltonian simulation · 3 parts inside — click the line to open it hereSchrödingerisation (linear PDEs as Schrödinger equations) · 3 parts insideSchrödingerisation (linear PDEs as Schrödinger equations) · 3 parts inside — click the line to open it hereLinear multistep method, all-at-once encoding · 2 parts inside — click the name to read about itMultistep, all-at-onceTaylor propagator, all-at-once encoding · 2 parts inside — click the name to read about itTaylor, all-at-onceChebyshev spectral method, global collocation · 2 parts inside — click the name to read about itSpectral methodDyson propagator, all-at-once encoding · 2 parts inside — click the name to read about itDyson, all-at-onceTime-marching with uniform singular value amplification · 2 parts inside — click the name to read about itTime-marchingLCHS — linear combination of Hamiltonian simulation · 3 parts inside — click the name to read about itLCHSSchrödingerisation (linear PDEs as Schrödinger equations) · 3 parts inside — click the name to read about itSchrödingerisationLinear ODE system — you start hereAnswer about the solution — you finish here

Drag to pan. Pinch, or hold ctrl and scroll, to zoom. Arrow keys pan, plus and minus zoom, zero resets the view.

From Linear ODE system to Answer about the solution

A circle is an object you are holding. Each line between the two ends is one recorded way through this slot; where a way is built from smaller slots, those are its own lines. Circles are named on hover, and each one is a link.

7 lines here have ways through that this figure does not open. The map opens them in place. See it on the map

Why this is a layer

This is the pivot of the cluster. Methods fulfilling it split into two structurally different families: those that assemble one large linear system and call a quantum linear solver, and those that never form a linear system at all, reducing instead to Hamiltonian simulation or to repeated singular value amplification. The two families differ in how many queries they make to the initial-state preparation oracle, and that difference is structural rather than a matter of constants — when the initial state is expensive to prepare, it dominates the end-to-end cost.

Ways to do this

9 methods recorded

  • 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 ∑j∣tj⟩∣xj⟩\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 Δt\Delta t scaling: plain Euler costs at least O(Δt4)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/ε)\log(1/\varepsilon).

  • Chebyshev spectral method, global collocation

    The route that brought poly(log⁡(1/ε))\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∞C^{\infty} convergence of the Chebyshev series that makes the series length logarithmic in 1/ε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.

  • 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)β)f(z) = 1/(C_β e^{(1+iz)^β}) with β∈(0,1)β ∈ (0,1) and Cβ=2πe−2βC_β = 2π e^{-2^β}. The kernel decays at a near-exponential rate e−c∣k∣β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.

Routes that skip this layer

No recorded route avoids this step.

This is a step inside

  • Level-set method for observables of nonlinear PDEs

    Use the exact level-set mapping to a linear PDE, solve the linear problem quantumly, and compute physical observables from it. For MM sets of initial data the cost does not grow with MM.

  • Homotopy-perturbation series, embedded as a linear ODE

    Embed the homotopy-perturbation series into a finite-dimensional linear ODE system and solve that with a quantum linear-ODE algorithm, obtaining a state ε\varepsilon-close to the normalized exact solution with Ω(1)Ω(1) success probability.

In the Atlas

  • Quantum algorithms for linear differential equations

    Given a first-order linear differential equation d/dt x = A(t)x + b(t) with N-dimensional vectors x and b and an N×N matrix A, and given an initial condition x(0), produce the solution x(t) at a later time t to precision ε, in the sense that the normalized vector x(t)/‖x(t)‖ returned is at distance at most ε from the exact solution.

  • Quantum algorithm for simulating the wave equation

    Simulate the wave equation under Dirichlet and Neumann boundary conditions on a quantum computer, using Hamiltonian simulation and quantum linear system algorithms as subroutines.