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.
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.
Simulating quantum many-body systems is essential for understanding complex phenomena in condensed matter, chemistry, and materials science. Quantum computing offers a way to overcome the limitations of classical methods by operating directly in exponentially large Hilbert spaces. In particular, classical methods often fail to capture the dynamics of strongly correlated systems, which makes quantum algorithms a promising alternative for exploring these challenging regimes. This thesis uses quantum dynamics simulations to probe the behaviour of many-body systems. We first introduce a spectroscopy-based protocol to extract excitation spectra from the time evolution of observables and analyse its performance on near-term quantum devices. We show that the protocol requires only short evolution times and is resilient to errors, facilitating its implementation on real hardware. Building on this, we simulate fermionic excitation spectra using current quantum devices, introducing resource optimisations - including an approximate free-fermion initial state, a unitary quench without ancillae, and reduced Trotter steps - that significantly lower circuit depth. These improvements enable simulations at system sizes competitive with the state of the art, yielding results that match classical benchmarks. While most studies focus on unitary dynamics of isolated systems, open quantum dynamics is increasingly relevant for describing non-equilibrium processes across biology, materials science, and quantum control. We extend our scope to systems coupled to an environment and governed by Lindbladian evolution. By studying simulation complexity through physically meaningful quantities - such as correlation length and mixing time - we explore whether open-system dynamics can be as tractable as their unitary counterparts. These findings provide insights into the computational complexity landscape of open-system simulation and highlight regimes where quantum methods offer a clear advantage.
Open quantum systems (OQS's) are ubiquitous in non-equilibrium quantum dynamics and in quantum science and technology. Solving the dynamics of an OQS in a quantum many-body bath has been considered a computationally hard problem because of the dimensionality curse. Here, considering that full knowledge of the bath dynamics is unnecessary for describing the reduced dynamics of an OQS, we prove a polynomial complexity theorem, that is, the number of independent equations required to fully describe the dynamics of an OQS increases at most linearly with the evolution time and polynomially with the bath size. Therefore, efficient computational algorithms exist for solving the dynamics of a small-sized OQS (such as a qubit or an atom). We further prove that, when the dynamics of an OQS and the bath is represented by a tensor network, a tensor contraction procedure can be specified such that the bond dimension (i.e., the range of tensor indices contracted in each step) increases only linearly (rather than exponentially) with the evolution time, providing explicitly efficient algorithms for a wide range of OQS's. We demonstrate the theorems and the tensor-network algorithm by solving two widely encountered OQS problems, namely, a spin in a Gaussian bath (the spin-boson model) and a central spin coupled to many environmental spins (the Gaudin model). This work provides approaches to understanding dynamics of OQS's, learning the environments via quantum sensors, and optimizing quantum information processing in noisy environments.
Open quantum systems have drawn attention over decades due to its applicability in the foundation of theoretical physics, e.g. statistical mechanics, quantum mechanics and condensed matter physics. The dynamics of open quantum systems has been described as separate entities from their surrounding environment that consists of a very large number of modes, somehow coupled to the mode of the system. Even though the exact solution of the dynamical behavior of the system is impossible to calculate, we obtain a tentative solution using the crucial Markov approximation. The input-output formalism of the quantum Langevin equation (QLE) has been considered as a useful tool which provides a semi-classical description of the dynamics of the system, whereas the master equation provides a complete picture of the dynamics of the system expressed in terms of density matrix. While studying the dynamics of nonlinear system/environment coupling using QLE, we see, for a small value of external field, that the steady state system field does not change much from the steady state field obtained in the absence of nonlinear dissipation. However, in a case where a stronger external field is applied, we see that the deviation becomes substantial from the solution of linear system. We also see that the nonlinear coupling introduces significant difference in the cavity fluctuation spectrum. The description, therefore, provides a potential explanation of parametric effects in terms of nonlinear dissipation phenomena associated with the nonlinear coupling. Even though the theories developed in the context of open quantum systems have proven to be powerful tools, they do not provide a satisfactory platform to be implemented on non-linear Hamiltonians. We often approximate it by linearizing over nonlinear steady state field amplitude, and therefore, the interesting effects are often overlooked. The limitation of the analytics provokes us to simulate open quantum dynamics numerically. The numerical method consists of transformation of the environmental degrees of freedom to a one-dimensional many-body chain, and the computational technique includes numerical diagonalization and renormalization process. The time-adaptive density matrix renormalisation group (t-DMRG) is known as one of the most powerful techniques for the simulation of strongly-correlated many-body quantum systems. In this thesis, along with the theoretical modeling, we implement DMRG numerical scheme for the simulation of canonical S/B model by mapping it to one-dimensional harmonic chain with nearest neighbor interactions, and use the method to investigate the dynamics of the free dissipative system. The thermalization of open quantum systems is also studied by generating minimally entangled typical thermal states (METTS) through imaginary time evolution, and real-time evolving an empty system in the presence of the thermal bath. Further, we simulate coherently driven free dissipative Kerr nonlinear system numerically using Euler's method by solving Heisenberg equation of motion and t-DMRG algorithm, and demonstrate how the numerical results are analogous to classical bistability. By comparing with analytics, we see that the DMRG numerics is analogous to the quantum-mechanical exact solution obtained by mapping the equation of motion of the density matrix of the system to a Fokker-Plank equation. The comparison between two different numerical techniques shows that the semi-classical Euler's method determines the dynamics of the system field of one among two coherent branches, whereas DMRG numerics gives the superposition of both of them. Hence, DMRG-determined time dynamics undergoes generating non-classical states. Our approach of dealing with nonlinearity represents an important contribution in the developments of technique to study the dynamical and steady-state behavior of open quantum systems, which is a fundamental aspect of quantum physics.
Problems in the field of open quantum systems often involve an environment that strongly influences the dynamics of excited states. Here we present a numerical method to model optical spectra of non-Markovian open quantum systems. The method employs a process tensor framework to efficiently compute multitime correlations in a numerically exact way. To demonstrate the efficacy of our method, we compare 2D electronic spectroscopy simulations produced through our method to Markovian master equation simulations in three different system-bath coupling regimes.
Randomness is an intrinsic feature of quantum theory. The outcome of any measurement will be random, sampled from a probability distribution that is defined by the measured quantum state. The task of sampling from a prescribed probability distribution therefore seems to be a natural technological application of quantum devices. And indeed, certain random sampling tasks have been proposed to experimentally demonstrate the speedup of quantum over classical computation, so-called “quantum computational supremacy”. In the research presented in this thesis, I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms. Using the theory of computational complexity, I assess the computational power of natural quantum simulators and close loopholes in the complexity-theoretic argument for the classical intractability of quantum samplers (Part I). In particular, I prove anticoncentration for quantum circuit families that give rise to a 2-design and review methods for proving average-case hardness. I present quantum random sampling schemes that are tailored to large-scale quantum simulation hardware but at the same time rise up to the highest standard in terms of their complexity-theoretic underpinning. Using methods from property testing and quantum system identification, I shed light on the question, how and under which conditions quantum sampling devices can be tested or verified in regimes that are not simulable on classical computers (Part II). I present a no-go result that prevents efficient verification of quantum random sampling schemes as well as approaches using which this no-go result can be circumvented. In particular, I develop fully efficient verification protocols in what I call the measurement-device-dependent scenario in which single-qubit measurements are assumed to function with high accuracy. Finally, I try to understand the physical mechanisms governing the computational boundary between classical and quantum computing devices by challenging their computational power using tools from computational physics and the theory of computational complexity (Part III). I develop efficiently computable measures of the infamous Monte Carlo sign problem and assess those measures both in terms of their practicability as a tool for alleviating or easing the sign problem and the computational complexity of this task. An overarching theme of the thesis is the quantum sign problem which arises due to destructive interference between paths – an intrinsically quantum effect. The (non-)existence of a sign problem takes on the role as a criterion which delineates the boundary between classical and quantum computing devices. I begin the thesis by identifying the quantum sign problem as a root of the computational intractability of quantum output probabilities. It turns out that the intricate structure of the probability distributions the sign problem gives rise to, prohibits their verification from few samples. In an ironic twist, I show that assessing the intrinsic sign problem of a quantum system is again an intractable problem.
Recent advances in quantum technologies and related experiments have created a need for highly accurate, versatile, and computationally efficient simulation techniques for the dynamics of open quantum systems. Long-lived correlation effects (non-Markovianity), system-environment hybridization, and the necessity for accuracy beyond the Born-Markov approximation form particular challenges. Approaches to meet these challenges have been introduced, originating from different fields, such as hierarchical equations of motion, Lindblad-pseudomode formulas, chain-mapping approaches, quantum Brownian motion master equations, stochastic unravelings, and refined quantum master equations. This diversity, while indicative of the field's relevance, has inadvertently led to a fragmentation that hinders cohesive advances and their effective cross-community application to current problems for complex systems. How are different approaches related to each other? What are their strengths and limitations? Here we give a systematic overview and concise discussion addressing these questions. We make use of a unified framework which very conveniently allows to link different schemes and, this way, may also catalyze further progress. In line with the state of the art, this framework is formulated not in a fully reduced space of the system but in an extended state space which in a minimal fashion includes effective reservoir modes. This in turn offers a comprehensive understanding of existing methods, elucidating their physical interpretations, interconnections, and applicability.