On the sampling complexity of open quantum systems*

The simulation of open quantum systems remains one of the leading candidates for demonstrating quantum advantage, and has widespread applications in the areas of chemistry, condensed matter physics, optics, and many more. Understanding the computational complexity of these systems is a fundamental step towards precisely identifying which problems are beyond the reach of classical computation. Here, we map the temporal complexity of a process to the spatial complexity of a many-body state. With this, we are able to explore the simulation complexity of an open quantum system as a dynamic sampling problem: a system coupled to an environment can be probed at successive points in time -- accessing multi-time correlations. We argue that the complexity of multi-time sampling contains the complexity of master equations and stochastic maps as a special case. We present both analytical and numerical examples whose multi-time sampling is as complex as sampling from a many-body state that is classically hard. This implies that the corresponding family of master equations is also complex. Our results pave the way for studying open quantum systems from a complexity-theoretic perspective, highlighting the role quantum computers will play in our understanding of quantum dynamics.