Many-body systems arising in condensed matter physics and quantum optics inevitably couple to the environment and need to be modelled as open quantum systems.While near-optimal algorithms have been developed for simulating many-body quantum dynamics, algorithms for their open system counterparts remain less well investigated.We address the problem of simulating geometrically local many-body open quantum systems interacting with a stationary Gaussian environment.Under a smoothness assumption on the system-environment interaction, we develop near-optimal algorithms that, for a model with N spins and evolution time t, attain a simulation error δ in the system-state with O(N t(N t/δ) o( 1)) gates, O(t(N t/δ) o( 1)) parallelized circuit depth and Õ(N (N t/δ) o( 1)) ancillas.We additionally show that, if only simulating local observables is of interest, then the circuit depth of the digital algorithm can be chosen to be independent of the system size N .This provides theoretical evidence for the utility of these algorithms for simulating physically relevant models, where typically local observables are of interest, on pre-fault tolerant devices.Finally, for the limiting case of Markovian dynamics with commuting jump operators, we propose two algorithms based on sampling a Wiener process and on a locally dilated Hamiltonian construction, respectively.These algorithms reduce the asymptotic gate complexity on N compared to currently available algorithms in terms of the required number of geometrically local gates.
Many-body systems arising in condensed matter physics and quantum optics inevitably couple to the environment and need to be modelled as open quantum systems.While near-optimal algorithms have been developed for simulating many-body quantum dynamics, algorithms for their open system counterparts remain less well investigated.We address the problem of simulating geometrically local many-body open quantum systems interacting with a stationary Gaussian environment.Under a smoothness assumption on the system-environment interaction, we develop near-optimal algorithms that, for a model with N spins and evolution time t, attain a simulation error δ in the system-state with O(N t(N t/δ) o( 1)) gates, O(t(N t/δ) o( 1)) parallelized circuit depth and Õ(N (N t/δ) o( 1)) ancillas.We additionally show that, if only simulating local observables is of interest, then the circuit depth of the digital algorithm can be chosen to be independent of the system size N .This provides theoretical evidence for the utility of these algorithms for simulating physically relevant models, where typically local observables are of interest, on pre-fault tolerant devices.Finally, for the limiting case of Markovian dynamics with commuting jump operators, we propose two algorithms based on sampling a Wiener process and on a locally dilated Hamiltonian construction, respectively.These algorithms reduce the asymptotic gate complexity on N compared to currently available algorithms in terms of the required number of geometrically local gates.
Many-body systems arising in condensed matter physics and quantum optics inevitably couple to the environment and need to be modelled as open quantum systems. While near-optimal algorithms have been developed for simulating many-body quantum dynamics, algorithms for their open system counterparts remain less well investigated. We address the problem of simulating geometrically local many-body open quantum systems interacting with a stationary Gaussian environment. Under a smoothness assumption on the system-environment interaction, we develop near-optimal algorithms that, for a model with N spins and evolution time t, attain a simulation error δ in the system-state with O(Nt(Nt/δ)o(1)) gates, O(t(Nt/δ)o(1)) parallelized circuit depth and O~(N(Nt/δ)o(1)) ancillas. We additionally show that, if only simulating local observables is of interest, then the circuit depth of the digital algorithm can be chosen to be independent of the system size N. This provides theoretical evidence for the utility of these algorithms for simulating physically relevant models, where typically local observables are of interest, on pre-fault tolerant devices. Finally, for the limiting case of Markovian dynamics with commuting jump operators, we propose two algorithms based on sampling a Wiener process and on a locally dilated Hamiltonian construction, respectively. These algorithms reduce the asymptotic gate complexity on N compared to currently available algorithms in terms of the required number of geometrically local gates.
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy ε, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an n-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time T≥1, with circuit depth O(Tlog(nT/ε)) and gate count O(nTlog(nT/ε)). This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization.
Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time T in the stated regime and sufficiently small fixed error ε, any nearest-neighbor quantum circuit simulating these dynamics requires depth Ω(logn/loglogn). This matches our O(logn) upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.
We present an efficient algorithm for simulating open quantum systems dynamics described by the Lindblad master equation on quantum computers, addressing key challenges in the field. In contrast to existing approaches, our method achieves two significant advancements. First, we employ a repetition of unitary gates on a set of n system qubits and, remarkably, only a single ancillary bath qubit representing the environment. It follows that, for the typical case of m locality of the Lindblad operators, we reach an exponential improvement of the number of ancilla in terms of m and up to a polynomial improvement in ancilla overhead for large n with respect to other approaches. Although stochasticity is introduced, requiring multiple circuit realizations, the sampling overhead is independent of the system size. Second, we show that, under fixed accuracy conditions, our algorithm enables a reduction in the number of Trotter steps compared to other approaches, substantially decreasing circuit depth. These advancements hold particular significance for near-term quantum computers, where minimizing both width and depth is critical due to inherent noise in their dynamics. Published by the American Physical Society 2024
Open-system dynamics govern decoherence, transport, and engineered dissipation in quantum many-body systems. We propose a quantum algorithm for simulating time-independent, finite-range Lindblad dynamics with bounded local strength on a constant-dimensional lattice of n sites, allowing noncommuting jump operators. For time T≥1 and diamond-norm error at most ε, it has depth O(Tpolylog(nT/ε)) and gate count O(nTpolylog(nT/ε)). These results extend the HHKL spatial decomposition to open systems. The main obstacle is that the reversible overlap corrections used for unitary dynamics have no direct analogue for dissipative channels. We overcome this by retaining the environment in a shared unitary dilation, keeping information lost from the system coherently available and making the spatial corrections reversible. We prove exponential occupation bounds for the environmental states generated by the decomposition, allowing compact representation and coherent simulation of local factors on the inputs that arise. The construction reduces each short-time evolution to a constant number of parallel layers on regions of logarithmic diameter, using nearest-neighbour gates and polylogarithmic auxiliary density.
We also prove unconditional worst-case lower bounds using time-independent, purely dissipative processes that transport quantum information. For circuits with local quantum and classical communication, the lower bounds are Ω(nT) for the expected gate count and Ω(T) for depth on time scales up to the lattice diameter. They match the upper bounds' leading time and volume dependence up to polylogarithmic factors. At fixed time and sufficiently small fixed error, we further prove a depth lower bound of Ω(logn/loglogn), showing that global accuracy can require increasing depth as the lattice grows.
Many-body open quantum systems, described by Lindbladian master equations, are a rich class of physical models that display complex equilibrium and out-of-equilibrium phenomena which remain to be understood. In this paper, we theoretically analyze noisy analog quantum simulation of geometrically local open quantum systems and provide evidence that this problem both is hard to simulate on classical computers and could be approximately solved on near-term quantum devices. First, given a noiseless quantum simulator, we show that the dynamics of local observables and the fixed-point expectation values of rapidly mixing local observables in geometrically local Lindbladians can be obtained to a precision of ϵ in time that is poly ( ϵ − 1 ) and uniform in system size. Furthermore, we establish that the quantum simulator would provide a superpolynomial advantage, in run-time scaling with respect to the target precision and either the evolution time (when simulating dynamics) or the Lindbladian’s decay rate (when simulating fixed points), over any classical algorithm for these problems, assuming BQP ≠ BPP . We then consider the presence of noise in the quantum simulator in the form of additional geometrically local Lindbladian terms. We show that the simulation tasks considered in this paper are stable to errors; i.e., they can be solved to a noise-limited, but system-size independent, precision. Finally, we establish that, assuming BQP ≠ BPP , there are stable geometrically local Lindbladian simulation problems such that, as the noise rate on the simulator is reduced, classical algorithms must take time superpolynomially longer in the inverse noise rate to attain the same precision as the analog quantum simulator.
Simulating the dynamics of dissipative quantum many-body systems governed by local Lindbladians is a fundamental task in quantum computation. While the near-optimal gate count has been achieved for Hamiltonian simulation, comparable results for Lindbladian simulation remain elusive. In this work, we develop quantum algorithms for lattice Lindbladians by exploiting their locality. First, we consider sparsely dissipative systems, in which the dissipation is sparsely located, including boundary-driven systems. We establish a near-optimal quantum algorithm for their dynamics with gate count O(Ntpolylog(Nt/ε)), where N is the system size, t is the evolution time, and ε is the allowable error. We then consider generic lattice Lindbladians with finite-range interactions and dissipation, and develop an algorithm for simulating time-evolved observables with gate count O((Nt)4/3polylog(Nt/ε)) per sample with the sampling complexity Θ(ε−2). The gate count has the smallest known dependence on the system size among algorithms retaining polylogarithmic dependence on 1/ε. Our algorithms are based on two techniques that exploit locality: patching and merging. Patching decomposes dissipative dynamics into dynamics on subsystems with exponentially small error, generalizing a key idea underlying the Haah-Hastings-Kothari-Low algorithm for near-optimal Hamiltonian simulation. Merging absorbs reversed dissipative dynamics into other parts of the evolution, substantially reducing the overhead associated with quasi-probabilistic sampling. These results demonstrate that locality can be fully exploited to achieve fast quantum simulation of dissipative many-body dynamics, opening the way to applications such as predicting nonequilibrium phenomena and preparing desirable quantum states.