  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 analogue quantum simulation of geometrically local
open quantum systems and provide evidence that this problem is both 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 $\varepsilon$ in time that is
$\text{poly}(\varepsilon^{-1})$ and uniform in system size. Furthermore, we
establish that the quantum simulator would provide an exponential 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 unless
BQP = BPP. We then consider the presence of noise in the quantum simulator in
the form of additional geometrically-local Linbdladian 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 there are stable geometrically local Lindbladian simulation
problems such that as the noise rate on the simulator is reduced, classical
algorithms must take time exponentially longer in the inverse noise rate to
attain the same precision unless BQP = BPP.
