Quantum computers are naturally suited for simulating unitary dynamics, offering the prospect of simulating quantum systems that the best known classical algorithms cannot handle. Recent years have seen much effort in extending this advantage to general linear ordinary differential equations (ODEs) which are not necessarily unitary. On classical computers, these ODEs are usually solved via the time-marching strategy, i.e., dividing the time into short segments and evolving for one segment at a time. It was previously believed that implementing this strategy on a quantum computer would result in a computational cost that is exponential in the number of time steps. In this study, we present an efficient algorithm for solving linear ODEs using the time-marching strategy. Our algorithm can handle non-smooth coefficient matrices, requires fewer queries to the initial state, and is free of some of the technical constraints present in previous works. One main technical tool we develop is a "compression gadget" that enhances the success probability of a sequence of non-unitary operations, which could have independent interest.
Copyright. All Rights Reserved.