Quantum computers hold the promise of surpassing classical computers in solving certain problems. However, fault-tolerant quantum computers, necessary for most algorithms with performance guarantees, remain a significant technological challenge. Analogue quantum simulators, which mimic a target Hamiltonian, offer a near-term alternative for addressing many-body physics problems. These simulators, while not capable of universal computation, aim to approximate relevant Hamiltonians and measure intensive observables (local observables or correlation functions). They possess advantages over general-purpose quantum computers, including milder hardware requirements and natural suitability for many-body problems, avoiding error-prone Hamiltonian-to-circuit mappings. The expectation is that local intensive observables will be robust to errors, even if the global quantum state is sensitive. However, rigorously establishing the quantum advantage of noisy quantum simulators presents theoretical challenges. First, error correction is absent, and noise is inherent. While noiseless simulators' computational power has been explored, the impact of realistic errors on many-body problems hasn't been fully addressed. Second, the focus on intensive observables and the thermodynamic limit requires a revised notion of quantum advantage, shifting from system size to precision in the thermodynamic limit. This paper addresses these challenges by showing that noisy quantum simulators can determine the thermodynamic limits of intensive observables to a hardware-limited precision. A new notion of quantum advantage in the presence of errors is proposed, using computational time to obtain an intensive quantity in the thermodynamic limit to a hardware-limited precision as a figure of merit. Lower bounds on classical algorithms provide evidence of superpolynomial to exponential quantum advantage, even without error correction.

The paper references numerous works on fault-tolerant quantum computation, quantum algorithms, universal quantum simulators, and the computational power of noiseless quantum simulators. It also cites research on analogue quantum simulators, their application to various many-body physics problems (correlated electronic systems, quantum spin systems, lattice-gauge theories), and their implementation on different hardware platforms (cold atoms, trapped ions, superconducting qubits). The literature review highlights the lack of rigorous criteria for outlining the quantum advantage of noisy simulators and the need for a revised notion of quantum advantage focusing on the precision of intensive observables in the thermodynamic limit. Previous works on the stability of local observables in constant-time dynamics and equilibrium are also reviewed, along with studies on the stability of the gap in the presence of errors.

The authors analyze both closed (Hamiltonian) and open (Lindbladian) many-body systems. They model the implemented Lindbladian on a quantum simulator, accounting for errors in the Lindbladian configuration and interaction with a decohering environment. Non-Markovian incoherent errors are also considered, modeled using Gaussian environments. A key contribution is the definition of a 'stable quantum simulation task,' where the error in the observable's expectation value is bounded independently of the system size. The paper focuses on Gaussian fermion models with Gaussian errors, which allow for strong stability results. For these models, intensive observables are shown to be stable for constant-time dynamics and equilibrium, regardless of whether the model is gapped or gapless. The analysis then extends to non-Gaussian many-body spin systems, relying on existing stability results and imposing more restrictive assumptions on the model. The stability of ground states and Gibbs states of gapped Hamiltonians is also studied, considering coherent Hamiltonian errors and the stability of the gap and exponential clustering of correlations. For the stability analysis of local observables and weighted averages, Lieb-Robinson bounds and the input-output formalism are employed. The concept of quantum advantage in the presence of noise is established by comparing the classical and quantum runtimes required to achieve hardware-limited precision. Numerical studies of the Su-Schrieffer-Heeger (SSH) model illustrate the impact of errors on the energy density. The adiabatic algorithm is used in numerical studies to analyze the runtime as a function of hardware-limited precision.

The paper establishes a system-size independent notion of stability against extensive errors for specific many-body models, showing that intensive observables remain stable even in the presence of constant error rates. This stability is shown to hold for Gaussian fermion models, even for gapless critical models with long-range correlations. For non-Gaussian spin systems, stability is proven under more restrictive assumptions. The authors demonstrate that this stability can lead to a quantum advantage in computing the thermodynamic limit of many-body models, even without error correction. They provide a novel definition of quantum advantage in the presence of noise, based on the computational time to achieve a hardware-limited precision in the thermodynamic limit. Explicit lower bounds on classical algorithms show potential superpolynomial to exponential quantum advantage for various scenarios, including constant-time dynamics, ground states (both gapped and gapless), and fixed points of rapidly mixing Lindbladians. Numerical studies on the SSH model confirm the theoretical predictions regarding the stability of intensive observables in both gapped and gapless phases. The numerical analysis of the adiabatic algorithm confirms that the runtime scales polynomially with the hardware-limited precision. The paper also proposes a notion of a stability region where noisy quantum advantage is expected.

The findings challenge the common belief that noise fundamentally limits the utility of quantum simulators for many-body problems. The introduction of the 'stable quantum simulation task' and the demonstration of stability for significant classes of models and observables provide a strong foundation for building practical quantum simulators. The results establish the potential for superpolynomial to exponential quantum advantage even in the presence of realistic noise levels, opening new avenues for tackling previously intractable problems in many-body physics. The limitations of existing classical algorithms with rigorous guarantees are highlighted, showcasing the potential impact of the developed methodology. While the provable quantum advantage is shown against only certain classical algorithms (Krylov subspace methods and exact diagonalization), the paper conjectures that a similar quantum advantage holds against more general classical algorithms. The reliance on specific assumptions (stable gap, exponential clustering of correlations, rapid mixing) for some results is noted, which opens avenues for future research to explore the scope of these assumptions and investigate their validity in more general contexts. The potential of the presented stability results to be extended to more complex models, beyond Gaussian fermions, is discussed.

This work demonstrates that noisy analogue quantum simulators can offer a significant quantum advantage for specific classes of many-body problems, even without error correction. The introduction of stable quantum simulation tasks and the demonstration of stability in various scenarios (dynamics, ground states, fixed points) provide a strong theoretical foundation for the development and application of near-term quantum simulators. Future work could focus on extending the results to more general models and addressing the open problem of establishing universal lower bounds on classical algorithms for these problems. Further investigations into the validity of the assumptions made in the analysis and exploring the potential for quantum advantage in more complex many-body systems are also warranted.

The analysis relies on specific assumptions, such as the stability of the gap for ground state calculations and the rapid mixing property for fixed points. The proven quantum advantage is currently limited to comparisons with classical algorithms that possess rigorous guarantees (Krylov subspace methods, exact diagonalization), leaving open the question of whether a similar advantage holds against all possible classical algorithms. The focus on intensive observables and the thermodynamic limit may not be applicable to all many-body problems. The Gaussian fermion models, while useful for establishing theoretical bounds, might not fully capture the complexities of all real-world systems.