Sign outOpen workspaceSign in

MethodLayer 0

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.

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 simulation of the KvN representationQuantum 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 inside, openQuantum simulation of the KvN representation · 3 parts inside, openQuantum simulation of the KvN representation · 3 parts inside, open — click the line to close itKoopman-von Neumann lift to phase-space densitiesSimulate Hamiltonian evolution ×4K · 3 ways throughSimulate Hamiltonian evolution ×4K · 3 ways through — click the line to open it hereCoherent amplitude-estimation readoutLevel-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 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, open — click the name to close itKvN simulationKoopman-von Neumann lift to phase-space densities — click the name to read about itKoopman–von Neumann liftSimulate Hamiltonian evolution ×4K · 3 ways through — click the name to read about itSimulate Hamiltonian evolution ×4KCoherent amplitude-estimation readout — click the name to read about itCoherent amplitude-estimation readoutLevel-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 — 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 nextHermitian generator — what one part hands to the nextEvolution circuit, input in hand — 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

The exponential claim holds when the Koopman-von Neumann Hamiltonian is sparse — Joseph glosses this as local or banded — and is stated against a deterministic Eulerian discretization of the Liouville equation, not against the best classical method; Joseph says himself that the more interesting comparison is against the best probabilistic classical algorithm, where the gain falls to quadratic. The quadratic claim is conditioned instead on using quantum walks for state preparation and amplitude estimation for observables, not on sparsity. The output is the state psi = f^(1/2) e^(i phi), whose modulus squared is the phase-space density, and the readout Joseph supplies is for observables; measuring the entire PDF over all states is something he calls undesirable, so a trajectory-level answer is a separate problem the paper does not solve.

Requires

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

Example

given  a nonlinear, possibly non-Hamiltonian classical system dx/dt = v(x,t),
       an observable O on phase space, an evolution time, and accuracy eps

# --- nonlinear-linear-embedding, via koopman-von-neumann-lift --------------
lift   the Liouville equation for the phase-space density f onto the KvN
       Schroedinger equation  i hbar d_t psi = H_hat psi,  psi = f^(1/2) e^(i phi)
           H_hat = (1/2)( P_hat . v_hat + v_hat . P_hat ) + W_hat,  P_hat = -i hbar grad
       # H_hat is HERMITIAN and its propagator unitary.  That is the narrowing:
       # nothing is dilated and no linear system is assembled, so this route
       # bypasses both time-discretization and quantum-linear-solve
       # the lift is exact; its price is dimension, twice the classical
       # phase space

# --- put H_hat on a finite register ---------------------------------------
make   each coordinate x^j periodic on X_max^j with L_j levels,
           dx^j = X_max^j / L_j
       so the conjugate momentum also has L_j levels,
           dP_j = h / X_max^j,   range  P_j,max = h L_j / X_max^j
prepare the initial PDF as a SQUEEZED state: squeezing x^j by L_j^(-1/2) gives
           sigma_x^j = dx^j, the limit set by the discretization
       # keep initialization sparse -- e.g. near a Maxwell-Boltzmann
       # equilibrium, prepared by quantum walk.  Setting each initial condition
       # individually is not desirable

# --- hamiltonian-simulation, landing on a runnable evolution ---------------
simulate the unitary evolution generated by H_hat
       if H_hat is sparse (local or banded):
           split H_hat = sum_{j=1..m} H_j, m independent of the number of
               states N, and use a Trotter-Suzuki product formula
               # error proportional to sum_{j != k} <[H_j, H_k]>
       as general s-sparse simulation on n qubits, the cost is ~ s n T,
           T = || H_hat t ||_max, read as the number of required time steps
       # circuit + prepared input IS the routine for the state:
       # "the KvN simulation computes the state |psi>"

# --- observable-estimation, via amplitude-estimation-readout ---------------
append an ancillary qubit and build R_phi with phi = O^(1/2) psi:
           R_phi |psi>|0> = N^(-1/2) sum_x |x> ( phi'(x)|0> + phi(x)|1> )
       # R_phi is a reversible computation of phi and costs two KvN
       # simulations: one to compute phi, one to uncompute it by running the
       # KvN simulation backward in time
amplitude-estimate the amplitude of the ancillary |1> state
       # R_phi is a rotation by sin(theta) = <O/N>^(1/2)

repeat, coherently, 4K ~ O(1/eps) KvN simulations
       # R_phi and R_phi^dagger use two evaluations of |psi> each, so one
       # amplification step is four KvN simulations
       # averaging repeated projective measurements instead returns to the
       # classical O(1/eps^2) sampling law; overall complexity O(s D T / eps)

return <O> = sum_x O(x) f(x), an estimate to accuracy eps
       # a number, not a state.  Measuring the entire PDF over all states is
       # "not desirable", so a trajectory-level answer is a separate problem
       # this paper does not solve

Cost, as the source states it

Exponentially more efficient than a deterministic Eulerian discretization of the Liouville equation if the Koopman-von Neumann Hamiltonian is sparse — an exponential speedup in the phase-space dimension DD and a polynomial one in the number LL of grid points taken in each direction. Joseph also reports a quadratic improvement, up to polylogarithmic factors, over classical probabilistic Monte Carlo algorithms when quantum walk techniques are used for state preparation and amplitude estimation for the calculation of 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.

Where the claim is contested

Joseph limits both claims himself. On the exponential one: some important calculations can require a large number of time steps, potentially scaling as a power of DD, which would reduce the expected savings to polynomial at best. On the quadratic one: because the Koopman-von Neumann lift doubles the phase-space dimension, if the gains over classical Monte Carlo are only quadratic then that doubling would effectively eliminate the advantage — so where the underlying system is Hamiltonian and simulating the quantized Hamiltonian system suffices for the intended calculation, he states that quantizing the Hamiltonian is the more efficient approach.

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. Simulate Hamiltonian evolution 3 methodsruns 4K ∼ O(1/ε) KvN simulations — "the KvN simulation must be repeated 4K ∼ O(1/ε) times"

    Implement e−iHte^{-iHt} to error ε\varepsilon given some access model for HH. It is an application in its own right and also the engine inside phase estimation and several linear-system solvers.

    The loop stays coherent: nothing is measured between turns. The preparation may still be reapplied every turn — what the loop never pays is a readout and a restart from classical data. The price is depth, and a success probability that multiplies down the chain. The loop is the readout's, and what it turns is the simulation below: each amplification step evaluates R̂_φ and R̂_φ† once each, and each evaluation runs the simulation twice — forward to compute φ = O^{1/2}ψ, backward to uncompute it — so one step is four KvN simulations and K ∼ O(1/ε) steps buy accuracy ε. Coherent invocations are the whole price difference: averaging repeated measurements instead would return to the classical 1/ε² law.

  3. Estimate an observable 4 methods

    Given the ability to prepare ∣ψ⟩|ψ⟩ and a description of an observable OO, return a classical scalar within ε\varepsilon of ⟨O⟩⟨O⟩ at confidence 1−δ1−δ. The state is never returned; only the number is.

Slots it makes unnecessary

These do not fill the slot. They replace the span it belongs to, so this layer is not on their path at all.

  • Quantum linear solve

    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.

  • Choose a time discretization or propagator approximation

    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.

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.

  • 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

Sources