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

A rapidly mixing quantum Swendsen–Wang sampler and a locality lower bound for Gibbs sampling

Soo-Jong Rey

Published Jul 23, 2026• 0 citations
Publisher

Abstract

I study the mixing time of quantum Gibbs samplers (Davies / Chen– Kastoryano–Gilyén generators) at low temperature. I prove a locality lower bound: any local, KMS–detailed-balanced sampler whose target has an order- parameter bottleneck has an Arrhenius-small spectral gap, by a quantum Cheeger argument, and hence mixing time eΩ(β∆F). The bound is a quantum Cheeger argument and holds for every KMS–detailed-balanced sampler. The coherence cannot lift an order-parameter bottleneck, thereby the obstruction survives quantization. It is not, however, intrinsic to the target. I give a 3-local, detailed-balanced Lindbladian on an enlarged spin+bond register whose spin marginal realizes the Fortuin–Kasteleyn cluster update and which, for commuting ferromagnets, has an inverse-polynomial gap at every temperature and prepares σ in poly(n)log(1/ε) gates. This gives an unconditional separation from the local-reversible class in which locality (not coherence) is the operative resource. As a conjecture, I isolate the genuinely quantum question about cluster updates for noncommuting targets, where no nonnegative bond representation exists and the cluster must be grown coherently.

DOI
10.5281/zenodo.21501714

Related papers

Spectral Analysis Beyond the Spectral Gap: Rapid Mixing of Quantum Gibbs Samplers in One Dimension

Hongrui Chen, Zhiyan Ding

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(\log^4(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))$.

quant-pharXiv:2610.05848•Oct 6, 2026•0 citations

Rapid mixing of quantum spin chains at any finite temperature

Leeseok Kim

We prove that a quasi-local quantum Gibbs sampler rapidly mixes to the Gibbs state of any 1D finite-range Hamiltonian at all finite temperatures in $\mathcal{O}\left(\log (n/\varepsilon)\right)$ time. Each update traces out a contiguous block of constant length and reconstructs it using the Petz recovery map, following early proposals for quantum heat-bath Gibbs samplers by Kastoryano and Brandão~\cite{kastoryano2016quantum}. Our proof directly bounds the distance between the updated state and the target Gibbs state using quantum Wasserstein distance of order $1$. We further provide $\mathcal{O}(\text{polylog}(n/\varepsilon))$ depth of quantum circuits to prepare these Gibbs states. We hope these techniques will facilitate the analysis and design of other Gibbs samplers.

quant-pharXiv:2610.01190•Oct 2, 2026•0 citations

Efficient Quantum Gibbs Samplers with Kubo–Martin–Schwinger Detailed Balance Condition

Zhiyan Ding, Bowen Li, Lin Lin

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.

arXiv:2404.05998•Communications in Mathematical Physics•Feb 27, 2025•35 citations

Slow Mixing of Quantum Gibbs Samplers

David Gamarnik, Bobak T. Kiani, Alexander Zlokapa

Preparing thermal (Gibbs) states is a common task in physics and computer science. Recent algorithms mimic cooling via system-bath coupling, where the cost is determined by mixing time, akin to classical Metropolis-like algorithms. However, few methods exist to demonstrate slow mixing in quantum systems, unlike the well-established classical tools for systems like the Ising model and constraint satisfaction problems. We present a quantum generalization of these tools through a generic bottleneck lemma that implies slow mixing in quantum systems. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles and quantified either through Bohr spectrum jumps or operator locality. Using our bottleneck lemma, we establish unconditional lower bounds on the mixing times of Gibbs samplers for several families of Hamiltonians at low temperatures. For classical Hamiltonians with mixing time lower bounds $T_\mathrm{mix} = \exp[Ω(n^α)]$, we prove that quantum Gibbs samplers also have $T_\mathrm{mix} = \exp[Ω(n^α)]$. This applies to models like random $K$-SAT instances and spin glasses. For stabilizer Hamiltonians, we provide a concise proof of exponential lower bounds $T_\mathrm{mix} = \exp[Ω(n)]$ on mixing times of good $n$-qubit stabilizer codes at low constant temperature. Finally, we consider constant-degree classical Hamiltonians and show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques. We show generic results for models with linear free energy barriers, and we demonstrate that our techniques extend to models with sublinear free energy barriers by proving $T_\mathrm{mix} = \exp[n^{1/2-o(1)}]$ for the ferromagnetic 2D transverse field Ising model.

arXiv:2411.04300•Nov 6, 2024•1 citation

Rapid mixing of Gibbs samplers via quantum Dobrushin--Shlosman conditions

Cambyse Rouzé, Daniel Stilck França

Classical Dobrushin--Shlosman theory uses heat-bath block updates to identify sharp temperature thresholds for establishing the rapid mixing of Gibbs samplers. In particular, these mixing guarantees often hold even when stricter single-site conditions fail. We extend this approach to noncommuting quantum lattice systems through a quantum Dobrushin--Shlosman condition for finite-block dynamics, which we call smoothed heat-bath dynamics. We establish this condition in two regimes. For finite-range quantum spin chains at every fixed finite temperature, we prove logarithmic trace-norm mixing in system size, with normalized bounds uniform in on-site fields and single exponential in inverse temperature. We also prove stability under small local perturbations of interacting, possibly noncommuting reference Hamiltonians on graphs of polynomial volume growth. For classical references with bounded local interactions, uniform strong spatial mixing implies our quantum condition. With bounded local terms and fixed physical, geometric and block parameters, the resulting samplers prepare Gibbs states to trace-norm error $\varepsilon$ using $N\operatorname{polylog}(N/\varepsilon)$ gates and classical operations. Our block updates combine a local Gibbs reset with quantum belief propagation to incorporate interactions across the block boundary, yielding exactly Gibbs-preserving, KMS-reversible channels. Two independently tunable parameters control contraction: an internal evolution time suppresses the influence of sites inside a block, while the block size allows interior contraction to dominate boundary influence. This finite-time relaxation has no counterpart in a classical heat-bath block update.

quant-pharXiv:2610.03578•Oct 5, 2026•0 citations

Accelerating quantum Gibbs sampling without quantum walks

Jiaqi Leng, Jiaqing Jiang, Lin Lin

Szegedy's quantum walk quadratically accelerates reversible classical Markov chains, but extending this mechanism to efficiently implementable quantum Gibbs samplers has remained challenging beyond special classes. 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 and warm-start assumptions. The framework applies to several efficiently implementable Gibbs samplers beyond the Davies setting. Moreover, we construct noncommuting Hamiltonians with efficiently preparable warm starts whose refinement under quantum Gibbs samplers requires exponential time. For these models, our algorithm achieves an end-to-end quantum speedup over the worst-case mixing scale.

quant-pharXiv:2604.22996•Apr 28, 2026•0 citations
I study the mixing time of quantum Gibbs samplers (Davies / Chen– Kastoryano–Gilyén generators) at low temperature. I prove a locality lower bound: any local, KMS–detailed-balanced sampler whose target has an order- parameter bottleneck has an Arrhenius-small spectral gap, by a quantum Cheeger argument, and hence mixing time eΩ(β∆F). The bound is a quantum Cheeger argument and holds for every KMS–detailed-balanced sampler. The coherence cannot lift an order-parameter bottleneck, thereby the obstruction survives quantization. It is not, however, intrinsic to the target. I give a 3-local, detailed-balanced Lindbladian on an enlarged spin+bond register whose spin marginal realizes the Fortuin–Kasteleyn cluster update and which, for commuting ferromagnets, has an inverse-polynomial gap at every temperature and prepares σ in poly(n)log(1/ε) gates. This gives an unconditional separation from the local-reversible class in which locality (not coherence) is the operative resource. As a conjecture, I isolate the genuinely quantum question about cluster updates for noncommuting targets, where no nonnegative bond representation exists and the cluster must be grown coherently.
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 nnn 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(log⁡4(n)+log⁡(1/ε))O(\log^4(n)+\log(1/ε))O(log4(n)+log(1/ε)). This improves the previous O(n+log⁡(1/ε))O(n+\log(1/ε))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))Ω(\log^{-4}(n))Ω(log−4(n)).
We prove that a quasi-local quantum Gibbs sampler rapidly mixes to the Gibbs state of any 1D finite-range Hamiltonian at all finite temperatures in O(log⁡(n/ε))\mathcal{O}\left(\log (n/\varepsilon)\right)O(log(n/ε)) time. Each update traces out a contiguous block of constant length and reconstructs it using the Petz recovery map, following early proposals for quantum heat-bath Gibbs samplers by Kastoryano and Brandão~\cite{kastoryano2016quantum}. Our proof directly bounds the distance between the updated state and the target Gibbs state using quantum Wasserstein distance of order 111. We further provide O(polylog(n/ε))\mathcal{O}(\text{polylog}(n/\varepsilon))O(polylog(n/ε)) depth of quantum circuits to prepare these Gibbs states. We hope these techniques will facilitate the analysis and design of other Gibbs samplers.
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.
Preparing thermal (Gibbs) states is a common task in physics and computer science. Recent algorithms mimic cooling via system-bath coupling, where the cost is determined by mixing time, akin to classical Metropolis-like algorithms. However, few methods exist to demonstrate slow mixing in quantum systems, unlike the well-established classical tools for systems like the Ising model and constraint satisfaction problems. We present a quantum generalization of these tools through a generic bottleneck lemma that implies slow mixing in quantum systems. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles and quantified either through Bohr spectrum jumps or operator locality. Using our bottleneck lemma, we establish unconditional lower bounds on the mixing times of Gibbs samplers for several families of Hamiltonians at low temperatures. For classical Hamiltonians with mixing time lower bounds Tmix=exp⁡[Ω(nα)]T_\mathrm{mix} = \exp[Ω(n^α)]Tmix​=exp[Ω(nα)], we prove that quantum Gibbs samplers also have Tmix=exp⁡[Ω(nα)]T_\mathrm{mix} = \exp[Ω(n^α)]Tmix​=exp[Ω(nα)]. This applies to models like random KKK-SAT instances and spin glasses. For stabilizer Hamiltonians, we provide a concise proof of exponential lower bounds Tmix=exp⁡[Ω(n)]T_\mathrm{mix} = \exp[Ω(n)]Tmix​=exp[Ω(n)] on mixing times of good nnn-qubit stabilizer codes at low constant temperature. Finally, we consider constant-degree classical Hamiltonians and show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques. We show generic results for models with linear free energy barriers, and we demonstrate that our techniques extend to models with sublinear free energy barriers by proving Tmix=exp⁡[n1/2−o(1)]T_\mathrm{mix} = \exp[n^{1/2-o(1)}]Tmix​=exp[n1/2−o(1)] for the ferromagnetic 2D transverse field Ising model.
Classical Dobrushin--Shlosman theory uses heat-bath block updates to identify sharp temperature thresholds for establishing the rapid mixing of Gibbs samplers. In particular, these mixing guarantees often hold even when stricter single-site conditions fail. We extend this approach to noncommuting quantum lattice systems through a quantum Dobrushin--Shlosman condition for finite-block dynamics, which we call smoothed heat-bath dynamics. We establish this condition in two regimes. For finite-range quantum spin chains at every fixed finite temperature, we prove logarithmic trace-norm mixing in system size, with normalized bounds uniform in on-site fields and single exponential in inverse temperature. We also prove stability under small local perturbations of interacting, possibly noncommuting reference Hamiltonians on graphs of polynomial volume growth. For classical references with bounded local interactions, uniform strong spatial mixing implies our quantum condition. With bounded local terms and fixed physical, geometric and block parameters, the resulting samplers prepare Gibbs states to trace-norm error ε\varepsilonε using Npolylog⁡(N/ε)N\operatorname{polylog}(N/\varepsilon)Npolylog(N/ε) gates and classical operations. Our block updates combine a local Gibbs reset with quantum belief propagation to incorporate interactions across the block boundary, yielding exactly Gibbs-preserving, KMS-reversible channels. Two independently tunable parameters control contraction: an internal evolution time suppresses the influence of sites inside a block, while the block size allows interior contraction to dominate boundary influence. This finite-time relaxation has no counterpart in a classical heat-bath block update.
Szegedy's quantum walk quadratically accelerates reversible classical Markov chains, but extending this mechanism to efficiently implementable quantum Gibbs samplers has remained challenging beyond special classes. 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 and warm-start assumptions. The framework applies to several efficiently implementable Gibbs samplers beyond the Davies setting. Moreover, we construct noncommuting Hamiltonians with efficiently preparable warm starts whose refinement under quantum Gibbs samplers requires exponential time. For these models, our algorithm achieves an end-to-end quantum speedup over the worst-case mixing scale.