MethodLayer 1

Carleman-Fourier 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.

Takes

$F$ , $y_{\mathrm{in}}$ , $T$ , $\varepsilon$ , and a truncation or lift parameter (Carleman truncation level $N$ , a phase-space grid, the level-set dimension, the homotopy order).

Returns

A linear generator with any inhomogeneity, a lift map, a readout map, and an error bound as a function of the truncation parameter.

Same contract as the slot it fills.

From Nonlinear initial-value problem to Linear ODE system

A circle is an object you are holding. This method is drawn heavier, opened into its own steps; the other lines between the same two ends are the alternatives recorded for the same slot. Circles are named on hover, and each one is a link.

Nothing drawn here has a recorded way through it that this figure leaves shut. See it on the map

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 the rescaled ODE $dx/dt = F_0 + F_1 e^{ix}$ with time-independent coefficient matrices. Katz et al. give two truncation regimes. The dissipative one requires $µ̃_0 := \min_j Im$ { $(F_0)_j$ } $\geq 0$ and $R_p := ||F_1||_row,q ||\Psi_1(0)||_p / µ̃_0 < 1$ , under which the $k$ -th truncation error component is bounded by $(||\Psi_1(0)||_p)^{N+1} (||F_1||_row,q / µ̃_0)^{N+1−k}$ . The second drops dissipativity and holds only on a finite interval $[0, T_max]$ with $T_max = \min$ { $T_r, \ln r / (||F_0||_∞ + ||F_1||_row,q)$ }, where $r$ is the rescaling parameter and $T_r$ is the horizon their Lemma 4.3 supplies. Chen, Motee and Sun state the linearization for periodic vector fields with several fundamental frequencies and prove exponential convergence in the truncation length, achieved across the whole time horizon only for particular classes of system.

Requires

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

Example

given  the Fourier ODE  du/dt = G_0 + G_1 e^{iu},  u(0) = u_0,  u(t) in C^n,
       G_0 in C^n,  G_1 in C^{n x n},  e^{iu} the vector with entries {e^{iu_j}},
       the Fourier coefficients d_j of the readout g,
       a truncation level N

# rescale first
choose  nu > 0 large enough that  gamma := ||e^{ix_0}|| = ||e^{iu_0}|| / nu  <  1
set     x_j = u_j + i ln(nu),   j = 1..n
        # the rescaled ODE is  dx/dt = F_1 e^{ix} + F_0,
        # with  F_1 = nu G_1  and  F_0 = G_0
        # mu~_0 and R_p are invariant under this rescaling
set     c_j = nu^{|j|} d_j
        # f(x) = sum_j c_j e^{i x . j}  then satisfies  f(x) = g(u)

# lift onto the Fourier tower, not the monomial tower
set     Psi_j(x) = [e^{ix}]^{tensor j},   j = 1, 2, ...
        # expanding the same equation in monomials leaves the coefficient
        # matrix non-sparse; in the single-variable illustration
        #   d(e^{ix})/dt = i F_0 e^{ix} + i F_1 e^{2ix}
        # each row of the Fourier coefficient matrix has two non-zero entries
form    F~_0 = diag(F_0)  in C^{n x n}
        F~_1 in C^{n x n^2}, the rows of F_1 laid out blockwise
        # d(e^{ix})/dt = i F~_1 Psi_2 + i F~_0 Psi_1
form    B^(1)_{j+1} = i F~_1 (x) I^(x)(j-1) + I (x) i F~_1 (x) I^(x)(j-2)
                      + ... + I^(x)(j-1) (x) i F~_1
        B^(0)_j     = the same expression with F~_0 in place of F~_1
        # recurrence:  dPsi_j/dt = B^(1)_{j+1} Psi_{j+1} + B^(0)_j Psi_j
        # so  dPsi/dt = L^T Psi  is block upper bidiagonal

# truncate at level N
keep    the first N blocks:  dPsi^(N)/dt = L_N^T Psi^(N),  initial data Psi^(N)(x_0)
        # L_N^T is the top-left block of L^T; its last block row is
        #   ( 0 ... 0  B^(0)_N ),  i.e. the coupling B^(1)_{N+1} is dropped,
        # and that is where  eta_k = Psi_k - Psi^(N)_k  enters
pad     Psi^(N)(t) = direct sum over j = 1..N of  e_1^(x)(N-j) (x) Psi_j(t),
        in C^{N n^N}
        # blocks of unequal size complicate the circuit

hand the truncated linear ODE, its initial data Psi^(N)(x_0) and the rescaled
     readout coefficients c to the layer below
     # which bound eta obeys depends on the regime: Theorem 4.2 for all time
     # under mu~_0 >= 0 and R_p < 1, Theorem 4.4 on [0, Tmax] without them

Cost, as the source states it

Chen, Motee and Sun price nothing algorithmic: their Theorem 4.1 bounds each entry of the order- $N$ truncation's first block classically by $C_1 N^{-3/2}e^{D_1(t-\tilde{T}_{CF})N}$ up to a horizon $\tilde{T}_{CF}$ , with $C_1$ , $D_1$ , $\tilde{T}_{CF}$ fixed by the field's frequencies and initial state; no query or gate count appears. The query count is Katz, Muraleedharan and Alase's: their informal Theorem 6.3 gives, under dissipativity, $\tilde{O}\left(\frac{T^{3/2}\lVert G_0\rVert_\infty\lVert d\rVert}{\varepsilon}\left(1+\frac{\lVert G_1\rVert_2}{\lVert G_1\rVert_{\mathrm{row},q}}\right)\left(1+\frac{\tilde\mu_0}{\lVert G_1\rVert_{\mathrm{row},q}}\right)^K\right)$ queries to oracles for the ODE's $n$ -dimensional coefficients $G_0,G_1$ : $T$ the final time, $\varepsilon$ the accuracy, $K$ the Fourier degree of the readout and $d$ its coefficient vector, $\tilde\mu_0$ the dissipativity parameter, $p$ and $q$ Hölder conjugates. That is $\mathrm{polylog}(n)$ , hence exponentially faster than classical, only once all six of $T$ , $\lVert G_0\rVert_\infty$ , $\lVert d\rVert$ , $1/\varepsilon$ , $\lVert G_1\rVert_2/\lVert G_1\rVert_{\mathrm{row},q}$ and $\tilde\mu_0/\lVert G_1\rVert_{\mathrm{row},q}$ are themselves $\mathrm{polylog}(n)$ ; they call the $T^{3/2}$ scaling suboptimal. Without dissipativity (Theorem 6.7) the count loses $T$ , $\lVert G_0\rVert_\infty$ and $\lVert G_1\rVert_{\mathrm{row},q}$ , growing instead with the rescaling parameter $r$ , $\lVert d\rVert_q$ , $\lVert e^{iu_0}\rVert_p$ and $1/\varepsilon$ .

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

Carleman linearization a narrower version of Koopman linearization
Lift the quadratic ODE onto the tower $y, y⊗y, y⊗y⊗y, \ldots$ , on which the dynamics is exactly linear and each level couples only to its neighbours, then truncate at level $N$ . The lift itself is exact; all of the error comes from the truncation. Katz, Muraleedharan and Alase derive it as one instance of Koopman linearization: taking the space of observables to be the polynomials and the basis functions to be the monomials reproduces exactly this tower, in one variable and in $n$ .
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.
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

Carleman-Fourier Linearization of Complex Dynamical Systems: Convergence and Explicit Error Bounds ↗Panpan Chen, Nader Motee, Qiyu Sun · 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

This one, drawn