Sign outOpen workspaceSign in

MethodLayer 0

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.

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

Level-set method for observables of nonlinear PDEsQuantum 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 inside, openLevel-set method for observables of nonlinear PDEs · 2 parts inside, openLevel-set method for observables of nonlinear PDEs · 2 parts inside, open — click the line to close itLevel-set exact linearizationSolve 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 hereHomotopy-perturbation series, embedded as a linear ODE · 2 parts insideHomotopy-perturbation series, embedded as a linear ODE · 2 parts inside — 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, open — click the name to close itLevel sets for PDE observablesLevel-set exact linearization — click the name to read about itLevel-set exact linearizationSolve 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)Homotopy-perturbation series, embedded as a linear ODE · 2 parts inside — click the name to read about itHomotopy series, linear ODENonlinear 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 nonlinear Hamilton-Jacobi and scalar hyperbolic PDEs, where the mapping is exact for arbitrary nonlinearity. For general nonlinear PDEs, quantum advantage with respect to MM is claimed only in the large-MM limit. The advantage is stated for computing observables, not for producing the full solution vector; that distinction is load-bearing and is frequently dropped in secondary summaries.

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
           or scalar hyperbolic,  d_t u^[k] + F(u^[k]).grad_x u^[k] + Q(x, u^[k]) = 0
       an observable function G, a time T = t_n, a precision eps

# ---- step 1: nonlinear-linear-embedding, performed by level-set-linearization ----
# "the exact level-set mapping to a linear PDE": no truncation, no convergence parameter

build the level-set function:  phi_i^[k](t, x, p = u^[k](t,x)) = 0
    phi^[k] solves the LINEAR Liouville equation
        d_t phi + grad_p H . grad_x phi - grad_x H . grad_p phi = 0
        phi_i^[k](0, x, p) = p_i - u_i^[k](0, x)
    # (2d+1) dimensions for Hamilton-Jacobi, (d+2) for the scalar hyperbolic case:
    # the price of exactness is dimension, not an error term

solve instead for psi, on the SAME linear equation, with the M initial data
folded into ONE initial datum:
    psi(0, x, p) = (1/M) sum_{k=1..M} prod_{i=1..d} delta(p_i - u_i^[k](0, x))
    # Lemma 9:  psi(t, x, p) = (1/M) sum_k delta(phi^[k](t, x, p))
    # this is why "for M sets of initial data the cost does not grow with M"

# ---- step 2: linear-ode-solve.  the route names no algorithm for this slot ----
# it says only "solve the linear problem quantumly"

discretise psi on the phase-space mesh [0,1]^{2d}:  forward Euler in time,
upwind in x and p,  h = 1/N,  x -> h j,  p -> h l,  t_n = n dt
    require the CFL condition
        d (dt/h) max_i sup_{x,p} { |dH/dx_i| , |dH/dp_i| }  <=  1
    replace delta by the smoothed delta_omega,  omega = m h
    # the three approximations live here, not in step 1: first-order scheme,
    # smoothed delta, quadrature for the p-integral
    # Lemma 12:  eps_CL <= C (omega + d h / omega^2) = C (d h)^{1/3} at omega = (d h)^{1/3}

assemble  K . (psi_1, ..., psi_{N_t})^T = (psi_0, 0, ..., 0)^T
    # K is N_t N^{2d} x N_t N^{2d}, Toeplitz
K is not Hermitian, so hand down the dilation M carrying K and K^dagger off-diagonal
    # "the same sparsity and condition number as K"
    # Lemma 10:  kappa <= O(d N T),  s = O(d)

# ---- readout: observables, NOT the full solution vector ----

ask for  Upsilon = <psi_0| (M^-1)^dagger  G  M^-1 |psi_0>,  G = |G_n,j><G_n,j|
    # by amplitude estimation on the block encodings (Appendix H, steps 0-5)
return  <G(t_n, x = j/N)>  ~=  n_psi0 . n_G . |sqrt(Upsilon)|
    # error split (Lemma 15):  eps_CL + eps_Q <= eps,  eps_G ~ eps / (n_G n_psi0)
    # the advantage claimed is for computing observables, not for producing the
    # full solution vector

Cost, as the source states it

Computational cost independent of MM, the number of sets of initial data. Depending on the details of the initial data it can also display up to exponential advantage in both the dimension of the PDE and the error in computing its observables.

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.

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

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