Chebyshev pseudospectral collocation

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

**Smoothness of the solution, and the rate is a function of how much of it there is.** Lemma 1, quoted by Childs and Liu from Gheorghiu, covers a solution $\hat{x}(t) \in C^{r+1}(-1,1)$: $\max_{t}\|\hat{x}(t) - x(t)\| \leq C\max_{t}\|\hat{x}^{(n+1)}(t)\|/n^{r-2}$ for a constant $C$ independent of $n$. Lemma 2 covers $\hat{x}(t) \in C^{\infty}(-1,1)$ and is the one the exponential precision needs: $\max_{t}\|\hat{x}(t) - x(t)\| \leq \sqrt{2/\pi}\max_{t}\|\hat{x}^{(n+1)}(t)\|(e/2n)^{n}$. In Childs and Liu's summary, "the convergence behavior of the spectral method is related to the smoothness of the solution". Chebyshev rather than Fourier is a stated choice with a stated reason: "a Fourier series provides an appropriate basis for periodic problems, whereas Chebyshev polynomials can be applied more generally", and "since general linear ODEs are non-periodic, and interpolation facilitates constructing a straightforward linear system, we develop a quantum algorithm based on the Chebyshev pseudo-spectral method". The Chebyshev-Gauss-Lobatto nodes are likewise chosen rather than assumed — they "achieve the highest convergence rate among all schemes with the same number of nodes", and they have the convenient property $T_k(t_l) = \cos(kl\pi/n)$.

Requires

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

Example

Read in full: arXiv:1901.00961, the only paper this node cites, carries no numerics anywhere — no figure, no table, no computed value, no dataset and no simulator. Its Appendix B is titled "An example of the quantum spectral method" and is a structural display rather than a run: it takes $d = 1$, $m = 3$, $n = 2$, $p = 1$ and writes out the shape of the linear system with $A(t)$, $f(t)$ and $\gamma$ left symbolic. The register row for 1901.00961 records that as a full-text read.

given  A(t), f(t), initial value gamma, interval [-1, 1], series length n

take the n+1 Chebyshev-Gauss-Lobatto nodes
    t_l = cos(l*pi/n)   for l = 0 ... n,   so  1 = t_0 > t_1 > ... > t_n = -1
    # highest convergence rate of any scheme with this many nodes;
    # t_0 and t_n are the initial and final times, which is what lets the
    # initial condition and the answer both be read off a node

write each component as an undetermined truncated Chebyshev series
    x_i(t) = sum_{k=0..n} c_{i,k} T_k(t)

express the derivative in the same basis
    dx_i/dt = sum_{k=0..n} c'_{i,k} T_k(t)
    c'_{i,k} = sum_{j=0..n} [D_n]_{kj} c_{i,j}
    [D_n]_{kj} = 2j/sigma_k   for k+j odd and j > k,  else 0
    sigma_0 = 2,  sigma_k = 1 for k >= 1
    # D_n is upper triangular; it comes from 2T_k = T'_{k+1}/(k+1) - T'_{k-1}/(k-1)

collocate: demand the ODE hold at every node
    for l = 0 ... n, for i = 0 ... d-1:
        sum_k T_k(t_l) c'_{i,k} = sum_j A_ij(t_l) sum_k T_k(t_l) c_{j,k} + f_i(t_l)
    # T_k(t_l) = cos(k*l*pi/n), so no evaluation of T_k is needed

add the initial condition as further rows
    x_i(1) = gamma_i        for i = 0 ... d-1

return the linear system in the unknowns c_{i,k}
    # one global system for the whole interval, not one system per step

Cost, as the source states it

What Childs and Liu state for the discretization by itself is **the number of terms**, not an end-to-end complexity — the latter belongs to the route that calls a solver on the assembled system. Under Lemma 2's $C^{\infty}$ hypothesis: "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". Under Lemma 1's weaker hypothesis the same construction costs "$n = \mathrm{poly}(1/\varepsilon)$". That gap between the two is the whole reason a spectral discretization is worth building, and it is also the reason the smoothness hypothesis cannot be dropped quietly.

Implementations

The same document as `example.text` above, read again for a different question, and the paper's own wording is the trap: its introduction does say "we implement a Chebyshev pseudospectral method [4, 22] using the QLSA". That is the algorithm being constructed on paper. Across all 29 pages of arXiv:1901.00961 the words Qiskit, MATLAB, Python and benchmark do not occur, there is no numbered figure and no numbered table, and the one worked passage — Appendix B, "An example of the quantum spectral method" — fixes $d = 1$, $m = 3$, $n = 2$, $p = 1$ and then writes the linear system out with $A(t)$, $f(t)$ and $\gamma$ left symbolic. Nothing was built and nothing was run, so there is no implementation of this method in the only paper this record cites. Said of that one document and not of the method: this is a classical pseudospectral scheme lifted onto the QLSA, its classical half has been implemented for decades, and a paper that does report a quantum implementation would belong here rather than replacing this reason.

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 Taylor series of the propagator

  Rather than approximating the derivative, approximate the propagator $e^{hA}$ itself by $k$ Taylor terms and encode those terms as extra rows of a sparse linear system. Truncation error falls factorially in $k$, so accuracy is bought by adding rows rather than by shrinking $h$ and lengthening the system.

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

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 spectral methods for differential equations↗Andrew M. Childs, Jin-Peng Liu · 2019theory yes · simulation no · hardware no