PaperlayerView exact revision on arXiv

Source-linked AI summary

High-order quantum algorithm for solving linear differential equations

Dominic W. Berry

arXiv:1010.2745v2quant-phmath.NA

TL;DR

Large sparse linear differential equations arise throughout science and engineering, motivating quantum algorithms that improve on earlier approaches. The paper encodes general inhomogeneous sparse systems as quantum linear systems and uses high-order linear multistep methods. Under reasonable conditions, the complexity scales as ˜O(∆t^2), with the solution encoded in quantum-state amplitudes.

  • Problem

    Quantum algorithms are sought for large sparse linear differential equations arising in science and engineering, including systems beyond the homogeneous equations of quantum mechanics.

  • Method

    The paper encodes discretized sparse linear differential equations as linear systems using a time register and applies quantum linear-system algorithms with high-order linear multistep methods.

  • Results

    Under reasonable conditions, the complexity scales as ˜O(∆t^2) in evolution time, while the solution at the final time can be obtained as a quantum state to trace distance ǫ.

  • Takeaways & Limitations

    The approach extends quantum simulation algorithms to general inhomogeneous sparse linear differential equations whose solutions are encoded in amplitudes, allowing useful global information to be extracted in many cases.

Abstract

from arXiv · show

Linear differential equations are ubiquitous in science and engineering. Quantum computers can simulate quantum systems, which are described by a restricted type of linear differential equations. Here we extend quantum simulation algorithms to general inhomogeneous sparse linear differential equations, which describe many classical physical systems. We examine the use of high-order methods to improve the efficiency. These provide scaling close to $Δt^2$ in the evolution time $Δt$. As with other algorithms of this type, the solution is encoded in amplitudes of the quantum state, and it is possible to extract global features of the solution.

I. INTRODUCTION

The paper targets sparse linear differential equations as a more natural and efficient quantum-computing application than general nonlinear equations. It seeks logarithmic dimension scaling while addressing inhomogeneous systems and evolution-time efficiency.

  • Motivation: Quantum algorithms for differential equations are motivated by their broad use in industrial design, weather prediction, supercomputing, and discretized physical models.Examples include Stokes, heat, and Maxwell equations, whose discretization produces large sparse ordinary differential equations.
  • Motivation: Restricting the problem to linear differential equations enables substantially more efficient quantum algorithms than the earlier nonlinear approach.Quantum mechanics itself is described by linear differential equations, although the paper addresses more general forms.
  • Problem setting: The considered systems are first-order, sparse, and may be inhomogeneous, with x and b as Nx-component vectors and A as a sparse Nx × Nx matrix.Higher-order linear equations can be converted into first-order systems with larger dimension.
  • Problem setting: The quantum algorithm aims to solve these equations in time O(poly log Nx), compared with at least linear classical complexity in Nx.The target concerns dimension scaling rather than explicit output of every solution component.
  • Scope: The paper extends quantum simulation beyond homogeneous Hamiltonian-like equations to general systems whose solutions may grow or decay exponentially.Quantum-mechanical cases have b(t) = 0 and A(t) = iH(t) with H(t) Hermitian.
  • Contribution: High-order methods are introduced to obtain complexity scaling as ˜O(∆t^2) in evolution time, while the solution remains encoded in quantum-state amplitudes.The paper notes that useful global information may nevertheless be extracted from the encoded state.

II. LIE-TROTTER FORMULA APPROACH

The Lie-Trotter approach decomposes a general matrix into Hermitian and antiHermitian parts and combines their simulated evolutions. Its main drawback is exponential complexity in the evolution interval and inability to handle inhomogeneous equations.

  • Homogeneous cases: For homogeneous equations with antiHermitian A, the problem is analogous to Hamiltonian evolution and can use Hamiltonian-simulation methods.When A is Hermitian, it can instead be diagonalized using a unitary eigenvector matrix and real diagonal eigenvalue matrix.
  • State encoding: The solution can be encoded in a quantum state whose computational-basis amplitudes are proportional to the components of x.The state may also be expressed in the eigenbasis of A.
  • State encoding: Phase estimation and coherent amplitude changes can encode the time-evolved solution when evolution under iA is simulable.For an eigenstate, the eigenvalue is determined and the amplitude is rescaled according to its shifted eigenvalue.
  • General equations: For general A, decomposing it into Hermitian and antiHermitian components allows separate simulation followed by Lie-Trotter combination.This approach is presented as an informal preliminary method rather than the paper’s main proposal.
  • General equations: The amplitude decays exponentially because the simulation must accommodate the largest eigenvalue of the Hermitian component, which can exceed the largest real part of A’s eigenvalues.This mismatch does not generally occur for purely Hermitian A.
  • Limitations: Exponential complexity in ∆t and inability to simulate inhomogeneous equations make the Lie-Trotter approach unsuitable as the main method.The paper seeks polynomial evolution-time scaling instead.

III. LINEAR SYSTEMS APPROACH

The linear-systems approach encodes the discretized time evolution, including the initial condition and a constant extension after the target time, into one quantum state. Its Euler-based analysis gives poor ∆t scaling, motivating higher-order multistep methods.

  • Linear-system encoding: The proposed approach uses a linear-system algorithm with an additional Feynman’s-clock register that encodes time.This avoids the exponential evolution-time behavior of the Lie-Trotter approach.
  • Linear-system encoding: One quantum state encodes the solution across all discretized times, with tj = t0 + jh and Nt time steps over total interval ∆t.The vectors xj approximate x at each time tj.
  • Readout: Extending x as constant from t0 + ∆t to t0 + 2∆t increases the probability of measuring a time in the final-time interval.Without this extension, measuring the final time succeeds with probability 1/(Nt + 1).
  • Discretization: The encoded linear system includes an initial-condition row, Euler discretization rows, and constant-extension rows after the target time.The Euler rows enforce xj+1 − (xj + Axjh) = bh, while the extension rows enforce xj+1 − xj = 0.
  • Error and complexity: O(∆t^2/Nt) total Euler error requires Nt = O(∆t^2/ǫ) time steps to achieve error ǫ.This scaling contributes to the cost analysis of solving the resulting linear system.
  • Error and complexity: O(∆t^4) complexity follows from the estimated condition number O(Nt) in the basic Euler-based linear-systems approach.The paper describes this ∆t scaling as unexpectedly poor and motivates higher-order methods.
  • Higher-order methods: Higher-order linear multistep methods are proposed to improve the unexpectedly poor evolution-time scaling.The supplied passage identifies the motivation but does not state the improved bound here.

IV. MULTISTEP METHODS

The paper uses linear multistep methods to obtain higher-order discretizations while controlling stability, error, and quantum linear-system implementation. Under suitable stability conditions, the resulting time-step requirement is close to linear in evolution time.

  • Method order: Linear multistep methods approximate the differential equation with local errors O(h^p+1) for order p.Higher order reduces discretization error as the step size h decreases.
  • Stability: A-stability preserves boundedness for problems whose scalar eigenvalues lie in the left half-plane, but the Dahlquist barrier restricts A-stable multistep methods to order p ≤2.The paper therefore uses the weaker A(α)-stability condition for higher-order methods.
  • Stability: A(α)-stability requires the relevant eigenvalues to lie within a wedge in the left half of the complex plane.For vector equations, the eigenvalues of A must lie inside this wedge.
  • Error bounds: For order-p methods, the total error scales as O(N_t(Δt)^p+1), so the discretization error can decrease with higher order.The rigorous bound is specialized to time-independent A and b and includes stability assumptions.
  • Error bounds: The resulting error scales as O((∥A∥h)^p∥A∥Δt), and the required number of time steps is close to linear in the evolution time.This excludes dependence on several quantities and omits starting-method error.
  • Quantum encoding: The multistep method is encoded as a sparse linear system using Euler initialization, higher-order recurrence rows, and final rows enforcing constant solution blocks.The construction requires N_t ≥2k and sparse oracles for A, b, and the initial condition.

V. BOUNDING THE CONDITION NUMBER

The condition number of the encoded linear system is bounded by analyzing its block structure after diagonalizing the differential-equation matrix. Under stability and step-size assumptions, it grows linearly with the number of time steps.

  • Matrix-norm bounds: The block matrix norm satisfies ∥A∥ = O(1) provided the time step obeys h = O(1/∥A∥).The proof decomposes the matrix into block-diagonal components and applies the triangle inequality.
  • Inverse-norm bound: The inverse norm satisfies ∥A^-1∥ = O(N_tκ_V) under the same diagonalizability and eigenvalue conditions.This bound follows by transforming the system into decoupled scalar multistep blocks.
  • Inverse-norm bound: The bound on ∥A^-1∥ is obtained by treating each diagonalized block as a linear multistep solution for a decoupled scalar differential equation.The overall norm is bounded by the largest inverse-block norm.
  • Condition-number bound: The encoded matrix has condition number κ = O(N_tκ_V) when the multistep method is A(α)-stable and A is diagonalizable with eigenvalues in the stability wedge.Here κ_V is the condition number of the diagonalizing matrix V, and h = O(1/∥A∥).
  • Interpretation: Each right-hand-side block can be interpreted as an excitation at one time, whose effect persists for at most the remaining stable evolution.This gives the intuitive N_t factor in the inverse-norm bound.

VI. ALGORITHM FOR SOLVING LINEAR SYSTEMS

The algorithm converts time evolution under sparse linear differential equations into a quantum linear-system problem, encoding time and solution data in quantum registers. Under stated stability and diagonalization conditions, it obtains the final-time solution with controlled trace-distance error and constant success probability.

  • Algorithm construction: The method translates solving a linear differential equation into solving a sparse linear system whose registers encode time and vector data.A Feynman-clock register represents time, while additional registers encode the relevant vectors.
  • Conditions and guarantee: Theorem 9 applies when the multistep method is order p and A(α)-stable, A is diagonalizable, and its eigenvalues satisfy the stated angular condition.These are the principal assumptions used for the complexity guarantee.
  • Algorithm construction: The quantum state encoding the solution at t0+∆t is obtained by measuring the time register in the final-time interval.The accepted interval is t0+∆t to t0+2∆t, corresponding to indices Nt/2 through Nt.
  • Conditions and guarantee: The algorithm achieves trace distance O(ǫ) while maintaining success probability Ω(1).The linear-system error can be set to ǫL = Θ(ǫ), and the resulting success probability remains bounded below by a constant.
  • Complexity: The overall oracle complexity follows from the linear-system solver, condition-number bound, state preparation, and a time-step choice enforcing h = O(1/∥A∥).The construction assumes oracles for A, b, and xin, with vector-state preparation contributing to the total complexity.
  • Complexity: Including starting-error terms makes the reported complexity conservative, while neglecting that error preserves the ∥A∥∆t scaling and improves other parameter dependences.The authors explicitly separate the conservative bound from the improved expression obtained under negligible starting error.

VII. VARIABLE TIME AMPLITUDE AMPLIFICATION

The paper examines variable time amplitude amplification as a possible route to improve the algorithm’s dependence on evolution time and condition number. Its recursive Estimate procedure adds complexity that prevents the apparent near-linear scaling from being attained.

  • Motivation: The presented algorithm scales close to ∆t^2, although the known lower bound is linear in ∆t.The authors identify the κ^2 dependence inherited from HHL as the factor increasing the evolution-time scaling.
  • Apparent improvement: Because κ scales linearly in Nt, which is close to linear in ∆t, variable time amplitude amplification initially appears capable of yielding near-linear evolution-time scaling.This apparent improvement considers only the scaling in κ and ǫL.
  • Recursive overhead: The Estimate procedure prevents that near-linear scaling by adding complexity to the recursive construction of the algorithms Ai and Bi.The recursion uses estimated probabilities to choose later amplification parameters.
  • Recursive overhead: The resulting overhead scales as (κ/ǫL)[log log(κ/ǫL)]/2 in the large-κ/ǫL limit, exceeding linear scaling and yielding no apparent improvement in ∆t.The bound follows from recursively multiplying the amplitude-amplification contribution across m = log Tmax steps.

VIII. CONCLUSIONS

The paper presents a quantum algorithm for sparse linear differential equations by encoding them as linear systems, with applications to systems whose solutions can be represented in quantum states. The results assume constant coefficients, while time-dependent coefficients remain possible but require more difficult error analysis.

  • The algorithm solves sparse linear differential equations by encoding them as a linear system and applying a quantum linear-system algorithm.Its complexity analysis includes scaling in ∥A∥ and Δt.
  • The method applies when the differential-equation solution can be encoded in a quantum state rather than output explicitly.
  • The algorithm improves on previous nonlinear-differential-equation results that scaled exponentially in the number of time steps.
  • These results target ubiquitous differential-equation systems, including large systems arising from discretized partial differential equations.
  • The analysis is for constant coefficients; time-dependent coefficients are also approachable, but their error analysis is more difficult.
Loading 1010.2745v2…