Quantum Simulation of many-body physics with accuracy guarantees*

Several quantum hardware platforms, while being unable to perform fully fault-tolerant quantum computation, can still be operated as analogue quantum simulators for addressing many-body problems. However, due to the presence of errors and without explicit error correction, both (a) the extent to which the output of the quantum simulator can be trusted, and (b) if the quantum simulators provide a computational advantage over classical algorithms, remain unclear.

In this work we aim to theoretically answer both of these questions. We consider the use of noisy analogue quantum simulators for computing physically relevant properties of many-body systems both in  equilibrium and undergoing dynamics. We first propose a system-size independent criteria of stability against extensive errors, which if satisfied by the many-body models to be simulated, would allow us to compute its thermodynamic limit within a hardware-error limited but system-size independent precision on a noisy quantum simulator. We prove that this criteria is satisfied for various many-body models, including Gaussian fermion models, as well as for several (non-gaussian) spin systems. Remarkably, for Gaussian fermion models, our analysis shows the stability of translationally invariant observables in critical models inspite of them have long-range correlations. Furthermore, we analyze how this stability may lead to a quantum advantage, for the problem of computing the thermodynamic limits of many-body models, in the presence of a constant error rate and without any explicit error correction.

Finally, we outline and analyze concrete quantum simulation tasks, together with their implementation, for measuring local observables in both dynamics and steady state of spatially local master equations. We show that these tasks are stable to both coherent and incoherent errors in the simulator. Furthermore, we show a super-polynomial speedup, for the problem of dynamics, or an exponential speedup, for the problem of fixed points, can be obtained on a noisy quantum simulator over currently available classical algorithms.