Sign outOpen workspaceSign in

MethodLayer 1

Schrödingerisation (linear PDEs as Schrödinger equations)

A simple change of variable — the warped phase transformation, which introduces one extra variable — recasts any linear PDE or ODE system into a system of Schrödinger equations in real time, which ordinary Hamiltonian simulation then runs. The original solution is recovered from the auxiliary dimension.

Takes

A block-encoding of A(t)A(t) with a normalization αA≥max⁡t∥A(t)∥\alpha_A \ge \max_t \lVert A(t)\rVert, preparation unitaries for u0u_0 and bb, the evolution time TT, and an error tolerance ε\varepsilon.

Returns

A state proportional to u(T)u(T), or a history state, together with separately stated matrix-query and initial-state-query complexity.

Same contract as the slot it fills.

This one, drawn

Schrödingerisation (linear PDEs as Schrödinger equations)Linear multistep method, all-at-once encoding · 2 parts insideLinear multistep method, all-at-once encoding · 2 parts inside — click the line to open it hereTaylor propagator, all-at-once encoding · 2 parts insideTaylor propagator, all-at-once encoding · 2 parts inside — click the line to open it hereChebyshev spectral method, global collocation · 2 parts insideChebyshev spectral method, global collocation · 2 parts inside — click the line to open it hereDyson propagator, all-at-once encoding · 2 parts inside, openDyson propagator, all-at-once encoding · 2 parts inside, openDyson propagator, all-at-once encoding · 2 parts inside, open — click the line to close itTruncated Dyson series of the propagatorQuantum linear solve · 5 ways throughQuantum linear solve · 5 ways through — click the line to open it hereTime-marching with uniform singular value amplification · 2 parts insideTime-marching with uniform singular value amplification · 2 parts inside — click the line to open it hereLCHS — linear combination of Hamiltonian simulation · 3 parts insideLCHS — linear combination of Hamiltonian simulation · 3 parts inside — click the line to open it hereSchrödingerisation (linear PDEs as Schrödinger equations) · 3 parts inside, openSchrödingerisation (linear PDEs as Schrödinger equations) · 3 parts inside, openSchrödingerisation (linear PDEs as Schrödinger equations) · 3 parts inside, open — click the line to close itWarped phase transformationSimulate Hamiltonian evolution · 3 ways throughSimulate Hamiltonian evolution · 3 ways through — click the line to open it hereSchrödingerisation (linear PDEs as Schrödinger equations)Linear multistep method, all-at-once encoding · 2 parts inside — click the name to read about itMultistep, all-at-onceTaylor propagator, all-at-once encoding · 2 parts inside — click the name to read about itTaylor, all-at-onceChebyshev spectral method, global collocation · 2 parts inside — click the name to read about itSpectral methodDyson propagator, all-at-once encoding · 2 parts inside, open — click the name to close itDyson, all-at-onceTruncated Dyson series of the propagator — click the name to read about itTruncated Dyson seriesQuantum linear solve · 5 ways through — click the name to read about itQuantum linear solveTime-marching with uniform singular value amplification · 2 parts inside — click the name to read about itTime-marchingLCHS — linear combination of Hamiltonian simulation · 3 parts inside — click the name to read about itLCHSSchrödingerisation (linear PDEs as Schrödinger equations) · 3 parts inside, open — click the name to close itSchrödingerisationWarped phase transformation — click the name to read about itWarped phase transformationSimulate Hamiltonian evolution · 3 ways through — click the name to read about itSimulate Hamiltonian evolutionSchrödingerisation (linear PDEs as Schrödinger equations) — click the name to read about itinverse Fourier transform, keep p > 0Linear ODE system — you start hereAnswer about the solution — you finish hereLinear system Ax = b — what one part hands to the nextHamiltonian surrogate, with the map back — what one part hands to the nextCircuit for e^{-iHt} — 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 Linear ODE system 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.

7 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 linear ODE du/dt = A(t)u + b(t)

    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.

When it applies

Stated for general linear partial differential equations: unlike LCHS there is no positive-semidefiniteness requirement in order to form the Schrödinger system, and that is the structural difference between the two. The cost reappears at recovery: the original solution is read back from the warped variable, either as u(t,x)=∫0∞w(t,x,p)dpu(t,x) = ∫_0^∞ w(t,x,p) dp or pointwise as u(t,x)=ep∗w(t,x,p∗)u(t,x) = e^{p*} w(t,x,p*) for a chosen p∗>0p* > 0. Worked examples include the heat, convection, Fokker-Planck, linear Boltzmann and Black-Scholes equations, with extensions to the Vlasov-Fokker-Planck equation and to the Liouville representation equation for nonlinear ODEs — which is how a nonlinear problem reaches this method. The companion technical paper does prove gate-complexity theorems — Theorem 3.1 for the general method, recorded under cost — but in step sizes and qubit counts whose ε\varepsilon-dependence is left to the discretisation scheme, so no like-for-like count against the LCHS figures is given here.

Requires

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

Example

The short paper (arXiv:2212.13969) carries no numerical test and points elsewhere for one: "For more details and numerical experiments on justifying the setup in Eq. (14), see our technical companion paper". That companion's Example 2.1 is a classical spectral solve of the one-dimensional heat equation, and it tests the warped phase transformation — the recasting — rather than this route end to end. It is written up on the `warped-phase-transformation` record, where it belongs.

given  A from the spatial discretisation (in general non-Hermitian), u_0, evolution time t
#   du(t)/dt = -A u(t)

split A into Hermitian parts:
    A = H + i H_bar,   H = (A + A^dag)/2,   H_bar = i(A^dag - A)/2
#   to ensure stability, H is assumed positive semi-definite

# ---- hamiltonian-recasting, via the warped phase transformation ----
introduce p > 0 and set   v(t,p) = e^{-p} u(t)
extend the initial data:  v(0,p) = e^{-|p|} u(0)   on p in (-inf, inf)
#   v then satisfies  d_t v + H d_p v - i H_bar v = 0
Fourier transform in p:   i d_t v~ = (eta H + H_bar) v~
#   one Schrodinger equation for each eta, since eta H + H_bar is Hermitian
discretise eta:           i d/dt v~ = (H (x) D + H_bar (x) 1) v~ = H_total v~

# ---- hamiltonian-simulation ----
simulate the Hermitian H_total under sparse access to it
#   no linear system is assembled, and no time discretisation is chosen

# ---- this method's own stretch: read the answer back out of p ----
apply the inverse QFT F_p^{-1} on the p register to obtain |w(t)>
project onto p > 0:   1 (x) sum_{k=N/2}^{N} |k><k|
#   or pointwise instead: u(t,x) = e^{p*} w(t,x,p*) for a chosen p* > 0
amplitude-amplify with Q = -S_w S_p to recover |u(t)>

Cost, as the source states it

The companion technical paper states the general bound as Theorem 3.1: gate complexity NGates=(md+mp)O~(s(A)∣∣A∣∣max/Δp)+O(mplog⁡mp)N_{Gates} = (m_d + m_p) \tilde{O}( s(A) ||A||_{max} / \Delta p ) + O( m_p \log m_p ) for the spatially discretised linear system ∂tu=−Au\partial_t u = -A u, where s(A)s(A) is the sparsity of AA, mdm_d and mpm_p count the system and auxiliary-register qubits, and Δp\Delta p is the auxiliary variable's grid step; when H1H_1 diagonalises in the momentum basis and H2H_2 is diagonal this improves to T/Δt⋅O(dmlog⁡m+mplog⁡mp)T/\Delta t \cdot O(d m \log m + m_p \log m_p). Per-equation prices follow the same pattern — heat (Theorem 2.1), convection (Theorem 2.2), Black-Scholes (Theorem 4.1), linear Boltzmann (Theorem 4.3). All of these are deliberately stated in step sizes and qubit counts: the paper says the ε\varepsilon-dependence "is determined by the particular scheme one wishes to use", which is why no single ε\varepsilon-form figure is quoted here.

Implementations

  • Algorithm I — diagonal Hamiltonian evolution between QFTs, under first-order splitting

    The paper's own name for the cheap route, fixed in Remark 2.4: "we refer to the algorithm mentioned in [21,27] to implement eiHte^{iHt} as Algorithm I, where HH is a diagonal matrix". It is what the paper uses whenever the Schrödingerised generator can be brought to diagonal form — the heat, convection and Black-Scholes equations, and the special case of the general theorem. The two references it names for the diagonal-unitary implementation are outside this record and are not cited here.

    For the heat equation the Schrödingerised generator is H=(P12+⋯+Pd2−V)⊗DμH = (P_1^2 + \dots + P_d^2 - V) \otimes D_\mu, and it is solved by first-order time (Trotter) splitting: one step evolves the kinetic part, diagonal in the momentum basis as HD=((D1μ)2+⋯+(Ddμ)2)⊗DμH_D = ((D_1^\mu)^2 + \dots + (D_d^\mu)^2)\otimes D_\mu, the second evolves the potential part HV=V⊗DμH_V = V \otimes D_\mu, diagonal in the original basis, and a Fourier transform sits between them — c~n→eiHDΔt→c~∗→(Fx⊗I)→w~∗→e−iHVΔt→w~n+1→(Fx−1⊗I)→c~n+1\tilde c^n \to e^{iH_D\Delta t} \to \tilde c^* \to (F_x \otimes I) \to \tilde w^* \to e^{-iH_V\Delta t} \to \tilde w^{n+1} \to (F_x^{-1}\otimes I) \to \tilde c^{n+1}. Each one-dimensional quantum Fourier transform costs O(mlog⁡m)O(m\log m) gates and each diagonal unitary O(mH)O(m_H) gates, with mH=md+mpm_H = m_d + m_p, md=dmm_d = dm, m∼log⁡(1/Δx)m \sim \log(1/\Delta x) and mp∼log⁡(1/Δp)m_p \sim \log(1/\Delta p). The QFT on the pp register is not inside the loop: it "is only performed twice".

    Gate counts, not measurements. Theorem 2.1 for the heat equation gives NGates=T/Δt⋅O(dmlog⁡m+mplog⁡mp)N_{Gates} = T/\Delta t \cdot O(dm\log m + m_p\log m_p); Theorem 2.2 for the convection equation gives NGates=O((d+1)mlog⁡m)N_{Gates} = O((d+1)m\log m); Theorem 4.1 for Black-Scholes gives NGates=O(mlog⁡m+mplog⁡mp)N_{Gates} = O(m\log m + m_p\log m_p); and the special case of Theorem 3.1, when H1H_1 diagonalises in the momentum basis and H2H_2 is diagonal, returns the same T/Δt⋅O(dmlog⁡m+mplog⁡mp)T/\Delta t \cdot O(dm\log m + m_p\log m_p). Remark 3.3 adds that the splitting is unconditionally stable, so Δt=O(Δx)\Delta t = O(\Delta x) may be taken and the heat equation's count becomes T/Δx⋅O(dmlog⁡m+mplog⁡mp)T/\Delta x \cdot O(dm\log m + m_p\log m_p). The ε\varepsilon-dependence is left open deliberately — "for the given error bound ε\varepsilon, the ε\varepsilon-dependence of these quantities is determined by the particular scheme one wishes to use" — with the heat equation's mesh strategy given as Δx∼(ε/d)1/ℓ\Delta x \sim (\varepsilon/d)^{1/\ell}, Δt∼ε\Delta t \sim \varepsilon, Δp∼ε\Delta p \sim \varepsilon, and the note that the initial condition's lack of regularity "implies first-order accuracy on pp". No execution is reported: no device, no simulator, no counted circuit.

  • Algorithm II — sparse access Hamiltonian simulation

    The general route, imported rather than built: Lemma 3.1 is labelled "Algorithm II, Theorems 1-2 in [5]", which is Berry, Childs and Kothari's near-optimal sparse Hamiltonian simulation. It is what the paper uses when the Schrödingerised generator cannot be brought to diagonal form, and it is also the route the short paper takes for the heat equation, where the same lemma carries its Theorem 3 and Theorem 4.

    The Hamiltonian to be simulated is −i(H1⊗Dμ)+i(H2⊗I)-i(H_1 \otimes D_\mu) + i(H_2 \otimes I), reached from du(t)/dt=Au(t)du(t)/dt = Au(t) by splitting A=H1+iH2A = H_1 + iH_2, applying the warped phase transformation and Fourier transforming in pp. Access to it is the sparse-access 4-tuple (s,∥A∥max,OA,OF)(s, \|A\|_{max}, O_A, O_F) of Definition 3.1, with OA∣j⟩∣k⟩∣z⟩=∣j⟩∣k⟩∣z⊕Ajk⟩O_A|j\rangle|k\rangle|z\rangle = |j\rangle|k\rangle|z \oplus A_{jk}\rangle and OF∣j⟩∣l⟩=∣j⟩∣F(j,l)⟩O_F|j\rangle|l\rangle = |j\rangle|F(j,l)\rangle, where FF returns the column index of the ll-th non-zero element in row jj. Lemma 3.1 then simulates an ss-sparse HH on mHm_H qubits within error ε\varepsilon using O(τlog⁡(τ/ε)/log⁡log⁡(τ/ε))O(\tau\log(\tau/\varepsilon)/\log\log(\tau/\varepsilon)) queries and O(τ(mH+log⁡2.5(τ/ε))log⁡(τ/ε)/log⁡log⁡(τ/ε))O(\tau(m_H + \log^{2.5}(\tau/\varepsilon))\log(\tau/\varepsilon)/\log\log(\tau/\varepsilon)) additional two-qubit gates, with τ=s∥H∥maxt\tau = s\|H\|_{max}t. The generator is assumed not to move: "in the sequel, we assume AA is independent of time", with time-dependent Hamiltonians left to other references.

    Theorem 3.1's general bound, NGates,Schr=(md+mp)O~(s(A)∥A∥max/Δp)+O(mplog⁡mp)N_{Gates,Schr} = (m_d + m_p)\tilde{O}(s(A)\|A\|_{max}/\Delta p) + O(m_p\log m_p), which this record already carries under cost, and Theorem 4.3 for the linear Boltzmann equation, whose count is assembled from two applications of the lemma. Where the auxiliary variable is charged is stated explicitly: ∥Dμ∥max≲1/Δp\|D_\mu\|_{max} \lesssim 1/\Delta p inside the proof, and the paper's own warning that for the convection equation of §2.2, whose pp-derivative is second order, this "leads to 1/Δp21/\Delta p^2 as the multiplicative factor in the time complexity if Algorithm II is used". The short paper reaches the same shape from the other end, O~((∥u(0)∥/∥u(t)∥)st∥H∥max/ε)\tilde{O}((\|u(0)\|/\|u(t)\|)st\|H\|_{max}/\varepsilon) in its Theorem 3. No execution is reported for any of it.

What it needs

  1. Recast a non-Hermitian generator as Hamiltonian evolution 2 methods

    Given a generator A(t)A(t) whose evolution is not unitary, produce a Hermitian generator — or a quadrature-indexed family of them — on a space at least as large, whose unitary evolution reproduces the original dynamics, together with the map that recovers the original solution. Both halves are required: a construction that reaches a Hamiltonian and cannot get back is not a route.

  2. Simulate Hamiltonian evolution 3 methods

    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.

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

  • Linear multistep method, all-at-once encoding

    The first quantum algorithm for general linear ODEs. Discretize with a high-order linear multistep method, lay every time step out at once against a clock register so that one state ∑j∣tj⟩∣xj⟩\sum_j |t_j\rangle|x_j\rangle holds the whole history, and solve the resulting sparse linear system with a quantum linear system algorithm. Going high-order is what buys the Δt\Delta t scaling: plain Euler costs at least O(Δt4)O(\Delta t^4) here.

  • Taylor propagator, all-at-once encoding

    Encode a truncated Taylor series of the propagator into a single sparse linear system approximating the whole evolution, then solve it with a quantum linear system algorithm. This is what brought the precision dependence down to polynomial in log⁡(1/ε)\log(1/\varepsilon).

  • Chebyshev spectral method, global collocation

    The route that brought poly(log⁡(1/ε))\mathrm{poly}(\log(1/\varepsilon)) precision to linear ODEs with **time-dependent** coefficients, which is what its abstract says was missing: "no such algorithm was previously known for differential equations with time-dependent coefficients". It does it by not stepping. The solution is approximated globally by a truncated Chebyshev series, the coefficients are fixed by collocating the differential equation at Chebyshev nodes, and the resulting sparse system goes to a high-precision quantum linear system algorithm. The exponential precision is bought by smoothness rather than by the solver: it is the C∞C^{\infty} convergence of the Chebyshev series that makes the series length logarithmic in 1/ε1/\varepsilon.

  • Krovi's reanalysis of the all-at-once encoding a narrower version of Taylor propagator, all-at-once encoding

    Reanalyses the all-at-once propagator encoding and shows that the norm of the matrix exponential, rather than the eigenvector condition number, characterizes the run time. It still forms a global linear system and still calls a quantum linear solver.

  • Dyson propagator, all-at-once encoding

    Encode the Dyson series in a system of linear equations and solve it via the optimal quantum linear equation solver, extending the all-at-once approach to genuinely time-dependent generators.

  • Time-marching with uniform singular value amplification

    Propagate the solution one step at a time and defeat the exponentially vanishing success probability by repeatedly invoking uniform singular value amplification, improved further by a compression gadget lemma. Fang, Lin and Tong present it explicitly as a design path alternative to solvers based on quantum linear systems algorithms.

  • LCHS — linear combination of Hamiltonian simulation

    Express a general non-unitary evolution operator as a linear combination of unitary evolution operators, each of which solves a Hamiltonian simulation problem, rather than converting the problem into a dilated linear system. An, Liu and Lin state that the method can achieve optimal cost in terms of state preparation.

  • LCHS with the improved kernel a narrower version of LCHS — linear combination of Hamiltonian simulation

    A family of identities expressing non-unitary evolution as a linear combination of unitary evolutions, built on the kernel f(z)=1/(Cβe(1+iz)β)f(z) = 1/(C_β e^{(1+iz)^β}) with β∈(0,1)β ∈ (0,1) and Cβ=2πe−2βC_β = 2π e^{-2^β}. The kernel decays at a near-exponential rate e−c∣k∣βe^{-c|k|^β}, replacing the original Cauchy kernel's quadratic decay and exponentially enhancing accuracy.

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