PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved quantum algorithms for linear and nonlinear differential equations

Hari Krovi

arXiv:2202.01054v5quant-phcs.DSphysics.plasm-ph

TL;DR

The paper addresses limited quantum algorithms for inhomogeneous linear and nonlinear ODEs, especially their diagonalizability and error-dependence requirements. It characterizes linear-ODE runtime through the matrix exponential and combines the resulting algorithm with Carleman linearization. The resulting methods cover broader matrix classes and improve prior bounds, including exponentially better error dependence for nonlinear equations.

  • Problem

    Prior quantum ODE algorithms required diagonalizability or normality in important cases and had weaker error dependence for nonlinear equations.

  • Method

    The paper uses a matrix-exponential-based linear ODE algorithm, block-encoded linear systems, and Carleman linearization for nonlinear equations.

  • Results

    The algorithms extend to many non-diagonalizable and singular linear systems, improve bounds exponentially for certain diagonalizable systems, and exponentially improve error dependence for nonlinear equations.

  • Takeaways & Limitations

    Negative log-norm permits the nonlinear algorithm to handle sparse, invertible, non-normal, and even non-diagonalizable dissipation matrices.

  • Takeaways & Limitations

    For broader nonlinear cases, the paper leaves open extending the definition of R and proving convergence of Carleman linearization; dependence on ∥A∥ for stable matrices also remains open.

Abstract

from arXiv · show

We present substantially generalized and improved quantum algorithms over prior work for inhomogeneous linear and nonlinear ordinary differential equations (ODE). Specifically, we show how the norm of the matrix exponential characterizes the run time of quantum algorithms for linear ODEs opening the door to an application to a wider class of linear and nonlinear ODEs. In Berry et al., (2017), a quantum algorithm for a certain class of linear ODEs is given, where the matrix involved needs to be diagonalizable. The quantum algorithm for linear ODEs presented here extends to many classes of non-diagonalizable matrices. The algorithm here is also exponentially faster than the bounds derived in Berry et al., (2017) for certain classes of diagonalizable matrices. Our linear ODE algorithm is then applied to nonlinear differential equations using Carleman linearization (an approach taken recently by us in Liu et al., (2021)). The improvement over that result is two-fold. First, we obtain an exponentially better dependence on error. This kind of logarithmic dependence on error has also been achieved by Xue et al., (2021), but only for homogeneous nonlinear equations. Second, the present algorithm can handle any sparse, invertible matrix (that models dissipation) if it has a negative log-norm (including non-diagonalizable matrices), whereas Liu et al., (2021) and Xue et al., (2021) additionally require normality.

1 Introduction

The paper develops quantum algorithms for inhomogeneous linear and nonlinear ODEs that broaden applicable matrix classes and improve error dependence and runtime bounds over prior work.

  • Context: The work is motivated by quantum simulation methods developed for differential equations and linear systems, including block-encoded matrix operations and improved QLSA error scaling.The paper places its ODE algorithms within broader applications spanning fluid mechanics, plasma physics, quantum physics, and machine learning.
  • Linear ODEs: The linear ODE algorithm covers many non-diagonalizable and even singular matrices while retaining logarithmic dependence on solution error.The analysis avoids diagonalization by directly characterizing efficient matrices through the matrix exponential and revised condition/error bounds.
  • Linear ODEs: For diagonalizable matrices with non-positive log-norm and exponentially high κV, the algorithm removes the prior linear dependence on κV, yielding an exponential improvement.The comparison applies when the eigenvector matrix has exponentially large condition number.
  • Algorithmic approach: The algorithm uses truncated Taylor series, a quantum linear system, block encoding, and amplitude amplification through a ramp.Its linear system differs from prior work because it is easier to analyze and implement with block-encoding techniques.
  • Nonlinear ODEs: Carleman linearization applies the linear ODE algorithm to nonlinear equations, exponentially improving error dependence over the authors’ earlier Euler-based method.The resulting Carleman ODE can be non-normal and non-diagonalizable when the nonlinear system’s dissipation matrix has negative log-norm.

2 Problem statement and preliminaries

The paper formulates quantum solution of a stable, sparse linear ODE as preparation of a state proportional to x(T), then builds the required linear system from block-encoded matrix operations.

  • Problem formulation: The target problem is to produce a quantum state proportional to x(T) for a stable, sparse d × d matrix A and inhomogeneous linear ODE, within l2 error ϵ.The input includes oracle access to A, b, and x0, with normalized state preparation for the vector data.
  • Input assumptions: The input model assumes sparse matrix access through oracles and known norms for the initial and forcing vectors, with ODE solution error measured in l2 norm.The algorithm applies QLSA results to block encodings whose norms may be O(1) rather than exactly one without changing asymptotic gate complexity.
  • Block encoding: Block encoding embeds a sparse matrix into a unitary so that matrix arithmetic can construct the linear system associated with the ODE.The construction uses subtraction, multiplication, and inversion of block-encoded matrices.
  • Block encoding: Sparse matrices can be block-encoded using oracle access to nonzero positions and values, with gate and ancilla costs scaling polylogarithmically in sparsity, precision, and dimension parameters.The cited lemma provides an explicit block encoding for row- and column-sparse matrices.
  • Linear-system solution: The preliminaries supply block-encoding operations for Hermitian complements, addition, multiplication, and inversion, alongside a QLSA for preparing normalized A^-1|b⟩.These operations are the components used to implement and solve the ODE-derived linear system.

3 Norm of the matrix exponential

The section characterizes quantum ODE algorithm performance through the matrix-exponential norm, relating its behavior to log-norm, stability, decompositions, and condition numbers. It also identifies matrix classes where the resulting bounds improve substantially over prior analyses.

  • Matrix-exponential behavior: The norm of exp(At) is governed by the log-norm at short times and by the spectral abscissa at long times.A uniformly bounded matrix exponential requires additional assumptions beyond α(A)<0.
  • Stability: α(A)<0 is equivalent to exp(At) converging to zero as t→∞, defining the stable-matrix regime.Matrices with eigenvalues having negative real parts are stable; allowing zero real parts gives semi-stability.
  • Log-norm regimes: Matrices with identical negative eigenvalues can exhibit different short-term growth because one has µ>0 while the other has µ<0.Figure 1 compares the corresponding matrix-exponential norms over time.
  • Non-positive log-norm: For the twisted Toeplitz example, µ=−1/d and κV is exponential in log d, making the prior κV-based bound exponentially worse than the new bound.The matrix is diagonalizable but non-normal, while its Hermitian part has negative entries.
  • Condition numbers: Numerical comparisons show that κC is far smaller than the prior exponential bound and appears polynomial, while κL differs from κC increasingly with dimension d.Figure 2 compares κL, κC, and κV across dimensions 15 to 100.
  • Scope of bounds: Uniform bounds for arbitrary matrices can scale as large as the matrix dimension, motivating restrictions based on Jordan or Schur structure and non-normality.Polynomial control can require bounds on Jordan-block size, κV, or the Schur nilpotent part ∥N∥.
  • Algorithmic quantity: The quantity C(A)=sup_{t∈[0,T]}∥exp(At)∥ supports analysis beyond stable matrices and can be bounded for block matrices without normality or diagonalizability assumptions.This is particularly useful for block-matrix applications to nonlinear differential equations.

4 Description of the quantum algorithm

The algorithm discretizes a time-independent inhomogeneous linear ODE with a truncated Taylor method, encodes the resulting recurrence into a linear system, and solves it using a quantum linear-system procedure. Post-selection extracts a normalized state close to the solution at the target time.

  • Target solution: The solution at time T is represented by the matrix-exponential form of the inhomogeneous ODE and remains valid when A is singular.The algorithm targets the time-independent system with constant A and b.
  • Discretization: The time interval [0,T] is divided into m=⌈T/h⌉ steps, and each step is approximated with truncated Taylor functions Tk and Sk.The resulting discrete equation uses h as the single-step time interval.
  • Linear-system encoding: The discrete evolution is encoded into a linear system L and solved with the quantum linear systems algorithm.The operator L is designed for easier analysis and broader generalization than the prior construction.
  • Operator construction: The registers store the time step, Taylor step, and states on which A acts, while p additional steps boost the success probability.The construction uses matrix operations and nilpotent operators to represent the truncated recurrence.
  • State preparation: Applying L^−1 to the initial state produces an entangled state whose components encode the intermediate solution vectors yi.The derivation uses the nilpotence of N and M1 to truncate the relevant series exactly.
  • Solution extraction: Measuring the time-step register and post-selecting outcomes m through m+p−1 yields a state proportional to ym, which is normalized to obtain the solution state.Subsequent analysis bounds the approximation error, measurement probability, condition number, query complexity, and gate complexity.

5 Analysis of the quantum algorithm

The analysis bounds solution error, condition number, success probability, and implementation complexity for the truncated-Taylor quantum algorithm. It establishes validity for arbitrary sparse matrices, including non-diagonalizable and singular cases.

  • Solution-error analysis: The truncation analysis is valid for arbitrary sparse A, including non-diagonalizable and singular matrices.The approach bounds the number of Taylor terms needed without relying on diagonalizability.
  • Solution-error analysis: Theorem 3 bounds the error between the exact solution xT and the truncated-Taylor solution ym after m time steps.The truncation order k is chosen so the Taylor approximation error remains controlled.
  • Solution-error analysis: The required Taylor order k does not depend on the condition number of A or its diagonalizing matrix.This removes a dependence present in analyses restricted to diagonalizable matrices.
  • Condition-number analysis: Theorem 4 bounds the condition number κL of the linear system used by the algorithm.The bound is derived from norms of the constructed system and the truncated Taylor representation.
  • Implementation and complexity: The algorithm prepares the initial state using oracle calls and applies block-encoded linear-system operations with polylogarithmic ancillary-gate overhead.The implementation uses sparse block encodings and the quantum linear systems algorithm.

6 Main result

The main result gives a quantum algorithm for sparse linear nonhomogeneous ODEs that prepares a state close to the normalized solution. Its complexity is expressed through matrix-dependent quantities and remains applicable beyond diagonalizable systems.

  • Main theorem: Theorem 7 provides a quantum algorithm for any sparse matrix A that prepares an ϵ-close state proportional to the solution.The theorem specifies overall query complexity and a corresponding gate-complexity bound.
  • Main theorem: Amplitude amplification accounts for the factor g in the final query and gate complexities.The success probability is proportional to O(1/g^2), requiring amplification for constant success probability.

7 Application to nonlinear differential equations

The paper applies Carleman linearization to quadratic nonlinear ODEs, converting them into higher-dimensional linear systems. Under negative log-norm and a suitable rescaling, truncation error is bounded and the resulting system can be solved quantumly.

  • Assumptions: The nonlinear model assumes time-independent F0, F1, and F2, with F1 allowed to be non-diagonalizable when μ(F1) < 0.The negative log-norm condition replaces a diagonalizability requirement for the dissipative linear term.
  • Carleman linearization: Carleman linearization converts a quadratic ODE into a linear equation of higher dimension.The construction produces a block-structured linear system whose truncation level controls the approximation.
  • Rescaling: A rescaling u = γy can make the initial-state norm strictly less than unity before applying the truncated linearization.Lemma 18 establishes a rescaling satisfying the required conditions when R < 1.
  • Error analysis: When R < 1, the truncation error ∥η1(t)∥ = ∥x1(t) − u(t)∥ is bounded through the Carleman approximation.The analysis uses convergence of the truncated error vector after rescaling.
  • Quantum algorithm: Theorem 8 gives an efficient quantum algorithm that prepares a state ϵ-close to a state proportional to the quadratic ODE solution.The algorithm measures truncation level 1 to recover a normalized state close to u(T)/∥u(T)∥.
  • Quantum algorithm: The truncated Carleman system has sparsity 3^N s, dimension O(d^N), and condition quantity C(A) ≤ N.These parameters determine the cost of applying the linear ODE algorithm to the nonlinear problem.

8 Conclusions

The conclusions emphasize broader matrix coverage and improved nonlinear-ODE error dependence. They also identify unresolved complexity dependence on ∥A∥ and the need to extend nonlinear analysis beyond the current conditions.

  • Linear equations: The linear algorithm handles many non-diagonalizable and even singular matrices, with exponentially better bounds for some diagonalizable matrices than prior work.The improvement applies when the matrix has non-positive log-norm and an exponentially large eigenvector condition number.
  • Linear equations: The matrix-exponential condition is useful for block matrices arising in nonlinear ODEs because it avoids checking diagonalizability or other spectral conditions.The conclusion connects the linear analysis to the block structure produced by nonlinear formulations.
  • Open questions: The dependence on ∥A∥ for stable matrices remains an open question, including whether it can be replaced by a quantity proportional to ρ(A).The spectral radius can be considerably smaller than the matrix norm for some matrices.
  • Nonlinear equations: For nonlinear differential equations, the algorithm exponentially improves the dependence on error and works with non-normal or non-diagonalizable F1 when its log-norm is negative.Extending the nonlinear result to more general sparse matrices requires a broader definition of R and a convergence proof for Carleman linearization.

A Proof of Lemma 15

The proof reduces the norm of a quadratic ODE solution to a scalar quadratic equation. Under R < 1, the resulting bound shows that the solution norm decreases from its initial value and remains below the larger root.

  • Scalar reduction: The proof bounds ∥u(t)∥ using a one-dimensional quadratic ODE with coefficients a = ∥F2∥, b = µ(F1), and c = ∥F0∥.The scalar equation is written as dx/dt = ax^2 + bx + c with x(0) = ∥uin∥.
  • Root structure: When R < 1, the scalar quadratic has distinct nonnegative roots satisfying 0 ≤ r− < r+.The equation factors as a(x − r−)(x − r+).
  • Closed-form solution: The shifted variable y = x − r− obeys a separable quadratic equation, yielding the closed-form solution for x(t).The transformed equation is dy/dt = ay[y − (r+ − r−)].
  • Norm bound: The solution norm satisfies the bound in (A.10), obtained by applying the scalar solution to ∥u(t)∥.This bound tracks the dependence on the initial norm and the two scalar roots.
  • Decay conclusion: Because ∥uin∥ lies strictly between r− and r+, the bound decreases from ∥uin∥ and gives ∥u(t)∥ < ∥uin∥ < r+ for every t > 0.The strict inequality follows from the sign of the bracketed term in (A.10).

B Proof of Lemma 18

The proof establishes a rescaling for quadratic ODEs satisfying R < 1. Choosing a scale between the initial norm and the larger root makes the rescaled coefficients satisfy the required dominance condition while preserving R < 1.

  • Rescaled system: Rescaling u = γy makes the new initial norm ∥y(0)∥ = ∥uin∥/γ < 1.The rescaled coefficients are denoted ã, b̃, and c̃.
  • Root interval: For R < 1, the quadratic equation associated with the ODE has nonnegative unequal roots 0 ≤ r− < r+, with Q(x) < 0 between them.The initial norm lies strictly inside this interval.
  • Choice of rescaling: Since Q(∥uin∥) < 0, a scale γ can be chosen in (∥uin∥, r+) such that Q(γ) < 0.The initial norm is not an endpoint because Q(∥uin∥) ≠ 0.
  • Required condition: The rescaled coefficients satisfy |b̃| > c̃ + ã, which fulfills condition (1) using Lemma 16.This is the key coefficient inequality established after choosing γ.
  • Invariance: Rescaling leaves R < 1 unchanged, so the second required condition remains valid for the rescaled ODE.The proof explicitly states that R is invariant under the rescaling.
Loading 2202.01054v5…