Sign outOpen workspaceSign in

MethodLayer 1

Krovi's reanalysis of the 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.

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

Krovi's reanalysis of the all-at-once encodingLinear 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 inside, openTaylor propagator, all-at-once encoding · 2 parts inside, opennarrower versions, nested under the line they refineTaylor propagator, all-at-once encoding · 2 parts inside, open — click the line to close itKrovi's reanalysis of the all-at-once encoding, a narrower version of Taylor propagator, all-at-once encoding · 2 parts inside, openKrovi's reanalysis of the all-at-once encoding, a narrower version of Taylor propagator, all-at-once encoding · 2 parts inside, openKrovi's reanalysis of the all-at-once encoding, a narrower version of Taylor propagator, all-at-once encoding · 2 parts inside, open — click the line to close itChoose a time discretization or propagator approximation · 6 ways throughChoose a time discretization or propagator approximation · 6 ways through — click the line to open it hereQuantum linear solve · 5 ways throughQuantum linear solve · 5 ways through — click the line to open it hereTruncated Taylor series of the propagatorQuantum linear solve · 5 ways throughQuantum linear solve · 5 ways through — 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 insideDyson propagator, all-at-once encoding · 2 parts inside — 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 insideSchrödingerisation (linear PDEs as Schrödinger equations) · 3 parts inside — click the line to open it hereLinear 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, open — click the name to close itTaylor, all-at-onceKrovi's reanalysis of the all-at-once encoding, a narrower version of Taylor propagator, all-at-once encoding · 2 parts inside, open — click the name to close itKrovi's reanalysisChoose a time discretization or propagator approximation · 6 ways through — click the name to read about itDiscretize time or the propagatorQuantum linear solve · 5 ways through — click the name to read about itQuantum linear solveTruncated Taylor series of the propagator — click the name to read about itTruncated Taylor propagatorQuantum linear solve · 5 ways through — click the name to read about itQuantum linear solveChebyshev spectral method, global collocation · 2 parts inside — click the name to read about itSpectral methodDyson propagator, all-at-once encoding · 2 parts inside — click the name to read about itDyson, all-at-onceTime-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 — click the name to read about itSchrödingerisationLinear ODE system — you start hereAnswer about the solution — you finish hereLinear system Ax = b — what one part hands to the nextLinear system Ax = b — 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.

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

A narrower version of Taylor propagator, all-at-once encoding

When it applies

Extends to many classes of non-diagonalizable matrices, which the Berry-Childs-Ostrander-Wang analysis required to be diagonalizable, and is exponentially faster than those bounds for certain classes of diagonalizable matrices. Applied back to nonlinear ODEs through Carleman linearization, it handles any sparse, invertible matrix modelling dissipation that has a negative log-norm, where Liu et al. and Xue et al. additionally require normality. It improves the constant of the bottleneck; it does not remove the quantum-linear-solve layer.

Requires

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

Example

Krovi (arXiv:2202.01054) integrates no differential equation and names no quantum linear solver, no hardware and no simulator. Its one piece of numerical work, Section 3.1 with Figure 2, measures the condition number of the linear system the discretisation hands down to the solver, on the tridiagonal twisted-Toeplitz family of Eq. (3.10) at dimensions 15 to 100 — a quantity from inside the method, not a run of it.

given  sparse A, b, x_0 through the oracles O_A, O_b, O_x;  horizon T;  error e

choose the parameters (Theorem 7):
    h = T / ceil(T ||A||),   m = p = T/h = ceil(T ||A||),   delta <= e/2
    Omega = e^3 T ||A|| (1 + T e^2 ||b|| / ||x_T||)
    k = ceil( 2 log Omega / log log Omega )        # this choice makes (k+1)! > Omega

# the discretization is the parent's truncated Taylor recurrence:
#     y_{i+1} = T_k(Ah) y_i + S_k(Ah) h b        over the m steps
# what is different here is the operator it is packed into

build  L = I - N  from block encodings:
    M_1 = sum_{j=0..k-1}  |j+1><j|  (x)  Ah/(j+1)
    M_2 = sum_{j=0..k}    |0><j|    (x)  I
    N   = sum_{i=0..m}       |i+1><i| (x) M_2 (I - M_1)^{-1}
        + sum_{i=m+1..m+p-1} |i+1><i| (x) I          # the p padding steps, the "ramp"

prepare  |psi_in> = |0,0,x_0> + h sum_{i=0..m-1} |i,1,b>
    # one call each to O_x and O_b, plus polylog(m) elementary gates

solve  L |y> = |psi_in>  with the QLSA               # the layer below
    # kappa_L <= (m+p) C(A) (1+delta) e (1+e),  C(A) = sup_{t in [0,T]} ||exp(At)||
    # this is the whole point of the reanalysis: the kappa charged here is bounded
    # through the norm of the matrix exponential, not through kappa_V

measure the time-step register; keep the outcomes m, ..., m+p-1
    # succeeds with probability >= 1/(18 g^2),  g = max_t ||x(t)|| / ||x(T)||
    # amplitude amplification to constant success multiplies the cost by g

return the collapsed state  y_m / ||y_m||            # within 2*delta <= e of x_T/||x_T||

Cost, as the source states it

The paper's own framing: the norm of the matrix exponential characterizes the run time of quantum algorithms for linear ODEs. The precise bound is not reproduced here.

Implementations

  • Block-encoded circuit construction (sections 4 and 5.4)

    Krovi's own account of why a second linear system was built rather than the published one reused: the linear system is different in his case and he implements it using the techniques of block encoding, and the reason he picks a different linear system is that it is easier to analyze. The problem it is built for is Problem 1 — given a stable, sparse d×dd \times d matrix AA reachable only through oracles, produce a quantum state proportional to the solution x(T)x(T) of x˙=Ax+b\dot{x} = Ax + b, x(0)=x0x(0) = x_0, to within error ε\varepsilon in l2l_2 norm.

    The operator L=I−NL = I - N is never held as a matrix. I−M1I - M_1 is (sr+1,sc+1)(s_r+1, s_c+1)-sparse and has condition number at most 2k2k, since ∥I−M1∥≤2\lVert I - M_1 \rVert \le 2 and ∥(I−M1)−1∥=∥I+M1+⋯+M1k−1∥≤k\lVert (I-M_1)^{-1}\rVert = \lVert I + M_1 + \cdots + M_1^{k-1}\rVert \le k; it is block encoded from the sparse-access oracles by Lemma 1 as a (srsc,O(log⁡dk),ϵ0)(\sqrt{s_r s_c}, O(\log dk), \epsilon_0) block unitary at cost O(log⁡(dk)+log⁡2.5(s/ϵ0))O(\log(dk) + \log^{2.5}(s/\epsilon_0)). Its inverse is produced by Lemma 2 as an (α1,a1,ϵ1)(\alpha_1, a_1, \epsilon_1) block unitary with α1=2k\alpha_1 = 2k at cost O(sk(log⁡(dk)+log⁡2.5(k/ϵ1)))O(sk(\log(dk) + \log^{2.5}(k/\epsilon_1))), the factor 2k2k coming from that condition number. M2M_2 is (k,1)(k,1)-sparse with unit entries and is encoded by Lemma 1 with α2=k\alpha_2 = \sqrt{k}; the product M2(I−M1)−1M_2(I-M_1)^{-1} and then I−NI - N follow from two applications of Lemma 3. The initial state proportional to ∣ψin⟩=∣0,0,x0⟩+h∑i=0m−1∣i,1,b⟩\lvert \psi_{in}\rangle = \lvert 0,0,x_0\rangle + h\sum_{i=0}^{m-1}\lvert i,1,b\rangle is prepared by Lemma 14 with a single call each to OxO_x and ObO_b plus polylog(m)\mathrm{polylog}(m) elementary gates: a one-qubit rotation setting the weights ∥x0∥\lVert x_0 \rVert and mh∥b∥\sqrt{m}h\lVert b \rVert, the two oracles applied conditionally on that qubit, and a controlled rotation spreading the first register uniformly over the mm time-step labels. The block QLSA of Theorem 1 is then applied at O(κLlog⁡(1/ε))O(\kappa_L\log(1/\varepsilon)) uses of those encodings and of the state preparation. To hold the total error at ε\varepsilon the per-factor errors are tied together as ϵ1=ϵ2≤O(ε/(κLklog⁡(1/ε)))\epsilon_1 = \epsilon_2 \le O(\varepsilon/(\kappa_L k \log(1/\varepsilon))), which fixes α3=O(k1.5)\alpha_3 = O(k^{1.5}) and the ancilla count a=O(log⁡(mκLdklog⁡(1/ε)/ε))a = O(\log(m\kappa_L dk\log(1/\varepsilon)/\varepsilon)).

    No dataset. The inputs are oracles fixed by Definition 1: OrO_r and OcO_c returning the positions of the nonzero entries of AA, OAO_A returning their bb-bit values, and unitaries OxO_x and ObO_b preparing x0/∥x0∥x_0/\lVert x_0\rVert and b/∥b∥b/\lVert b\rVert with both norms assumed known. The paper states this input model is the same one prior work on quantum algorithms for differential equations uses.

    The construction is carried as far as counted complexity and no further. Theorem 6 gives the QLSA applied to this system a query complexity O(skκL polylog(k,m,d,κL,1/ε))O(sk\kappa_L\,\mathrm{polylog}(k, m, d, \kappa_L, 1/\varepsilon)), with gate complexity larger by at most O(polylog(k,m,1/ε))O(\mathrm{polylog}(k, m, 1/\varepsilon)), and Theorem 7 assembles the whole algorithm at O(gT∥A∥C(A) poly(s,log⁡d,log⁡(1+Te2∥b∥/∥xT∥),log⁡(1/ε),log⁡(T∥A∥C(A))))O(gT\lVert A\rVert C(A)\,\mathrm{poly}(s, \log d, \log(1 + Te^2\lVert b\rVert/\lVert x_T\rVert), \log(1/\varepsilon), \log(T\lVert A\rVert C(A)))) queries, where g=max⁡t∈[0,T]∥x(t)∥/∥x(T)∥g = \max_{t \in [0,T]}\lVert x(t)\rVert/\lVert x(T)\rVert. No hardware and no simulator is named anywhere in the paper, so this implementation exists as a specified circuit and not as an executed one.

What it needs

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

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

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

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

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

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