We revisit the Markov Entropy Decomposition, a classical convex relaxation algorithm introduced by Poulin and Hastings to approximate the free energy in quantum spin lattices. We identify a sufficient condition for its convergence, namely the decay of the effective interaction. The effective interaction, also known as Hamiltonians of mean force, is a widely established correlation measure, and we show our decay condition in 1D at any temperature as well as in the high-temperature regime under a certain commutativity condition on the Hamiltonian building on existing results. This yields polynomial and quasi-polynomial time approximation algorithms in these settings, respectively. Furthermore, the decay of the effective interaction implies the decay of the conditional mutual information for the Gibbs state of the system. We then use this fact to devise a rounding scheme that maps the solution of the convex relaxation to a global state and show that the scheme can be efficiently implemented on a quantum computer, thus proving efficiency of quantum Gibbs sampling under our assumption of decay of the effective interaction.
We revisit the Markov Entropy Decomposition, a classical convex relaxation algorithm introduced by Poulin and Hastings to approximate the free energy in quantum spin lattices. We identify a sufficient condition for its convergence, namely the decay of the effective interaction. The effective interaction, also known as Hamiltonians of mean force, is a widely established correlation measure, and we show our decay condition in 1D at any temperature as well as in the high-temperature regime under a certain commutativity condition on the Hamiltonian building on existing results. This yields polynomial and quasi-polynomial time approximation algorithms in these settings, respectively. Furthermore, the decay of the effective interaction implies the decay of the conditional mutual information for the Gibbs state of the system. We then use this fact to devise a rounding scheme that maps the solution of the convex relaxation to a global state and show that the scheme can be efficiently implemented on a quantum computer, thus proving efficiency of quantum Gibbs sampling under our assumption of decay of the effective interaction.
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.
We prove that the quantum Gibbs states of spin systems above a certain threshold temperature are approximate quantum Markov networks, meaning that the conditional mutual information decays rapidly with distance. We demonstrate the exponential decay for short-ranged interacting systems and power-law decay for long-ranged interacting systems. Consequently, we establish the efficiency of quantum Gibbs sampling algorithms, a strong version of the area law, the quasilocality of effective Hamiltonians on subsystems, a clustering theorem for mutual information, and a polynomial-time algorithm for classical Gibbs state simulations.
We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.
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 Markov property entails the conditional independence structure inherent in Gibbs distributions for general classical Hamiltonians, a feature that plays a crucial role in inference, mixing time analysis, and algorithm design. However, much less is known about quantum Gibbs states. In this work, we show that for any Hamiltonian with a bounded interaction degree, the quantum Gibbs state is locally Markov at arbitrary temperature, meaning there exists a quasi-local recovery map for every local region. Notably, this recovery map is obtained by applying a detailed-balanced Lindbladian with jumps acting on the region. Consequently, we prove that (i) the conditional mutual information (CMI) for a shielded small region decays exponentially with the shielding distance, and (ii) under the assumption of uniform clustering of correlations, Gibbs states of general non-commuting Hamiltonians on D-dimensional lattices can be prepared by a quantum circuit of depth eO(logD(n/ε)), which can be further reduced assuming certain local gap condition. Our proofs introduce a regularization scheme for imaginary-time-evolved operators at arbitrarily low temperatures and reveal a connection between the Dirichlet form, a dynamic quantity, and the commutator in the KMS inner product, a static quantity. We believe these tools pave the way for tackling further challenges in quantum thermodynamics and mixing times, particularly in low-temperature regimes.
We establish improved locally Markovian properties of quantum Gibbs states at every fixed positive temperature. For finite-range interactions of bounded interaction degree, the conditional mutual information (CMI) decays exponentially with separation, with a prefactor exponential in the boundary size of only one of the two regions and independent of the size of the other region and the total system. This improves the exponential volume dependence of the local Markov bounds established by Chen and Rouzé \cite{Chen2025}. For exponentially and stretched-exponentially decaying interactions, we obtain stretched-exponential CMI decay with a boundary-dependent prefactor. For power-law interactions, we prove inverse-logarithmic or algebraic decay with polynomial region-size dependence. Our proof is static, in contrast to the dynamical approach of Chen and Rouzé. We compare the Gibbs state with a product state obtained by removing boundary interactions, reducing the CMI bound to a relative-entropy loss that we control using locality estimates.