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:2610.06769

Fast convergence of propagation algorithms for open quantum systems

Giorgio Facelli, Hamza Fawzi, Omar Fawzi, Cambyse Rouzé, Sam Slezak, Daniel Stilck França

quant-phSubmitted Oct 5, 2026• Announced Oct 6, 2026• 2 citations
arXivHTMLPDF

Abstract

We establish general conditions for the rapid convergence of propagation algorithms for computing expectation values of local observables in quantum many-body systems, covering both spin and fermionic systems. Our results apply to evolutions that are sufficiently contractive, providing a general mechanism by which contractivity controls the growth generated by local interactions and enables efficient classical simulation. As a first application, we consider noisy time evolution generated by local Hamiltonians on arbitrary interaction graphs. We show that the dynamics can be efficiently simulated when the noise strength $λ$ is sufficiently large compared to the degree of the interaction graph. More generally, for systems with an interaction strength $u$, our bounds determine a time horizon $t_{\text{max}}$ as a function of the interaction strength $u$, the noise strength $λ$, and the interaction structure below which the algorithm is efficient. In the noiseless limit, $λ=0$, our analysis extends the efficiently simulable time scale from $\log(1/u)$ proved in Facelli, Fawzi, and Fawzi (2026) to $t_{\text{max}} \sim 1/u$ matching the recent improvement by Zhao, Marvian and Tong (2026). As a second application, we apply the same framework to the computation of local observables in Gibbs states of local Hamiltonians. We consider a pseudo-Lindbladian whose steady state is the Gibbs state and show that, at sufficiently high temperature, its propagation algorithm converges rapidly. In particular, for weakly-interacting systems with interaction strength $u$, our result applies up to inverse temperatures $β\sim\log(1/u)$.

AI Summary

The paper asks when degree-truncated Pauli/Majorana propagation can rigorously approximate local-observable dynamics and thermal expectations. It develops a contraction-based analysis: exponential weights on string degree control high-degree tails, and stability plus short-step error bounds control accumulated propagation error. For dynamics generated by $\mathcal L=i[H_0+uV,\cdot]-\lambda\mathcal N$, $H_0$ preserves degree, interactions increase it by at most $\delta$, and the Hamiltonian is $\Delta$-sparse. A time-dependent weighted Frobenius norm contracts whenever $a'(t)\leq\lambda-2\Delta u\sinh(\delta a(t))$. This yields an all-time guarantee for $\lambda\geq2\Delta u\sinh(1)$ and a finite simulation window below that threshold, scaling as $1/(\Delta u)$ without noise. For fixed-degree observables, cutoff $\ell=d+O(\log((1+t)/\varepsilon))$ gives normalized Frobenius error $\varepsilon\|A\|_F$ with runtime $N^{O(\log((1+t)/\varepsilon))}$. This norm controls ensemble-averaged expectation errors, not arbitrary-state worst-case errors. For fermionic Gibbs expectations, an auxiliary, generally non-completely-positive pseudo-Lindbladian fixes the Gibbs state in the dual picture. Weighted coefficient $\ell_1$ contraction proves relaxation to the thermal expectation times identity; a Dyson expansion controls interactions and supplies computable short steps. With geometrically local quadratic hopping and sparse quartic interactions, a sufficient condition is $u\Delta e^{C\beta}(e^{2\beta}-1)\leq c$, permitting $\beta=O(\log(1/u))$ at fixed degree. The deterministic runtime is $(N+1)^{O(d+\log(1/\varepsilon))}\operatorname{poly}(d,1/\varepsilon)$. The paper notes weaker runtime and temperature guarantees than existing randomized cumulant-expansion methods; improved selective truncation is left open.

Little sign of AI-generated textAI use disclosedStrong assumptions
OpenAI's ChatGPT Sol 5.6 and ChatGPT Astra 6 assisted with exploring and checking proof strategies and technical details.

Error found: The formal dynamics theorems omit a coefficient bound on V independent of u, making their weighted-contraction conclusion false under the written assumptions, although the introduction states the intended missing restriction. The introductory thermal theorem advertises a condition uniform in interaction degree Δ that is not established by the formal contraction theorem's exponentially stronger dependence on Δβ.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
31 pages

Related papers

Efficient Classical Simulation of Weakly Interacting Fermion Dynamics

Chu Zhao, Iman Marvian, Yu Tong

We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable $A$ at time $t$. By analyzing the convergence of the perturbative expansion in the interaction strength $λ$ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime $λ|t|^{2D+1}=\mathcal{O}(1)$, when the Hamiltonian is geometrically local on a $D$-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to $λ|t|=\mathcal{O}(1)$ with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to $λ|t|=\mathcal{O}(1)$, modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable.

quant-pharXiv:2608.19448•Aug 21, 2026•2 citations

Fast convergence of Majorana Propagation for weakly interacting fermions

Giorgio Facelli, Hamza Fawzi, Omar Fawzi

Simulating the time dynamics of an observable under Hamiltonian evolution is one of the most promising candidates for quantum advantage as we do not expect efficient classical algorithms for this problem except in restricted settings. Here, we introduce such a setting by showing that Majorana Propagation, a simple algorithm combining Trotter steps and truncations, efficiently finds a low-degree approximation of the time-evolved observable as soon as such an approximation exists. This provides the first provable guarantee about Majorana Propagation for Hamiltonian evolution. As an application of this result, we prove that Majorana Propagation can efficiently simulate the time dynamics of any sparse quartic Hamiltonian up to time $t_{\text{max}}(u)$ depending on the interaction strength $u$. For a time horizon $t \leq t_{\text{max}}(u)$, the runtime of the algorithm is $N^{O(\log(t/\varepsilon))}$ where $N$ is the number of Majorana modes and $\varepsilon$ is the error measured in the normalized Frobenius norm. Importantly, in the limit of small $u$, $t_{\text{max}}(u)$ goes to $+\infty$, formalizing the intuition that the algorithm is accurate at all times when the Hamiltonian is quadratic.

quant-pharXiv:2601.05226•Jan 9, 2026•10 citations

Polynomial-time thermalization and Gibbs sampling from system-bath couplings

Samuel Slezak, Matteo Scandi, Álvaro M. Alhambra +2 more

Many physical phenomena, including thermalization in open quantum systems and quantum Gibbs sampling, are modeled by Lindbladians approximating a system weakly coupled to a bath. Understanding the convergence speed of these Lindbladians to their steady states is crucial for bounding algorithmic runtimes and thermalization timescales. We study two such families of processes: one characterizing a repeated-interaction Gibbs sampling algorithm, and another modeling open many-body quantum thermalization. We prove that both converge in polynomial time for several non-commuting systems, including high-temperature local lattices, weakly interacting fermions, and 1D spin chains. These results demonstrate that simple dissipative quantum algorithms can prepare complex Gibbs states and that Lindblad dynamics accurately capture thermal relaxation. Our proofs rely on a novel technical result that extrapolates spectral gap lower bounds from quasi-local Lindbladians to the non-local generators governing these dynamics.

quant-pharXiv:2601.16154•Jan 23, 2026•10 citations

Rapid mixing for Gibbs samplers for quantum spin systems with all-to-all interactions

Nicola Bertoni, Giacomo De Palma

Understanding when quantum many-body systems rapidly converge to thermal equilibrium is a central problem in quantum statistical mechanics. While spatial locality provides powerful tools for systems with an underlying geometry, fully connected models require estimates that accommodate interactions between every pair of spins. We study Gibbs-state preparation for two-local quantum Hamiltonians on arbitrary interaction graphs, including fully connected systems, via Lindblad dynamics that satisfies Kubo--Martin--Schwinger (KMS) detailed balance. Our approach is based on a quantum analogue of the classical Dobrushin condition, which controls the influence of local perturbations on the rest of the system. Using the quantum Wasserstein distance of order $1$, we quantify how these perturbations propagate under the dynamics and derive contraction estimates in a high-temperature regime controlled by the maximum total interaction strength per site. These estimates require no assumptions on spatial geometry or graph growth and yield mixing times logarithmic in the system size and the inverse error tolerance, uniformly over all initial states.

quant-pharXiv:2610.40361•Oct 30, 2026•1 citation

Optimal Quantum Algorithm for Gibbs State Preparation

Cambyse Rouzé, Daniel Stilck França, Alvaro Martin Alhambra

It is of great interest to understand the thermalization of open quantum many-body systems, and how quantum computers are able to efficiently simulate that process. A recently introduced dissipative evolution, inspired by existing models of open system thermalization, has been shown to be efficiently implementable on a quantum computer. Here, we prove that, at high enough temperatures, this evolution reaches the Gibbs state in time scaling logarithmically with system size. The result holds for Hamiltonians that satisfy the Lieb-Robinson bound, such as local Hamiltonians on a lattice, and includes long-range systems. To the best of our knowledge, these are the first results rigorously establishing the rapid mixing property of high-temperature quantum Gibbs samplers, which is known to give the fastest possible speed for thermalization in the many-body setting. We then apply our result to the problem of estimating partition functions at high temperature, showing an improved performance over previous classical and quantum algorithms.

arXiv:2411.04885•Physical Review Letters•Jan 14, 2026•94 citations

Rapid Mixing of Quantum Gibbs Samplers for Weakly-Interacting Quantum Systems

Štěpán Šmíd, Meister, Richard, Mario Berta +1 more

Dissipative quantum algorithms for state preparation in many-body systems are increasingly recognised as promising candidates for achieving large quantum advantages in application-relevant tasks. Recent advances in algorithmic, detailed-balance Lindbladians enable the efficient simulation of open-system dynamics converging towards desired target states. However, the overall complexity of such schemes is governed by system-size dependent mixing times. In this work, we analyse algorithmic Lindbladians for Gibbs state preparation and prove that they exhibit rapid mixing, i.e., convergence in time poly-logarithmic in the system size. We first establish this for non-interacting spin systems, free fermions, and free bosons, and then show that these rapid mixing results are stable under perturbations, covering weakly interacting qudits and perturbed non-hopping fermions. Further, we adapt the techniques from separable qudits to the fermionic setting and prove rapid mixing of the strongly-interacting regime of the Fermi-Hubbard model, for which we also explicitly evaluate the guaranteed parameter regimes. Our results constitute the first efficient mixing bounds for non-commuting qudit models and bosonic systems at arbitrary temperatures. Compared to prior spectral-gap-based results for fermions, we achieve exponentially faster mixing, further featuring explicit constants on the maximal allowed interaction strength. This not only improves the overall polynomial runtime for quantum Gibbs state preparation, but also enhances robustness against noise. Our analysis relies on oscillator norm techniques from mathematical physics, where we introduce tailored variants adapted to specific Lindbladians $\unicode{x2014}$ an innovation that we expect to significantly broaden the scope of these methods.

arXiv:2510.04954•Oct 6, 2025•29 citations
We establish general conditions for the rapid convergence of propagation algorithms for computing expectation values of local observables in quantum many-body systems, covering both spin and fermionic systems. Our results apply to evolutions that are sufficiently contractive, providing a general mechanism by which contractivity controls the growth generated by local interactions and enables efficient classical simulation. As a first application, we consider noisy time evolution generated by local Hamiltonians on arbitrary interaction graphs. We show that the dynamics can be efficiently simulated when the noise strength λλλ is sufficiently large compared to the degree of the interaction graph. More generally, for systems with an interaction strength uuu, our bounds determine a time horizon tmaxt_{\text{max}}tmax​ as a function of the interaction strength uuu, the noise strength λλλ, and the interaction structure below which the algorithm is efficient. In the noiseless limit, λ=0λ=0λ=0, our analysis extends the efficiently simulable time scale from log⁡(1/u)\log(1/u)log(1/u) proved in Facelli, Fawzi, and Fawzi (2026) to tmax∼1/ut_{\text{max}} \sim 1/utmax​∼1/u matching the recent improvement by Zhao, Marvian and Tong (2026). As a second application, we apply the same framework to the computation of local observables in Gibbs states of local Hamiltonians. We consider a pseudo-Lindbladian whose steady state is the Gibbs state and show that, at sufficiently high temperature, its propagation algorithm converges rapidly. In particular, for weakly-interacting systems with interaction strength uuu, our result applies up to inverse temperatures β∼log⁡(1/u)β\sim\log(1/u)β∼log(1/u).
The paper asks when degree-truncated Pauli/Majorana propagation can rigorously approximate local-observable dynamics and thermal expectations. It develops a contraction-based analysis: exponential weights on string degree control high-degree tails, and stability plus short-step error bounds control accumulated propagation error.
For dynamics generated by L=i[H0+uV,⋅]−λN\mathcal L=i[H_0+uV,\cdot]-\lambda\mathcal NL=i[H0​+uV,⋅]−λN, H0H_0H0​ preserves degree, interactions increase it by at most δ\deltaδ, and the Hamiltonian is Δ\DeltaΔ-sparse. A time-dependent weighted Frobenius norm contracts whenever a′(t)≤λ−2Δusinh⁡(δa(t))a'(t)\leq\lambda-2\Delta u\sinh(\delta a(t))a′(t)≤λ−2Δusinh(δa(t)). This yields an all-time guarantee for λ≥2Δusinh⁡(1)\lambda\geq2\Delta u\sinh(1)λ≥2Δusinh(1) and a finite simulation window below that threshold, scaling as 1/(Δu)1/(\Delta u)1/(Δu) without noise. For fixed-degree observables, cutoff ℓ=d+O(log⁡((1+t)/ε))\ell=d+O(\log((1+t)/\varepsilon))ℓ=d+O(log((1+t)/ε)) gives normalized Frobenius error ε∥A∥F\varepsilon\|A\|_Fε∥A∥F​ with runtime NO(log⁡((1+t)/ε))N^{O(\log((1+t)/\varepsilon))}NO(log((1+t)/ε)). This norm controls ensemble-averaged expectation errors, not arbitrary-state worst-case errors.
For fermionic Gibbs expectations, an auxiliary, generally non-completely-positive pseudo-Lindbladian fixes the Gibbs state in the dual picture. Weighted coefficient ℓ1\ell_1ℓ1​ contraction proves relaxation to the thermal expectation times identity; a Dyson expansion controls interactions and supplies computable short steps. With geometrically local quadratic hopping and sparse quartic interactions, a sufficient condition is uΔeCβ(e2β−1)≤cu\Delta e^{C\beta}(e^{2\beta}-1)\leq cuΔeCβ(e2β−1)≤c, permitting β=O(log⁡(1/u))\beta=O(\log(1/u))β=O(log(1/u)) at fixed degree. The deterministic runtime is (N+1)O(d+log⁡(1/ε))poly⁡(d,1/ε)(N+1)^{O(d+\log(1/\varepsilon))}\operatorname{poly}(d,1/\varepsilon)(N+1)O(d+log(1/ε))poly(d,1/ε). The paper notes weaker runtime and temperature guarantees than existing randomized cumulant-expansion methods; improved selective truncation is left open.
We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable AAA at time ttt. By analyzing the convergence of the perturbative expansion in the interaction strength λλλ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime λ∣t∣2D+1=O(1)λ|t|^{2D+1}=\mathcal{O}(1)λ∣t∣2D+1=O(1), when the Hamiltonian is geometrically local on a DDD-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to λ∣t∣=O(1)λ|t|=\mathcal{O}(1)λ∣t∣=O(1) with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to λ∣t∣=O(1)λ|t|=\mathcal{O}(1)λ∣t∣=O(1), modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable.
Simulating the time dynamics of an observable under Hamiltonian evolution is one of the most promising candidates for quantum advantage as we do not expect efficient classical algorithms for this problem except in restricted settings. Here, we introduce such a setting by showing that Majorana Propagation, a simple algorithm combining Trotter steps and truncations, efficiently finds a low-degree approximation of the time-evolved observable as soon as such an approximation exists. This provides the first provable guarantee about Majorana Propagation for Hamiltonian evolution. As an application of this result, we prove that Majorana Propagation can efficiently simulate the time dynamics of any sparse quartic Hamiltonian up to time tmax(u)t_{\text{max}}(u)tmax​(u) depending on the interaction strength uuu. For a time horizon t≤tmax(u)t \leq t_{\text{max}}(u)t≤tmax​(u), the runtime of the algorithm is NO(log⁡(t/ε))N^{O(\log(t/\varepsilon))}NO(log(t/ε)) where NNN is the number of Majorana modes and ε\varepsilonε is the error measured in the normalized Frobenius norm. Importantly, in the limit of small uuu, tmax(u)t_{\text{max}}(u)tmax​(u) goes to +∞+\infty+∞, formalizing the intuition that the algorithm is accurate at all times when the Hamiltonian is quadratic.
Many physical phenomena, including thermalization in open quantum systems and quantum Gibbs sampling, are modeled by Lindbladians approximating a system weakly coupled to a bath. Understanding the convergence speed of these Lindbladians to their steady states is crucial for bounding algorithmic runtimes and thermalization timescales. We study two such families of processes: one characterizing a repeated-interaction Gibbs sampling algorithm, and another modeling open many-body quantum thermalization. We prove that both converge in polynomial time for several non-commuting systems, including high-temperature local lattices, weakly interacting fermions, and 1D spin chains. These results demonstrate that simple dissipative quantum algorithms can prepare complex Gibbs states and that Lindblad dynamics accurately capture thermal relaxation. Our proofs rely on a novel technical result that extrapolates spectral gap lower bounds from quasi-local Lindbladians to the non-local generators governing these dynamics.
Understanding when quantum many-body systems rapidly converge to thermal equilibrium is a central problem in quantum statistical mechanics. While spatial locality provides powerful tools for systems with an underlying geometry, fully connected models require estimates that accommodate interactions between every pair of spins. We study Gibbs-state preparation for two-local quantum Hamiltonians on arbitrary interaction graphs, including fully connected systems, via Lindblad dynamics that satisfies Kubo--Martin--Schwinger (KMS) detailed balance. Our approach is based on a quantum analogue of the classical Dobrushin condition, which controls the influence of local perturbations on the rest of the system. Using the quantum Wasserstein distance of order 111, we quantify how these perturbations propagate under the dynamics and derive contraction estimates in a high-temperature regime controlled by the maximum total interaction strength per site. These estimates require no assumptions on spatial geometry or graph growth and yield mixing times logarithmic in the system size and the inverse error tolerance, uniformly over all initial states.
It is of great interest to understand the thermalization of open quantum many-body systems, and how quantum computers are able to efficiently simulate that process. A recently introduced dissipative evolution, inspired by existing models of open system thermalization, has been shown to be efficiently implementable on a quantum computer. Here, we prove that, at high enough temperatures, this evolution reaches the Gibbs state in time scaling logarithmically with system size. The result holds for Hamiltonians that satisfy the Lieb-Robinson bound, such as local Hamiltonians on a lattice, and includes long-range systems. To the best of our knowledge, these are the first results rigorously establishing the rapid mixing property of high-temperature quantum Gibbs samplers, which is known to give the fastest possible speed for thermalization in the many-body setting. We then apply our result to the problem of estimating partition functions at high temperature, showing an improved performance over previous classical and quantum algorithms.
Dissipative quantum algorithms for state preparation in many-body systems are increasingly recognised as promising candidates for achieving large quantum advantages in application-relevant tasks. Recent advances in algorithmic, detailed-balance Lindbladians enable the efficient simulation of open-system dynamics converging towards desired target states. However, the overall complexity of such schemes is governed by system-size dependent mixing times. In this work, we analyse algorithmic Lindbladians for Gibbs state preparation and prove that they exhibit rapid mixing, i.e., convergence in time poly-logarithmic in the system size. We first establish this for non-interacting spin systems, free fermions, and free bosons, and then show that these rapid mixing results are stable under perturbations, covering weakly interacting qudits and perturbed non-hopping fermions. Further, we adapt the techniques from separable qudits to the fermionic setting and prove rapid mixing of the strongly-interacting regime of the Fermi-Hubbard model, for which we also explicitly evaluate the guaranteed parameter regimes. Our results constitute the first efficient mixing bounds for non-commuting qudit models and bosonic systems at arbitrary temperatures. Compared to prior spectral-gap-based results for fermions, we achieve exponentially faster mixing, further featuring explicit constants on the maximal allowed interaction strength. This not only improves the overall polynomial runtime for quantum Gibbs state preparation, but also enhances robustness against noise. Our analysis relies on oscillator norm techniques from mathematical physics, where we introduce tailored variants adapted to specific Lindbladians $\unicode{x2014}$ an innovation that we expect to significantly broaden the scope of these methods.