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.
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 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.
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.
Gibbs state preparation, or Gibbs sampling, is a key computational technique extensively used in physics, statistics, and other scientific fields. Recent efforts for designing fast mixing Gibbs samplers for quantum Hamiltonians have largely focused on commuting local Hamiltonians (CLHs), a non-trivial subclass of Hamiltonians which include highly entangled systems such as the Toric code and quantum double model. Most previous Gibbs samplers relied on simulating the Davies generator, which is a Lindbladian associated with the thermalization process in nature.Instead of using the Davies generator, we design a different Gibbs sampler for various CLHs by giving a reduction to classical Hamiltonians, in the sense that one can efficiently prepare the Gibbs state for some CLH H on a quantum computer as long as one can efficiently do classical Gibbs sampling for the corresponding classical Hamiltonian H ( c ) . We demonstrate that our Gibbs sampler is able to replicate state-of-the-art results as well as prepare the Gibbs state in regimes which were previously unknown, such as the low temperature region, as long as there exists fast mixing Gibbs samplers for the corresponding classical Hamiltonians. Our reductions are as follows.– If H is a 2-local qudit CLH, then H ( c ) is a 2-local qudit classical Hamiltonian.– If H is a 4-local qubit CLH on 2D lattice and there are no classical qubits, then H ( c ) is a 2-local qudit classical Hamiltonian on a planar graph. As an example, our algorithm can prepare the Gibbs state for the (defected) Toric code at any non-zero temperature in O ( n 2 p o l y ( l o g n ) ) time.– If H is a 4-local qubit CLH on 2D lattice and there are classical qubits, assuming that quantum terms are uniformly correctable, then H ( c ) is a constant-local classical Hamiltonian.