Carleman linearization

What it fills

• Embed a nonlinear system into a linear one

  Given a nonlinear vector field $F$, produce a (truncated) linear generator on a lifted space, a lift of the initial condition into that space, and a decoding of the target quantity, such that linear evolution reproduces the nonlinear dynamics to accuracy $\varepsilon$. The truncation or lift parameter fixes both the accuracy and the dimension.

A narrower version of Koopman linearization

When it applies

Stated for $du/dt = F_2 u^{\otimes2} + F_1 u + F_0(t)$ with $F_1$ diagonalizable and eigenvalues ordered $Re(\lambda_n) \leq \ldots \leq Re(\lambda_1) < 0$, that is, a strictly dissipative linear part. Liu et al. give a convergence theorem for $R < 1$, where $R = (1/|Re(\lambda_1)|)(||u_in|| ||F_2|| + ||F_0||/||u_in||)$. It does not apply when the linear part has an eigenvalue with non-negative real part.

Requires

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

Example

given  F_2, F_1, F_0(t), u_in, horizon T, error tolerance eps,
       for the quadratic ODE  du/dt = F_2 u^(x)2 + F_1 u + F_0(t)

# conditions, as this record states them: F_1 diagonalizable with eigenvalues
#   ordered Re(lambda_n) <= ... <= Re(lambda_1) < 0, that is, a strictly
#   dissipative linear part, and R < 1 for
#       R = (1/|Re(lambda_1)|)(||u_in|| ||F_2|| + ||F_0||/||u_in||).
#   Liu et al.'s truncation bound also assumes ||F_0|| <= ||F_2||.

rescale  u -> gamma u      # leaves R unchanged, and gives
                           # ||F_2|| + ||F_0|| < |Re(lambda_1)| and ||u_in|| < 1

choose the truncation level
    N = ceil( log(2 T ||F_2|| / delta) / log(1/||u_in||) ),
    with delta = g eps/(1 + eps)  and  g = ||u(T)||

# the lift: the tower of tensor powers.  The lift itself is exact; all of the
# error comes from the truncation
y_j  := u^(x)j                         for j = 1 ... N
y_in  = [ u_in ; u_in^(x)2 ; ... ; u_in^(x)N ]

# each level couples only to its neighbours, so A(t) is block tridiagonal
for j = 1 ... N:
    A^j_{j+1} = F_2 (x) I^(x)(j-1) + I (x) F_2 (x) I^(x)(j-2) + ... + I^(x)(j-1) (x) F_2
    A^j_j     = the same sum built from F_1
    A^j_{j-1} = the same sum built from F_0(t)
# A is (3 N s)-sparse, and the lifted system has dimension
#     Delta = n + n^2 + ... + n^N = O(n^N)

# truncate at level N: the exact level-N equation carries the coupling
# A^N_{N+1} u^(x)(N+1) to the level above, and cutting at N drops that term
emit  dy/dt = A(t) y + b(t),  y(0) = y_in,  b(t) = [ F_0(t) ; 0 ; ... ; 0 ]

# under R < 1 the truncation error decays with N:
#     ||u(t) - y_1(t)|| <= ||eta(t)|| <= t N ||F_2|| ||u_in||^(N+1)
#   and, for F_0 = 0,  ||eta_j(t)|| <= ||u_in||^j R^(N+1-j)
# R < 1 is sufficient, not necessary: the intractability result begins at
# R >= sqrt(2), and 1 <= R < sqrt(2) is open

return y_1 as the approximation of u; the linear system this produces is solved
       by the layer below -- on its own the linearization is a change of
       variables and buys nothing until something solves the system it produces

Cost, as the source states it

Liu et al. state the algorithm's complexity as $T^2 q \cdot \mathrm{poly}(\log T, \log n, \log(1/\varepsilon))/\varepsilon$, where $T$ is the evolution time, $n$ the dimension of the nonlinear system, $\varepsilon$ the allowed error, and $q$ a quantity measuring the decay of the solution. It is quoted here as the paper states it: a complexity for the complete algorithm — this embedding together with the linear solver the truncated tower feeds — and not a standalone cost for the linearization, which on its own is a change of variables and buys nothing until something solves the system it produces. The bound holds under the $R < 1$ hypothesis recorded above. How the truncation level $N$ depends on $R$ and $\varepsilon$ is in the paper's full text and is not quoted here.

Implementations

Nobody has written one up yet. That is a gap in this record, not a statement that the method has never been run — the paper register already records, per paper, which sources report numerics or a hardware run.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Koopman linearization

  Pick a space of observables $G$ containing the quantity of interest and a basis $Ψ$ for it; the Koopman generator acting on $Ψ$ gives an infinite-dimensional linear ODE, truncated by projecting onto $N$ basis functions. $G$ fixes which observables the lifted dynamics can report and $Ψ$ fixes the structure of the generator, so this is a family of lifts parameterised by that choice rather than a single lift. Only basis choices a cited paper has carried through are recorded here — Katz, Muraleedharan and Alase name Chebyshev and Hermite bases as directions rather than results — so the narrower versions recorded under it are a sample of the framework and not an enumeration of it.

• Carleman-Fourier linearization a narrower version of Koopman linearization

  Lift the rescaled ODE $dx/dt = F_0 + F_1 e^{ix}$ — the problem as posed is $du/dt = G_0 + G_1 e^{iu}$, rescaled so that $F_0 = G_0$ and $F_1 = νG_1$ — onto the Fourier tower $e^{ix}, (e^{ix})^{\otimes2}, \ldots$ instead of the monomial tower, then truncate at level $N$. Katz, Muraleedharan and Alase give the reason for the choice: expanding the same equation in monomials leaves the coefficient matrix non-sparse, whereas in the Fourier basis the coefficient matrix of their single-variable illustration has only two non-zero entries in each row.

• Koopman-von Neumann lift to phase-space densities

  Represent nonlinear non-Hamiltonian classical dynamics by the Liouville equation for the phase-space density; the generalized Koopman-von Neumann formulation recasts that as a Schrödinger equation with a Hermitian Hamiltonian operator and a unitary propagator. The lift is exact, and its cost is dimensional rather than an approximation error.

• Level-set exact linearization

  Map a nonlinear PDE exactly onto a linear one using the level-set method, with no truncation and therefore no convergence parameter. The price is a higher-dimensional linear problem.

• Homotopy perturbation embedding

  Convert the original nonlinear ODE into another nonlinear system whose homotopy-perturbation terms embed into a single finite-dimensional linear ODE system, truncated at a chosen homotopy order. The embedding is finite-dimensional by construction.

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

• 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 · 2020theory yes · simulation yes · hardware no
• Quantum Algorithms for Nonlinear Dynamics: Revisiting Carleman Linearization with No Dissipative Conditions↗Hsuan-Cheng Wu, Jingyao Wang, Xiantao Li · 2024theory yes · simulation yes · hardware no
• Efficient quantum algorithm for solving differential equations with Fourier nonlinearity via Koopman linearization↗Judd Katz, Gopikrishnan Muraleedharan, Abhijeet Alase · 2025theory yes · simulation ? · hardware no