Stated for constant-coefficient $A$. Berry, Childs, Ostrander and Wang describe the resulting object as a sparse, well-conditioned linear system, and state that unlike with finite difference methods their approach does not require additional hypotheses to ensure numerical stability.

The generator $A(t)$, the interval $[0,T]$, an error tolerance $\varepsilon$, and a target algebraic form.

1. Linear ODE system → Linear system Ax = bexpand the propagator to order k, as rows

   The propagator over one step is replaced by $T_k(Ah) = \sum_{j=0}^{k}(Ah)^j/j!$, whose terms become extra rows of the linear system. approximation: For $\lvert z\rvert \le 1$ and $\operatorname{Re}(z) \le 0$, Lemma 10 gives $\lvert T_k(z) - e^{z}\rvert \le 1/(k+1)!$ and Lemma 12 gives $\lvert S_k(z) - (e^{z}-1)z^{-1}\rvert \le 1/(k+1)!$, and Theorem 6 accumulates these into $\lVert x(jh) - x_{j,0}\rVert \le 2.8\,\kappa_V\,j\,(\lVert x_{\mathrm{in}}\rVert + mh\lVert b\rVert)/(k+1)!$. Because the bound falls factorially in $k$, for the quantity $\Omega$ of Eq. (114) the order $k = \lceil 2\log\Omega/\log\log\Omega\rceil$ already gives $(k+1)! \ge \Omega$ — accuracy is bought by adding rows rather than by shrinking $h$ and lengthening the system. assumption: $A$ has constant coefficients and is diagonalizable as $A = VDV^{-1}$ with $\operatorname{Re}(\lambda_i) \le 0$, the step satisfies $\lVert Ah\rVert \le 1$, and $k \ge 5$ with $(k+1)! \ge 2m$.

   approximationassumption

The discrete object, its truncation-error bound, and its conditioning bound.

Its only source is arXiv:1701.03684, and the full-text read that settled `taylor-all-at-once` above settles this record too: the paper reports no numerics of any kind. Nothing about the truncated propagator was run separately either.

given  A (constant coefficients), b, u_0, horizon T, error budget e

choose k so that the truncation error of  sum_{j=0..k} (hA)^j / j!  is below e
    # the error falls factorially in k, so accuracy is bought by adding rows
    # rather than by shrinking h and lengthening the system

assemble a sparse linear system whose extra rows carry the k Taylor terms:
    for j = 1 ... k:  the row for (hA)^j / j!  is built from the row for
                      (hA)^{j-1} / (j-1)!
    plus the rows tying the truncated propagator to the step's output state

hand the system to the layer below
    # the source describes the result as sparse and well-conditioned: unlike
    # finite difference methods, no additional hypothesis is needed to ensure
    # numerical stability

The resulting algorithm's complexity is polynomial in the logarithm of the inverse error, an exponential improvement over previous quantum algorithms for this problem. That is a statement about the full algorithm, not a standalone cost for the discretization.

• The matrix family $C_{m,k,p}$ of Definition 1 (section 2)

  • Quantum algorithm for linear differential equations with exponentially improved dependence on precision

    Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, Guoming Wang · 2017

  About

  How the truncation becomes rows, in the paper's own order. Section 2 starts from the exact solution $\vec{x}(t) = \exp(At)\vec{x}(0) + (\exp(At)-I)A^{-1}\vec{b}$ and, for a short step $h \le 1/\lVert A\rVert$ and large $k$, approximates it by $\vec{x}(h) \approx T_k(Ah)\vec{x}(0) + S_k(Ah)h\vec{b}$ with $T_k(z) = \sum_{j=0}^{k}z^j/j!$ and $S_k(z) = \sum_{j=1}^{k}z^{j-1}/j!$. The approximate solution is then used as the initial condition of a further step and the procedure repeated for $m$ steps, and what is encoded is that whole procedure rather than a single step. Section 1 places the encoding against the alternative it replaces: because it effectively implements a linear combination of operations, the approach is conceptually similar to quantum simulation by a linear combination of unitaries, but the combination is constructed stepwise through a system of linear equations instead of applied directly.

  Methods

  Definition 1 writes the family explicitly as $C_{m,k,p}(A) = \sum_{j=0}^{d}\lvert j\rangle\langle j\rvert \otimes I - \sum_{i=0}^{m-1}\sum_{j=1}^{k}\lvert i(k+1)+j\rangle\langle i(k+1)+j-1\rvert \otimes A/j - \sum_{i=0}^{m-1}\sum_{j=0}^{k}\lvert (i+1)(k+1)\rangle\langle i(k+1)+j\rvert \otimes I - \sum_{j=d-p+1}^{d}\lvert j\rangle\langle j-1\rvert \otimes I$ with $d = m(k+1)+p$, the first register labelling the block structure. Read as equations, the rows are $\lvert x_{0,0}\rangle = \lvert x_{\mathrm{in}}\rangle$; the Taylor-term rows $x_{i,j} = (Ah/j)\,x_{i,j-1}$ for $2 \le j \le k$, with $\lvert x_{i,1}\rangle = Ah\lvert x_{i,0}\rangle + h\lvert b\rangle$ carrying the inhomogeneity; the row that closes a step, $\lvert x_{i,0}\rangle = \sum_{j=0}^{k}x_{i-1,j}$ for $1 \le i \le m$; and $p$ padding rows $x_{m,j} = x_{m,j-1}$ that hold the solution constant after the last step, so that a measurement has a significant probability of landing on the final time. Solving these gives $\lvert x_{i,0}\rangle$ as an approximation of the state at time $ih$ and $x_{i,j} = ((Ah)^j/j!)\lvert x_{i,0}\rangle + ((Ah)^{j-1}/j!)h\lvert b\rangle$ for the interior rows, which the paper notes is a richer object than the history state of the earlier multistep algorithm: it encodes the intermediate solutions and those extra combinations as well. $C_{m,k,p}(Ah)$ is nonsingular because it is lower triangular with nonzero diagonal entries, is $(d+1)N \times (d+1)N$ for $A$ of size $N$, and for $A$ with $s$ nonzero entries per row and column has $O(ks)$ of them per row and column.

  Data

  No dataset and no instantiated matrix. The construction takes $A$ and $\vec{b}$ as symbols together with the step $h$ and the three integers $m$, $k$ and $p$. The only concrete choice of those integers written anywhere in the paper is the display of $C_{2,3,2}(Ah)$ in Eq. (8) — eleven block rows for $d = m(k+1)+p = 10$, against the right-hand side $\lvert 0\rangle\lvert x_{\mathrm{in}}\rangle + h\sum_{i=0}^{1}\lvert 4i+1\rangle\lvert b\rangle$ — and it is drawn to make the block structure legible, with $A$ and $\vec{b}$ still symbolic.

  Code

  None found yet.

  Results

  What this construction produces in the paper are theorems, not measurements. Lemma 4 bounds the norm, $\lVert C_{m,k,p}(A)\rVert \le 2\sqrt{k}$ for $\lVert A\rVert \le 1$ and $k \ge 5$, by splitting the matrix into its identity, step-closing and Taylor-term parts. Lemma 2 bounds the columns of the inverse in the scalar case under $\lvert\lambda\rvert \le 1$, $\operatorname{Re}(\lambda) \le 0$, $k \ge 5$ and $(k+1)! \ge 2m$; Lemma 3 lifts that to $\lVert C_{m,k,p}(A)^{-1}\rVert \le 3\kappa_V\sqrt{k}(m+p)$ by diagonalising the whole system as $C(A) = \tilde{V}C(D)\tilde{V}^{-1}$ with $\tilde{V} = \sum_{j}\lvert j\rangle\langle j\rvert \otimes V$, whose condition number is that of $V$; and Theorem 5 multiplies the two into $\kappa_C \le 6\kappa_V k(m+p)$. Theorem 6 accumulates the per-step truncation, in the diagonalised variables and through the two $1/(k+1)!$ lemmas of Appendix A, into $\lVert\lvert x(jh)\rangle - x_{j,0}\rVert \le 2.8\kappa_V j(\lVert x_{\mathrm{in}}\rVert + mh\lVert b\rVert)/(k+1)!$ for every $j \in \{0, 1, \ldots, m\}$. Nothing is computed numerically: the paper reports no experiment, contains no figure and no table, and names no simulator and no hardware.