Sign outOpen workspaceSign in

MethodLayer 0

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.

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

Quantum Carleman linearization algorithmQuantum 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

Requires R<1R < 1 with R=(1/∣Re(λ1)∣)(∣∣uin∣∣∣∣F2∣∣+∣∣F0∣∣/∣∣uin∣∣)R = (1/|Re(\lambda_1)|)(||u_in|| ||F_2|| + ||F_0||/||u_in||), F1F_1 diagonalizable with Re(λn)≤…≤Re(λ1)<0Re(\lambda_n) \leq \ldots \leq Re(\lambda_1) < 0, and sparse access to F0F_0, F1F_1 and F2F_2. Theorem 1 additionally assumes ∣∣F0∣∣≤∣∣F2∣∣||F_0|| \leq ||F_2|| and normalizes so that ∣∣uin∣∣<1||u_in|| < 1. Exponential decay of the solution precludes efficiency because it inflates q=∣∣uin∣∣/∣∣u(T)∣∣q = ||u_in||/||u(T)||, so the useful regime is driven equations that avoid decay despite the dissipation. Krovi's later analysis relaxes the hypothesis on the dissipative matrix: it handles any sparse, invertible matrix with a negative log-norm, including non-diagonalizable ones, where Liu et al. and Xue et al. additionally require normality.

Requires

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

Example

given  quadratic ODE   du/dt = F_2 u^(x)2 + F_1 u + F_0(t),   u(0) = u_in     (Problem 1)
       F_2, F_1, F_0 s-sparse;  F_1 diagonalizable with
           Re(lambda_n) <= ... <= Re(lambda_1) < 0
       sparse-access oracles O_F2, O_F1, O_F0;  O_x : |00...0> -> |u_in>
       known ||u_in||, Re(lambda_1), ||F_2||, ||F_1||, ||F_0(t)||, ||F_0||, ||F_0'||
       horizon T,  error tolerance eps <= 1,  and g = ||u(T)||, q = ||u_in||/||u(T)||

requires  R = (1/|Re(lambda_1)|) (||u_in|| ||F_2|| + ||F_0||/||u_in||) < 1,
          and ||F_0|| <= ||F_2||
    # R >= sqrt(2): the same paper proves the general quadratic ODE problem
    #   intractable there -- any quantum algorithm has worst-case complexity
    #   exponential in T.  1 <= R < sqrt(2) is left open.
    # exponential decay of the solution precludes efficiency because it inflates q,
    #   so the useful regime is driven equations that avoid decay despite dissipation

# --- rescale first: R is invariant, and this buys the two normalisations used below
gamma = 1 / sqrt(||u_in|| r_+),
    r_+ = (-Re(lambda_1) + sqrt(Re(lambda_1)^2 - 4 ||F_2|| ||F_0||)) / (2 ||F_2||)
u <- gamma u        # gives ||u_in|| < 1 and ||F_2|| + ||F_0|| < |Re(lambda_1)|

set  delta = g eps / (1 + eps)          # <= g/2; split half here, half at Euler

# --- nonlinear-linear-embedding, via carleman-linearization -------------------
N = ceil( log(2 T ||F_2|| / delta) / log(1/||u_in||) )
    # half the budget:  ||u(T) - yhat_1(T)|| <= delta/2  by Lemma 2
lift   yhat_j = u^(x)j,   yhat_in = [u_in; u_in^(x)2; ...; u_in^(x)N]
build  dyhat/dt = A(t) yhat + b(t),   b(t) = [F_0(t); 0; ...; 0]
       A(t) tri-diagonal in blocks:
           A^j_{j+1} = F_2 (x) I^(x)(j-1) + ... + I^(x)(j-1) (x) F_2
           A^j_j     the same sum built from F_1
           A^j_{j-1} the same sum built from F_0(t)
    # the lift itself is exact; all of the error comes from the truncation at N
    # A is (3Ns)-sparse;  dimension Delta = n + n^2 + ... + n^N = O(n^N)

# --- time-discretization, via forward-euler ----------------------------------
h = min{ g eps / (12 N^2.5 T [(||F_2||+||F_1||+||F_0||)^2 + ||F_0'||]),   # other half
         1 / (N ||F_1||),
         2 (|Re(lambda_1)| - ||F_2|| - ||F_0||)
           / (N (|Re(lambda_1)|^2 - (||F_2||+||F_0||)^2 + ||F_1||^2)) }
    # h <= 1/(N ||F_1||) alone suffices when the eigenvalues of F_1 are all real
    # the last two entries are what ensure ||I + Ah|| <= 1, which Lemma 3's
    #   linear-in-T error bound and Lemma 4's condition number both rest on
m = p = ceil(T / h)

# explicit: each step's recurrence is evaluated, never solved
#     y^{k+1} = [I + A(kh)h] y^k + b(kh),   y^0 = y_in = yhat_in
# and all y^k are held equal for k = m+1 ... m+p  (the padding steps)

assemble the banded all-at-once system  L|Y> = |B>  over all m+p+1 blocks:
    row 0     :  y^0                                = y_in
    row k     :  y^k - [I + A((k-1)h)h] y^{k-1}     = b((k-1)h)     1 <= k <= m
    row k     :  y^k - y^{k-1}                      = 0             m <  k <= m+p
    # (m+p+1)Delta x (m+p+1)Delta, lower triangular, O(Ns) nonzeros per row or
    #   column, condition number at most 3(m+p+1)                    (Lemma 4)

# --- own work: prepare the right-hand side -----------------------------------
embed y_in into z_in = [u_in (x) v_0^{N-1}; ...; u_in^(x)N]   # tensor structure
prepare |B> from ||z_in|| |0>|z_in> and ||b((k-1)h)|| |k>|b((k-1)h)>, k = 1..m,
        over the normalising factor B_m
    # O(N) queries to O_x and O(m) queries to O_F0                  (Lemma 5)

# --- quantum-linear-solve ----------------------------------------------------
solve L|Y> = |B> with the high-precision QLSA of Childs, Kothari and Somma
    # this route reduces to a quantum linear solve; it does not remove that layer.
    #   the whole horizon is handed down once, not one solve per time step
    # the QLSA's own error is the third contribution and is bounded separately,
    #   at poly(log(1/eps)) cost

# --- own work: extract the answer --------------------------------------------
measure k and accept iff k lies in {m, m+1, ..., m+p}
    # those p+1 blocks all hold y_1^m, the state at time T, up to normalisation
    # one round succeeds with probability >= (p+1)/(9(m+p+1) N q^2) = Omega(1/N q^2)
repeat coherently: O(sqrt(N) q) rounds of amplitude amplification give Omega(1)

return  y_1^m / ||y_1^m||  --  a state eps-close to u(T)/||u(T)||, with a flag
        indicating success

# end-to-end cost, under R < 1:
#     T^2 q poly(log T, log n, log 1/eps) / eps                      (Theorem 1)

Cost, as the source states it

T2q poly(log⁡T,log⁡n,log⁡1/ε)/εT^2 q\,\mathrm{poly}(\log T, \log n, \log 1/\varepsilon)/\varepsilon, where TT is the evolution time, ε\varepsilon the allowed error, nn the dimension and qq measures decay of the solution — stated in the abstract under the assumption R<1R < 1.

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

The same paper proves the general quadratic ODE problem is intractable for R ≥ √2: any quantum algorithm then has worst-case complexity exponential in TT. Penuel et al. cost out end to end a neighbouring Carleman-linearized lattice Boltzmann workflow — same lift, a different time discretization and a different linear solver — for drag on a sphere, and find (logical qubits)×(T-gates) ranging from 10^21 to 10^39 over Reynolds numbers 10^1 to 10^8, with quantum resource scaling O(Re^2.68) against classical direct numerical simulation at O(Re^3): in their words, no exponential quantum advantage. They attribute that to explicit time-evolution of nonlinear differential equations subject to the CFL condition or a similar condition linking time step to grid spacing, not to one implementation.

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. Choose a time discretization or propagator approximation 6 methods

    Reduce continuous evolution over [0,T][0,T] to a finite algebraic object — a banded linear system, a product of step propagators, or a spectral coefficient system — with a stated truncation error. When a linear system is formed, a conditioning bound is stated with it.

  3. Quantum linear solve 5 methods

    Given access to a matrix AA and a unitary that prepares ∣b>|b>, produce a flagged quantum state that is ε\varepsilon-close in l2l2 to the normalised A−1bA^{-1}b. The deliverable is a state, not a classical vector.

Other ways to fill the same slot

Different approaches

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

  • 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