Truncated Taylor series of the propagator

What it fills

• Choose a time discretization or propagator approximation

  Reduce continuous evolution over $[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.

When it applies

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.

Requires

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

Example

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

Cost, as the source states it

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.

Implementations

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

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

  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.

  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.

  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.

  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.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Forward (explicit) Euler

  First-order explicit stepping, $u_{k+1} = (I + hA)u_k + h b_k$, assembled into a banded all-at-once linear system. Liu et al. use it inside the Carleman route because its structure is simple enough to bound explicitly.

• Backward (implicit) Euler

  First-order implicit stepping: each step solves $(I - hA)u_{k+1} = u_k + h b_{k+1}$. $A$-stability is the classical reason to prefer it for stiff generators, since it removes the explicit method's step-size restriction.

• Trapezoidal rule (Crank-Nicolson)

  Second-order implicit stepping that averages the generator at the two ends of each step, and is $A$-stable. As a rational approximation of $e^{hA}$ it is the $(1,1)$ diagonal Padé approximant.

• Truncated Dyson series of the propagator

  Truncate the Dyson series — the expansion that stands in for the propagator once the generator varies with time — and encode its terms as rows of a system of linear equations. This is what extends the all-at-once approach to genuinely time-dependent generators; solving the system those rows make up is the layer below.

• Chebyshev pseudospectral collocation

  A **global** discretization, and the only one on this slot. Write each component of the solution as a truncated Chebyshev series $x_i(t) = \sum_{k=0}^{n} c_{i,k}T_k(t)$ with the coefficients undetermined, then fix them by demanding that the differential equation hold exactly at the $n+1$ Chebyshev-Gauss-Lobatto nodes $t_l = \cos(l\pi/n)$. What comes out is one linear system in the coefficients. Childs and Liu put the difference from every stepping scheme plainly: "instead of locally approximating the ODE at discretized times, these linear equations use the behavior of the differential equations at the $n+1$ times $\{t_l\}$ to capture their behavior over the entire interval $[-1,1]$".

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

• Quantum algorithm for linear differential equations with exponentially improved dependence on precision↗Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, Guoming Wang · 2017theory yes · simulation no · hardware no