Description and complexity of Non-markovian open quantum dynamics

Understanding and simulating non-Markovian quantum dynamics remains an important challenge in open quantum system theory. A key advance in this endeavour would be to develop a unified mathematical description of non-Markovian dynamics, and classify its complexity in the many-body setting. In this paper, we identify a general class of non-Markovian memory kernels, described by complex-valued radon measures, and define their dynamics through a regularization procedure constructing the corresponding system-environment unitary groups. Building on this definition, we then consider $k-$local many-body non-Markovian systems with physically motivated assumptions on the total variation and smoothness of the memory kernels. We establish that their dynamics can be efficiently approximated on quantum computers, thus providing a rigorous verification of the Extended Church-Turing thesis for this general class of non-Markovian open quantum systems.