Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2404.11081 · Physical Review X

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

Vikram Kashyap, Georgios Styliaris, Sara Mouradian, J. I. Cirac, Rahul Trivedi

Published Apr 16, 2025• 13 citations
arXivHTMLPDF

Abstract

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 ϵ in time that is poly ( ϵ − 1 ) 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 BQP ≠ BPP . 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 BQP ≠ BPP , 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.

DOI
10.1103/physrevx.15.021017

Related papers

Stochastic Error Cancellation in Analog Quantum Simulation

Yiyi Cai, Yu Tong, John P. Preskill

Analog quantum simulation is a promising path towards solving classically intractable problems in many-body physics on near-term quantum devices. However, the presence of noise limits the size of the system and the length of time that can be simulated. In our work, we consider an error model in which the actual Hamiltonian of the simulator differs from the target Hamiltonian we want to simulate by small local perturbations, which are assumed to be random and unbiased. We analyze the error accumulated in observables in this setting and show that, due to stochastic error cancellation, with high probability the error scales as the square root of the number of qubits instead of linearly. We explore the concentration phenomenon of this error as well as its implications for local observables in the thermodynamic limit. Moreover, we show that stochastic error cancellation also manifests in the fidelity between the target state at the end of time-evolution and the actual state we obtain in the presence of noise. This indicates that, to reach a certain fidelity, more noise can be tolerated than implied by the worst-case bound if the noise comes from many statistically independent sources.

arXiv:2311.14818•Leibniz international proceedings in informatics•Nov 24, 2023•1 citation

Noise robustness of problem-to-simulator mappings for quantum many-body physics

Rahul Trivedi, J. I. Cirac

Simulating quantum dynamics on digital or analog quantum simulators often requires ``problem-to-simulator" mappings such as trotterization, floquet-magnus expansion or perturbative expansions. When the simulator is noiseless, it is well understood that these problem-to-simulator mappings can be made as accurate as desired at the expense of simulator run-time. However, precisely because the simulator has to be run for a longer time to increase its accuracy, it is expected that noise in the quantum simulator catastrophically effects the simulator output. We show that, contrary to this expectation, these mappings remain stable to noise when considering the task of simulating dynamics of local observables in quantum lattice models. Specifically, we prove that in all of these mappings, local observables can be determined to a system-size independent, precision that scales sublinearly with the noise-rate in the simulator. Our results provide theoretical evidence that quantum simulators can be used for solving problems in many-body physics without or with modest error correction.

arXiv:2509.17579•Sep 22, 2025•0 citations

Noisy Quantum Learning Theory

Jordan Cotler, Weiyuan Gong, Ishaan Kannan

We develop a framework for learning from noisy quantum experiments in which fault-tolerant devices access uncharacterized systems through noisy couplings. Introducing the complexity class $\textsf{NBQP}$ ("noisy BQP''), we model noisy fault-tolerant quantum computers that cannot generally error-correct the oracle systems they query. Using this class, we prove that while noise can eliminate the exponential quantum learning advantages of unphysical, noiseless learners, a superpolynomial gap remains between $\textsf{NISQ}$ and fault-tolerant devices. Turning to canonical learning tasks in noisy settings, we find that the exponential two-copy advantage for purity testing collapses under local depolarizing noise. Nevertheless, we identify a setting motivated by AdS/CFT in which noise-resilient physical structure restores this quantum learning advantage. We then analyze noisy Pauli shadow tomography, deriving lower bounds characterizing how instance size, quantum memory and noise jointly control sample complexity, and design algorithms with parametrically matching scalings. We study similar tradeoffs in quantum metrology, and show that the Heisenberg-limited sensitivity of existing error-correction-based protocols persists only up to a timescale inverse-polynomial in the error rate per probe qubit. Together, our results demonstrate that the primitives underlying quantum-enhanced experiments are fundamentally fragile to noise, and that realizing meaningful quantum advantages in future experiments will require interfacing noise-robust physical properties with available algorithmic techniques.

quant-pharXiv:2512.10929•Nature Communications•Dec 12, 2025•0 citations

Efficiently learning non-Markovian noise in many-body quantum simulators

Jordi A. Montañà-López, Andreas Elben, Joonhee Choi +1 more

As quantum simulators are scaled up to larger system sizes and lower noise rates, non-Markovian noise channels are expected to become dominant. While provably efficient protocols for Markovian models of quantum simulators, either closed system models (described by a Hamiltonian) or open system models (described by a Lindbladian), have been developed, it remains less well understood whether similar protocols for non-Markovian models exist. In this paper, we consider geometrically local lattice models with both quantum and classical non-Markovian noise and show that, under a Gaussian assumption on the noise, we can learn the noise with sample complexity scaling logarithmically with the system size. Our protocol requires preparing the simulator qubits initially in a product state, introducing a layer of single-qubit Clifford gates and measuring product observables.

quant-pharXiv:2511.16772•Nov 24, 2025•0 citations

Optimizing digital quantum simulation of open quantum lattice models

Xie-Hang Yu, Hongchao Li, J. I. Cirac +1 more

Many-body systems arising in condensed matter physics and quantum optics inevitably couple to the environment and need to be modelled as open quantum systems. While near-optimal algorithms have been developed for simulating many-body quantum dynamics, algorithms for their open system counterparts remain less well investigated. We address the problem of simulating geometrically local many-body open quantum systems interacting with a stationary Gaussian environment. Under a smoothness assumption on the system-environment interaction, we develop near-optimal algorithms that, for a model with $N$ spins and evolution time $t$, attain a simulation error $δ$ in the system-state with $\mathcal{O}(Nt(Nt/δ)^{o(1)})$ gates, $\mathcal{O}(t(Nt/δ)^{o(1)})$ parallelized circuit depth and $\tilde{\mathcal{O}}(N(Nt/δ)^{o(1)})$ ancillas. We additionally show that, if only simulating local observables is of interest, then the circuit depth of the digital algorithm can be chosen to be independent of the system size $N$. This provides theoretical evidence for the utility of these algorithms for simulating physically relevant models, where typically local observables are of interest, on pre-fault tolerant devices. Finally, for the limiting case of Markovian dynamics with commuting jump operators, we propose two algorithms based on sampling a Wiener process and on a locally dilated Hamiltonian construction, respectively. These algorithms reduce the asymptotic gate complexity on $N$ compared to currently available algorithms in terms of the required number of geometrically local gates.

arXiv:2509.02268•Sep 2, 2025•0 citations

Quantum advantage and stability to errors in analogue quantum simulators

Rahul Trivedi, Adrián Franco-Rubio, J. I. Cirac

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, it is not clear to what extent those devices can provide us with an advantage with respect to classical computers. In this work, we make progress on this problem for noisy analogue quantum simulators computing physically relevant properties of many-body systems both in equilibrium and undergoing dynamics. We first formulate a system-size independent notion of stability against extensive errors, which we prove for Gaussian fermion models, as well as for a restricted class of spin systems. Remarkably, for the Gaussian fermion models, our analysis shows the stability of critical models which have long-range correlations. Furthermore, we analyze how this stability may lead to a quantum advantage, for the problem of computing the thermodynamic limit of many-body models, in the presence of a constant error rate and without any explicit error correction.

arXiv:2212.04924•Nature Communications•Aug 2, 2024•42 citations
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 ϵ in time that is poly ( ϵ − 1 ) 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 BQP ≠ BPP . 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 BQP ≠ BPP , 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.
Analog quantum simulation is a promising path towards solving classically intractable problems in many-body physics on near-term quantum devices. However, the presence of noise limits the size of the system and the length of time that can be simulated. In our work, we consider an error model in which the actual Hamiltonian of the simulator differs from the target Hamiltonian we want to simulate by small local perturbations, which are assumed to be random and unbiased. We analyze the error accumulated in observables in this setting and show that, due to stochastic error cancellation, with high probability the error scales as the square root of the number of qubits instead of linearly. We explore the concentration phenomenon of this error as well as its implications for local observables in the thermodynamic limit. Moreover, we show that stochastic error cancellation also manifests in the fidelity between the target state at the end of time-evolution and the actual state we obtain in the presence of noise. This indicates that, to reach a certain fidelity, more noise can be tolerated than implied by the worst-case bound if the noise comes from many statistically independent sources.
Simulating quantum dynamics on digital or analog quantum simulators often requires ``problem-to-simulator" mappings such as trotterization, floquet-magnus expansion or perturbative expansions. When the simulator is noiseless, it is well understood that these problem-to-simulator mappings can be made as accurate as desired at the expense of simulator run-time. However, precisely because the simulator has to be run for a longer time to increase its accuracy, it is expected that noise in the quantum simulator catastrophically effects the simulator output. We show that, contrary to this expectation, these mappings remain stable to noise when considering the task of simulating dynamics of local observables in quantum lattice models. Specifically, we prove that in all of these mappings, local observables can be determined to a system-size independent, precision that scales sublinearly with the noise-rate in the simulator. Our results provide theoretical evidence that quantum simulators can be used for solving problems in many-body physics without or with modest error correction.
We develop a framework for learning from noisy quantum experiments in which fault-tolerant devices access uncharacterized systems through noisy couplings. Introducing the complexity class NBQP\textsf{NBQP}NBQP ("noisy BQP''), we model noisy fault-tolerant quantum computers that cannot generally error-correct the oracle systems they query. Using this class, we prove that while noise can eliminate the exponential quantum learning advantages of unphysical, noiseless learners, a superpolynomial gap remains between NISQ\textsf{NISQ}NISQ and fault-tolerant devices. Turning to canonical learning tasks in noisy settings, we find that the exponential two-copy advantage for purity testing collapses under local depolarizing noise. Nevertheless, we identify a setting motivated by AdS/CFT in which noise-resilient physical structure restores this quantum learning advantage. We then analyze noisy Pauli shadow tomography, deriving lower bounds characterizing how instance size, quantum memory and noise jointly control sample complexity, and design algorithms with parametrically matching scalings. We study similar tradeoffs in quantum metrology, and show that the Heisenberg-limited sensitivity of existing error-correction-based protocols persists only up to a timescale inverse-polynomial in the error rate per probe qubit. Together, our results demonstrate that the primitives underlying quantum-enhanced experiments are fundamentally fragile to noise, and that realizing meaningful quantum advantages in future experiments will require interfacing noise-robust physical properties with available algorithmic techniques.
As quantum simulators are scaled up to larger system sizes and lower noise rates, non-Markovian noise channels are expected to become dominant. While provably efficient protocols for Markovian models of quantum simulators, either closed system models (described by a Hamiltonian) or open system models (described by a Lindbladian), have been developed, it remains less well understood whether similar protocols for non-Markovian models exist. In this paper, we consider geometrically local lattice models with both quantum and classical non-Markovian noise and show that, under a Gaussian assumption on the noise, we can learn the noise with sample complexity scaling logarithmically with the system size. Our protocol requires preparing the simulator qubits initially in a product state, introducing a layer of single-qubit Clifford gates and measuring product observables.
Many-body systems arising in condensed matter physics and quantum optics inevitably couple to the environment and need to be modelled as open quantum systems. While near-optimal algorithms have been developed for simulating many-body quantum dynamics, algorithms for their open system counterparts remain less well investigated. We address the problem of simulating geometrically local many-body open quantum systems interacting with a stationary Gaussian environment. Under a smoothness assumption on the system-environment interaction, we develop near-optimal algorithms that, for a model with NNN spins and evolution time ttt, attain a simulation error δδδ in the system-state with O(Nt(Nt/δ)o(1))\mathcal{O}(Nt(Nt/δ)^{o(1)})O(Nt(Nt/δ)o(1)) gates, O(t(Nt/δ)o(1))\mathcal{O}(t(Nt/δ)^{o(1)})O(t(Nt/δ)o(1)) parallelized circuit depth and O~(N(Nt/δ)o(1))\tilde{\mathcal{O}}(N(Nt/δ)^{o(1)})O~(N(Nt/δ)o(1)) ancillas. We additionally show that, if only simulating local observables is of interest, then the circuit depth of the digital algorithm can be chosen to be independent of the system size NNN. This provides theoretical evidence for the utility of these algorithms for simulating physically relevant models, where typically local observables are of interest, on pre-fault tolerant devices. Finally, for the limiting case of Markovian dynamics with commuting jump operators, we propose two algorithms based on sampling a Wiener process and on a locally dilated Hamiltonian construction, respectively. These algorithms reduce the asymptotic gate complexity on NNN compared to currently available algorithms in terms of the required number of geometrically local gates.
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, it is not clear to what extent those devices can provide us with an advantage with respect to classical computers. In this work, we make progress on this problem for noisy analogue quantum simulators computing physically relevant properties of many-body systems both in equilibrium and undergoing dynamics. We first formulate a system-size independent notion of stability against extensive errors, which we prove for Gaussian fermion models, as well as for a restricted class of spin systems. Remarkably, for the Gaussian fermion models, our analysis shows the stability of critical models which have long-range correlations. Furthermore, we analyze how this stability may lead to a quantum advantage, for the problem of computing the thermodynamic limit of many-body models, in the presence of a constant error rate and without any explicit error correction.