Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems
Abstract
We present an efficient quantum algorithm for solving linear matrix differential equations, with
applications to the simulation of open quantum systems and beyond. The algorithm computes an entry of the solution matrix with query complexity O(L /ϵ), where L is a product of time integrals of the norms of the evolution operators induced by individual matrices and ϵ is the error. This L is quadratic in the evolution time t for unitary dynamics and can be logarithmic in t 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. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of quantum Langevin dynamics for non-interacting fermions, and comment on applications to other quantum and classical systems. We compare with classical algorithms and give evidence of significant polynomial quantum speedups for systems in a lattice, which become more significant for systems with long-range interactions, and are exponential in general. We also provide a lower bound of Ω(t2/ϵ) for non-dissipative or weakly dissipative systems that proves our algorithm is optimal up to logarithmic factors.
applications to the simulation of open quantum systems and beyond. The algorithm computes an entry of the solution matrix with query complexity O(L /ϵ), where L is a product of time integrals of the norms of the evolution operators induced by individual matrices and ϵ is the error. This L is quadratic in the evolution time t for unitary dynamics and can be logarithmic in t 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. We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of quantum Langevin dynamics for non-interacting fermions, and comment on applications to other quantum and classical systems. We compare with classical algorithms and give evidence of significant polynomial quantum speedups for systems in a lattice, which become more significant for systems with long-range interactions, and are exponential in general. We also provide a lower bound of Ω(t2/ϵ) for non-dissipative or weakly dissipative systems that proves our algorithm is optimal up to logarithmic factors.
