Szegedy's quantum walk gives a generic quadratic speedup for reversible classical Markov chains, but extending this mechanism to quantum Gibbs sampling has remained challenging beyond special cases. We present a walk-free quantum algorithm for preparing purified Gibbs states with a quadratic improvement in spectral-gap dependence for a broad class of quantum Gibbs samplers that satisfy exact Kubo-Martin-Schwinger detailed balance. Our main structural result is an explicit factorization of the corresponding parent Hamiltonian into noncommutative first-order operators. This turns purified Gibbs-state preparation into a singular-value filtering problem and enables a quantum singular value transformation algorithm with quadratically improved gap dependence under standard coherent-access assumptions. The framework applies to several efficiently implementable Gibbs samplers beyond the Davies setting. We also introduce an auxiliary dissipative dynamics based on the same factorization, which can be used to generate warm starts in the doubled Hilbert space in metastable regimes.
Szegedy's quantum walk gives a generic quadratic speedup for reversible classical Markov chains, but extending this mechanism to quantum Gibbs sampling has remained challenging beyond special cases. We present a walk-free quantum algorithm for preparing purified Gibbs states with a quadratic improvement in spectral-gap dependence for a broad class of quantum Gibbs samplers that satisfy exact Kubo-Martin-Schwinger detailed balance. Our main structural result is an explicit factorization of the corresponding parent Hamiltonian into noncommutative first-order operators. This turns purified Gibbs-state preparation into a singular-value filtering problem and enables a quantum singular value transformation algorithm with quadratically improved gap dependence under standard coherent-access assumptions. The framework applies to several efficiently implementable Gibbs samplers beyond the Davies setting. We also introduce an auxiliary dissipative dynamics based on the same factorization, which can be used to generate warm starts in the doubled Hilbert space in metastable regimes.
Preparing thermal and ground states is an essential quantum algorithmic task for quantum simulation. In this work, we construct the first efficiently implementable and exactly detailed-balanced Lindbladian for Gibbs states of arbitrary noncommutative Hamiltonians. Our construction can also be regarded as a continuous-time quantum analog of the Metropolis-Hastings algorithm. To prepare the quantum Gibbs state, our algorithm invokes Hamiltonian simulation for a time proportional to the mixing time and the inverse temperature β, up to polylogarithmic factors. Moreover, the gate complexity reduces significantly for lattice Hamiltonians as the corresponding Lindblad operators are (quasi-) local (with radius ∼β) and only depend on local Hamiltonian patches. Meanwhile, purifying our Lindbladians yields a temperature-dependent family of frustration-free "parent Hamiltonians", prescribing an adiabatic path for the canonical purified Gibbs state (i.e., the Thermal Field Double state). These favorable features suggest that our construction serves as a quantum algorithmic counterpart to classical Markov chain Monte Carlo sampling.
Gibbs state preparation is an important subroutine in quantum computing. In this work we use the detectability lemma to improve Gibbs state preparation. Specifically, we design new Gibbs state preparation methods that do not rely on simulating Lindbladian evolution, thus avoiding the overhead from it. For local Lindbladians consisting of M terms, this approach reduces the cost by a factor of O(M). We also combine the detectability lemma operator and quantum singular value transformation to implement ground state projection operators of frustration-free Hamiltonians, resulting in a quadratic speedup in the spectral gap dependence. Applying this method to Lindbladians for the Gibbs state of local commuting Hamiltonians, we achieve quadratically better dependence on the Lindbladian spectral gap.
We prove rapid mixing of a quantum Gibbs sampler for general one-dimensional non-commuting local spin systems at every fixed positive temperature. In particular, for a system of n sites, we show that the Kubo--Martin--Schwinger (KMS) detailed-balanced Gibbs sampler of~\cite{CKG2023} converges from any initial state to trace-norm error ε in time O(log4(n)+log(1/ε)). This improves the previous O(n+log(1/ε)) bound and establishes rapid mixing beyond high-temperature and weak-interaction regimes. Our proof explains why the slowest decay rate, captured by the spectral gap, can substantially underestimate the speed of equilibration. The key insight is that a state far from equilibrium must have a substantial component outside the span of low-weight Pauli operators, where stronger dissipation estimates apply. This yields two stages of relaxation: a double-exponential convergence from a bad initial state, followed by exponential convergence near equilibrium. We turn this mechanism into a framework for proving rapid mixing through spectral analysis beyond the gap. Our decay estimate is equivalent to exponential convergence in sandwiched Rényi-2 divergence. Together with the spectral gap, it also implies a modified logarithmic Sobolev inequality with rate Ω(log−4(n)).
Abstract Lindblad dynamics and other open-system dynamics provide a promising path towards efficient Gibbs sampling on quantum computers. In these proposals, the Lindbladian is obtained via an algorithmic construction akin to designing an artificial thermostat in classical Monte Carlo or molecular dynamics methods, rather than being treated as an approximation to weakly coupled system-bath unitary dynamics. Recently, Chen, Kastoryano, and Gilyén (arXiv:2311.09207) introduced the first efficiently implementable Lindbladian satisfying the Kubo–Martin–Schwinger (KMS) detailed balance condition, which ensures that the Gibbs state is a fixed point of the dynamics and is applicable to non-commuting Hamiltonians. This Gibbs sampler uses a continuously parameterized set of jump operators, and the energy resolution required for implementing each jump operator depends only logarithmically on the precision and the mixing time. In this work, we build upon the structural characterization of KMS detailed balanced Lindbladians by Fagnola and Umanità, and develop a family of efficient quantum Gibbs samplers using a finite set of jump operators (the number can be as few as one), akin to the classical Markov chain-based sampling algorithm. Compared to the existing works, our quantum Gibbs samplers have a comparable quantum simulation cost but with greater design flexibility and a much simpler implementation and error analysis. Moreover, it encompasses the construction of Chen, Kastoryano, and Gilyén as a special instance.
We consider the dynamic Schrödinger bridge problem on a finite state space and exploit its Markov structure to decompose the problem into an endpoint coupling and a collection of conditional Markov bridges. To sample from the conditional bridges, we develop a quantum Gibbs sampler based on quantum walks on the bridge path space. Under uniformly positive transition probabilities, we derive a spectral-gap bound and provide an explicit procedure for preparing the initial state. Compared with the update bounds of the corresponding classical Gibbs sampler, our quantum walk-query complexity improves the dependence on the time horizon T from quadratic to linear. For the endpoint coupling, we adapt a quantum box-constrained Newton method to compute the Schrödinger potentials, improving the matrix-scaling complexity, at fixed accuracy, from quadratic to N3/2 in the state-space size N. Finally, we show that exponential reweighting extends both the Schrödinger bridge formulation and the Gibbs spectral-gap estimate to models with additive running costs.
Preparing Gibbs states through dissipative dynamics requires controlling convergence for the chosen Hamiltonian H and coupling operators. However, efficient implementation requires convergence guarantees from the spectral gap of the generator of the dynamics, which remains a crucial challenge. Recent results address the challenge by restricting the dynamics with structural assumptions about the Hamiltonian and its interactions. For the Chen-Kastoryano-Gilyen (CKG) construction and arbitrary finite-dimensional Hamiltonians, we prove an explicit comparison that converts a spectral gap estimate for the infinite-temperature generator into a lower bound on the spectral gap of the CKG quantum Gibbs sampler at every finite positive inverse temperature β. It allows a single spectral gap estimate at infinite temperature to certify convergence across Hamiltonians and temperatures. Such an estimate is often known from a classical spectral gap estimate, such as the classical random walk spectral gap. For Hodge Laplacians of simplicial complexes as Hamiltonians, we construct coupling operators whose generator at infinite temperature has the same spectral gap as a classical simplicial down-up walk. A positive spectral gap of the walk and bounded spectral width W=λmax(H)−λmin(H) give a generator spectral gap independent of the number of simplices at every fixed temperature. We then establish conditions under which the sampler approximately prepares zero-energy (harmonic) states in polynomial evolution time. This provides a conditional convergence guarantee for the state preparation in the thermal approach to quantum topological data analysis.