Accuracy Guarantees and Quantum Advantage in Analog Open Quantum Simulation with and without Noise

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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"><a:mi>ϵ</a:mi></a:math> in time that is <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"><c:mrow><c:mi>poly</c:mi></c:mrow><c:mo stretchy="false">(</c:mo><c:msup><c:mi>ϵ</c:mi><c:mrow><c:mo>−</c:mo><c:mn>1</c:mn></c:mrow></c:msup><c:mo stretchy="false">)</c:mo></c:math> 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 <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"><g:mrow><g:mi>BQP</g:mi><g:mo stretchy="false">≠</g:mo><g:mi>BPP</g:mi></g:mrow></g:math>. 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 <j:math xmlns:j="http://www.w3.org/1998/Math/MathML" display="inline"><j:mrow><j:mi>BQP</j:mi><j:mo stretchy="false">≠</j:mo><j:mi>BPP</j:mi></j:mrow></j:math>, 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.