Level-set exact 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.

When it applies

Jin and Liu state the exact mapping for nonlinear Hamilton-Jacobi equations and scalar nonlinear hyperbolic PDEs, for arbitrary nonlinearity. Systems of conservation laws lie outside that stated scope. Because the map is exact there is no convergence condition analogous to Carleman's $R < 1$; what the mapping preserves is physical observables rather than a directly readable solution vector.

Requires

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

Example

given  a (d+1)-dimensional nonlinear PDE with M initial data, k = 1..M:
           Hamilton-Jacobi in gradient form,
               d_t u^[k] + grad H(u^[k], x) = 0,        u^[k] = grad S^[k] in R^d
           or scalar hyperbolic,
               d_t u^[k] + F(u^[k]).grad_x u^[k] + Q(x, u^[k]) = 0,   u^[k] in R

# 1. lift: put the solution inside the zero level set of a new function

define  phi^[k](t, x, p)  by   phi_i^[k](t, x, p = u^[k](t,x)) = 0,   i = 1..d
    initial data:  phi_i^[k](0, x, p) = p_i - u_i^[k](0, x)          # Hamilton-Jacobi
                   phi^[k](0, x, p)   = p   - u_0^[k](x)             # scalar hyperbolic

# 2. the lifted equation is linear -- exactly, for arbitrary nonlinearity

Hamilton-Jacobi:    d_t phi + grad_p H . grad_x phi - grad_x H . grad_p phi = 0
                    # (2d+1)-dimensional
scalar hyperbolic:  d_t phi + F(p) . grad_x phi - Q(x,p) d_p phi = 0
                    # (d+2)-dimensional, because p is a scalar here
    # no truncation, and therefore no convergence parameter:
    # "the price is a higher-dimensional linear problem", not an error term
    # there is no analogue of Carleman's R < 1

# 3. read back

u^[k](t, x) = { p(t,x) | phi_i^[k](t,x,p) = 0, i = 1..d }
    # the intersection of the d zero level sets
    # phi_i^[k] = 0 may have J_k roots p_gamma: all multi-valued branches are kept

# 4. what the mapping preserves is physical observables, not a directly
#    readable solution vector

<G(t,x)> = integral_{R^d} G(p) psi(t,x,p) dp
         = (1/M) sum_{k=1..M} sum_{gamma=1..J_k} G(u_gamma^[k](t,x)) / J_gamma^[k]
    # J_gamma^[k] = |det(d phi^[k] / d p)| at p = u_gamma^[k](t,x)
    # the level-set encoding carries these Jacobian weights automatically;
    # an amplitude encoding of u itself would have to inject them, and they are
    # not known a priori

return  the linear PDE, its initial datum, and the observable rule

Cost, as the source states it

Stated in the abstract as complete-algorithm claims, not a standalone cost for the mapping: computing physical observables at a cost independent of $M$, the number of initial data, for arbitrary nonlinearity; up to exponential advantage in both the dimension of the PDE and the error in computing its observables, depending on the details of the initial data; and for general nonlinear PDEs, quantum advantage with respect to $M$ in the large-$M$ limit. No closed form appears in the abstract.

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.

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

• 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

• Quantum algorithms for computing observables of nonlinear partial differential equations↗Shi Jin, Nana Liu · 2022theory yes · simulation ? · hardware no