# Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers

Cambyse Rouzé, Daniel Stilck França, Álvaro Alhambra

► To cite this version:

Cambyse Rouzé, Daniel Stilck França, Álvaro Alhambra. Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers. STOC 2025 - 57th Annual ACM Symposium on Theory of Computing, Jun 2025, Prague Czechia, Czech Republic. pp.1488-1495, 10.1145/3717823.3718268. hal-05335877

HAL Id: hal-05335877

https://hal.science/hal-05335877v1

Submitted on 29 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers

### Cambyse Rouzé

Inria, Télécom Paris - LTCI, Institut Polytechnique de Paris Palaiseau, France
rouzecambyse@gmail.com

### Daniel Stilck França

Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP
Lyon Cedex 07, France
Department of Mathematical Sciences, University of Copenhagen Copenhagen, Denmark
dsfranca@math.ku.dk

### Álvaro M. Alhambra

Instituto de Física Téorica UAM/CSIC Madrid, Spain
alvaro.alhambra@csic.es

## Abstract

The preparation of quantum Gibbs states is a crucial task in quantum computing. In this work, we prove that a recently introduced, efficiently implementable dissipative evolution thermalizes to the Gibbs state in time scaling polynomially or even logarithmically with system size at high enough temperatures for any Hamiltonian that satisfies a Lieb-Robinson bound, such as local Hamiltonians on a lattice. Furthermore, we show the efficient adiabatic preparation of the associated purifications or “thermofield double” states. To the best of our knowledge, these are the first results rigorously establishing the efficient preparation of high-temperature Gibbs states and their purifications.

In the low-temperature regime, we show that implementing this family of dissipative evolutions for inverse temperatures polynomial in the system's size is computationally equivalent to standard quantum computations. On a technical level, for high temperatures, our proof makes use of the mapping of the generator of the evolution into a Hamiltonian, and then connecting its convergence to that of the infinite temperature limit. We further present an alternative proof that is based on showing the exponential decay of the so-called oscillator norm, yielding convergence in logarithmic times. For low temperature, we instead perform a perturbation at zero temperature and resort to circuit-to-Hamiltonian mappings akin to the proof of universality of quantum adiabatic computing.

Taken together, our results show that a family of quasi-local dissipative evolutions efficiently prepares a large class of quantum many-body states of interest, and has the potential to mirror the success of classical Monte Carlo methods for quantum many-body systems.

## CCS Concepts

* Theory of computation → Quantum computation theory;
* Quantum complexity theory; • Mathematics of computing; • Applied computing → Physics;

<figure><img src="image_2.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License.
STOC '25, *Prague, Czechia*

© 2025 Copyright held by the owner/author(s).
ACM ISBN 979-8-4007-1510-5/25/06
https://doi.org/10.1145/3717823.3718268

## Keywords

Quantum Gibbs states, Quantum computing, Dissipative evolution, Quantum complexity, Monte Carlo methods, Mixing Times.

## ACM Reference Format:

Cambyse Rouzé, Daniel Stilck França, and Álvaro M. Alhambra. 2025. Efficient Thermalization and Universal Quantum Computing with Quantum Gibbs Samplers. In *Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC '25), June 23–27, 2025, Prague, Czechia*. ACM, New York, NY, USA, 8 pages. https://doi.org/10.1145/3717823.3718268

## 1 Introduction

Markov Chain Monte Carlo (MCMC) methods are one of the go-to tools for sampling from classical Gibbs states (GS) of spin systems [37]. They exhibit efficiency in practice [14] and are also provably efficient in some cases, such as at high temperatures [4, 10, 21, 26, 41]. These methods traditionally rely on “local updates”, where a few spins are flipped based on local energy changes, a feature crucial for both practical implementation and theoretical analysis. However, extending such algorithms to quantum systems has been a formidable challenge. Despite significant research efforts [7–9, 12, 33, 51, 56, 62, 64], general quantum algorithms capable of (quasi-)local updates that also provably converge to a quantum GS have remained elusive, until the recent breakthroughs of [19, 20].

The present work delves into the quantum algorithm proposed in [19, 20] showing its ability to efficiently prepare quantum states of interest. We investigate both the high-temperature and the low-temperature regimes. In the high-temperature regime, we give two proofs that above a certain constant threshold temperature, the Lindbladians constructed in [20] efficiently converge to the GS for all Hamiltonians obeying a Lieb-Robinson bound, which includes local Hamiltonians on a lattice [44] and even some long-range models. To the best of our knowledge, this is the first unconditional result that shows efficient preparation of high-temperature quantum Gibbs states on a quantum computer for any lattice dimension [7, 12, 33, 64]<fnref n="1" />. Interestingly, our results also imply the efficient adiabatic preparation (starting with the state at inverse temperature $\beta = 0$) of the associated purifications. The preparation of such purified states is of independent interest [15, 25, 54],

<footnote n="1">¹After the completion of this work, we became aware of the results of [6], where the authors show that high-temperature Gibbs states can be prepared efficiently both on a quantum and classical computer. However, their results have qualitative and quantitative differences to ours, which we discuss in detail in Section 3</footnote>
and this scheme is the first provably efficient for a general class of models.

For low temperatures, we show that implementing the Lindbladians of [20] for $\beta = \Omega(\text{poly}(n))$ gives rise to a universal model for quantum computing equivalent to the circuit model. To this end, we show that the Lindbladians corresponding to circuit-to-Hamiltonian mappings efficiently converge to a state with a polynomial overlap with the ground state corresponding to the output of the circuit. This state can then be leveraged to efficiently obtain the ground state through a series of local measurements<fnref n="2" />. These results are in analogy with those of [18], where the authors established results at polynomially larger temperatures and polynomial rounds of mid-circuit measurements, compared to one round at the end for our construction. Our construction also has a better dependency on the temperature, and does not require mid-circuit measurements.

On a technical level, for high temperature, our analysis establishes efficient preparation through two routes. First, we show a spectral gap for the Lindbladians defined in [20]. This is done by viewing the high-temperature generator as a perturbation of its infinite temperature counterpart, and employing results on quasi-local perturbations of gapped Hamiltonians [43]. This yields that simulating the Lindbladians for times linear in system size is sufficient to prepare the Gibbs state. We then also show rapid mixing, i.e. convergence in time logarithmic in system size, employing so-called gradient techniques [2, 52]. Although these yield better mixing times and also work for long-range systems, we believe that our perturbative approach is of independent interest. Whereas the gradient method is highly tailored to the high temperature case, we expect that the perturbative approach will yield efficient preparation beyond this regime by considering perturbations of gapped Hamiltonians whose fixed point satisfies local topological order. At low temperature, we also follow a perturbative approach, but now at $\beta = +\infty$. We are inspired by the classical results of [16] and the recent quantum results of [18] to show that the Lindbladians of [20] have the power to simulate polynomial-size quantum circuits already at $\beta = \Omega(\text{poly}(n))$. Taken together, our findings show that the algorithm of [20] is a powerful tool to prepare non-trivial quantum many-body states, and to replicate the success of classical MCMC in the quantum realm.

# 2 Summary of Main Results

## 2.1 Quantum Gibbs Sampling

We start by recalling the generator of the quantum Gibbs sampler recently introduced in [20]. For $\beta > 0$ and a local Hamiltonian $H$ over the lattice $\Lambda \equiv [0, L]^D$ with $n := |\Lambda|$, we denote $\gamma(\omega) := \exp(-(\beta\omega + 1)^2/2)$ and we consider the Lindbladian

$$ \mathcal{L}^{(\beta)}(\rho) = -i[B, \rho] + \sum_{a \in \Lambda, \alpha \in [3]} \int_{-\infty}^{\infty} \gamma(\omega) \mathcal{D}_{\omega}^{a, \alpha}(\rho) d\omega \quad (2.1) $$

where $\mathcal{D}_{\omega}^{a, \alpha}$ stands for the dissipative term corresponding to the jump operators

$$ A^{a,\alpha}(\omega) := \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{iHt} A^{a,\alpha} e^{-iHt} e^{-i\omega t} f(t) dt $$

with $f(t) := \exp(-t^2/\beta^2) \sqrt{\beta^{-1}\sqrt{2/\pi}}$. Above, $A^{a,1} \equiv \sigma_x$, $A^{a,2} \equiv \sigma_y$ and $A^{a,3} \equiv \sigma_z$ denote the 1-local Pauli matrices on site a. The coherent part is defined through the self-adjoint matrix

$$ B = \beta^{-2} \sum_{a \in \Lambda, \alpha \in [3]} \int_{-\infty}^{\infty} b_1(t/\beta) e^{-iHt} A^{a,\alpha}(t) e^{iHt} dt $$

with

$$ A^{a,\alpha}(t) = \int_{-\infty}^{\infty} b_2(t'/\beta) e^{iHt'} A^{a,\alpha} e^{-2iHt'} A^{a,\alpha} e^{iHt'} dt' \quad (2.2) $$

for some rapidly decaying functions $b_1, b_2$ with $\|b_1\|_{L_1}, \|b_2\|_{L_1} \le 1$ whose exact expression can be found in [20]. The Lindbladian constructed above has the main advantage of being both quasi-local and reversible in the Heisenberg picture $\langle X, \mathcal{L}^{(\beta)\dagger}(Y) \rangle_{\sigma_{\beta}} = \langle \mathcal{L}^{(\beta)\dagger}(X), Y \rangle_{\sigma_{\beta}}$, where $\langle X, Y \rangle_{\sigma_{\beta}} := \text{tr}(X^{\dagger} \sigma_{\beta}^{1/2} Y \sigma_{\beta}^{1/2})$ denotes the KMS inner product, and where the Gibbs state $\sigma_{\beta} = \exp(-\beta H)/Z_{\beta}$ is the unique fixed point of the evolution generated by $\mathcal{L}^{(\beta)}$, with partition function $Z_{\beta} := \text{tr}(e^{-\beta H})$.

## 2.2 Mixing for High-Temperature Quantum Gibbs Sampler

Next, we consider a local Hamiltonian $H$ on the lattice $\Lambda$. More precisely, such a Hamiltonian is defined through a function that maps any non-empty finite set $X \subset \Lambda$ to a self-adjoint element $h_X$ supported in $X$ with $\max_X \|h_X\|_{\infty} \le h$. The Hamiltonian of the system in a region $A \subset \Lambda$ is then defined as the sum over interactions included in $A$, $H_A := \sum_{X \subseteq A} h_X$.

In addition, we assume that the Hamiltonian is such that no interaction $h_X$ has support on more than $k$ sites, and each site $u$ appears on at most $l$ non-zero operators $h_X$. We refer to such Hamiltonian as $(k, l)$-local. As is often done, we will make the implicit assumption that $H$ is one element of a family of Hamiltonians indexed by the lattice size $n$, in which case the constants $h, k$ and $l$ are assumed to be independent of $n$. In this regime, we give two proofs that it is possible to prepare quantum Gibbs states above a certain constant threshold temperature. The first one is based on a perturbative approach and yields that we need to simulate the Lindbladian for times linear in the number of qubits to achieve convergence and is based on a spectral gap estimate. The second proof is based on a gradient method and implies rapid mixing, that is, we only need to simulate the Lindbladian for times logarithmic in the number of qubits to ensure convergence. Furthermore, as we will see later, this method also extends to long-range systems and, unlike the perturbative approach, it is simpler to obtain explicit threshold temperatures. However, the perturbative approach also has its advantages; whereas the gradient method is tailored for high temperatures, the perturbative approach can be extended to other models for which a spectral gap can be shown for a given fixed point that satisfies as in [13, 43] and should yield that the generators of perturbations of the model also satisfy a spectral gap. One such

<footnote n="2">²we could remove the local measurements at the end by considering Gibbs states at lower temperatures such that the overlap with the ground state is close to 1. However, as one of our goals is to optimize the temperature of the Gibbs sampler, we instead work in the regime where the overlap is at least polynomially small and we can recover the ground state by a series of measurements instead of further decreasing the temperature.</footnote>
example should be the generator of thermal states associated to the 2D toric code, but leave the details to future work.

Let us start with our spectral gap approach. For the formal statement and proof of this and all other results of this paper, we refer the reader to the full version of the paper [49, 50]. We show that for any $\beta \le \beta^* = O((hkl)^{-1}) = O(1)$, the spectral gap of $-\mathcal{L}^{(\beta)\dagger}$, i.e. the smallest nonzero eigenvalue, is constant.

**Theorem 2.1.** In the notations of the previous paragraph, for any $(k, l)$-local Hamiltonian $H$, there exists a constant $\beta^* > 0$ independent of $n$ such that for $\beta \le \beta^*$, the spectral gap of $-\mathcal{L}^{(\beta)\dagger}$, is lower bounded by $\frac{1}{2\sqrt{2}e^{1/4}}$.

By a standard argument, Theorem 2.1 implies the following guarantee on the convergence of the Gibbs sampler:

**Corollary 2.2.** For any $\varepsilon > 0$, the evolution generated by $\mathcal{L}^{(\beta)}$ gets $\varepsilon$-close to $\sigma_{\beta}$ in polynomial time, i.e. for any initial state $\rho$,

$$ \|e^t \mathcal{L}^{(\beta)}(\rho) - \sigma_{\beta}\|_1 \le \varepsilon \quad \text{for all} \quad t = \Omega(\ln(1/\varepsilon) + n). \quad (2.3) $$

Furthermore, we can prepare an $\varepsilon$-approximation of $\sigma_{\beta}$ on a quantum computer with $\tilde{O}(n^2)$ Hamiltonian simulation time and $\tilde{O}(n^2)$ two qubit gates, where $\tilde{O}$ omits terms poly-log in $\varepsilon^{-1}$ and $n$.

Given Equation (2.3), the result on the efficient preparation on a quantum computer immediately follows from [20, Theorem 1.2], where the authors show how to efficiently simulate the Lindbladians of Equation (2.1) on a quantum computer. We now explain the proof steps to obtain the bound on the spectral gap.

**Mapping the Lindbladians to Hamiltonians:** for any $\beta > 0$ we define as in [19]

$$ \tilde{\mathcal{L}}^{(\beta)}(X) := \sigma_{\beta}^{-\frac{1}{4}} \mathcal{L}^{(\beta)}(\sigma_{\beta}^{\frac{1}{4}} X \sigma_{\beta}^{\frac{1}{4}}) \sigma_{\beta}^{-\frac{1}{4}} = \sum_{a, \alpha} \tilde{\mathcal{L}}_{a, \alpha}^{(\beta)}. \quad (2.4) $$

Letting $|\sqrt{\sigma_{\beta}}\rangle$ be the vectorization of $\sqrt{\sigma_{\beta}}$, we see that it is in the kernel of $\tilde{\mathcal{L}}^{(\beta)}$. Furthermore, as $\tilde{\mathcal{L}}^{(\beta)}$ is related to the original Lindbladian by a similarity transformation, they both share the same spectrum, and $\tilde{\mathcal{L}}^{(\beta)}$ is self-adjoint with respect to the Hilbert-Schmidt inner product for all $\beta > 0$, by KMS symmetry of $\mathcal{L}^{(\beta)\dagger}$. Thus, we can interpret $\tilde{\mathcal{L}}^{(\beta)}$ as a Hamiltonian. Furthermore, the Hilbert space on which it is defined is independent of $\sigma_{\beta}$.

**Decomposing the generator:** we can write the generator as the following telescopic sum:

$$ \tilde{\mathcal{L}}_{a, \alpha}^{(\beta)} = \tilde{\mathcal{L}}_{a, \alpha}^{\beta, 0} + \sum_{r=0}^{\infty} \tilde{\mathcal{L}}_{a, \alpha}^{\beta, r+1} - \tilde{\mathcal{L}}_{a, \alpha}^{\beta, r}, $$

where for $r > 0$ and a site $a$, $\tilde{\mathcal{L}}_{a, \alpha}^{\beta, r+1}$ is defined as the generator for the state with the reduced Hamiltonian $H_{B_a}(r)$ associated to the ball $B_a(r)$ centered in site $a$ and of radius $r$, i.e. the Hamiltonian we obtain from $H$ by only keeping the terms that act on $B_a(r)$. Thus, $\tilde{\mathcal{L}}_{a, \alpha}^{\beta, r+1} - \tilde{\mathcal{L}}_{a, \alpha}^{\beta, r}$ is strictly supported on $B_a(r+1)$.

**The $\beta \to 0$ limit:** by construction, for $\beta \to 0$, the $\tilde{\mathcal{L}}^{(\beta)}$ converges to the generator of the 1-local depolarizing channel. When performing the mapping to Hamiltonians described in Equation (2.4), we thus obtain a Hamiltonian $\tilde{H}_0$ that is frustration-free, gapped,

and satisfies local topological quantum order (LTQO) as in [13, 43]. It is straightforward to show these properties, so we omit them. Showing the convergence to the depolarizing semigroup requires slightly more work. We sketch the argument here. In essence, the choice of the functions $f, b_1$ and $b_2$ ensures that they become delta functions in the limit $\beta \to 0$. It is not difficult to see that at $\beta = 0$, the matrices we integrate over are just proportional to the jump operators $A^{a,i}$, which are those of the depolarizing channel. The proportionality constant we obtain is $\lambda = \frac{1}{\sqrt{2}e^{1/4}}$.

**Quasi-locality of the generator:** the next crucial step is to bound the generators in $\tilde{\mathcal{E}}_{a, \alpha}^{\beta, r} := \tilde{\mathcal{L}}_{a, \alpha}^{\beta, r+1} - \tilde{\mathcal{L}}_{a, \alpha}^{\beta, r}$ as a function of $r$ and $\beta$. By using Lieb-Robinson bounds, we find that

$$ \| \tilde{\mathcal{E}}_{a, \alpha}^{\beta, r} \|_{2 \to 2} = e^{-\Omega(r)}, \quad (2.5) $$

where the decay rate depends on $\beta$ and the Lieb-Robinson velocity. This means that we can see the finite $\beta$ contributions to $\tilde{\mathcal{L}}_{a, \alpha}^{(\beta)}$ as a quasi-local perturbation whose strength vanishes with lower $\beta$. With this, we find that $\tilde{\mathcal{L}}_{a, \alpha}^{(\beta)}$ satisfies all the assumptions from [43], from which we can guarantee the lower bound on the gap in Theorem 2.1. The expression of $\beta^*$ then only depends on the Lieb-Robinson velocity of $H$, and the lattice dimension. The proof extends straightforwardly to systems with exponentially decaying interactions with similar Lieb-Robinson bounds [30], and it is likely to also extend to systems with polynomially decaying interactions [5, 57].

We now turn to our proof strategy that yields rapid mixing at high temperatures. Our threshold temperature will be given in terms of the so-called Lieb-Robinson velocity of the model $J$, given by:

$$ J := \max_{u \in \Lambda} \sum_{Z \ni u} |Z| \|h_Z\|_{\infty} = O(hkl), $$

We have:

**Theorem 2.3.** In the notations of the previous paragraph, for any $(k, l)$-local Hamiltonian $H$ on a $D$ dimensional lattice, there exists a constant $\beta^* = \frac{1}{615^D J} > 0$ such that, for any $\beta < \beta^*$,

$$ \|e^t \mathcal{L}^{(\beta)}(\rho) - \sigma_{\beta}\|_1 \le \varepsilon \quad \text{for all} \quad t = \Omega(\log(n/\varepsilon)). \quad (2.6) $$

Furthermore, we can prepare an $\varepsilon$-approximation of $\sigma_{\beta}$ on a quantum computer with $\tilde{O}(n)$ Hamiltonian simulation time and $\tilde{O}(n)$ two-qubit gates, where $\tilde{O}$ hides polylogarithmic terms in $\varepsilon$, and $n$.

Given Eq. 2.6, the result on the efficient preparation on a quantum computer immediately follows from [20, Theorem 1.2], where the authors show how to efficiently simulate the Lindbladians of Eq. (2.1) on a quantum computer. In the next paragraphs, we briefly explain the proof steps. Let us explain the proof steps.

**The oscillator norm as a proxy:** The trace norm (or its dual operator norm) is insensitive to local perturbations, and hence unsuited to local-to-global analyses recurrent in proofs of rapid mixing. An alternative is to use the so-called oscillator norm $\|\|X\|$ := $\sum_{a \in \Lambda} \|\delta_a(X)\|_{\infty}$, where $\delta_a(X) := X - \frac{1}{2}I_a \otimes \text{tr}_a(X)$. In particular, we aim at proving that, for $\beta < \beta^*$, there exists $\kappa \equiv \kappa(\beta) \in (0, \lambda)$
with $\lambda = \frac{1}{\sqrt{2}e^{1/4}}$ such that, for any initial observable $X$,

$$ \|e^t \mathcal{L}^{(\beta)\dagger}(X)\| \le e^{-(\lambda-\kappa)t} \|X\|. \quad (2.7) $$

Hence, for any initial state $\rho$, denoting $\rho_t := e^t \mathcal{L}^{(\beta)}(\rho)$ and $X_t := e^t \mathcal{L}^{(\beta)\dagger}(X)$,

$$ \|\rho_t - \sigma\|_1 = \sup_{\|X\|_{\infty} \le 1} \mathrm{tr}(X(\rho_t - \sigma)) = $$

$$ \sup_{\|X\|_{\infty} \le 1} \|X_t - 2^{-n} \mathrm{tr}(X_t) I\| \|\rho - \sigma\|_1 \le \sup_{\|X\|_{\infty} \le 1} \|X_t\| \|\rho - \sigma\|_1 \\ \le e^{-(\lambda-\kappa)t} \sup_{\|X\|_{\infty} \le 1} \|X\| \|\rho - \sigma\|_1 \le 4ne^{-(\lambda-\kappa)t}, $$

where the last inequality uses the fact that $\|X\| \le 2n$. Furthermore, to see the inequality in (1), note that:

$$ \|X_t - 2^{-n} \mathrm{tr}(X_t) I\| \le \|X_t - \frac{1}{2} I_1 \otimes \mathrm{tr}_1(X_t)\| + \|\frac{1}{2} I_1 \otimes \mathrm{tr}_1(X_t) - 2^{-n} \mathrm{tr}(X_t) I\| $$

Now:

$$ \begin{aligned} \|\frac{1}{2} I_1 \otimes \mathrm{tr}_1(X_t) - 2^{-n} \mathrm{tr}(X_t) I\| &\le \|\frac{1}{2} I_1 \otimes \mathrm{tr}_1(X_t) - \frac{1}{4} I_{1,2} \otimes \mathrm{tr}_{1,2}(X_t)\| + \\ &\le \|\frac{1}{4} I_{1,2} \otimes \mathrm{tr}_{1,2}(X_t) - 2^{-n} \mathrm{tr}(X_t) I\| \\ &\le \|X_t - \frac{1}{2} I_2 \otimes \mathrm{tr}_2(X_t)\| + \|\frac{1}{4} I_{1,2} \otimes \mathrm{tr}_{1,2}(X_t) - 2^{-n} \mathrm{tr}(X_t) I\|, \end{aligned} $$

where we used the data-processing inequality for the completely depolarizing channel $X \mapsto \frac{1}{2} I_1 \otimes \mathrm{tr}_1(X)$ for the last inequality. Repeating this argument $n$ times we obtain (1). Hence, rapid mixing is implied by the existence of a constant $\kappa$ independent of $|\Lambda|$.

**Local conditions for oscillator norm decay:** In the classical literature on Markov chains, the decay of the oscillator norm (2.7) at high enough temperature can be derived by considering its differential form and identifying local sufficient conditions on the generator of the evolution [2, 52]. This idea was extended to the quantum, commuting setting in [39, 55]. Here, we adapt it to the noncommuting regime. In particular, we show that $\sum_a \sum_{b \ne a} \kappa_{a,b}^c + \sum_a \gamma_a^c \le \kappa$ for positive constants (that can depend on $\beta$) $\kappa_{a,b}^c \ge 0$ and $\gamma_a^c \ge 0$ such that, for all $X, b \ne a$

$$ \begin{aligned} \|[\delta_a, \mathcal{L}_b^{(\beta)\dagger}](X)\|_{\infty} &\le \sum_c \kappa_{a,b}^c \|\delta_c(X)\|_{\infty}, \\ \|\delta_a(\mathcal{L}_a^{(\beta)\dagger} - \mathcal{L}_a^{(0)\dagger})(X)\|_{\infty} &\le \sum_c \gamma_a^c \|\delta_c(X)\|_{\infty}. \end{aligned} $$

**Local conditions via Lindblad approximations:** It remains to show the two conditions listed above, at high enough temperature. For this, we show that the Lindbladians can be approximated in space and in $\beta$ as follows: given a constant $r_0 \in \mathbb{N}$ to be chosen later,

$$ \sum_{r \ge r_0} \| \mathcal{L}_b^{\beta,r \dagger} - \mathcal{L}_b^{\beta,r-1 \dagger} \|_{\infty} \to \Delta(r_0), \\ \| \mathcal{L}_b^{(\beta)\dagger} - \mathcal{L}_b^{(0)\dagger} \|_{\infty} \to \eta(\beta), $$

where $\mathcal{L}_b^{\beta,r \dagger}$ corresponds to the local Lindbladian $\mathcal{L}_b^{(\beta)}$ with associated Hamiltonian $H$ replaced by $H_{B_b(r)}$, i.e. the sum of interactions

supported in a ball of radius $r$ around site $b$. Above, $\Delta$ is a fast decaying function, whereas $\eta$ is an increasing function of $\beta$ with $\eta(0) = 0$.

Then, we show that $\kappa_{a,b}^c$ and $\gamma_a^c$ can be chosen so that, for any $r_0 \in \mathbb{N}$ and $c \in \Lambda$,

$$ \sum_a \sum_{b \ne a} \kappa_{a,b}^c + \sum_a \gamma_a^c \le 4(2r_0 + 1)^{2D} \eta(\beta) + f(r_0), \quad (2.8) $$

where $f(r_0)$ is a fast-decaying function depending on $\Delta(l)$ and $D$. Hence, in order to obtain $\kappa < \lambda$, it is enough that the RHS is also smaller than $\lambda$. This means we need to take $r_0$ large enough and choose $\beta$ small enough accordingly.

**Spatial and thermal approximations via Lieb-Robinson bounds:** We can derive the following expressions. Assuming initially that $\beta J \le 1/200$,

$$ \Delta(l) := \frac{14g(\beta J)r_0}{1 - g(\beta J)}, \\ \eta(\beta) := \beta J, $$

where $g(x) = \sqrt{x}/(1 + \sqrt{x})$. Plugging these into the bounds derived in (2.8), $\kappa$ may be chosen as

$$ \kappa \equiv 4(2r_0 + 1)^{2D} \beta J + f(r_0), $$

and if we choose $r_0 = 4$ and $\beta J \le 1/615^D$, we find that $\kappa$ is strictly less than $\lambda$. For low-dimensional models with large connectivity $k$, this includes lower temperatures than the results of [6] (where $\beta^*$ depends on $k^{-2}$).

The proof strategy outlined above holds as long as the Hamiltonian obeys a strong enough Lieb-Robinson bound. As such, it also extends to long-range models, for which these bounds have been proven [36, 57]. These Hamiltonians are such that

$$ \sup_{i \in \Lambda} \sum_{X \in \Lambda, i \in X} \|h_X\|_{\infty} \le g r^{D-v}, \quad (2.9) $$

$$ \sup_{i,j \in \Lambda} \sum_{\{i,j\} \in X} \|h_X\|_{\infty} \le g_0 (\mathrm{dist}(i,j) + 1)^{-v}, \quad (2.10) $$

for some constants $g, g_0$. The parameter $v$ controls the range of the interactions. We then have:

**Theorem 2.4.** Let $H$ be long-range and such that $v > 2D + 3$. There exists a constant $C$ depending solely on $D, g_0$ and $v$ such that for $\beta < \beta^* := C/g$,

$$ \|e^t \mathcal{L}^{(\beta)}(\rho) - \sigma_{\beta}\|_1 \le \varepsilon \quad \text{for all} \quad t = \Omega(\log(n/\varepsilon)). \quad (2.11) $$

## 2.3 Adiabatic Preparation of the Purified Gibbs State

The proof of Theorem 2.1 involves a lower bound on the gap of the Lindbladian, done by mapping this Lindbladian to a Hamiltonian with the same gap, but in a doubled Hilbert space. By construction, the Hamiltonian $\tilde{\mathcal{L}}^{(\beta)}$ is quasi-local, and has the purified GS as a fixed point. This means that $\tilde{\mathcal{L}}^{(\beta)}$ is a provable realization of Hamiltonians such as those suggested in e.g. [25, 28].

Additionally, the fact that we can control the gap starting from $\beta = 0$ means that we can straightforwardly devise an adiabatic scheme to prepare the purified GS. The adiabatic path consists of
lowering the temperature from $\beta = 0$, so that our parametrized Hamiltonian is $\mathcal{H}(s) \equiv \tilde{\mathcal{L}}_{s\beta}$ with $s \in [0, 1]$, and $\beta \le \beta^*$. This way, by initially preparing the GS of $\mathcal{H}(0)$, which consists of a product of Bell pairs $\bigotimes_{i=1}^n |\Phi^+\rangle_i$, we can adiabatically sweep towards the purified Gibbs state (or thermofield double) $|\sqrt{\sigma_{\beta}}\rangle$.

**Theorem 2.5.** In the notations of the previous paragraphs, and given $\beta^*$ as introduced in Theorem 2.1, for any $\beta \in [0, \beta^*]$, the minimum time required to adiabatically prepare a state $\varepsilon$-close to the purified Gibbs state at inverse temperature $\beta$ is

$$T_{\text{ad}} = O\left((\beta n)^3 \varepsilon^{-2}\right). \qquad (2.12)$$

The proof follows from the lower bound of the gap from Theorem 2.1, as well as standard estimates on the runtime of the adiabatic algorithm [3]. To obtain the estimate of Equation (2.12), we give upper bounds to the first and second derivatives of the Hamiltonian $\mathcal{H}(s)$ with respect to the parameter $s$. We note that rapid mixing also implies a constant spectral gap [12], but we will stick to using our spectral gap estimates as a departing point for simplicity.

The generator $\tilde{\mathcal{L}}^{(\beta)}$ thus provides a polynomial-time scheme to prepare high temperature purified GS. Being able to prepare these states is key in quantum simulations of certain models of entangled black holes [15, 25, 40, 45], and their generation allows for the measurement of OTOCs [54]. Because of this, many algorithms to prepare them have been devised [23, 27, 42, 53, 60], and even implemented in small experiments [63]. However, these are largely limited to variational approaches, without guarantees of efficiency or scalability. In contrast, the performance of our adiabatic algorithm at high temperatures is at most cubic in system size and quadratic in the inverse precision.

## 2.4 Zero-temperature Gibbs sampling and Universal Quantum Computing

Next, we consider the near-zero temperature regime, where we prove the existence of Gibbs samplers that reach states with inverse polynomial overlap with the ground states of BQP-hard Hamiltonians at $\beta = \Omega(\text{poly}(n))$ in polynomial time. This result leads to a dissipative variant of the well-known equivalence between the complexity class BQP of decision problems decidable with polynomially-sized uniform families of quantum circuits, and the class AdiabQP of those decidable by means of unitary quasi-adiabatic evolutions [1, 3, 34, 46].

It turns out that the Gaussian filter introduced in Equation (2.1) does not work as well for low temperatures, since the corresponding Markov chain does not necessarily converge to the ground state. However, it was conjectured in [20] that better mixing properties might be attained by means of linear combinations of Gaussian filters without loss of KMS symmetry. In particular, with such a linear combination we can generate the following filter

$$\gamma^M(\omega) := e^{-\beta \max\left(\omega + \frac{\beta \sigma_E^2}{2}, 0\right)},$$

where $\sigma_E$ is a free parameter quantifying the energy resolution. This is reminiscent of Metropolis sampling, and privileges transitions to lower energy levels.

**Definition 2.6** (The class GibbsQP$\beta(n)$). The class of decision problems decidable through the measurement of arbitrary few-qubit observables at the output of polynomially sized uniform families of Gibbs samplers associated with $(k, l)$-local Hamiltonians for some constants $k, l$ independent of the instance size, inverse temperature $\beta(n)$, and inverse polynomial spectral gap, where $n$ denotes the size of the problem's instance. As commonly assumed, the precision of the implementation of real parameters involved is inverse polynomially small in $n$.

**Theorem 2.7.** BQP = AdiabQP = GibbsQP$_{\text{poly}(n)}$.

The proof is sketched below. As previously mentioned, the equivalence BQP = AdiabQP was derived in the seminal paper [1], and later refined in [46] by exhibiting a simpler circuit-to-Hamiltonian (CTH) construction with a family of 2-local qubit Hamiltonians over a 2D grid (see also previous refinements in [3, 34, 46]). That GibbsQP$_{\text{poly}(n)} \subseteq$ BQP follows from the quantum algorithm prescribed in [19, 20]. Here, we are thus proving the opposite inclusion that BQP $\subseteq$ GibbsQP$_{\text{poly}(n)}$ by making use of circuit-to-Hamiltonian constructions akin to those appearing in the proofs of BQP $\subseteq$ AdiabQP.

*Proof sketch.*: Similar to the quantum adiabatic algorithm, our method consists of encoding the output states of a uniform, polynomially sized family of quantum circuits C into the ground states of a uniform family of local Hamiltonians $H_C$ that can usually be decomposed into a clock part $H_{\text{clock}}$ and circuit part. The adiabatic theorem requires a path between $H_C$ and a trivial Hamiltonian with gap closing at most polynomially fast. Here, we instead need to show the rapid convergence towards states with enough overlap with the ground state of $H_C$ for a Gibbs sampling algorithm with the properly selected filter function $\gamma^M(\omega)$. The Hamiltonians in CTH constructions can be chosen to be frustration free and have ground state energy 0. It then suffices to measure all energy terms and eventually obtain 0 to ensure we have prepared the ground state. For this procedure to succeed with high probability, it suffices to produce an approximation of the GS with large overlap with the ground state.

Now, consider the generator $\mathcal{L}^{(\sigma_E, \beta)} \equiv \mathcal{L}_H^{(\sigma_E, \beta)}$ constructed through $m$ jump operators $\{A^a\}_{a \in [m]}$ given by single-qubit Paulis as in Section 2.1, and Gaussian filter $\gamma$ replaced by the Metropolis filter $\gamma^M$. The associated Hamiltonian $H$ is on $n' = n + T$ qubits, with $T$ quadratic in the number of gates in the circuit, and has $M = \text{poly}(n + T)$ distinct eigenvalues. To show rapid convergence to the GS, we use several continuity bounds to connect the gap of $\mathcal{L}^{(\sigma_E, \beta)}$ to that of a simpler generator we can control.

First, we show the following perturbation bound for gap $(\mathcal{L}^{(\sigma_E, \beta)^\dagger})$ under changes in the Hamiltonian. Given $H = H_0 + V$, a perturbed Hamiltonian with $\|V\|_{\infty}$ small enough,

$$\text{gap}(\mathcal{L}_H^{(\sigma_E, \beta)^\dagger}) > \text{gap}(\mathcal{L}_{H_0}^{(\sigma_E, \beta)^\dagger}) - \delta_{\beta, \sigma_E}$$

where $\delta_{\beta, \sigma_E}''$ is proportional to $\|V\|_{\infty}$, $m$ and to $\max\{\frac{\ln \beta \sigma_E}{\sigma_E}, \frac{1}{\beta \sigma_E^2}\}$. In this case, we choose the full CTH for $V = H_C$, and only a classical "clock" part of it as $H_0 = H_{\text{clock}}$, which has a significantly simpler spectrum.
We then control the gap of the generator corresponding to the Hamiltonian $H_{\text{clock}}$ by connecting it to the gap in the limit of $\sigma_E \to 0$ and $\beta \to \infty$, which is done in two steps. For these to work, we exploit the additional structure of the spectrum of $H_{\text{clock}}$, namely that it is such that $M = \text{poly}(n')$ and that its smallest energy gap is $\Omega(1)$. One can prove that

$$ \text{gap}(\mathcal{L}^{(\sigma_E, \beta)\dagger}) \ge \text{gap}(\mathcal{L}^{(0, \beta)\dagger})(1 - \delta_{\beta, \sigma_E}) \quad (2.13) $$

with $\delta_{\beta, \sigma_E}$ polynomial in $M, m, \sigma_E$ and exponentially decaying in $\beta$. This means that at low enough temperatures, we can estimate the gap by focusing on the limit $\sigma_E \to 0$. We then connect with the gap at zero temperature. We show the inequality

$$ \text{gap}(\mathcal{L}^{(0, \beta)\dagger}) \ge \text{gap}(\mathcal{L}^{(0, \infty)\dagger}) - \delta'_{\beta}, $$

with $\delta'_{\beta}$ scaling polynomially with $M, m$ and decays exponentially in $\beta$. Thus, the gap of the generator $\mathcal{L}^{(0, \infty)\dagger}$ provides a good approximation to that of $\mathcal{L}^{(\sigma_E, \beta)\dagger}$ as long as $\beta = \Omega(\text{poly}(n'))$ and $\sigma_E = O(1)$.

The last part of the argument is a lower bound on $\text{gap}(\mathcal{L}^{(0, \infty)\dagger})$, which is possible due to the simple structure of the spectrum of $H_{\text{clock}}$ and of the generator $\mathcal{L}^{(0, \infty)\dagger}$ in the limit. To do this, we consider the explicit form of $\mathcal{L}^{(0, \infty)\dagger}$, which simplifies to a “quasi-classical” Lindbladian in which the gap can be bounded with two key ingredients: Gershgorin’s circle theorem and bounds on the gap of graph Laplacians, which appear due to the structure of the jump operators. Putting everything together, we find that there are regimes of large $\beta$, constant $\sigma_E$ and small $\|V\|_{\infty}$ within which the continuity bounds allows us to lower bound $\text{gap}(\mathcal{L}_{H_C}^{(\sigma_E, \beta)\dagger})$.

This argument shows that one can obtain a low temperature GS $\frac{e^{-\beta H_C}}{Z_\beta}$ in polynomial time. To prove that it has high overlap with the ground state at large enough $\beta$, we control the spectral gap of $H_C$ using once again the fact that it is a perturbation of a simpler Hamiltonian $H_{\text{clock}}$. This means that picking the temperature such that $\beta = \Omega((n')^{11})$, and adjusting the choice $\|V\|_{\infty} = O(1/(n')^5 \ln(n'))$ accordingly, considering the constraints from the continuity bounds, yields the desired polynomial overlap. Although the resulting Lindbladian is not necessarily quasi-local like in the high-temperature case, the results of [20] show that it can still be simulated efficiently on a quantum computer.

The previous Theorem can be used to show a separation between classical and quantum computers for approximating expected values of fast mixing observables similar (see also [32] for similar results): a local observable $O$ with $\|O\|_{\infty} \le 1$ is said to be fast mixing if the time-evolved observable $O_t := e^{t \mathcal{L}^{(\sigma_E, \beta)\dagger}}(O)$ satisfies $|\langle 0^n | O_t | 0^n \rangle - \text{tr}(\sigma_B O)| \le \varepsilon$ at $t = \text{poly}(\beta, \frac{1}{\varepsilon})$.

**Corollary 2.8.** *There exists no poly($\beta, \varepsilon^{-1}$)-runtime classical algorithm outputting an $\varepsilon$-additive approximation of the expected value $\text{tr}(\sigma_B O)$ for any fast-mixing observable $O$ unless BPP = BQP.*

**PROOF.** Assume such algorithm $\mathcal{A}_{\text{cl}}$ exists and take our Gibbs sampler encoding a poly-sized circuit $U$. By the proof of Theorem 2.7 sketched in the above paragraph, for $\beta = \Theta((n')^{11})$ and $\sigma_E = \Theta(1)$, the generator $\mathcal{L}^{(\sigma_E, \beta)\dagger}$ has spectral gap $\lambda = \Omega((n')^{-2})$. Since $\|H\|_{\infty} \le \beta T = O((n')^{12})$, this implies that $|\langle 0^n | O_t | 0^n \rangle - \text{tr}(\sigma_B O)| \le \varepsilon$.

$\text{tr}(\sigma_B O) \le \varepsilon \|O\|_{\infty}$ for $t = \text{poly}((n')^{14}, \log(\varepsilon^{-1})) = \text{poly}(\beta, \varepsilon^{-1})$, by a standard proof of fast convergence from gap estimates, hence any observable $O$ is fast mixing for the evolution considered. Now choosing $O$ as a 1-qubit POVM element encoding the solution of the circuit $U$, if $\mathcal{A}_{\text{cl}}$ could return an $\varepsilon$-additive approximation of the thermal average $\text{tr}(\sigma_B O)$, it would solve the problem encoded in $U$, which would imply BPP = BQP. $\square$

### 3 Comparison to Previous Work

The analysis of the runtime of Monte Carlo Markov chain algorithms for sampling of various distributions has a long and rich history and is still the topic of active research [4, 10, 21, 26, 41]. Even though the results available for quantum systems pale in comparison to that, there is an extensive and rapidly growing literature on sampling from quantum GS on a quantum computer. It includes numerous schemes with exponential runtimes for general Hamiltonians and temperatures [24, 31, 47, 51, 56, 62], including a range of variational algorithms [23, 59]. Others are aimed at mimicking the natural thermalization process of open systems [17, 38, 48], for which a fast convergence is only guaranteed in restricted cases such as commuting Hamiltonians [7, 33]. To the best of our knowledge, our results together with the algorithm of [20] are the first to give efficient (polynomial-time) preparation for general non-commuting models, even restricting to high temperatures. It also does not require any assumptions on the GS besides the temperature, unlike previous polynomial-time algorithms limited to 1D [11] or commuting Hamiltonians [29]. A result with a comparable degree of generality is that of [12]. However, there the authors need to assume conditions on the decay of correlations of the GS. Although these are believed to hold at high enough temperatures, they also require the application of gates acting on $\ln^D(n)$ qubits, where $D$ is the dimension of the lattice. Except for $D = 1$, standard compilation results would then give a quasi-polynomial $e^{O(\ln^D(n))}$ overhead to compile such gates, so the resulting algorithm is quasi-polynomial. Another algorithm with potential for efficiency at high temperatures is the adiabatic evolution proposed in the Appendix of [29] based on cluster expansions, but it is not clear whether it has a polynomial runtime.

It is also worthwhile to compare our results to those of [6], which appeared at a similar time as our work. There, the authors show that at high enough temperatures, Gibbs states can be approximated arbitrarily well by completely separable states that can be sampled from efficiently. Thus, their result also gives both efficient classical and quantum algorithms to sample from such Gibbs states. The critical temperature for our gap bounds scales inverse linearly with the locality of the Hamiltonian. In contrast, that of [6] scales inverse quadratically. Thus, the Gibbs sampler is guaranteed to work at lower temperatures in the high locality limit. Furthermore, their classical algorithm to sample from the distribution has a runtime that scales like $\bar{O}(n^{7+\log(\beta)/\log(\beta_c/\beta)})$, where we have only included the dependency in $n$ and $\beta$ is the degree of the interaction graph. In contrast, our algorithm has no dependency on extra parameters
of the problem and runs in time $\tilde{O}(n)^3$, thus achieving a large polynomial speedup compared to their methods. Their methods also apply to Hamiltonians beyond ours, such as k-local ones not on lattices, but our results only require Lieb-Robinson bounds, so they also extend to a range of long-range models [57] that their method does not cover. Furthermore, they also obtain as a corollary of their algorithm that these high temperature states are fully separable, a strong statement which does not follow from our results.

The idea of solving BQP-hard problems by engineering Lindbladians can be traced back to [35, 58]. However, the Lindbladians constructed there did not emulate the naturally occurring physical process of thermalization. In contrast to these early works, the authors of the recent paper [18] developed a thermal gradient descent algorithm inspired by natural physical processes that generate low-energy states. This algorithm involves intertwining dissipation through Gibbs sampling, followed by measurements to confirm the reduction in energy at the output of the dissipation. While this new model of quantum computing is polynomially equivalent to the circuit model, the measurements at each step necessitate a possibly prohibitive overhead in practice. Moreover, the algorithm is guaranteed to work only at inverse temperatures that scale as $\beta = O(T^{19})$ in the size $T$ of the circuit being emulated.

In contrast, our approach is proved to work already at $\beta = O(T^{11})$ for circuits of polynomial size, and does not require an active change of the dissipation depending on intermediate energy measurements: we simply need to let the system thermalize under a Lindbladian with a Hamiltonian corresponding to a CTH encoding for a polynomial amount of time. We then measure a series of local tests corresponding to the terms of another CTH mapping. If they all accept, which we show happens with high probability, we obtain the output of the circuit. Thus, repeating this procedure a few times suffices to reach the ground state.

Additionally, our procedure is also closer in spirit to the quantum adiabatic algorithm, while its dissipative nature compared to quantum adiabatic computing could provide a natural resilience to errors. In contrast, we recall that the proof of a version of the threshold theorem for adiabatic quantum computing remains a major open problem to this date [22, 61]. Finally, our proof is arguably much more straightforward than that of [18].

## Acknowledgements

CR acknowledges financial support from the ANR project QTraj (ANR-20-CE40-0024-01) of the French National Research Agency (ANR). DSF acknowledges funding from the European Union under Grant Agreement 101080142 and the project EQUALITY and from the Novo Nordisk Foundation (Grant No. NNF20OC0059939 Quantum for Life). AMA acknowledges support from the Spanish Agencia Estatal de Investigación through the grants “IFT Centro de Excelencia Severo Ochoa CEX2020-001007-S” and “Ramón y Cajal RyC2021-031610-I”, financed by MCIN/AEI/10.13039/501100011033 and the European Union NextGenerationEU/PRTR. This project was funded within the QuantERA II Programme that has received

## References

[1] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. 2008. Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation. *SIAM Rev.* 50, 4 (2008), 755–787. https://doi.org/10.1137/080734479

[2] M. Aizenman and R. Holley. 1987. *Rapid Convergence to Equilibrium of Stochastic Ising Models in the Dobrushin Shlosman Regime*. Springer New York, 1–11. https://doi.org/10.1007/978-1-4613-8734-3_1

[3] Andris Ambainis and Oded Regev. 2006. An Elementary Proof of the Quantum Adiabatic Theorem. https://doi.org/10.1201/9780203643204-12 arXiv:quant-ph/0411152 [quant-ph]

[4] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. 2022. Entropic independence: optimal mixing of down-up random walks. In *Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC '22)*. ACM. https://doi.org/10.1145/3519935.3520048

[5] Chi-Fang (Anthony) Chen, Andrew Lucas, and Chao Yin. 2023. Speed limits and locality in many-body quantum dynamics. *Reports on Progress in Physics* 86, 11 (September 2023), 116001. https://doi.org/10.1088/1361-6633/acfaae

[6] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. 2024. High-Temperature Gibbs States are Unentangled and Efficiently Preparable. https://doi.org/10.48550/ARXIV.2403.16850

[7] Ivan Bardet, Ángela Capel, Li Gao, Angelo Lucia, David Pérez-García, and Cambseby Rouzé. 2023. Rapid Thermalization of Spin Chain Commuting Hamiltonians. *Physical Review Letters* 130, 6 (feb 2023). https://doi.org/10.1103/physrevlett.130.060401

[8] Ivan Bardet, Ángela Capel, Li Gao, Angelo Lucia, David Pérez-García, and Cambseby Rouzé. 2024. Entropy Decay for Davies Semigroups of a One Dimensional Quantum Lattice. *Communications in Mathematical Physics* 405, 2 (10 Feb 2024), 42. https://doi.org/10.1007/s00220-023-04869-5

[9] Ivan Bardet, Ángela Capel, Angelo Lucia, David Pérez-García, and Cambseby Rouzé. 2021. On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1D systems. *J. Math. Phys.* 62, 6 (2021), 061901. https://doi.org/10.1063/1.5142186 arXiv:https://doi.org/10.1063/1.5142186

[10] Roland Bauerschmidt and Thierry Bodineau. 2019. A very simple proof of the LSI for high temperature spin systems. *Journal of Functional Analysis* 276, 8 (April 2019), 2582–2588. https://doi.org/10.1016/j.jfa.2019.01.007

[11] Ersen Bilgin and Sergio Boixo. 2010. Preparing thermal states of quantum systems by dimension reduction. *Physical Review Letters* 105, 17 (October 2010), 170405. https://doi.org/10.1103/PhysRevLett.105.170405

[12] Fernando G. S. L. Brandão and Michael J. Kastoryano. 2019. Finite Correlation Length Implies Efficient Preparation of Quantum Thermal States. *Communications in Mathematical Physics* 365, 1 (01 Jan 2019), 1–16. https://doi.org/10.1007/s00220-018-3150-8

[13] Sergey Bravyi, Matthew B. Hastings, and Spyridon Michalakis. 2010. Topological quantum order: Stability under local perturbations. *J. Math. Phys.* 51, 9 (September 2010). https://doi.org/10.1063/1.3490195

[14] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. 2011. *Handbook of markov chain monte carlo*. CRC press. https://doi.org/10.1201/b10905-2

[15] Adam R. Brown, Hrant Gharibyan, Stefan Leichenauer, Henry W. Lin, Sepehr Nezami, Grant Salton, Leonard Susskind, Brian Swingle, and Michael Walter. 2023. Quantum Gravity in the Lab. I. Teleportation by Size and Traversable Wormholes. *PRX Quantum* 4, 1 (February 2023), 010320. https://doi.org/10.1103/PRXQuantum.4.010320 Publisher: American Physical Society.

[16] Pietro Caputo, Fabio Martinelli, FranAôis Simenhaus, and Fabio Lucio Toninelli. 2011. Zero temperature stochastic 3D ising model and dimer covering fluctuations: A first step towards interface mean curvature motion. *Communications on Pure and Applied Mathematics* 64, 6 (2011), 778–831. https://doi.org/10.1002/cpa.20359

[17] Chi-Fang Chen and Fernando G. S. L. Brandão. 2023. Fast Thermalization from the Eigenstate Thermalization Hypothesis. https://doi.org/10.53846/goediss-9799 arXiv:2112.07646 [quant-ph]

[18] Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, and Leo Zhou. 2023. Local minima in quantum systems. https://doi.org/10.1038/s41567-025-02781-4 arXiv:2309.16596 [quant-ph]

[19] Chi-Fang Chen, Michael J. Kastoryano, Fernando G. S. L. Brandão, and András Gilyén. 2023. Quantum Thermal State Preparation. https://doi.org/10.22331/q-2023-10-10-1132 arXiv:2303.18224 [quant-ph]

[20] Chi-Fang Chen, Michael J. Kastoryano, and András Gilyén. 2023. An efficient and exact noncommutative quantum Gibbs sampler. https://doi.org/10.1109/icassp.2015.7178739 arXiv:2311.09207 [quant-ph]

[21] Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2021. Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. In *Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC '21)*. ACM. https://doi.org/10.1145/3406325.3451035

[22] Andrew M. Childs, Edward Farhi, and John Preskill. 2001. Robustness of adiabatic quantum computation. *Phys. Rev. A* 65 (Dec 2001), 012322. Issue 1. https://doi.org/10.1103/PhysRevA.65.012322

<footnote n="3">³The different scaling compared with that of Corollary 2.2 comes from a standard overhead due to time discretization in order to have a fair comparison of our bound with that of [6].</footnote>

<footnote>funding from the EU's H2020 research and innovation programme under the GA No 101017733.</footnote>
[23] Anirban N. Chowdhury, Guang Hao Low, and Nathan Wiebe. 2020. A Variational Quantum Algorithm for Preparing Quantum Gibbs States. https://doi.org/10.48550/arXiv.2002.00055 arXiv:2002.00055 [quant-ph].

[24] Anirban Narayan Chowdhury and Rolando D. Somma. 2017. Quantum algorithms for Gibbs sampling and hitting-time estimation. *Quantum Information and Computation* 17, 1 (2 2017). https://doi.org/10.26421/qic17.1-2

[25] William Cottrell, Ben Freivogel, Diego M. Hofman, and Sagar F. Lokhande. 2019. How to Build the Thermofield Double State. *Journal of High Energy Physics* 2019, 2 (February 2019), 58. https://doi.org/10.1007/JHEP02(2019)058 arXiv:1811.11528 [cond-mat, physics:hep-th, physics:quant-ph].

[26] Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. 2021. A spectral condition for spectral gap: fast mixing in high-temperature Ising models. *Probability Theory and Related Fields* 182, 3-4 (August 2021), 1035-1051. https://doi.org/10.1007/s00440-021-01085-x

[27] Daniel Failde, Juan Santos-Suárez, David A. Herrera-Martí, and Javier Mas. 2023. Hamiltonian Forging of a Thermofield Double. https://doi.org/10.48550/arXiv.2311.10566

[28] Adrian F. Feiguin and Israel Klich. 2013. Hermitian and non-Hermitian thermal Hamiltonians. https://doi.org/10.48550/arXiv.1308.0756 arXiv:1308.0756 [cond-mat, physics:physics].

[29] Yimin Ge, András Molnár, and J. Ignacio Cirac. 2016. Rapid Adiabatic Preparation of Injective Projected Entangled Pair States and Gibbs States. *Phys. Rev. Lett.* 116 (Feb 2016), 080503. Issue 8. https://doi.org/10.1103/PhysRevLett.116.080503

[30] Matthew B. Hastings and Tohru Koma. 2006. Spectral Gap and Exponential Decay of Correlations. *Communications in Mathematical Physics* 265, 3 (01 Aug 2006), 781–804. https://doi.org/10.1007/s00220-006-0030-4

[31] Zoe Holmes, Gopikrishnan Muraleedharan, Rolando D. Somma, Yigit Subasi, and Burak Şahinoğlu. 2022. Quantum algorithms from fluctuation theorems: Thermal-state preparation. *Quantum* 6 (October 2022), 825. https://doi.org/10.22331/q-2022-10-06-825

[32] Vikram Kashyap, Georgios Styliaris, Sara Mouradian, Juan Ignacio Cirac, and Rahul Trivedi. 2024. Accuracy guarantees and quantum advantage in analogue open quantum simulation with and without noise. *arXiv preprint arXiv:2404.11081* (2024). https://doi.org/10.1021/acs.jpclett.4c02313.s001

[33] Michael J. Kastoryano and Fernando G. S. L. Brandão. 2016. Quantum Gibbs Samplers: The Commuting Case. *Communications in Mathematical Physics* 344, 3 (01 Jun 2016), 915–957. https://doi.org/10.1007/s00220-016-2641-8

[34] Julia Kempe, Alexei Kitaev, and Oded Regveg. 2006. The Complexity of the Local Hamiltonian Problem. *SIAM J. Comput.* 35, 5 (2006), 1070–1097. https://doi.org/10.1137/S0097539704445226 arXiv:https://doi.org/10.1137/S0097539704445226

[35] B. Kraus, H. P. Büchler, S. Diehl, A. Kantian, A. Micheli, and P. Zoller. 2008. Preparation of entangled states by quantum Markov processes. *Phys. Rev. A* 78 (Oct 2008), 042307. Issue 4. https://doi.org/10.1103/PhysRevA.78.042307

[36] Tomotaku Kuwahara and Keiji Saito. 2020. Strictly Linear Light Cones in Long-Range Interacting Systems of Arbitrary Dimensions. *Phys. Rev. X* 10 (Jul 2020), 031010. Issue 3. https://doi.org/10.1103/PhysRevX.10.031010

[37] David A Levin and Yuval Peres. 2017. *Markov chains and mixing times*. Vol. 107. American Mathematical Soc. https://doi.org/10.1090/mbk/107/01

[38] Xiantao Li and Chunhao Wang. 2023. Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion. In *50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 261)*, Kousha Etessami, Uriel Feige, and Gabriele Puppis (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 87:1–87:20. https://doi.org/10.4230/LIPIcs.ICALP.2023.87

[39] Adam W. Majewski and Bogusław Zegarlinski. 1995. Quantum stochastic dynamics. I. *Mathematical Physics Electronic Journal* [electronic only] 1, 2 (1995). https://doi.org/10.1007/978-3-7091-8780-7_2

[40] Juan Maldacena and Xiao-Liang Qi. 2018. Eternal traversable wormhole. https://doi.org/10.48550/arXiv.1804.00491 arXiv:1804.00491 [cond-mat, physics:gr-qc, physics:hep-th].

[41] Fabio Martinelli. 1999. Lectures on Glauber dynamics for discrete spin models. *Lectures on probability theory and statistics (Saint-Flour, 1997)* 1717 (1999), 93–191. https://doi.org/10.1007/978-3-540-48115-7_2

[42] John Martyn and Brian Swingle. 2019. Product Spectrum Ansatz and the Simplicity of Thermal States. *Physical Review A* 100, 3 (September 2019), 032107. https://doi.org/10.1103/PhysRevA.100.032107

[43] Spyridon Michalakis and Justyna P. Zwolak. 2013. Stability of Frustration-Free Hamiltonians. *Communications in Mathematical Physics* 322, 2 (01 Sep 2013), 277–302. https://doi.org/10.1007/s00220-013-1762-6

[44] Bruno Nachtergaele and Robert Sims. 2006. Lieb-Robinson Bounds and the Exponential Clustering Theorem. *Communications in Mathematical Physics* 265, 1 (March 2006), 119–130. https://doi.org/10.1007/s00220-006-1556-1

[45] Sepehr Nezami, Henry W. Lin, Adam R. Brown, Hrant Gharibyan, Stefan Leichenauer, Grant Salton, Leonard Susskind, Brian Swingle, and Michael Walter. 2023. Quantum Gravity in the Lab: Teleportation by Size and Traversable Wormholes, Part II. *PRX Quantum* 4, 1 (February 2023), 010321. https://doi.org/10.1103/PRXQuantum.4.010321 arXiv:2102.01064 [hep-th, physics:quant-ph].

[46] Roberto Oliveira and Barbara M. Terhal. 2008. The complexity of quantum spin systems on a two-dimensional square lattice. *Quantum Info. Comput.* 8, 10 (nov 2008), 900–924. https://doi.org/10.26421/qic8.10-2

[47] David Poulin and Pawel Wocjan. 2009. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. *Physical Review Letters* 103, 22 (November 2009), 220502. https://doi.org/10.1103/PhysRevLett.103.220502 arXiv:0905.2199 [quant-ph].

[48] Patrick Rall, Chunhao Wang, and Pawel Wocjan. 2023. Thermal State Preparation via Rounding Promises. *Quantum* 7 (October 2023), 1132. https://doi.org/10.22331/q-2023-10-10-1132

[49] Cambyse Rouzé, Daniel Stilck França, and Álvaro M. Alhambra. 2024. Efficient thermalization and universal quantum computing with quantum Gibbs samplers. *arXiv.2403.12691* (2024). https://doi.org/10.48550/ARXIV.2403.12691

[50] Cambyse Rouzé, Daniel Stilck França, and Álvaro M. Alhambra. 2024. Optimal quantum algorithm for Gibbs state preparation. *arXiv.2411.04885* (2024). https://doi.org/10.48550/ARXIV.2411.04885

[51] Oles Shtanko and Ramis Movassagh. 2023. Preparing thermal states on noiseless and noisy programmable quantum processors. https://doi.org/10.1103/prxquantum.2.030308 arXiv:2112.14688 [quant-ph]

[52] Daniel W Stroock and Bogusław Zegarlinski. 1992. The equivalence of the logarithmic Sobolev inequality and the Dobrushin-Shlosman mixing condition. *Communications in mathematical physics* 144 (1992), 303–323. https://doi.org/10.1007/bf02101094

[53] Vincent Paul Su. 2021. Variational preparation of the thermofield double state of the Sachdev-Ye-Kitaev model. *Physical Review A* 104, 1 (July 2021). https://doi.org/10.1103/physreva.104.012427

[54] Bhuvanesh Sundar, Andreas Elben, Lata Kh Joshi, and Torsten V. Zache. 2022. Proposal for measuring out-of-time-ordered correlators at finite temperature with coupled spin chains. *New Journal of Physics* 24, 2 (February 2022), 023037. https://doi.org/10.1088/1367-2630/ac5002 arXiv:2107.02196 [cond-mat, physics:nlin, physics:quant-ph]

[55] Kristan Temme and Michael J Kastoryano. 2015. How fast do stabilizer Hamiltonians thermalize? *arXiv preprint arXiv:1505.07811* (2015). https://doi.org/10.1103/physrevc.71.064904

[56] K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, and F. Verstraete. 2011. Quantum Metropolis sampling. *Nature* 471, 7336 (March 2011), 87–90. https://doi.org/10.1038/nature09770

[57] Minh C. Tran, Andrew Y. Guo, Christopher L. Baldwin, Adam Ehrenberg, Alexey V. Gorshkov, and Andrew Lucas. 2021. Lieb-Robinson Light Cone for Power-Law Interactions. *Phys. Rev. Lett.* 127 (Oct 2021), 160401. Issue 16. https://doi.org/10.1103/PhysRevLett.127.160401

[58] Frank Verstraete, Michael M. Wolf, and J. Ignacio Cirac. 2009. Quantum computation and quantum-state engineering driven by dissipation. *Nature Physics* 5, 9 (July 2009), 633–636. https://doi.org/10.1038/nphys1342

[59] Youle Wang, Guangxi Li, and Xin Wang. 2021. Variational Quantum Gibbs State Preparation with a Truncated Taylor Series. *Physical Review Applied* 16, 5 (November 2021), 054035. https://doi.org/10.1103/PhysRevApplied.16.054035 Publisher: American Physical Society.

[60] Jingxiang Wu and Timothy H. Hsieh. 2019. Variational Thermal Quantum Simulation via Thermofield Double States. *Physical Review Letters* 123, 22 (November 2019), 220502. https://doi.org/10.1103/PhysRevLett.123.220502

[61] Kevin C. Young, Mohan Sarovar, and Robin Blume-Kohout. 2013. Error Suppression and Error Correction in Adiabatic Quantum Computation: Techniques and Challenges. *Phys. Rev. X* 3 (Nov 2013), 041013. Issue 4. https://doi.org/10.1103/PhysRevX.3.041013

[62] Daniel Zhang, Jan Lukas Bosse, and Toby Cubitt. 2023. Dissipative Quantum Gibbs Sampling. https://doi.org/10.1109/tqe.2024.3511419 arXiv:2304.04526 [quant-ph]

[63] D. Zhu, S. Johri, N. M. Linke, K. A. Landsman, N. H. Nguyen, C. H. Alderete, A. Y. Matsuura, T. H. Hsieh, and C. Monroe. 2020. Generation of Thermofield Double States and Critical Ground States with a Quantum Computer. *Proceedings of the National Academy of Sciences* 117, 41 (October 2020), 25402–25406. https://doi.org/10.1073/pnas.2006337117

[64] Ángela Capel, Cambyse Rouzé, and Daniel Stilck França. 2021. The modified logarithmic Sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions. https://doi.org/10.1142/9789812770271_0026 arXiv:2009.11817 [quant-ph]

Received 2024-11-04; accepted 2025-02-01