Sign outOpen workspaceSign in

MethodLayer 0

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.

Takes

Access oracles for the components of FF (for example a linear part F1F_1, a quadratic part F2F_2, a forcing term F0F_0), a preparation unitary for yiny_{\mathrm{in}}, the evolution time TT, and an error tolerance ε\varepsilon.

Returns

A normalized state ε\varepsilon-close to y(T)/∥y(T)∥y(T)/\lVert y(T)\rVert, a history state over [0,T][0,T], or an estimate of an observable of the solution.

Same contract as the slot it fills.

This one, drawn

Homotopy-perturbation series, embedded as a linear ODEQuantum Carleman linearization algorithm · 3 parts inside, openQuantum Carleman linearization algorithm · 3 parts inside, openQuantum Carleman linearization algorithm · 3 parts inside, open — click the line to close itCarleman linearization, a narrower version of Koopman linearizationForward (explicit) EulerQuantum linear solve · 5 ways throughQuantum linear solve · 5 ways through — click the line to open it hereQuantum simulation of the KvN representation · 3 parts insideQuantum simulation of the KvN representation · 3 parts inside — click the line to open it hereLevel-set method for observables of nonlinear PDEs · 2 parts insideLevel-set method for observables of nonlinear PDEs · 2 parts inside — click the line to open it hereHomotopy-perturbation series, embedded as a linear ODE · 2 parts inside, openHomotopy-perturbation series, embedded as a linear ODE · 2 parts inside, openHomotopy-perturbation series, embedded as a linear ODE · 2 parts inside, open — click the line to close itHomotopy perturbation embeddingSolve a linear ODE du/dt = A(t)u + b(t) · 9 ways throughSolve a linear ODE du/dt = A(t)u + b(t) · 9 ways through — click the line to open it hereQuantum Carleman linearization algorithm · 3 parts inside, open — click the name to close itQuantum Carleman linearization algorithmCarleman linearization, a narrower version of Koopman linearization — click the name to read about itCarleman linearizationForward (explicit) Euler — click the name to read about itForward (explicit) EulerQuantum linear solve · 5 ways through — click the name to read about itQuantum linear solveQuantum simulation of the KvN representation · 3 parts inside — click the name to read about itKvN simulationLevel-set method for observables of nonlinear PDEs · 2 parts inside — click the name to read about itLevel sets for PDE observablesHomotopy-perturbation series, embedded as a linear ODE · 2 parts inside, open — click the name to close itHomotopy series, linear ODEHomotopy perturbation embedding — click the name to read about itHomotopy perturbation embeddingSolve a linear ODE du/dt = A(t)u + b(t) · 9 ways through — click the name to read about itSolve a linear ODE du/dt = A(t)u + b(t)Nonlinear initial-value problem — you start hereAnswer about the solution — you finish hereLinear ODE system — what one part hands to the nextLinear system Ax = b — what one part hands to the nextLinear ODE system — what one part hands to the next

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 Answer about the solution

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.

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

What it fills

  • Solve a nonlinear ODE dy/dt = F(y)

    Given access to a nonlinear vector field FF — in practice quadratic or polynomial — and a preparation unitary for the initial state, produce a quantum state proportional to y(T)y(T) or an estimate of an observable of it. Quantum time evolution is linear, so no quantum primitive acts on this contract directly.

When it applies

Stated for nn-dimensional nonlinear dissipative ODEs. Krovi notes that the logarithmic dependence on error achieved here holds only for homogeneous nonlinear equations, and that this route, like Liu et al., additionally requires normality of the matrix modelling dissipation.

Requires

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

Example

given  n-dimensional quadratic ODEs  du/dt = F_1 u + F_2 u^{(x)2},  u(0) = u_in
       F_1, F_2 time-independent and s-sparse
       F_1 normal, eigenvalues Re(lambda_n) <= ... <= Re(lambda_1) < 0
       oracles O_F1, O_F2 for nonzero positions and values of F_1, F_2
       oracle  O_u : |0> -> |u_in / ||u_in|| >
       horizon T, error budget eps

# the parameter that characterises the nonlinearity, Eq.(3)
K     = 4 ||u_in|| ||F_2|| / |Re(lambda_1)|
        # require K < sqrt(2)/2   -- stronger than the K < 1 convergence alone needs
        # if K < ||u_in||, rescale u -> zeta u by a constant that leaves K unchanged
eta   = ||u_in|| / ||u(T)||
eta'  = eta K / ||u_in||
g     = max_{t in [0,T]} || |y(t)> || / || |y(T)> ||
c     = ceil( log_{1/K}( 4 ||u_in|| / ((1-K) eps eta) ) )      # truncation order
        # require (c+1) ||F_2|| / |Re(lambda_1)| <= 1

# --- nonlinear-linear-embedding, via homotopy-perturbation-lift --------------
build  dy/dt = A y,  y(0) = y_in                # Eq.(8);  N ~ (n+1)^{c+1}
    # embed the homotopy-perturbation series into a finite-dimensional linear
    # ODE system -- the whole of that construction is the lift's own card
    # what comes back:  sparsity O(s c^2), ||A|| <= (c+1)(||F_1|| + ||F_2||),
    #     Re(gamma_i) < 0 for every eigenvalue of A,
    #     the lift y_in, and the readout: the first block of y is utilde
    # O_A costs O(c) queries to O_F1 and O(1) queries to O_F2   (Lemma 6)
    # |0>|y_in> is prepared with O(c) queries to O_u            (Lemma 1)

# --- linear-ode-solve --------------------------------------------------------
h     = T / ceil(T ||A||)
m = p = T/h = ceil(T ||A||)
delta = eps sqrt(1 - 2K^2) / (30 sqrt(78 m) g eta')     # the solver's budget
Omega = 50 m (c+1)(c+2) g / delta
k     = floor( 2 log(Omega) / log(log(Omega)) )         # so that (k+1)! >= Omega

repeat O( g eta' / sqrt(1 - 2K^2) ) times, coherently -- amplitude amplification:

    prepare |0>|y_in>
    assemble  C_{m,k,p}(Ah) |x> = |0>|y_in>              # Eq.(21), Eq.(22)
        Taylor-term rows : |x_{i,1}> = Ah |x_{i,0}>,
                           |x_{i,j}> = (Ah/j) |x_{i,j-1}>,   2 <= j <= k
        step-closing row : |x_{i,0}> = sum_{j=0..k} |x_{i-1,j}>
        padding rows     : |x_{m,j}> = |x_{m,j-1}>,          1 <= j <= p
        # sparsity        s_C < k + c^2 s
        # condition no.   kappa_C <= 2 e sqrt(k) (m(k+1)+p)(c+2)   (Lemma 8)
    solve that system with the quantum linear system algorithm, to within delta
        of the normalised solution
        # this route reduces to a quantum linear solve; it does not remove it

    # --- measurement, in two steps (Sect. III D) ---
    measure the first register of |x>
    accept iff the outcome lies in S = {m(k+1), ..., m(k+1)+p}
        # those p+1 blocks all hold |y(T)>
        # probability >= 1 / (p + 77 m g^2)                       (Lemma 11)
    measure the block register of |y(T)> = sum_{i,j} |i,j> |y_{i,j}(T)>
    accept iff the outcome is |0,0>
        # that block is utilde(T) = nu_0 + ... + nu_c
        # probability >= (1 - 2K^2) / (1 - 2K^2 + 2 eta'^2)       (Lemma 12)

return the remaining register -- a state eps-close to the normalized exact
       solution u(T)/||u(T)||, with Omega(1) success probability

# query complexity for O_F1, O_F2, O_u:
#   O( g eta s T (||F_1|| + ||F_2||) / (sqrt(1-2K^2) ||u_in||)
#      * poly log( g eta s T ||F_1|| ||F_2|| / (eps (1-2K^2) ||u_in||) ) )
# gate complexity is larger by a factor O(poly log(n g eta s T ||F_1|| ||F_2||
#                                          / (eps (1-2K^2) ||u_in||)))
# quoted on this record as  O(g eta T poly(log(nT/eps)))

Cost, as the source states it

O(gηT poly(log⁡(nT/ε)))O(g \eta T\,\mathrm{poly}(\log(nT/\varepsilon))), where η\eta and gg measure the decay of the solution, nn is the dimension, TT the evolution time and ε\varepsilon the error.

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

  1. Embed a nonlinear system into a linear one 6 methods

    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.

  2. Solve a linear ODE du/dt = A(t)u + b(t) 9 methods

    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.

Other ways to fill the same slot

Different approaches

  • Quantum Carleman linearization algorithm

    Carleman-linearize the quadratic ODE, discretize with forward Euler, assemble the whole history into one large sparse linear system, and solve that system with a quantum linear system algorithm. This is the route that made dissipative nonlinear ODEs tractable in evolution time.

  • Quantum simulation of the KvN representation

    Because the Koopman-von Neumann generator is Hermitian and its propagator unitary, the lifted evolution can be run by Hamiltonian simulation directly. No linear system is assembled and no linear solver is called.

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

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