On the sampling complexity of open quantum systems

Abstract

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 whose effective dimension grows exponentially. This raises the question: can quantum computers help model these complex dynamics? A first step in answering this question requires understanding 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 multi-time correlations. The complexity of multi-time 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 whose multi-time sampling is as complex as sampling from a many-body state that is classically hard. This also implies that the corresponding family of master equations are 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.

References in corpus (10)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Operational Markov condition for quantum processes
• Variational Quantum Monte Carlo Method with a Neural-Network Ansatz for Open Quantum Systems
• Local controllability of quantum networks
• Inchworm Monte Carlo for exact non-adiabatic dynamics I. Theory and algorithms
• Initial System-Environment Correlations via the Transfer Tensor Method
• Multi-time density correlation functions in glass-forming liquids: Probing dynamical heterogeneity and its lifetime
• Quantum Markovianity as a supervised learning task
• What the foundations of quantum computer science teach us about chemistry

Cited by in corpus (11)

• A Site-Resolved 2D Quantum Simulator with Hundreds of Trapped Ions
• Simulating open quantum systems with giant atoms
• Capturing long-range memory structures with tree-geometry process tensors
• Quantum processes as thermodynamic resources: the role of non-Markovianity
• Relations between Markovian and non-Markovian correlations in multitime quantum processes
• Noise Correlations in a 1D Silicon Spin Qubit Array
• Unifying non-Markovian characterisation with an efficient and self-consistent framework
• Process tensor distinguishability measures
• Diagnosing chaos with projected ensembles of process tensors
• Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
• Efficient learning and optimizing non-Gaussian correlated noise in digitally controlled qubit systems