**Problem 1** fixes the access model and one smoothness assumption before any theorem runs: $A(t) \in \mathbb{C}^{d\times d}$ is $s$-sparse for every $t \in [0,T]$, and "we assume that $A_{ij}, f_i \in C^{\infty}(0,T)$ for all $i,j \in [d]$". Everything is reached through oracles — one computing "the locations and values of the nonzero entries of $A(t)$" in a given row or column, and oracles preparing $|\gamma\rangle$ and $|f(t)\rangle$ that "also compute $\|\gamma\|$ and $\|f(t)\|$" — and the deliverable is a quantum state, "a quantum state $\varepsilon$-close to $|x(T)\rangle$", never an explicit vector. **Theorem 1** adds the spectral hypothesis: "$A(t)$ can be diagonalized as $A(t) = V(t)\Lambda(t)V^{-1}(t)$ where $\Lambda(t) = \mathrm{diag}(\lambda_1(t),\ldots,\lambda_d(t))$ with $\mathrm{Re}(\lambda_i(t)) \leq 0$ for each $i \in [d]_0$ and $t \in [0,T]$". The paper gives the reason and the comparison in one breath: the non-positive real parts are required "so that the solution cannot grow exponentially", and this "is essentially the same as in the time-independent case considered in [10] and improves upon the analogous condition in [5] (which requires an additional stability condition)" — [5] being Berry's multistep route on this same slot, whose $A(\alpha)$-stability is the extra condition being improved upon. **The hypothesis the abstract does not carry is smoothness of the solution, and the headline rests on it.** Section 2: "if the solution is in $C^{\infty}$, the spectral method approximates the solution to within $\varepsilon$ using only $n = \mathrm{poly}(\log(1/\varepsilon))$ terms in the Chebyshev series", whereas "for a solution in $C^{r+1}$, the spectral method approximates the solution with $n = \mathrm{poly}(1/\varepsilon)$". The Discussion lists it as an open problem rather than a technicality: "our algorithm must assume that the solution is smooth. If the solution is in $C^r$, the solution error is $O(1/n^{r-2})$ by Lemma 1. Can we improve the complexity to $\mathrm{poly}(\log(1/\varepsilon))$ under such weaker smoothness assumptions?" Diagonalisability is the softer of the two hypotheses and the paper says so: "our algorithm can produce approximate solutions for non-diagonalizable $A(t)$, although the dependence on $\varepsilon$ degrades to $\mathrm{poly}(1/\varepsilon)$".

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

   What crosses here is a whole interval at once. The approximation is Eq. (2.1), $x_i(t) = \sum_{k=0}^{n}c_{i,k}T_k(t)$ with the $c_{i,k}$ undetermined, and what determines them is Eq. (2.2) — the demand that $dx(t_l)/dt = A(t_l)x(t_l) + f(t_l)$ at the Chebyshev-Gauss-Lobatto nodes $t_l = \cos(l\pi/n)$ — together with $x_i(t_0) = \gamma_i$. The derivative stays in the basis through the differentiation matrix of Eq. (2.8), $[D_n]_{kj} = 2j/\sigma_k$ for $k+j$ odd and $j > k$, which comes from the Chebyshev identity $2T_k(t) = T'_{k+1}(t)/(k+1) - T'_{k-1}(t)/(k-1)$; Eq. (2.10) is the resulting system. approximation: Lemma 2, the $C^{\infty}$ bound $\max_{t}\|\hat{x}(t)-x(t)\| \leq \sqrt{2/\pi}\max_{t}\|\hat{x}^{(n+1)}(t)\|(e/2n)^{n}$, is what makes $n$ logarithmic in $1/\varepsilon$; under Lemma 1's weaker $C^{r+1}$ hypothesis the same construction needs $n = \mathrm{poly}(1/\varepsilon)$ and the headline is gone. assumption: The solution is smooth. The Discussion states this as a limitation and an open problem — "our algorithm must assume that the solution is smooth" — not as a formality. **The interval is subdivided even so, and the reason is a norm rather than an error.** Rescaling $[0,T]$ onto $[-1,1]$ sends $A \mapsto -(T/2)A$, "which can dramatically increase the spectral norm. To avoid this phenomenon, we divide the interval $[0,T]$ into subintervals" $[0,\Gamma_1],\ldots,[\Gamma_{m-1},T]$, each rescaled by $K_h$, with $\tau_h \leq 2/\max_{t}\|A(t)\|$ by Eq. (3.8) — so $m$ is chosen to make $\|A\|T/2m \leq 1$. Global on each piece, pieced together across $m$ of them.

   approximationassumption

   Open this step

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

   The assembled system is $L|X\rangle = |B\rangle$ of Eq. (3.12), and it goes to "the high-precision QLSA" of Childs, Kothari and Somma. assumption: The condition number that matters is the assembled system's, not $A$'s. Lemma 4: $\kappa_L \leq (\pi m + p + 2)(n+1)^{3.5}(2\kappa_V + e\|\gamma\|)$, which under the chosen parameters is $O(\kappa_V(m+p)n^{3.5})$ — so the number of subintervals, the padding $p$ and the series length all enter the solve directly, and $\kappa_V$ enters in place of any conditioning of $A$ itself. $L$ is an $(m+p+1)d(n+1)$-square matrix "with $O(ns)$ nonzero entries in any row or column", so the series length also multiplies the sparsity the solver sees. approximation: The two error budgets are tied through Eq. (8.11): $\|\hat{x}(T)-x(T)\| \leq \delta$ gives $\|\hat{x}(T)/\|\hat{x}(T)\| - x(T)/\|x(T)\|\| \leq \delta/(g-\delta) =: \varepsilon$, and $n$ is chosen by Eq. (8.6) from $\log(\Omega)/\log(\log(\Omega))$ to make that hold. **The readout is a measurement on a padded register and the padding is what makes it cheap.** The first and third registers are measured, an outcome in $S = \{m, m+1,\ldots,m+p\}$ is kept, and Lemma 5 puts that probability at $(p+1)(n+1)/(\pi m q^{2} + (p+1)(n+1))$. Choosing $p = O(m) = O(\|A\|T)$ then gives success probability $\Omega(1)$ with $O(q/\sqrt{n})$ repetitions of amplitude amplification — which is where the factor $q$ in the cost comes from.

   approximationassumption

   Open this step

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

Read in full: arXiv:1901.00961, the only paper this record cites, reports no run of the method. There is no figure, no table, no computed value, no dataset, no simulator and no hardware anywhere in it — the word "simulation" occurs only in the sense of Hamiltonian simulation and in reference titles. Its ten sections are a construction and its analysis end to end: the spectral method, the linear system, the solution error, the condition number, the success probability, state preparation, the main result and the boundary value problem. Appendix B, "An example of the quantum spectral method", is a structural display and not a run — $d = 1$, $m = 3$, $n = 2$, $p = 1$, with $A(t)$, $f(t)$ and $\gamma$ left symbolic. So there is no run to transcribe here, and no nearby numerics to point at instead.

given  oracles for A(t) (s-sparse), f(t), gamma; horizon T; error budget e

choose m so that  ||A||*T / (2*m) <= 1
    # NOT an accuracy choice. Rescaling [0,T] onto [-1,1] sends A -> -(T/2)A,
    # which 'can dramatically increase the spectral norm'; subdividing avoids it
divide [0,T] into [0,G_1], [G_1,G_2], ... , [G_{m-1},T]
    map each [G_h, G_{h+1}] onto [-1,1] by K_h, with K_h(G_h)=1, K_h(G_{h+1})=-1

choose the series length n from Eq. (8.6)
    n = (e/2) * max( floor(log(Omega)/log(log(Omega))),
                     floor(log(omega)/log(log(omega))) )
    Omega = g'*e*m*(1+eps)/(g*eps),   omega = (g'/||gamma||)*(m+1)
    # poly-logarithmic in 1/eps only because the solution is assumed C^infinity

for each subinterval, hand the layer above's collocation to this one:
    build the rows of  (L_1 + L_2(A_h)) |X> = |B_h>
    L_3 carries the coefficients c_{i,l}(G_{h+1}) into the next block
        as its initial condition
assemble one system  L |X> = |B>          # Eq. (3.12)
    L is (m+p+1)*d*(n+1) square, with O(n*s) nonzeros per row
    pad the final state p = O(m) = O(||A||*T) times via L_4, L_5

hand L |X> = |B> to the layer below          # the high-precision QLSA

measure the first and third registers
    keep outcomes in S = {m, m+1, ... , m+p}
    # success probability (p+1)(n+1) / (pi*m*q^2 + (p+1)(n+1)) by Lemma 5
amplitude-amplify O(q/sqrt(n)) times to reach success probability Omega(1)

return the second register: a state e-close to x(T)/||x(T)||

**Theorem 1**, the main result: $O(\kappa_V s \|A\| T q\,\mathrm{poly}(\log(\kappa_V s \|A\| g' T/\varepsilon g)))$ queries to the oracles $O_A(h,l)$, $O_x$ and $O_f(h,l)$, with a gate complexity "larger than the query complexity by a factor of $\mathrm{poly}(\log(\kappa_V d s \|A\| g' T/\varepsilon))$". Eq. (8.2) names every parameter rather than leaving them to a reader: $\|A\| := \max_{t\in[0,T]}\|A(t)\|$; $\kappa_V := \max_t \kappa_V(t)$, where $\kappa_V(t)$ is the condition number of the eigenvector matrix $V(t)$; $g := \|\hat{x}(T)\|$; $g' := \max_{t\in[0,T]}\max_{n\in\mathbb{N}}\|\hat{x}^{(n+1)}(t)\|$; and $q := \max_{t\in[0,T]}\|\hat{x}(t)\|/\|x(T)\|$. **Corollary 1** specialises to time-independent equations, replacing $g'$ by $\|\gamma\| + 2\tau\|f\|$: $O(\kappa_V s\|A\|Tq\,\mathrm{poly}(\log(\kappa_V s\gamma\|A\|\|f\|T/\varepsilon g)))$. **The boundary value problem is much worse in the horizon** — Theorem 2 gives $O(\kappa_V s\|A\|^{4}T^{4}q\,\mathrm{poly}(\log(\kappa_V s\|A\|g'T/\varepsilon g)))$, a fourth power where the initial value problem has a first. Two of these parameters carry the paper's own warnings and neither is decoration. Of $g'$: "in general, $g'$ could be unbounded above as $n \to \infty$", and removing it is left open — "the query complexity of Hamiltonian simulation is independent of that parameter. Can we develop quantum algorithms for general differential equations with query complexity independent of $g'$?" Of $q$, which "characterizes the decay of the final state relative to the initial state": "it is unlikely that the dependence on $q$ can be significantly improved, since renormalization of the state effectively implements postselection and an efficient procedure for performing this would have the unlikely consequence $\mathsf{BQP} = \mathsf{PP}$". The horizon dependence, by contrast, is close to the floor: "our algorithm has nearly optimal dependence on $T$, scaling as $O(T\,\mathrm{poly}(\log T))$", against the no-fast-forwarding bound that "the complexity must be at least linear in $T$".

• The global Chebyshev linear system $L|X\rangle = |B\rangle$ (sections 2 and 3)

  • Quantum spectral methods for differential equations

    Andrew M. Childs, Jin-Peng Liu · 2019

  About

  Why a global approximation, in the paper's own order. Section 1 sets out the obstacle first: "most of the aforementioned algorithms use a local approximation: they discretize the differential equations into small time intervals", and even at high order "when solving an equation over the interval $[0,T]$, the number of iterations is $T/h = \Theta(\varepsilon^{-1/k})$ for fixed $k$, giving a total complexity that is $\mathrm{poly}(1/\varepsilon)$ even using high-precision methods for the QLSA or Hamiltonian simulation". Two escapes already existed and both need structure the general case does not have: "when $A(t)$ is anti-Hermitian and $f(t) = 0$, we can directly apply Hamiltonian simulation; if $A$ and $f$ are time-independent, then [10] uses a Taylor series to achieve complexity $\mathrm{poly}(\log(1/\varepsilon))$. However, the case of general time-dependent linear ODEs had remained elusive." Section 2's answer is the one this record is about: represent the components "as linear combinations of basis functions $\phi_j(t)$ expressing the time dependence", so that no step count stands between the horizon and the error.

  Methods

  The approximation is Eq. (2.1), $x_i(t) = \sum_{k=0}^{n}c_{i,k}T_k(t)$, and the coefficients "are determined by demanding that $x(t)$ satisfies the ODE and initial conditions at a set of interpolation nodes $\{t_l\}_{l=0}^{n}$ (with $1 = t_0 > t_1 > \cdots > t_n = -1$), where $x(t_0)$ and $x(t_n)$ are the initial and final states" — Eq. (2.2) and Eq. (2.3). The nodes are Chebyshev-Gauss-Lobatto, $t_l = \cos(l\pi/n)$, "since these nodes achieve the highest convergence rate among all schemes with the same number of nodes", and because "these nodes also have the convenient property that $T_k(t_l) = \cos(kl\pi/n)$". Differentiation stays inside the basis: from $2T_k(t) = T'_{k+1}(t)/(k+1) - T'_{k-1}(t)/(k-1)$ comes the upper-triangular matrix $D_n$ of Eq. (2.8), $[D_n]_{kj} = 2j/\sigma_k$ for $k+j$ odd and $j > k$, with $\sigma_0 = 2$ and $\sigma_k = 1$ otherwise, giving Eq. (2.10). Section 3 assembles this into $L|X\rangle = |B\rangle$, Eq. (3.12), over $m$ rescaled subintervals with initial conditions chained by $x_h(1) = x_{h-1}(-1)$, and pads the final state $(p+1)(n+1)$ times through $L_4$ and $L_5$ so the readout succeeds with constant probability. **The subdivision is the part most easily mistaken for a step count.** It is not chosen against the error budget at all: rescaling $[0,T]$ onto $[-1,1]$ sends $A \mapsto -(T/2)A$, "which can dramatically increase the spectral norm", so the subintervals are sized by Eq. (3.8), $\tau_h \leq 2/\max_{t\in[\Gamma_h,\Gamma_{h+1}]}\|A(t)\|$. The error is controlled by $n$, and $n$ is logarithmic in $1/\varepsilon$ by Lemma 2.

  Data

  No dataset and no instantiated matrix. $A(t)$, $f(t)$ and $\gamma$ stay symbolic throughout and are reached only through oracles, exactly as on `berry-multistep`. The sole concrete display is Appendix B, "An example of the quantum spectral method", which fixes $d = 1$, $m = 3$, $n = 2$ and $p = 1$ and writes out the resulting block structure of $L$ — drawn to make that structure legible, with $A(t)$ and $f(t)$ still symbolic and no value computed. The quantitative choices the construction itself fixes are the node set $t_l = \cos(l\pi/n)$, the subinterval bound $\tau_h \leq 2/\max_t\|A(t)\|$, and $p = O(m) = O(\|A\|T)$.

  Code

  None found yet.

  Results

  None found yet.