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.

AI Summary

The paper asks how quickly a prepared thermal state can recover after extensive disruptive measurements, rather than how long preparation from an arbitrary state takes. It studies a classical proxy: independently reset spins with probability $p$ to infinite-temperature configurations, then evolve with local Glauber dynamics. The models are the 2D Ising ferromagnet, 3D XY ferromagnet, and 3D $\mathbb{Z}_2$ lattice gauge theory. Numerics and heuristic coarsening arguments indicate rapid recovery, $t_{\rm res}=O(\log L)$, for every fixed $p<1$ in the ferromagnets, with fidelity to the initial orientation approaching unity. The proposed mechanism is that residual local magnetization confines defects to small regions. In the gauge theory, simulations instead locate a transition at $p_c\approx0.226$, above which recovery scales approximately as $L^2$ and logical fidelity falls. Mapping recovery to toric-code decoding gives an upper bound $p_c\lesssim0.466$ for faithful recovery under any decoder. A structured protocol measures boxes separated by unmeasured collars; defect-confinement arguments predict rapid recovery while allowing the measured fraction to approach one as box size increases. These conclusions concern classical models, not quantum Gibbs samplers: entanglement-mediated measurement effects are omitted. The logarithmic scaling is heuristic, and numerics do not exclude other polylogarithmic behavior. Recovery times exclude runs trapped in metastable states, although fidelity counts these as failures. Continuous-spin recovery uses a magnetization threshold rather than exact restoration. Generalization to all local-order-parameter phases is conjectural; point defects lack a general confinement argument, and finite-temperature collar estimates are heuristic.

No sign of AI-generated textStrong assumptionsOverclaims

Central claim may not hold: The reported quadratic slow-resampling times are conditioned on avoiding frozen trajectories; the unconditional mean is infinite at strictly zero temperature when freezing has positive probability, and can have a larger polynomial scaling at finite temperature. The structured protocol establishes logarithmic resampling for fixed box size and an arbitrarily small fixed unmeasured fraction, but does not establish the joint limit of logarithmic resampling and an unmeasured fraction vanishing with system size. The finite-temperature structured protocol's claim of exactly unit logical fidelity is unsupported because its nonzero collar-crossing probabilities are not converted into a system-wide logical-failure bound.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

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

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•4 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•12 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

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: Theory, Algorithms, and Numerical Analysis

Bence Temesi

Over the past decades, the problem of classical Gibbs sampling has led to one of the most powerful algorithmic families of the computer age: the Markov Chain Monte Carlo algorithms. Recent theoretical advances in quantum Gibbs sampling have, understandably, sparked considerable excitement. A recent breakthrough provided the first Lindbladians that provably drive a general quantum system to its Gibbs state, efficiently up to the mixing time. In this thesis, we bridge the gap between theory and implementation, with both analytical and numerical contributions. We work out every detail -- from transition rate choices, through quadrature, Trotter, and generator-splitting errors, to quantum circuits that could run on early fault-tolerant quantum computers. Using our fast Krylov-based Lindblad simulators and analysers, we numerically confirm existing theoretical Gibbs sampling results, cross-check our theoretical contributions, and do extrapolatory simulations to understand how the structure of these Gibbs samplers affects convergence rates. Our open-source framework, QuantumFurnace.jl, is built to work hand in hand with theory, providing the community with a tool to further advance quantum Gibbs sampling.

•Jan 1, 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.
The paper asks how quickly a prepared thermal state can recover after extensive disruptive measurements, rather than how long preparation from an arbitrary state takes. It studies a classical proxy: independently reset spins with probability ppp to infinite-temperature configurations, then evolve with local Glauber dynamics. The models are the 2D Ising ferromagnet, 3D XY ferromagnet, and 3D Z2\mathbb{Z}_2Z2​ lattice gauge theory.
Numerics and heuristic coarsening arguments indicate rapid recovery, tres=O(log⁡L)t_{\rm res}=O(\log L)tres​=O(logL), for every fixed p<1p<1p<1 in the ferromagnets, with fidelity to the initial orientation approaching unity. The proposed mechanism is that residual local magnetization confines defects to small regions. In the gauge theory, simulations instead locate a transition at pc≈0.226p_c\approx0.226pc​≈0.226, above which recovery scales approximately as L2L^2L2 and logical fidelity falls. Mapping recovery to toric-code decoding gives an upper bound pc≲0.466p_c\lesssim0.466pc​≲0.466 for faithful recovery under any decoder. A structured protocol measures boxes separated by unmeasured collars; defect-confinement arguments predict rapid recovery while allowing the measured fraction to approach one as box size increases.
These conclusions concern classical models, not quantum Gibbs samplers: entanglement-mediated measurement effects are omitted. The logarithmic scaling is heuristic, and numerics do not exclude other polylogarithmic behavior. Recovery times exclude runs trapped in metastable states, although fidelity counts these as failures. Continuous-spin recovery uses a magnetization threshold rather than exact restoration. Generalization to all local-order-parameter phases is conjectural; point defects lack a general confinement argument, and finite-temperature collar estimates are heuristic.
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.
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 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.
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.
Over the past decades, the problem of classical Gibbs sampling has led to one of the most powerful algorithmic families of the computer age: the Markov Chain Monte Carlo algorithms. Recent theoretical advances in quantum Gibbs sampling have, understandably, sparked considerable excitement. A recent breakthrough provided the first Lindbladians that provably drive a general quantum system to its Gibbs state, efficiently up to the mixing time. In this thesis, we bridge the gap between theory and implementation, with both analytical and numerical contributions. We work out every detail -- from transition rate choices, through quadrature, Trotter, and generator-splitting errors, to quantum circuits that could run on early fault-tolerant quantum computers. Using our fast Krylov-based Lindblad simulators and analysers, we numerically confirm existing theoretical Gibbs sampling results, cross-check our theoretical contributions, and do extrapolatory simulations to understand how the structure of these Gibbs samplers affects convergence rates. Our open-source framework, QuantumFurnace.jl, is built to work hand in hand with theory, providing the community with a tool to further advance quantum Gibbs sampling.