Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems

We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations, with applications to the simulation of open quantum systems and beyond. For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query complexity widetilde{mathcal{O}}\(νmathcal{L} t/ε\), where the constant ν depends on the problem parameters, mathcal{L} involves a time integral of upper bounds on the norms of evolution operators, and ε is the error. In particular, νmathcal{L} is linear in t for unitary dynamics and can be a constant for dissipative dynamics. Our result contrasts prior quantum approaches for differential equations that typically require exponential time for this problem due to the encoding in a quantum state, which can lead to exponentially small amplitudes. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions, which can be extended to other quantum and classical systems. We compare with classical algorithms and give evidence of polynomial quantum speedups for systems in a lattice, which become more pronounced for systems with long-range interactions and can be shown to be exponential in general. We also provide a lower bound of Ω\(νmathcal{L} t/ε\) for unitary or dissipative dynamics that proves our algorithm is optimal up to logarithmic factors.