Time-marching based quantum solvers for time- dependent linear differential equations

Di Fang

doi:10.22331/q-2023-03-20-955

2023-03-20

Di Fang *

Lin Lin

Yu Tong

DOI：10.22331/q-2023-03-20-955

原文链接

原文求助

摘要

En 中文

The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general homogeneous linear differential equa-tions ddt| (t)) = A(t)|,(t)),|0(0)) = |???0), a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplifica-tion, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quan-tum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ra-tio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in the worst case. This algorithm also sur-passes existing QLSA based solvers in three aspects: (1) A(t) does not need to be diagonalizable. (2) A(t) can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state |???0). Finally, we demonstrate the time -marching strategy with a first-order truncated Magnus series, which simplifies the implementation compared to high-order truncated Dyson series approach, while retaining the aforementioned benefits. Our analysis also raises some open ques-tions concerning the differences between time-marching and QLSA based methods for solving differential equations.

Keyword:

HAMILTONIAN SIMULATION

ALGORITHMS