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.14639 · Annual Symposium on Foundations of Computer Science

Quantum Computational Advantage with Constant-Temperature Gibbs Sampling

Thiago Bergamaschi, Chi-Fang Chen, Yunchao Liu

Published Oct 27, 2024• 42 citations
arXivHTMLPDF

Abstract

A quantum system coupled to a bath at some fixed, finite temperature converges to its Gibbs state. This thermalization process defines a natural, physically-motivated model of quantum computation. However, whether quantum computational advantage can be achieved within this realistic physical setup has remained open, due to the challenge of finding systems that thermalize quickly, but are classically intractable. Here we consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures, and prove that this task demonstrates quantum computational advantage. We design a family of commuting local Hamiltonians (parent Hamiltonians of shallow quantum circuits) and prove that they rapidly converge to their Gibbs states under the standard physical model of thermalization (as a continuous-time quantum Markov chain). On the other hand, we show that no polynomial time classical algorithm can sample from the measurement outcome distribution by reducing to the classical hardness of sampling from noiseless shallow quantum circuits. The key step in the reduction is constructing a fault-tolerance scheme for shallow IQP circuits against input noise.

DOI
10.1109/focs61266.2024.00071

Related papers

An (almost) efficient classical algorithm for sampling from typical Gibbs states

Saleh Naghdi, Eric R. Anschuetz

Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum $p$-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum $p$-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum $p$-spin model at temperatures below that for which classical algorithms are also (almost) efficient.

quant-pharXiv:2609.40250•Oct 1, 2026•0 citations

Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians

Joel Rajakumar, James D. Watson

Sampling from Gibbs states – states corresponding to system in thermal equilibrium – has recently been shown to be a task for which quantum computers are expected to achieve super-polynomial speed-up compared to classical computers, provided the locality of the Hamiltonian increases with the system size \cite{bergamaschi2024sample}. We extend these results to show that this quantum advantage still occurs for Gibbs states of Hamiltonians with O(1)-local interactions at constant temperature by showing classical hardness-of-sampling and demonstrating such Gibbs states can be prepared efficiently using a quantum computer. In particular, we show hardness-of-sampling is maintained even for 5-local Hamiltonians on a 3D lattice. We additionally show that the hardness-of-sampling is robust when we are only able to make imperfect measurements.

arXiv:2408.01516•Quantum•Jan 22, 2026•35 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

Dissipative Quantum Gibbs Sampling

Daniel Zhang, Jan Lukas Bosse, Toby S. Cubitt

Systems in thermal equilibrium at non-zero temperature are described by their Gibbs state. For classical many-body systems, the Metropolis-Hastings algorithm gives a Markov process with a local update rule that samples from the Gibbs distribution. For quantum systems, sampling from the Gibbs state is significantly more challenging. Many algorithms have been proposed, but these are more complex than the simple local update rule of classical Metropolis sampling, requiring non-trivial quantum algorithms such as phase estimation as a subroutine. Here, we show that a dissipative quantum algorithm with a simple, local update rule is able to sample from the quantum Gibbs state. In contrast to the classical case, the quantum Gibbs state is not generated by converging to the fixed point of a Markov process, but by the states generated at the stopping time of a conditionally stopped process. This gives a new answer to the long-sought-after quantum analogue of Metropolis sampling. Compared to previous quantum Gibbs sampling algorithms, the local update rule of the process has a simple implementation, which may make it more amenable to near-term implementation on suitable quantum hardware. This dissipative Gibbs sampler works for arbitrary quantum Hamiltonians, without any assumptions on or knowledge of its properties, and comes with certifiable precision and run-time bounds. We also show that the algorithm benefits from some measure of built-in resilience to faults and errors (``fault resilience''). Finally, we also demonstrate how the stopping statistics of an ensemble of runs of the dissipative Gibbs sampler can be used to estimate the partition function.

arXiv:2304.04526•Apr 10, 2023•39 citations

Efficient Quantum Gibbs Sampling with Local Circuits

Dominik Hahn, Ryan Sweke, Abhinav Deshpande +1 more

The problem of simulating the thermal behavior of quantum systems remains a central open challenge in quantum computing. Unlike well-established quantum algorithms for unitary dynamics, algorithms for preparing thermal states—crucial for probing equilibrium behavior—became available only recently with breakthrough algorithms based on the simulation of well-designed dissipative processes, a quantum-analog to Markov chain Monte Carlo algorithms. We show a way to implement these algorithms avoiding expensive block encoding and relying only on dense local circuits, akin to Hamiltonian simulation. Specifically, our method leverages spatial truncation and Trotterization of exact quasilocal dissipative processes. We rigorously prove that the approximations we use have little effect on rapid mixing at high temperatures and allow convergence to the thermal state with small bounded error. Moreover, we accompany our analytical results with numerical simulations that show that this method, unlike previously thought, is within the reach of current generation of quantum hardware. These results provide the first provably efficient quantum thermalization protocol implementable on near-term quantum devices, offering a concrete path toward practical simulation of equilibrium quantum phenomena.

arXiv:2506.04321•PRX Quantum•Mar 17, 2026•12 citations

Mixing Time of Quantum Gibbs Sampling for Random Sparse Hamiltonians

Akshar Ramkumar, Mehdi Soleimanifar

Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm [Chen et al., 2023] provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The running time of this algorithm depends on the mixing time of the corresponding quantum Markov chain, which has not been rigorously bounded except in the high-temperature regime. In this work, we establish a polylog(n) upper bound on its mixing time for various families of random n × n sparse Hamiltonians at any constant temperature. We further analyze how the choice of the jump operators for the algorithm and the spectral properties of these sparse Hamiltonians influence the mixing time. Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.

arXiv:2411.04454•Leibniz international proceedings in informatics•Nov 7, 2024•19 citations
A quantum system coupled to a bath at some fixed, finite temperature converges to its Gibbs state. This thermalization process defines a natural, physically-motivated model of quantum computation. However, whether quantum computational advantage can be achieved within this realistic physical setup has remained open, due to the challenge of finding systems that thermalize quickly, but are classically intractable. Here we consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures, and prove that this task demonstrates quantum computational advantage. We design a family of commuting local Hamiltonians (parent Hamiltonians of shallow quantum circuits) and prove that they rapidly converge to their Gibbs states under the standard physical model of thermalization (as a continuous-time quantum Markov chain). On the other hand, we show that no polynomial time classical algorithm can sample from the measurement outcome distribution by reducing to the classical hardness of sampling from noiseless shallow quantum circuits. The key step in the reduction is constructing a fault-tolerance scheme for shallow IQP circuits against input noise.
Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum ppp-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum ppp-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum ppp-spin model at temperatures below that for which classical algorithms are also (almost) efficient.
Sampling from Gibbs states – states corresponding to system in thermal equilibrium – has recently been shown to be a task for which quantum computers are expected to achieve super-polynomial speed-up compared to classical computers, provided the locality of the Hamiltonian increases with the system size \cite{bergamaschi2024sample}. We extend these results to show that this quantum advantage still occurs for Gibbs states of Hamiltonians with O(1)-local interactions at constant temperature by showing classical hardness-of-sampling and demonstrating such Gibbs states can be prepared efficiently using a quantum computer. In particular, we show hardness-of-sampling is maintained even for 5-local Hamiltonians on a 3D lattice. We additionally show that the hardness-of-sampling is robust when we are only able to make imperfect measurements.
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.
Systems in thermal equilibrium at non-zero temperature are described by their Gibbs state. For classical many-body systems, the Metropolis-Hastings algorithm gives a Markov process with a local update rule that samples from the Gibbs distribution. For quantum systems, sampling from the Gibbs state is significantly more challenging. Many algorithms have been proposed, but these are more complex than the simple local update rule of classical Metropolis sampling, requiring non-trivial quantum algorithms such as phase estimation as a subroutine. Here, we show that a dissipative quantum algorithm with a simple, local update rule is able to sample from the quantum Gibbs state. In contrast to the classical case, the quantum Gibbs state is not generated by converging to the fixed point of a Markov process, but by the states generated at the stopping time of a conditionally stopped process. This gives a new answer to the long-sought-after quantum analogue of Metropolis sampling. Compared to previous quantum Gibbs sampling algorithms, the local update rule of the process has a simple implementation, which may make it more amenable to near-term implementation on suitable quantum hardware. This dissipative Gibbs sampler works for arbitrary quantum Hamiltonians, without any assumptions on or knowledge of its properties, and comes with certifiable precision and run-time bounds. We also show that the algorithm benefits from some measure of built-in resilience to faults and errors (``fault resilience''). Finally, we also demonstrate how the stopping statistics of an ensemble of runs of the dissipative Gibbs sampler can be used to estimate the partition function.
The problem of simulating the thermal behavior of quantum systems remains a central open challenge in quantum computing. Unlike well-established quantum algorithms for unitary dynamics, algorithms for preparing thermal states—crucial for probing equilibrium behavior—became available only recently with breakthrough algorithms based on the simulation of well-designed dissipative processes, a quantum-analog to Markov chain Monte Carlo algorithms. We show a way to implement these algorithms avoiding expensive block encoding and relying only on dense local circuits, akin to Hamiltonian simulation. Specifically, our method leverages spatial truncation and Trotterization of exact quasilocal dissipative processes. We rigorously prove that the approximations we use have little effect on rapid mixing at high temperatures and allow convergence to the thermal state with small bounded error. Moreover, we accompany our analytical results with numerical simulations that show that this method, unlike previously thought, is within the reach of current generation of quantum hardware. These results provide the first provably efficient quantum thermalization protocol implementable on near-term quantum devices, offering a concrete path toward practical simulation of equilibrium quantum phenomena.
Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm [Chen et al., 2023] provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The running time of this algorithm depends on the mixing time of the corresponding quantum Markov chain, which has not been rigorously bounded except in the high-temperature regime. In this work, we establish a polylog(n) upper bound on its mixing time for various families of random n × n sparse Hamiltonians at any constant temperature. We further analyze how the choice of the jump operators for the algorithm and the spectral properties of these sparse Hamiltonians influence the mixing time. Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.