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.
We develop a systematic and efficient approach for numerically solving the non-Markovian quantum state diffusion equation for an open quantum system that can be strongly coupled to an environment. As an important application, we consider a real-time simulation of a spin-boson model in a strong-coupling regime that is difficult to deal with using conventional methods. We show that the non-Markovian stochastic Schr\"odinger equation can be efficiently implemented as a real-time simulation for this model, so as to give an accurate description of spin-boson dynamics beyond the rotating-wave approximation.