Sign outOpen workspaceSign in

MethodLayer 1

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.

Takes

FF, yiny_{\mathrm{in}}, TT, ε\varepsilon, and a truncation or lift parameter (Carleman truncation level NN, 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.

This one, drawn

Homotopy perturbation embeddingKoopman linearizationnarrower versions, nested under the line they refineCarleman linearization, a narrower version of Koopman linearizationCarleman-Fourier linearization, a narrower version of Koopman linearizationKoopman-von Neumann lift to phase-space densitiesLevel-set exact linearizationHomotopy perturbation embeddingKoopman linearization — click the name to read about itKoopman linearizationCarleman linearization, a narrower version of Koopman linearization — click the name to read about itCarleman linearizationCarleman-Fourier linearization, a narrower version of Koopman linearization — click the name to read about itCarleman-Fourier linearizationKoopman-von Neumann lift to phase-space densities — click the name to read about itKoopman–von Neumann liftLevel-set exact linearization — click the name to read about itLevel-set exact linearizationHomotopy perturbation embedding — click the name to read about itHomotopy perturbation embeddingNonlinear initial-value problem — you start hereLinear ODE system — 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 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 FF, 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

Stated for nn-dimensional nonlinear dissipative ODEs. Krovi describes Xue et al., alongside Liu et al., as additionally requiring normality of the matrix that models dissipation.

Requires

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

Example

given  du/dt = F_1 u + F_2 u^{(x)2},  u(0) = u_in            # the quadratic ODEs, Eq.(1)
       F_1, F_2 time-independent and s-sparse
       F_1 normal, eigenvalues Re(lambda_n) <= ... <= Re(lambda_1) < 0
       homotopy truncation order c

# --- 1. homotopy perturbation: one nonlinear system becomes a chain -----------
#     construct the homotopy nu(t,p), Eq.(4):
#         H(nu,p) = dnu/dt - F_1 nu - p F_2 nu^{(x)2} = 0,   nu(0,p) = u_in
#     write nu = nu_0 + p nu_1 + p^2 nu_2 + ... + p^c nu_c and equate the terms
#     with identical powers of p, giving Eq.(6):
    dnu_0/dt = F_1 nu_0,                                       nu_0(0) = u_in
    dnu_i/dt = F_1 nu_i + F_2 sum_{j=0..i-1} nu_j (x) nu_{i-1-j},  nu_i(0) = 0
#     at p = 1:   utilde = nu_0 + nu_1 + ... + nu_c

# --- 2. embed that chain in linear ODEs, Eq.(8)-(12) -------------------------
    y_0     = [nu_0 + nu_1 + ... + nu_c]
    y_{i,j} = nu_{a_{i,j,0}} (x) nu_{a_{i,j,1}} (x) ... (x) nu_{a_{i,j,i}},   1 <= i <= c
              over the index vectors a_{i,j} with
                  a_{i,j,k} >= 0   and   i+1 <= sum_k (a_{i,j,k} + 1) <= c+1
    beta_0  = 1,   beta_i = sum_{k=i..c} binom(k,i)         # blocks at level i
    N       = sum_{i=0..c} n^{i+1} beta_i = (n+1)^{c+1} - 1 - cn

#     differentiating y_{i,j} gives a linear part inside level i and, through
#     F_2, terms that all lie in y_{i+1} -- that is the closure, and it is why A
#     is block bidiagonal with nothing below the diagonal:
    A_{i,i}   = I_{beta_i} (x) sum_{j=0..i} I_{n^j} (x) F_1 (x) I_n^{(x) i-j}
    A_{i,i+1} = the F_2 terms of that derivative,  i = 0 ... c-1
#     level c has A_{c,c} and nothing above it -- the truncation closes the system

#     fix y_{i,0} = nu_0^{(x) i+1}, so the lift of the initial condition is
    y_in = [[u_in], [u_in^{(x)2}, 0, ..., 0], ..., [u_in^{(x)c+1}, 0, ..., 0]]

# --- 3. what this layer hands down -------------------------------------------
return  dy/dt = A y,  y(0) = y_in       # finite-dimensional by construction
        the readout: the first block of y is utilde, so the answer is on |0,0>
        sparsity O(s c^2);  ||A|| <= (c+1)(||F_1|| + ||F_2||);  Re(gamma_i) < 0
        truncation error as a function of c:
            ||nu_i(t)|| < (4 K_1)^i ||u_in|| <= K^{i+1},
                K_1 = ||u_in|| ||F_2|| / |Re(lambda_1)|,   K = 4 K_1
            ||u(t) - utilde(t)|| <= eps   when K < 1 and
                c > log_{1/K} ( 1 / (eps (1-K)) )

# O_A is built from O(c) queries to O_F1 and O(1) queries to O_F2   (Lemma 6)
# solving dy/dt = A y with a quantum linear-ODE algorithm is the layer below

Cost, as the source states it

Xue, Wu and Guo state the algorithm's complexity as O(gηT poly(log⁡(nT/ε)))O(g\eta T\,\mathrm{poly}(\log(nT/\varepsilon))), where TT is the evolution time, nn the dimension, ε\varepsilon the allowed error, and η\eta and gg are quantities measuring the decay of the solution; the returned state is ε\varepsilon-close to the normalized exact solution with success probability Ω(1)\Omega(1). As with the Carleman route, this is a complexity for the complete algorithm — the embedding together with the quantum linear-ODE solver it feeds — not a standalone cost for the lift. The abstract claims exponential improvement over the best classical algorithms or previous quantum algorithms in nn or ε\varepsilon; how the homotopy truncation order enters the bound 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.

Where the claim is contested

Xue and co-authors later report that applying quantum simulation to each step of the related homotopy analysis method makes complexity grow exponentially with the truncation order, and introduce a quantum-compatible linearization that maps the whole process into one system of linear PDEs so that complexity grows only polynomially with that order.

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,…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 NN. 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 nn.

  • Koopman linearization

    Pick a space of observables GG 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 NN basis functions. GG 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=F0+F1eixdx/dt = F_0 + F_1 e^{ix} — the problem as posed is du/dt=G0+G1eiudu/dt = G_0 + G_1 e^{iu}, rescaled so that F0=G0F_0 = G_0 and F1=νG1F_1 = νG_1 — onto the Fourier tower eix,(eix)⊗2,…e^{ix}, (e^{ix})^{\otimes2}, \ldots instead of the monomial tower, then truncate at level NN. 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.

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