Southwest Quantum Information and Technology

Quantum algorithm for linear differential equations with exponentially improved dependence on precision

Presenting Author: Aaron Ostrander, QuICS, University of Maryland
Contributing Author(s): Dominic Berry, Andrew Childs and Guoming Wang

Recently quantum algorithms for Hamiltonian simulation have been proposed which have complexity logarithmic in the inverse error. Hamiltonian simulation is just a special case of simulating the ordinary differential equation dx/dt=Ax+b where A is anti-Hermitian and b=0. For more general A, the complexity of such a simulation is less well understood. Berry proposed a quantum algorithm for ODEs using linear multistep methods that is polynomial in the inverse error. This algorithm encoded the simulation problem in a linear system and used a quantum linear systems algorithm (QLSA) to solve the system. Recently, QLSAs which scale logarithmically in the inverse error have been proposed. However, this exponential improvement in solving linear systems does not necessarily translate to an exponential improvement for algorithms that use the QLSA as a subroutine. In fact, Berry’s algorithm has polynomial scaling regardless of which QLSA is used. This is because there are other error-dependent parameters in the algorithm that contribute to the complexity. In this work, we revisit the problem of solving linear differential equations and propose a new QLSA-based algorithm that scales logarithmically in the inverse error. Our approach is based on evolving according to the propagator exp(At) by approximating it using a Taylor series.

(Session 5 : Thursday from 5:00pm - 7:00pm)