Sampling Complexity of Open Quantum Systems

Open quantum systems are ubiquitous in the physical sciences, with widespread applications in the areas of chemistry, condensed-matter physics, material science, optics, and many more. Not surprisingly, there is significant interest in their efficient simulation. However, direct classical simulation quickly becomes intractable with coupling to an environment with an effective dimension that grows exponentially. This raises the question: Can quantum computers help model these complex dynamics A first step in answering this question requires an understanding of the computational complexity of this task. Here, we map the temporal complexity of a process to the spatial complexity of a many-body state using a computational model known as the process-tensor framework. 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 multitime correlations. The complexity of multitime sampling, which is an important and interesting problem in its own right, contains the complexity of master equations and stochastic maps as a special case. Our results show how the complexity of the underlying quantum stochastic process corresponds to the complexity of the associated family of master equations for the dynamics. We present both analytical and numerical examples where the multitime sampling of an open quantum system is as complex as sampling from a many-body state that is classically hard. This also implies that the corresponding family of master equations is classically hard. 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.