Stated for time-dependent linear differential equations, with a simplified approach in the time-independent case. It reduces to a quantum linear solve. An, Childs and Lin's comparison table places truncated Dyson in the family whose initial-state-preparation cost grows with the evolution, not in the bypass family.

A block-encoding of $A(t)$ with a normalization $\alpha_A \ge \max_t \lVert A(t)\rVert$, preparation unitaries for $u_0$ and $b$, the evolution time $T$, and an error tolerance $\varepsilon$.

1. Linear ODE system → Linear system Ax = bChoose a time discretization or propagator approximation

   The interval is cut into $r$ steps of length $\Delta t = T/\lceil \lambda_A T \rceil$ and the steps become rows of one lower bidiagonal block system $\mathcal{A}\mathcal{X} = \mathcal{B}$, row $m$ reading $\tilde{x}(m\Delta t) = V_m x((m-1)\Delta t) + v_m$ with $V_m = W_K(m\Delta t,(m-1)\Delta t)$ the truncated Dyson propagator over that step and $v_m = v_K(m\Delta t,(m-1)\Delta t)$ its driven counterpart. assumption: $A(t)$ has non-positive logarithmic norm, which gives $\|W(t,t_0)\| \le 1$ and is what bounds $\|\mathcal{A}^{-1}\| \le R(1+\varepsilon) = O(R)$, hence $\kappa_{\mathcal{A}} = O(R)$. assumption: $\lambda_A \Delta t \le 1$, the restriction limiting how large $\Delta t$ can be, imposed to keep the $\lambda$-value of the block encoding of $\mathcal{A}$ at $O(1)$; it is what fixes $r = \lambda_A T$. Rows $r+1$ to $R$ hold the solution constant rather than evolving it, and with an equal number of held and evolving steps, $R = 2r$, the condition number handed down is $\kappa_{\mathcal{A}} = O(\lambda_A T)$.

   assumption

   Open this step

2. Linear system Ax = b → Solution as a stateQuantum linear solve

   The assembled system is handed to the optimal quantum linear equation solver of Costa et al., whose complexity is $O(\kappa_{\mathcal{A}} \log(1/\varepsilon_{\mathrm{QLSP}}))$ calls to the block encodings of $\mathcal{A}$ and $\mathcal{B}$, which here is $O(\lambda_A T \log(1/\varepsilon))$. assumption: The solver's error $\varepsilon_{\mathrm{QLSP}}$ can be taken proportional to $\varepsilon$ — that is what the bound $d_{BW} \le \varepsilon_{\mathrm{QLSP}} x_{\max}\sqrt{R+1}/\sqrt{r}$ needs, and it holds because $R = 2r$. $\mathcal{B}$ is prepared twice inside that solver's walk step, which would square its success amplitude, so amplitude amplification boosts the preparation to $\Theta(1)$ first, at $O((\lambda_b/\lambda_A)/(\min_m \|v(m\Delta t,(m-1)\Delta t)\| - \varepsilon x_{\max}/(\lambda_A T)))$ steps — the second factor of the constant $R$ in Theorem 4.1. An, Childs and Lin name this hop as what the route pays for: even with the optimal solver the state-preparation oracle for $y$ in $Mx = y$ is queried $O(\kappa_M \log(1/\varepsilon))$ times, so the initial state is queried $\tilde{O}((\|u_0\|/\|u(T)\|)\alpha_A T \log(1/\varepsilon))$ times, linearly in $T$ and $\|A(t)\|$.

   assumption

   Open this step

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

Berry and Costa (arXiv:2212.03544) carry no numerical work at all — no figure, no table, no computed value from the first section through the appendix, and no hardware or simulator named. An, Childs and Lin, cited beside it, do compute, but every number there measures the LCHS kernel, which is the competing route rather than this one.

given  A(t) with non-positive logarithmic norm, b(t), x_0, horizon T, budget e
       the parameters provided through the unitaries U_A, U_b, U_x
       with known normalisations lambda_A, lambda_b, lambda_x
       x_max >= max_t ||x(t)||

split [0,T] into r steps of length dt = T / ceil(lambda_A T)
    # dt taken as large as lambda_A dt <= 1 allows, which is what makes r = lambda_A T

# encode the Dyson series in a system of linear equations
for each step m = 1 ... r:
    V_m = W_K(m dt, (m-1) dt)    # the Dyson series for the propagator, truncated at K
    v_m = v_K(m dt, (m-1) dt)    # the same integrals with b(t_k) in place of A(t_k)
    # forming these two is this route's time discretization

assemble the lower bidiagonal block system  AA X = B  over R = 2r rows:
    row 0       :  x~(0)                            = x_0     # the initial condition
    row m <= r  :  x~(m dt) - V_m x~((m-1) dt)      = v_m     # one row per time step
    row m > r   :  x~(m dt) -     x~((m-1) dt)      = 0       # solution held constant
    # the trailing rows do not evolve anything; they are there to boost the success
    # probability of the final amplitude amplification
    # AA is the paper's block matrix; kappa_AA = ||AA|| ||AA^-1|| = O(R) = O(lambda_A T)

prepare B, and amplitude-amplify its state preparation to amplitude Theta(1)
    # B is prepared twice inside the solver's walk step; without this boost the
    # success amplitude would enter squared

solve  AA X = B  with the optimal quantum linear equation solver
    # O(kappa_AA log(1/e)) calls to the block encodings of AA and B

amplitude-amplify the component of X over rows r+1 ... R
    # O(x_max / ||x(T)||) steps on average

return the state approximating |x(T)>

Logarithmic dependence of the complexity on the error and derivative, with the usual exponential improvement over classical approaches in the scaling with the dimension, the solution being encoded in the amplitudes of a quantum state.

• Bidiagonal block system with a Dyson-series block encoding (sections 2.1, 3.1 and 4.1)

  • Quantum algorithm for time-dependent differential equations using Dyson series

    Dominic W. Berry, Pedro C. S. Costa · 2022

  About

  The construction Theorem 4.1 is proved for, and the paper says plainly why it is not the earlier one: "We use a block matrix similar to [3], but we do not use extra lines of the block matrix to implement terms in the series as in that work. Instead we construct this matrix via a block encoding using a Dyson series, in an analogous way as the block encodings in [12, 15]." The conclusion names the payoff — this approach makes the analysis of the complexity simpler than in Berry, Childs, Ostrander and Wang, because it is not necessary to account for the extra lines in the encoding. The problem it is built for is $\dot{x}(t) = A(t)x(t) + b(t)$ with $x(0) = x_0$ and $A(t)$ an $N \times N$ coefficient matrix of non-positive logarithmic norm, the deliverable being a state $\hat{x}$ with $d_{BW}(\hat{x}, \lvert x(T) \rangle \langle x(T) \rvert) \le \varepsilon x_{\max}$ in the Bures-Wasserstein metric, which is adopted so that an approximate state that is not pure can still be scored and which reduces to the 2-norm distance for pure states.

  Methods

  The block matrix $\mathcal{A}$ of Eq. (26) is never held as a matrix. Eq. (54) splits it as the identity minus the product of an increment on the time register with a block-diagonal matrix carrying the $V_m$. The increment is block encoded by incrementing the register non-modularly and using the carry qubit, so that the projection onto $\lvert 0 \rangle$ deletes the top row. The $V_m$ diagonal comes from the intermediate matrix of Eq. (55), which holds $A(\delta t), A(\Delta t + \delta t), A(2\Delta t + \delta t), \ldots$ on the evolving rows and zeros on the held rows; it is built from $U_A$ by feeding the qubits encoding the offset $\delta t$ together with the qubits encoding the row of the block matrix as the time input, with the number of subintervals per $\Delta t$ and $M$ both taken as powers of two so that a single ancilla qubit flags the zero block. That matrix is fed to the truncated Dyson series of Eq. (56), block encoded as in the Hamiltonian-simulation constructions of Kieferova, Scherer and Berry and of Low and Wiebe. With $\lambda_A \Delta t \le 1$ that series has $\lambda$-value $\sum_{k=0}^{K}(\lambda_A\Delta t)^k/k! < e^{\lambda_A \Delta t} \le e$, and the whole of $\mathcal{A}$ no larger than $e+1$. The right-hand side $\mathcal{B}$ is $x_0$ from $U_x$ together with the $v_m$ of Eq. (59), whose block encoding is the same machinery with the innermost $A(t_k)$ replaced by the preparation of $\lvert b(t_k) \rangle$, at $\lambda$-value below $(e-1)\lambda_b\Delta t$; the composite state of Eqs. (61)-(62) is prepared and then amplitude-amplified to $\Theta(1)$ before the solve, because $\mathcal{B}$ is prepared twice inside the solver's walk step and would otherwise contribute its amplitude squared. The conditioning is read off the bidiagonal structure: $\lVert \mathcal{A} \rVert \le 1 + \max_m \lVert V_m \rVert = O(1)$, and the explicit inverse of a lower bidiagonal matrix, Eqs. (30)-(31), expanded as a sum over its $R$ diagonals gives $\lVert \mathcal{A}^{-1} \rVert \le R(1+\varepsilon) = O(R)$, so $\kappa_{\mathcal{A}} = O(R)$, and with an equal number of evolving and held steps, $R = 2r$ with $r = \lambda_A T$, this is $O(\lambda_A T)$. The system is solved by the optimal quantum linear equation solver of Costa, An, Sanders, Su, Babbush and Berry at $O(\kappa_{\mathcal{A}} \log(1/\varepsilon_{\mathrm{QLSP}}))$ calls, with $\varepsilon_{\mathrm{QLSP}}$ taken proportional to $\varepsilon$ because $R = 2r$; the measurement that solver uses to confirm its filtering is omitted so that the final amplitude amplification over rows $r+1$ to $R$ can be performed jointly with the filtering, which the paper notes introduces no further factors.

  Data

  No dataset. The inputs are the three block encodings of Eqs. (44)-(46): $U_A$ with the time register as a quantum input, giving $A(t)\lvert n_t \rangle/\lambda_A$; $U_b$ likewise giving $\lvert n_t \rangle \lvert b(t) \rangle_s/\lambda_b$, defined as a block encoding rather than a unitary preparation precisely so that $\lambda_b$ can be taken independent of time even though $\lVert b(t) \rVert$ varies; and $U_x$ preparing $\lvert x_0 \rangle_s/\lambda_x$. The normalisations $\lambda_A$, $\lambda_b$, $\lambda_x$ are assumed known, and so are the constants $x_{\max} \ge \max_t \lVert x(t) \rVert$, $b_{\max} \ge \max_t \lVert b(t) \rVert$, $D$ of Eq. (88) and $R$ of Eq. (87). The paper's reason for taking these as given rather than computed is that it may be too difficult to determine the maxima and minima required exactly.

  Code

  None found yet.

  Results

  The construction is carried as far as counted complexity and no further. Theorem 4.1 gives an average of $O(R\lambda_A T \log(1/\varepsilon))$ calls to $U_b$ and $U_x$, $O(R\lambda_A T \log(1/\varepsilon)\log(\lambda_{Ax}T/\varepsilon))$ calls to $U_A$, and $O(R\lambda_A T \log(1/\varepsilon)\log(\lambda_{Ax}T/\varepsilon)[\log(TD/(\lambda_A\varepsilon)) + \log(\lambda_A T/\varepsilon)])$ additional gates, where $\lambda_{Ax} = \max(\lambda_A, b_{\max}/x_{\max})$. The gate count is stated for a fixed gate set such as Toffoli or $T$ plus Clifford rather than arbitrary-precision rotations, which the paper equates up to a constant with the usual non-Clifford count. The two factors of $R$ are the two amplitude amplifications, $O(x_{\max}/\lVert x(T) \rVert)$ for extracting the final time and Eq. (95) for the preparation of $\mathcal{B}$, and the paper expects $R = O(1)$ in practice when the solution does not decay significantly and $b(t)$ does not vary so as to cancel. Nothing here is executed: the paper reports no numerical experiment, and names no hardware and no simulator.

• Simplified encoding for a time-independent generator (sections 1.3, 2.2, 3.2 and 4.2)

  • Quantum algorithm for time-dependent differential equations using Dyson series

    Dominic W. Berry, Pedro C. S. Costa · 2022

  About

  The same encoding when the coefficients do not vary — the abstract's "simplified approach in the case of time-independent differential equations", which the conclusion calls a significantly simplified result for the complexity in the time-independent case. The problem is $\dot{x}(t) = Ax(t) + b$ with $x(0) = x_0$ and $A$ of non-positive logarithmic norm. It is deliberately not the encoding Berry, Childs, Ostrander and Wang gave for that same problem: there the orders of the Taylor sum occupied extra lines of the block matrix, and here, as the conclusion puts it, the block matrix has each successive line encoding a new time step, with the whole sum inside one block encoding. The paper reaches it by substituting a constant $A$ into the solution for the time-varying case.

  Methods

  Every $V_m$ collapses to the single $V = \sum_{k=0}^{K}(A\Delta t)^k/k!$ of Eq. (40) and every $v_m$ to $v = \sum_{k=1}^{K}A^{k-1}\Delta t^k b/k!$ of Eq. (41), so the block matrix of Eq. (39) carries one repeated subdiagonal block. The oracles lose their time register: $\langle 0 \rvert_A U_A \lvert 0 \rangle_A = A/\lambda_A$, $U_b \lvert 0 \rangle = \lvert b \rangle/\lambda_b$ with $\lambda_b = \lVert b \rVert$, and $U_x \lvert 0 \rangle = \lvert x_0 \rangle/\lambda_x$, all of them ordinary unitaries on one register. The block encoding proceeds through the same Eq. (54) split except that there is no need for the time integrals, so only the register holding $k$ has to be prepared, and with $\lambda_A\Delta t \le 1$ the Taylor series is block encoded with a factor of at least $1/e$. The conditioning argument is the time-dependent one word for word, $\lVert \mathcal{A} \rVert \le 1 + \lVert V \rVert = O(1)$ and $\lVert \mathcal{A}^{-1} \rVert = O(R)$, so $\kappa_{\mathcal{A}} = O(R)$ again. One thing genuinely improves rather than merely simplifying: the cancellations in $v_m$ that force the time-dependent case to carry an amplitude-amplification factor cannot occur, because Eq. (69) gives $\lVert v \rVert > \lVert b \rVert \Delta t\,(1 - [\exp(\lVert A \rVert \Delta t) - (1 + \lVert A \rVert \Delta t)]/(\lVert A \rVert \Delta t)) \ge (3-e)\lVert b \rVert\Delta t$ under $\lVert A \rVert \Delta t \le \lambda_A \Delta t \le 1$, putting the state-preparation success amplitude at no less than the constant $(3-e)/(e-1)$, which therefore drops out of the scaling.

  Data

  No dataset. The inputs are the three time-independent unitaries of Eqs. (110)-(112) with known $\lambda_A$, $\lambda_b = \lVert b \rVert$ and $\lambda_x$, together with $x_{\max} \ge \max_t \lVert x(t) \rVert$ and the constant $R \ge x_{\max}/\lVert x(T) \rVert$. The bound $D$ that the time-dependent theorem needs does not appear, because no derivative of the parameters enters.

  Code

  None found yet.

  Results

  Theorem 4.2 gives an average of $O(R\lambda T \log(1/\varepsilon))$ calls to $U_b$ and $U_x$, $O(R\lambda T \log(1/\varepsilon)\log(\lambda_{Ax}T/\varepsilon))$ calls to $U_A$, and $O(R\lambda T \log(1/\varepsilon)\log(\lambda_{Ax}T/\varepsilon)\log(\lambda_A T/\varepsilon))$ additional gates, with $\lambda_{Ax} = \max(\lambda_A, \lVert b \rVert/x_{\max})$ and $\lambda$ standing where the time-dependent theorem writes $\lambda_A$. Two things shrink against Theorem 4.1 and the proof says which: the state preparation now succeeds with at least constant probability so that factor leaves $R$, and no arithmetic on time registers is needed so the $\log(TD/(\lambda\varepsilon))$ term leaves the gate count, though the rotations preparing the $k$ register keep the $\log(\lambda T/\varepsilon)$ factor. As with the time-dependent case, this is a specified circuit and not an executed one: no numerical experiment, no hardware and no simulator appears in the paper.