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 (72)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Random-Matrix Theory of Quantum Transport
• Random Matrix Theories in Quantum Physics: Common Concepts
• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Characterizing Quantum Supremacy in Near-Term Devices
• On the role of entanglement in quantum computational speed-up
• Informational derivation of Quantum Theory
• Statistics of resonance poles, phase shifts and time delays in quantum chaotic scattering for systems with broken time reversal invariance
• Efficient non-Markovian quantum dynamics using time-evolving matrix product operators
• Non-Markovian quantum processes: complete framework and efficient characterisation
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Operational Markov condition for quantum processes
• Simulating quantum many-body dynamics on a current digital quantum computer
• Quantum causal modelling
• Simulation methods for open quantum many-body systems
• Variational Quantum Monte Carlo Method with a Neural-Network Ansatz for Open Quantum Systems
• Non-Markovian Dynamical Maps: Numerical Processing of Open Quantum Trajectories
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Quantum stochastic processes and quantum non-Markovian phenomena
• Instantaneous Quantum Computation
• Exploiting the causal tensor network structure of quantum processes to efficiently simulate non-Markovian path integrals
• Memory Effects In Nonequilibrium Quantum Impurity Models
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Numerically Exact Long Time Magnetization Dynamics at the Nonequilibrium Kondo Crossover of the Anderson Impurity Model
• Demonstration of non-Markovian process characterisation and control on a quantum processor
• Numerically exact open quantum systems simulations for arbitrary environments using automated compression of environments
• Efficient factorization with a single pure qubit and $logN$ mixed qubits
• Composed ensembles of random unitary matrices
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Scalable quantum computation via local control of only two qubits
• Local controllability of quantum networks
• Machine learning non-Markovian quantum dynamics
• On the hardness of classically simulating the one clean qubit model
• Non-Markovian Quantum Process Tomography
• When is a non-Markovian quantum process classical?
• Simulation complexity of open quantum dynamics: Connection with tensor networks
• Efficient simulation of non-Markovian system-environment interaction
• Inchworm Monte Carlo for exact non-adiabatic dynamics I. Theory and algorithms
• Capturing Non-Markovian Dynamics on Near-Term Quantum Computers
• Kolmogorov extension theorem for (quantum) causal modelling and general probabilistic theories
• Classical quantum stochastic processes
• Initial System-Environment Correlations via the Transfer Tensor Method
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Driven quantum dynamics: will it blend?
• Local quantum control of Heisenberg spin chains
• Updating the Born rule
• Tomographically reconstructed master equations for any open quantum dynamics
• Tensor network based machine learning of non-Markovian quantum processes
• Multi-time density correlation functions in glass-forming liquids: Probing dynamical heterogeneity and its lifetime
• Dynamical phase transitions in sampling complexity
• Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
• Efficient decomposition of unitary matrices in quantum circuit compilers
• Witnessing quantum memory in non-Markovian processes
• Efficient Real-Time Path Integrals for Non-Markovian Spin-Boson Models
• Almost Markovian processes from closed dynamics
• Reconstructing open quantum system dynamics with limited control
• Exact Master Equation and General Non-Markovian Dynamics in Open Quantum Systems
• Genuine Multipartite Entanglement in Time
• Effect of Strong Electron Correlation on the Efficiency of Photosynthetic Light Harvesting
• A discrete memory-kernel for multi-time correlations in non-Markovian quantum processes
• Quantum Markovianity as a supervised learning task
• Markovianization with approximate unitary designs
• What the foundations of quantum computer science teach us about chemistry
• Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
• Exact sampling hardness of Ising spin models
• Transfer-tensor description of memory effects in open-system dynamics and multi-time statistics
• Entanglement and complexity of interacting qubits subject to asymmetric noise
• Model-Independent Simulation Complexity of Complex Quantum Dynamics

Cited by in corpus (12)

• 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
• What can unitary sequences tell us about multi-time physics?
• Noise Correlations in a 1D Silicon Spin Qubit Array
• Relations between Markovian and non-Markovian correlations in multitime quantum processes
• Unifying non-Markovian characterisation with an efficient and self-consistent framework
• Process tensor distinguishability measures
• Efficient learning and optimizing non-Gaussian correlated noise in digitally controlled qubit systems
• Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
• Diagnosing chaos with projected ensembles of process tensors