PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum spectral methods for differential equations

Andrew M. Childs, Jin-Peng Liu

arXiv:1901.00961v1quant-phmath.NA

TL;DR

General time-dependent linear differential equations lacked a quantum algorithm with poly(log(1/ε)) accuracy dependence. This paper uses global spectral approximations and the QLSA to solve them. It obtains poly(log d, log(1/ε)) algorithms for time-dependent initial and boundary value problems.

  • Problem

    General time-dependent linear ODEs lacked a quantum algorithm avoiding the poly(1/ε) dependence associated with local finite-difference approximations.

  • Method

    The paper uses a global Chebyshev spectral approximation and solves the resulting coefficient linear system with a high-precision QLSA.

  • Results

    The algorithm solves linear time-dependent ODEs with complexity poly(log(1/ε)) and extends to time-dependent initial and boundary value problems.

  • Takeaways & Limitations

    Compared with finite-difference approaches, the algorithm improves the stated time-dependent error dependence from poly(1/ε) to poly(log(1/ε)).

  • Takeaways & Limitations

    The complexity depends on q, which characterizes decay of the final state relative to the initial state, and this dependence is unlikely to be significantly improved.

Abstract

from arXiv · show

Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a $d$-dimensional system of linear equations or linear differential equations with complexity $\mathrm{poly}(\log d)$. While several of these algorithms approximate the solution to within $ε$ with complexity $\mathrm{poly}(\log(1/ε))$, no such algorithm was previously known for differential equations with time-dependent coefficients. Here we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity $\mathrm{poly}(\log d, \log(1/ε))$.

1 Introduction

Quantum algorithms for linear differential equations use implicit quantum-state outputs and sparse-oracle access to achieve favorable dimension scaling, but prior approaches struggled with general time-dependent coefficients. This paper introduces a global spectral-method approach for time-dependent initial and boundary value problems.

  • Quantum setting: Quantum linear-systems algorithms produce quantum states proportional to solutions of sparse d-dimensional systems with complexity poly(log d).These algorithms use quantum-state outputs and implicit access through sparse matrix and state-preparation oracles.
  • Prior limitations: Finite-difference and finite-element methods require Θ(ε^-1/k) time steps for fixed order k, resulting in complexity poly(1/ε).Their local discretization incurs this dependence even when the underlying QLSA or Hamiltonian simulation is high precision.
  • Prior limitations: Prior poly(log(1/ε)) quantum algorithms covered special cases, including anti-Hermitian homogeneous systems and time-independent equations, but not general time-dependent linear ODEs.The time-independent Taylor-series method assumes A(t) and f(t) are constant.
  • Contribution: The paper uses a nonlocal representation of the solution to obtain complexity poly(log(1/ε)) for time-dependent equations.The approach develops a quantum version of spectral methods rather than locally discretizing time.
  • Contribution: The same approach also gives a quantum algorithm for boundary value problems with complexity poly(log(1/ε)).The algorithm targets a normalized state proportional to x(t) for a desired time t.

2 Spectral method

The spectral method globally approximates the ODE solution with a truncated Chebyshev series and determines its coefficients from interpolated differential equations and initial conditions. For sufficiently smooth solutions, convergence is exponential enough to yield poly(log(1/ε)) complexity.

  • Spectral-method workflow: Spectral methods express an approximate solution as basis-function combinations, construct a coefficient linear system, and solve it.This replaces local time-step approximations with a global representation.
  • Chebyshev approximation: The algorithm uses a truncated Chebyshev series with undetermined coefficients and Chebyshev-Gauss-Lobatto interpolation nodes.The coefficients are chosen so the approximation satisfies the ODE and initial condition at the selected nodes.
  • Chebyshev approximation: The resulting coefficient equations interpolate the differential equations across n + 1 nodes, capturing solution behavior over the entire interval.Chebyshev polynomials and their differential properties provide the transformations needed to form the linear system.
  • Quantum implementation: The high-precision QLSA solves the coefficient system, and a further linear-system encoding forms the approximate solution x(t).The paper analyzes approximation error, condition number, and final-measurement success probability.
  • Convergence: For infinitely smooth solutions, ε accuracy requires n = poly(log(1/ε)) Chebyshev terms, yielding quantum complexity poly(log(1/ε)).For solutions in C^(r+1), the required number of terms is instead stated as n = poly(1/ε).

3 Linear system

The algorithm encodes a time-dependent initial-value problem into a quantum linear system using a piecewise Chebyshev pseudospectral representation. Each interval’s coefficients become the next interval’s initial conditions, while auxiliary repetitions support final-state measurement.

  • 3 Linear system: The construction targets linear, first-order, time-dependent ordinary differential equations with a specified initial condition.The desired output is a quantum state proportional to the solution at time T.
  • 3 Linear system: The time interval is partitioned into subintervals and each is rescaled to [−1, 1] before solving the equations successively.This rescaling controls the spectral norm of the interval-dependent matrix and links successive interval solutions.
  • 3 Linear system: The method substitutes truncated Chebyshev series into the differential equations and interpolates them at Chebyshev nodes.Chebyshev coefficients are determined through a linear system representing derivative, coefficient, and interpolation operations.
  • 3 Linear system: L4 and L5 repeat the final solution across auxiliary registers to increase the success probability of the final measurement.The repetition uses (p + 1)(n + 1) copies in the stated construction.
  • 3 Linear system: For each interval, L1 + L2(Ah) solves the differential equations, while L3 transfers the resulting coefficients into the next interval’s initial conditions.At the final interval, L3 and L4 form the final state coefficients.

4 Solution error

The solution-error analysis separates truncation and propagated initial-condition errors across subintervals. Under diagonalizability with nonpositive eigenvalue real parts, the Chebyshev approximation error decreases exponentially with the truncation order.

  • 4 Solution error: The analysis assumes A(t) is diagonalizable with Re(λi(t)) ≤ 0 and bounds the error using the eigenvector-condition number κV.These assumptions appear in the stated error lemma for sufficiently large n.
  • 4 Solution error: The approximation error on each interval has contributions from linear-system error and transported initial-condition error.The analysis introduces a recurrence for the error passed between successive subintervals.
  • 4 Solution error: The propagated error is bounded by comparing the linear-system solution with the exact solution for an induced initial perturbation.This comparison uses the interval evolution equation and an established lemma.
  • 4 Solution error: The solution error decreases exponentially with n, so error ǫ requires n = poly(log(1/ǫ)) Chebyshev terms.The same conclusion is stated for the quantum spectral method after iterating the interval recurrence.

5 Condition number

The condition-number analysis bounds the inverse of the encoded linear system by decomposing its action on basis vectors and controlling the associated Chebyshev and interval operators. The resulting bound depends on the number of intervals, repetitions, polynomial degree, and eigenvector conditioning.

  • 5 Condition number: The analysis derives a condition-number bound for L assuming A(t) is diagonalizable with Re(λi(t)) ≤ 0.The bound uses κV, an upper bound on the condition number of the diagonalizing eigenvector matrix.
  • 5 Condition number: The operator-norm calculation combines bounds for the Chebyshev differentiation matrix, cosine-transform matrix, and coefficient-dependent matrix blocks.These components contribute to the final norm estimate for L.
  • 5 Condition number: The inverse-system norm is bounded by analyzing its action on vectors associated with individual intervals and Chebyshev indices.The proof separates vectors with matching and nonmatching interpolation indices.
  • 5 Condition number: The proof constructs corresponding differential equations whose truncated Chebyshev solutions reproduce the vectors used in the linear-system analysis.For zero input and initial condition, the exact solution is zero, providing a direct comparison case.
  • 5 Condition number: The bounds control coefficient-vector norms by propagating initial conditions across intervals and treating separately the initial-condition and input-vector cases.The stated estimates include κV and e∥γ∥ terms.

6 Success probability

The algorithm obtains the final solution state by measuring registers of the QLSA output and postselecting the final-interval blocks. The success-probability analysis quantifies this measurement and supports the overall flagged-output procedure.

  • 6 Success probability: The success analysis evaluates the probability that QLSA output measurement yields a state proportional to the final solution x(T).The relevant measurement examines the first and third registers and outputs the second register when a final interval is observed.
  • 6 Success probability: Observing the first register in h ∈ {m, m + 1, . . . , m + p} produces a normalized second-register state proportional to the final state.The construction uses repeated final-state blocks in these registers.
  • 6 Success probability: The measurement success probability satisfies the bound derived from the final-interval contributions and Chebyshev orthogonality.The stated calculation accounts for the rescaling of the time intervals.

7 State preparation

The algorithm prepares the linear-system input state from the initial condition and time-dependent forcing using state-preparation oracles, with O(mn) gate and query complexity.

  • State preparation: The procedure prepares |B⟩, the right-hand-side state for the linear system encoding the differential-equation problem.It uses the given ability to prepare the initial state and evaluates the preparation cost.
  • State preparation: The state space uses registers for subinterval indices, vector components, and Chebyshev nodes to encode γ and f_h(cos(lπ/n)).The oracles act on basis states |h⟩|i⟩|l⟩ and prepare states proportional to γ or sampled forcing vectors.
  • State preparation: O(mn) gate and query complexity suffices for preparing the encoded state under the stated oracle model.This bound follows from the lemma’s state-preparation construction.
  • State preparation: A unitary transformation first normalizes the encoded components before applying the initial-condition and forcing-state oracles.The construction applies O_x and O_f(h,l) over all relevant subintervals and nodes.

8 Main result

The main result applies a quantum spectral method to time-dependent ODEs by encoding the problem in a sparse linear system and solving it with the QLSA. Under diagonalizability and non-positive eigenvalue real parts, the algorithm produces an ε-accurate normalized final state with probability Ω(1), while its complexity depends on conditioning, sparsity, solution norms, and q.

  • Main theorem: Theorem 1 gives an Ω(1)-success quantum algorithm producing an ε-close normalized approximation to x(T) under diagonalizability and Re(λ_i(t))≤0.The algorithm includes a flag indicating success.
  • Complexity: The query complexity depends on κ_V, s, ∥A∥, g′, T, and ε, while gate complexity adds a poly(log(κ_V d s∥A∥g′T/ε)) factor.The sparse linear system has dimension (m+p+1)d(n+1) and O(ns) nonzero entries per row or column.
  • Accuracy and success: The output state is ε-close to the normalized approximate solution when the truncation parameter n is chosen according to the error analysis.The extracted second register is the normalized state proportional to the final state.
  • Algorithm: The method builds a linear system L|X⟩=|B⟩ encoding the quantum spectral method, then applies the QLSA and measures registers to extract the final state.The construction partitions [0,T] into subintervals and maps each onto [-1,1] for local spectral representations.
  • Time-independent case: For time-independent equations, g′ can be replaced by ∥γ∥+2τ∥f∥, yielding a specialized complexity expression.The paper states this replacement explicitly for the time-independent case.
  • Limitations: The algorithm’s complexity depends on q, which characterizes decay of the final state relative to the initial state.The paper states that substantially improving this dependence is unlikely because renormalization effectively implements postselection.
  • Limitations: For non-diagonalizable A(t), approximate solutions remain possible, but the ε-dependence degrades to poly(1/ε).The main theorem assumes diagonalizability and non-positive real parts of the eigenvalues.

9 Boundary value problems

The paper extends the quantum spectral method to boundary value problems by encoding boundary conditions in a Chebyshev-based linear system. Under stated diagonalizability and oracle assumptions, the algorithm produces an ε-accurate quantum state with polylogarithmic error dependence.

  • Problem formulation: Boundary value problems impose a linear constraint relating the initial and final states, αx(0) + βx(T) = γ.The quantum input includes state-preparation oracles for the boundary data and the inhomogeneity.
  • Spectral construction: The method maps the full interval [0, T] directly onto [−1, 1] because boundary conditions prevent dividing it into subintervals.A higher-order Chebyshev series is then used to reduce the solution error.
  • Linear-system encoding: The boundary condition replaces the initial-condition equation in the Chebyshev linear system through an expanded series evaluated at the endpoints.Using Tk(t0) = 1 and Tk(tn) = (−1)^k simplifies the resulting terms.
  • Linear-system encoding: The resulting system retains the same general form as the initial-value construction, with m = 1 and corresponding adjustments to the linear operator.The associated lemmas continue to hold for boundary value problems.
  • Complexity and guarantees: The gate complexity exceeds the query complexity by a polylogarithmic factor, while the query count depends on discretization, conditioning, sparsity, and system parameters.The supplied theorem passage gives the query model and the logarithmic gate-overhead dependence.
  • Complexity and guarantees: Under the theorem’s assumptions, the algorithm outputs an ε-close normalized state proportional to the solution at a specified time with constant-order success probability.The assumptions include a diagonalizable A(t) whose eigenvalues have nonpositive real parts.

10 Discussion

The discussion presents the spectral algorithm as a global-approximation alternative that extends polylogarithmic-accuracy quantum ODE solving to time-dependent linear systems. It also identifies smoothness, fluctuation, evolution-time, and broader-equation-class questions for future work.

  • Contribution: The algorithm solves linear, time-dependent ordinary differential equations using a global spectral approximation instead of a finite difference method.This is the paper’s central methodological distinction.
  • Contribution: For time-independent equations, the algorithm has almost the same complexity as the earlier high-precision approach while also covering time-dependent equations.The comparison is stated directly in the discussion.
  • Open problems: The algorithm assumes a smooth solution, and the discussion asks whether poly(log(1/ε)) complexity remains possible under weaker smoothness assumptions.The cited passages state this as an open problem.
  • Open problems: The discussion asks whether query complexity can be made independent of g′, which characterizes fluctuation in the solution.Hamiltonian simulation is cited as having query complexity independent of that parameter.
  • Open problems: The algorithm has nearly optimal dependence on T, scaling as O(T poly(log T)), but linear dependence and an optimal T–ε tradeoff remain open.The discussion relates the target to the no-fast-forwarding lower bound and Hamiltonian simulation.
  • Open problems: The paper leaves open whether its techniques can improve quantum algorithms for linear PDEs, nonlinear ODEs, or nonlinear PDEs.These extensions are posed as future applications rather than established results.

A Chebyshev polynomials

This appendix develops the Chebyshev-polynomial machinery underlying the spectral approximation, including polynomial definitions, orthogonality, completeness, projection, and differentiation of Chebyshev series.

  • Definitions and recurrence: Chebyshev polynomials of the first kind can be defined through Tk(x) = cos(kθ), where θ = arccos x.The trigonometric definition supports the recurrence used in the appendix.
  • Definitions and recurrence: The first Chebyshev polynomials include T0(x) = 1, T1(x) = x, T2(x) = 2x^2 − 1, T3(x) = 4x^3 − 3x, and T4(x) = 8x^4 − 8x^2 + 1.These examples illustrate that Tk has degree k.
  • Orthogonality and completeness: Chebyshev polynomials are orthogonal on [−1, 1] under the weight w(x) = (1 − x^2)^−1/2.The appendix defines the associated weighted inner product.
  • Orthogonality and completeness: The Chebyshev basis is complete in the relevant weighted L2 space, enabling projection onto polynomials of degree at most N.The appendix introduces the orthogonal projection PN for this purpose.
  • Projection machinery: The appendix defines the projection and its coefficients as the basis operations used to represent functions and derivatives in the spectral method.These constructions provide the polynomial-space representation required by the linear-system formulation.
  • Differentiation: Differentiating a projected Chebyshev series produces a polynomial of degree at most N − 1, with derivative coefficients obtained from a recurrence.The derivative transformation is represented by an upper-triangular matrix with zero diagonal entries.

B An example of the quantum spectral method

The example constructs a small quantum spectral linear system by partitioning the time interval, expanding the solution in finite Chebyshev series, and enforcing the differential equation at interpolation nodes.

  • Example setup: The example illustrates the linear system used by the quantum spectral method for a one-dimensional system, d = 1.It provides a concrete instance of the general construction.
  • Example setup: The scalar time-dependent problem uses x(t), A(t), and f(t) together with an initial condition.The example specializes the general differential-equation variables to complex scalars.
  • Spectral discretization: The interval is divided into three subintervals, each mapped to [−1, 1], and x(t) is approximated with a degree-two Chebyshev series.The choices are m = 3, n = 2, and p = 1.
  • Linear-system construction: Interpolating the differential equation at the selected Chebyshev nodes produces the linear system for the unknown series coefficients.The nodes in this example are {0, −1}.
  • Success amplification: The final state is repeated once to increase the success probability of the quantum procedure.This corresponds to choosing p = 1 in the example.
  • Linear-system construction: The system’s unknown vector contains the Chebyshev coefficients c0, c1, and c2 at each of the three interval endpoints.The final state is identified with x(Γm) = x(−1).
Loading 1901.00961v1…