Quantum advantage and stability to errors in analogue quantum simulators

Quantum information processing systems promise speedups over classical computation for various problems, but most algorithms with guarantees require fault-tolerant quantum computers, which remain technologically challenging. This motivates identifying near-term tasks solvable without explicit error correction. Analogue quantum simulators aim to implement spatially local, often translationally invariant Hamiltonians to prepare physically relevant states (ground, Gibbs, or dynamical states) and measure intensive observables (local or low-order correlators). Such simulators avoid circuit decompositions that amplify errors and target observables expected to be more robust locally, potentially enabling advantage on many-body physics tasks. However, rigorous criteria for quantum advantage are complicated by realistic noise and by the focus on intensive observables in the thermodynamic limit. Instead of scaling with system size, it is natural to consider the computational effort to achieve a specified precision in the thermodynamic limit of intensive quantities. This work addresses both issues by establishing stability to errors for key many-body tasks and proposing a notion of quantum advantage under noise, using run-time to reach hardware-limited precision as the metric.

Prior theory developed universal quantum simulators and demonstrated possible advantage in the noiseless setting, but realistic errors in analogue simulators have not been fully incorporated. Stability of certain classes has been studied, including free (Gaussian) fermion Hamiltonians and rapidly mixing Lindbladians, and quasi-locality via Lieb-Robinson bounds underlies many robustness results for local observables in dynamics and equilibrium. For ground states of gapped models, stability under local perturbations has been established in specific settings (e.g., frustration-free models with local topological order), and exponential clustering of correlations ensures locality properties in thermal states. Classical methods with rigorous guarantees for generic many-body dynamics or ground states are typically limited to exact diagonalization or Krylov subspace approaches, with exponential scaling in system size. Heuristic classical methods (e.g., tensor networks) can be efficient in practice but lack universal guarantees. These contexts motivate defining stability notions suited to intensive observables and analyzing quantum-versus-classical complexity in terms of precision to thermodynamic limits under noise.

The paper models both closed (Hamiltonian) and open (Lindbladian) many-body problems implemented on analogue simulators with spatial locality. Implemented dynamics include coherent errors (mis-specified local terms) and incoherent noise, allowing for both Markovian and non-Markovian (Gaussian environment with memory kernel) perturbations. A formal stability definition is given for quantum simulation tasks: an intensive observable is stable if the deviation between noisy and ideal thermodynamic limits is bounded by a function f(δ) that vanishes with hardware error rate δ, independent of system size. The analysis focuses on two regimes: (i) Gaussian fermionic models with local quadratic Hamiltonians and linear jump operators, including Gaussian coherent and incoherent errors and Gaussian environment couplings, and (ii) general spin systems where stability is derived under more restrictive spectral or mixing assumptions using Lieb-Robinson bounds and input-output formalism for non-Markovian environments. For Gaussian systems, the dynamics and equilibrium properties are captured by covariance matrices; effective equations of motion under noise are derived, enabling perturbative bounds on observable errors. For equilibrium, translationally invariant observables are considered and bounds relate observable errors to covariance matrix deviations. For spin systems, quasi-locality yields stability for k-local observables under constant-time dynamics and, in equilibrium, for stably gapped Hamiltonians (ground states) and Gibbs states with stable exponential clustering; for fixed points, rapidly mixing Lindbladians yield stability under coherent and incoherent noise. The work also frames quantum advantage in terms of run-time versus precision ε for thermodynamic limits, comparing ideal/noisy quantum simulators to classical exact or Krylov methods, and using adiabatic preparation under a gapped path for ground states when applicable. Numerical experiments on the SSH model examine error scaling with system size and hardware error to support analytical claims.

- Definition of a system-size independent stability notion for intensive observables under extensive hardware errors; stable tasks permit estimating thermodynamic limits to precision set by the hardware error δ. - Gaussian fermion models: Provable stability of translationally invariant intensive observables to coherent Hamiltonian errors and Gaussian incoherent errors, including for gapless critical models with long-range correlations. Deviations scale with small functions of δ (e.g., f(δ) = O(δ) or higher-order), independent of system size. - Numerical evidence (SSH model): For both gapped (e.g., J = 0.5, 1.5) and gapless (J = 1.0) cases, the error in energy density between perturbed and unperturbed models becomes independent of system size as N increases; error versus δ fits approximately quadratic scaling in δ in the numerics presented. - Spin systems (dynamics): For constant-time dynamics under spatially local Lindbladians, k-local observables and their normalized weighted sums are stable to coherent and non-Markovian incoherent errors, with worst-case bounds scaling with error rate consistent with Lieb-Robinson light-cone arguments. - Spin systems (equilibrium): For stably gapped Hamiltonians, local observables and normalized weighted averages are stable to coherent errors with f(δ) = O(δ). For Gibbs states with stable exponential clustering, stability holds with f(δ) = O(δ log(1/δ)). For rapidly mixing Lindbladians’ fixed points, k-local observables are stable to coherent and incoherent errors. - Quantum advantage (noiseless): When complexity is measured versus precision ε to the thermodynamic limit, ideal quantum simulators can achieve poly(1/ε) scaling for local observables in finite-time dynamics and, under gapped adiabatic paths, for ground states, while classical exact/Krylov methods scale super-polynomial to exponential in 1/ε on worst-case instances. - Quantum advantage (noisy): For stable tasks, noisy simulators still reach the thermodynamic limit up to a hardware-limited precision set by δ; achieving this precision requires poly in the target precision parameter, whereas classical exact/Krylov methods require super-polynomial or exponential time in the same precision, indicating potential super-polynomial or exponential advantage without error correction. - Formal propositions summarized: stability for Gaussian dynamics/equilibrium (including gapless), constant-time spin dynamics (k-local observables), ground states of stably gapped Hamiltonians, Gibbs states with exponential clustering, and fixed points of rapidly mixing Lindbladians.

The study addresses whether noisy analogue quantum simulators can provide reliable and advantageous computations of intensive observables in many-body systems. By defining stability with respect to hardware error and proving it for Gaussian fermionic models (including critical cases) and for spin systems under standard locality and spectral assumptions, the work shows that thermodynamic limits of relevant observables can be approximated to a precision set by hardware noise, independent of system size. This reframes quantum advantage in the presence of noise: even without error correction, stable tasks allow quantum simulators to reach hardware-limited precision in polynomial time, whereas classical methods with rigorous guarantees scale super-polynomially or exponentially in the required precision. The significance is twofold: it justifies the practical utility of analogue simulators for many-body physics in near-term regimes and provides a theoretical framework that connects stability under noise to computational advantage. The results also highlight the role of locality (via Lieb-Robinson bounds), spectral gaps or mixing properties, and Gaussian structure in ensuring robustness, and they suggest that certain critical systems can still yield stable observables despite long-range correlations. Open challenges remain in tightening classical lower bounds and extending stability to broader classes beyond Gaussian or stably gapped models.

The paper introduces a system-size independent stability framework for analogue quantum simulators under realistic noise and proves stability for intensive observables in key classes: Gaussian fermionic models (including gapless) and spin systems subject to locality and spectral/mixing assumptions. It demonstrates, analytically and numerically, that errors in intensive observables can be bounded independently of system size and that noisy simulators can achieve thermodynamic limits to hardware-limited precision. Framing complexity versus precision, the work argues for super-polynomial to exponential quantum advantage over classical exact/Krylov methods even without error correction for stable tasks in dynamics, ground states, and fixed points. Future directions include establishing universal lower bounds for classical algorithms beyond exact/Krylov methods, extending stability proofs to more general non-Gaussian interacting systems and broader error models, verifying assumptions (e.g., stability of gaps, clustering) in experiments, and optimizing protocols to approach hardware-limited precision efficiently.

- Results rely on specific assumptions: Gaussian structure for fermion models; locality; translational invariance for some bounds; mild continuity of mode densities; stability of spectral gaps for ground states; exponential clustering for Gibbs states; rapid mixing for Lindbladian fixed points. - Stability of the spectral gap under perturbations is known only for certain classes (e.g., frustration-free models with local topological order) and does not universally hold. - Classical comparisons are against exact diagonalization or Krylov methods with rigorous guarantees; heuristic classical algorithms (e.g., tensor networks) might perform better in practice but lack universal worst-case guarantees, so definitive advantage over all classical methods is not established. - Quantitative constants and precise error exponents (e.g., dependence on δ) can be model-dependent; some statements are supported by supplemental proofs or numerics rather than general tight bounds. - Non-Markovian noise is modeled via Gaussian environments; more complex or non-Gaussian environments are not analyzed. - Advantage claims for critical models are conjectural beyond Gaussian cases; universal lower bounds for classical algorithms remain open. - Adiabatic ground-state preparation assumes an adiabatic path with inverse polynomial minimal gap, which may not exist for all target Hamiltonians.