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:2609.22425

Gibbs resampling transitions and structured fast-measurement protocols

Daan Timmers, Benedikt Placke, Siddharth A. Parameswaran

quant-phSubmitted Sep 18, 2026• Announced Sep 22, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum Gibbs sampling algorithms generalize classical Markov chain Monte Carlo (cMCMC) methods, and prepare thermal states on quantum computers by implementing local dissipative evolution for a mixing time $t_{\rm mix}$. Since quantum measurements disrupt the prepared state, the rate of extracting unbiased information from the system depends on the recovery of the underlying thermal correlations. The corresponding ''Gibbs resampling'' time $t_{\rm res}$ is distinct both from $t_{\rm mix}$ and from the autocorrelation time relevant to cMCMC sampling. We study this problem in effective classical models that emulate disruptive quantum measurements of local observables on extensive subsystems. When such subsystems are chosen randomly, in models with non-local order parameters we uncover a ''resampling transition'' as a function of the fraction of sites $p$ that are measured, from $t_{\rm res}\propto \log L$ for small $p$ to $t_{\rm res}\propto {\rm poly} L$ for large $p$, in systems of linear size $L$. We argue that this transition is generically absent in systems with local order parameters, and relate this dichotomy to one between the coarsening of initial states that break 1- and 0-form symmetries under Glauber dynamics. Finally, we devise a structured fast-measurement protocol that evades slow resampling even with non-local order parameters, while leaving only a vanishing fraction of all sites unmeasured.

Related papers

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•1 citation

Thermal expectation estimation via single-trajectory Gibbs sampling with non-destructive measurements

Hongrui Chen, Jiaqing Jiang, Bowen Li +1 more

Estimating thermal expectation values of quantum many-body systems is a central challenge in physics, chemistry, and materials science. Standard quantum Gibbs sampling protocols address this task by preparing the Gibbs state from scratch after every measurement, incurring a full mixing time cost at each step. Recent advances in single-trajectory Gibbs sampling [Jiang et al. 2026] substantially reduce this overhead: once stationarity is reached, measurements can be collected along a single trajectory without re-thermalizing, provided the measurement channel preserves the Gibbs ensemble. However, explicit constructions of such non-destructive measurements have been limited primarily to observables that commute with the Hamiltonian. In this work, we fundamentally extend the single-trajectory framework to arbitrary, non-commuting observables. We provide two measurement constructions that extract measurement information without fully destroying the Gibbs state, thereby eliminating the need for full re-mixing between samples. First, we construct a measurement that satisfies exact detailed balance. This ensures the system remains in equilibrium throughout the trajectory, allowing measurement outcomes to decorrelate in an autocorrelation time that could be significantly shorter than the global mixing time. Second, assuming the underlying quantum Gibbs sampler has a positive spectral gap, we design a simplified measurement scheme that ensures the post-selected state serves as a warm start for rapid re-mixing. This approach successfully decouples the resampling cost from the global mixing time. Both measurement schemes admit efficient quantum circuit implementations, requiring only polylogarithmic Hamiltonian simulation time.

quant-pharXiv:2603.21595•Mar 24, 2026•0 citations

Mixing Time of Quantum Gibbs Sampling for Random Sparse Hamiltonians

Ramkumar, Akshar, Soleimanifar, Mehdi

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.

•Jan 1, 2025•0 citations

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

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•2 citations

Convergence monitoring of quantum Gibbs samplers

Nikolaos Louloudis, Ruben Ibarrondo, Mikel Sanz +1 more

Recent progress in fully quantum Markov chain Monte Carlo methods enables efficient Gibbs-state sampling on quantum computers [Chen et al., Nature 646, 561 (2025)]. Although rigorous worst-case bounds on mixing times remain largely inaccessible for classically intractable systems, experience from classical Monte Carlo suggests that convergence of relevant observables may nevertheless be rapid. This raises the practical question of how to diagnose convergence efficiently, i.e., with at most polynomial overhead. We propose a low-cost criterion for convergence monitoring that exploits the weak measurements inherent in quantum Gibbs samplers and their qubit-efficient variants [Ding et al., arXiv:2508.05703 (2025)]. Our approach is based on the observation that, at thermal equilibrium, the net energy flow between system and environment vanishes and energy-exchange statistics satisfy a balance condition. This condition appears in the distribution of (quasi-)frequencies extracted from the weak-measurement record and we use it to construct a Hamiltonian-agnostic stopping criterion based solely on data already generated by the sampler. We provide a statistical analysis, along with numerical and analytical studies to understand its performance, assumptions, and limitations.

quant-pharXiv:2608.02038•Aug 4, 2026•0 citations
Quantum Gibbs sampling algorithms generalize classical Markov chain Monte Carlo (cMCMC) methods, and prepare thermal states on quantum computers by implementing local dissipative evolution for a mixing time tmixt_{\rm mix}tmix​. Since quantum measurements disrupt the prepared state, the rate of extracting unbiased information from the system depends on the recovery of the underlying thermal correlations. The corresponding ''Gibbs resampling'' time trest_{\rm res}tres​ is distinct both from tmixt_{\rm mix}tmix​ and from the autocorrelation time relevant to cMCMC sampling. We study this problem in effective classical models that emulate disruptive quantum measurements of local observables on extensive subsystems. When such subsystems are chosen randomly, in models with non-local order parameters we uncover a ''resampling transition'' as a function of the fraction of sites ppp that are measured, from tres∝log⁡Lt_{\rm res}\propto \log Ltres​∝logL for small ppp to tres∝polyLt_{\rm res}\propto {\rm poly} Ltres​∝polyL for large ppp, in systems of linear size LLL. We argue that this transition is generically absent in systems with local order parameters, and relate this dichotomy to one between the coarsening of initial states that break 1- and 0-form symmetries under Glauber dynamics. Finally, we devise a structured fast-measurement protocol that evades slow resampling even with non-local order parameters, while leaving only a vanishing fraction of all sites unmeasured.
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.
Estimating thermal expectation values of quantum many-body systems is a central challenge in physics, chemistry, and materials science. Standard quantum Gibbs sampling protocols address this task by preparing the Gibbs state from scratch after every measurement, incurring a full mixing time cost at each step. Recent advances in single-trajectory Gibbs sampling [Jiang et al. 2026] substantially reduce this overhead: once stationarity is reached, measurements can be collected along a single trajectory without re-thermalizing, provided the measurement channel preserves the Gibbs ensemble. However, explicit constructions of such non-destructive measurements have been limited primarily to observables that commute with the Hamiltonian. In this work, we fundamentally extend the single-trajectory framework to arbitrary, non-commuting observables. We provide two measurement constructions that extract measurement information without fully destroying the Gibbs state, thereby eliminating the need for full re-mixing between samples. First, we construct a measurement that satisfies exact detailed balance. This ensures the system remains in equilibrium throughout the trajectory, allowing measurement outcomes to decorrelate in an autocorrelation time that could be significantly shorter than the global mixing time. Second, assuming the underlying quantum Gibbs sampler has a positive spectral gap, we design a simplified measurement scheme that ensures the post-selected state serves as a warm start for rapid re-mixing. This approach successfully decouples the resampling cost from the global mixing time. Both measurement schemes admit efficient quantum circuit implementations, requiring only polylogarithmic Hamiltonian simulation time.
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.
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.
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.
Recent progress in fully quantum Markov chain Monte Carlo methods enables efficient Gibbs-state sampling on quantum computers [Chen et al., Nature 646, 561 (2025)]. Although rigorous worst-case bounds on mixing times remain largely inaccessible for classically intractable systems, experience from classical Monte Carlo suggests that convergence of relevant observables may nevertheless be rapid. This raises the practical question of how to diagnose convergence efficiently, i.e., with at most polynomial overhead. We propose a low-cost criterion for convergence monitoring that exploits the weak measurements inherent in quantum Gibbs samplers and their qubit-efficient variants [Ding et al., arXiv:2508.05703 (2025)]. Our approach is based on the observation that, at thermal equilibrium, the net energy flow between system and environment vanishes and energy-exchange statistics satisfy a balance condition. This condition appears in the distribution of (quasi-)frequencies extracted from the weak-measurement record and we use it to construct a Hamiltonian-agnostic stopping criterion based solely on data already generated by the sampler. We provide a statistical analysis, along with numerical and analytical studies to understand its performance, assumptions, and limitations.