  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.
