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

Low-Depth Quantum Metropolis Algorithm

Jonathan E. Moussa

Published Mar 4, 2019• 3 citations
arXivHTMLPDF

Abstract

We construct a simple quantum version of the classical Metropolis algorithm to prepare and observe quantum thermal states. It induces both a quantum Markov chain that mixes the quantum thermal state and a classical Markov chain that mixes its observable measurements and enables a low-depth quantum circuit implementation. A Gaussian-filtered variant of quantum phase estimation enables thermalization times proportional to the reciprocal of temperature and the logarithm of biasing error. This matches the thermalization time of imaginary-time evolution, against which our algorithm performs favorably.

DOI
10.48550/arxiv.1903.01451

Related papers

Measurement-Based Quantum Metropolis Algorithm

Jonathan E. Moussa

We construct a measurement-based quantum extension of a rejection-free classical Metropolis algorithm to sample expectation values of observables for quantum Hamiltonians at thermal equilibrium. Observable measurements are incorporated into a thermalizing quantum Markov chain to avoid disturbing it. Our use of Hamiltonian simulation for Gaussian-filtered quantum phase estimation sets a thermalization timescale inversely proportional to temperature. The rejection-free classical algorithm artificially mimics a quantum limitation of indirect access to stationary states of the Hamiltonian.

•Mar 4, 2019•2 citations

Quantum algorithm for preparing thermal Gibbs states

Paweł Wocjan

We present a quantum algorithm for preparing thermal Gibbs states of interacting quantum systems. This algorithm is based on Grover’s technique for quantum state engineering, and its running time is dominated by the factor sqrt{D/Z}, where D and Z_beta denote the dimension of the quantum system and its partition function at inverse temperature beta, respectively. We discuss the differences between this algorithm and quantum Metropolis sampling (see the presentation by David Poulin) and outline the analysis of the errors that arise due to imperfect simulation of Hamiltonian time evolutions and limited performance of phase estimation (finite accuracy and nonzero probability of failure).

•Jan 1, 2016•2 citations

Perfect sampling for quantum Gibbs states

Daniel Stilck França

We show how to obtain perfect samples from a quantum Gibbs state on a quantum computer. To do so, we adapt one of the ``Coupling from the Past''-algorithms proposed by Propp and Wilson. The algorithm has a probabilistic run-time and produces perfect samples without any previous knowledge of the mixing time of a quantum Markov chain. To implement it, we assume we are able to perform the phase estimation algorithm for the underlying Hamiltonian and implement a quantum Markov chain such that the transition probabilities between eigenstates only depend on their energy. We provide some examples of quantum Markov chains that satisfy these conditions and analyze the expected run-time of the algorithm, which depends strongly on the degeneracy of the underlying Hamiltonian. For Hamiltonians with highly degenerate spectrum, it is efficient, as it is polylogarithmic in the dimension and linear in the mixing time. For non-degenerate spectra, its runtime is essentially the same as its classical counterpart, which is linear in the mixing time and quadratic in the dimension, up to a logarithmic factor in the dimension. We analyze the circuit depth necessary to implement it, which is proportional to the sum of the depth necessary to implement one step of the quantum Markov chain and one phase estimation. This algorithm is stable under noise in the implementation of different steps. We also briefly discuss how to adapt different ``Coupling from the Past''-algorithms to the quantum setting.

arXiv:1703.05800•Quantum Information and Computation•May 1, 2018•3 citations

Quantum Metropolis-Hastings via Penalised Qubitized Walks: Spectral Filtering and Circuit Implementation

Miguel Carrasco-Arango, Rosa M. Badia, Artur Garcia-Saez

The Metropolis-Hastings algorithm is a cornerstone of Markov Chain Monte Carlo methods, underpinning a wide range of applications in computational physics, Bayesian inference, and machine learning. Quantum variants of Metropolis-Hastings promise accelerated mixing through quantum walks, but their practical realisation remains challenging. In this work, we construct and simulate an explicit circuit level implementation of a quantum Metropolis-Hastings algorithm based on the framework introduced by Claudon \emph{et al.} (arXiv:2506.11576). We present the full quantum workflow required to prepare a stationary distribution, including a number of modifications required to make the algorithm implementable in a realistic quantum circuit model. Our results demonstrate that these modifications are essential to recover the correct stationary behaviour and highlight both the potential and current limitations of quantum Metropolis-Hastings algorithms, which are expected to become practically relevant in the fault tolerant quantum computing regime.

quant-pharXiv:2604.15179•Apr 17, 2026•0 citations

Dissipative Quantum Gibbs Sampling

Daniel Zhang, Jan Lukas Bosse, Toby S. Cubitt

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.

arXiv:2304.04526•Apr 10, 2023•7 citations

An efficient and exact noncommutative quantum Gibbs sampler

Chi-Fang Chen, Michael J. Kastoryano, András Gilyén

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 $\simβ$) 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.

arXiv:2311.09207•Nov 15, 2023•12 citations
We construct a simple quantum version of the classical Metropolis algorithm to prepare and observe quantum thermal states. It induces both a quantum Markov chain that mixes the quantum thermal state and a classical Markov chain that mixes its observable measurements and enables a low-depth quantum circuit implementation. A Gaussian-filtered variant of quantum phase estimation enables thermalization times proportional to the reciprocal of temperature and the logarithm of biasing error. This matches the thermalization time of imaginary-time evolution, against which our algorithm performs favorably.
We construct a measurement-based quantum extension of a rejection-free classical Metropolis algorithm to sample expectation values of observables for quantum Hamiltonians at thermal equilibrium. Observable measurements are incorporated into a thermalizing quantum Markov chain to avoid disturbing it. Our use of Hamiltonian simulation for Gaussian-filtered quantum phase estimation sets a thermalization timescale inversely proportional to temperature. The rejection-free classical algorithm artificially mimics a quantum limitation of indirect access to stationary states of the Hamiltonian.
We present a quantum algorithm for preparing thermal Gibbs states of interacting quantum systems. This algorithm is based on Grover’s technique for quantum state engineering, and its running time is dominated by the factor sqrt{D/Z}, where D and Z_beta denote the dimension of the quantum system and its partition function at inverse temperature beta, respectively. We discuss the differences between this algorithm and quantum Metropolis sampling (see the presentation by David Poulin) and outline the analysis of the errors that arise due to imperfect simulation of Hamiltonian time evolutions and limited performance of phase estimation (finite accuracy and nonzero probability of failure).
We show how to obtain perfect samples from a quantum Gibbs state on a quantum computer. To do so, we adapt one of the ``Coupling from the Past''-algorithms proposed by Propp and Wilson. The algorithm has a probabilistic run-time and produces perfect samples without any previous knowledge of the mixing time of a quantum Markov chain. To implement it, we assume we are able to perform the phase estimation algorithm for the underlying Hamiltonian and implement a quantum Markov chain such that the transition probabilities between eigenstates only depend on their energy. We provide some examples of quantum Markov chains that satisfy these conditions and analyze the expected run-time of the algorithm, which depends strongly on the degeneracy of the underlying Hamiltonian. For Hamiltonians with highly degenerate spectrum, it is efficient, as it is polylogarithmic in the dimension and linear in the mixing time. For non-degenerate spectra, its runtime is essentially the same as its classical counterpart, which is linear in the mixing time and quadratic in the dimension, up to a logarithmic factor in the dimension. We analyze the circuit depth necessary to implement it, which is proportional to the sum of the depth necessary to implement one step of the quantum Markov chain and one phase estimation. This algorithm is stable under noise in the implementation of different steps. We also briefly discuss how to adapt different ``Coupling from the Past''-algorithms to the quantum setting.
The Metropolis-Hastings algorithm is a cornerstone of Markov Chain Monte Carlo methods, underpinning a wide range of applications in computational physics, Bayesian inference, and machine learning. Quantum variants of Metropolis-Hastings promise accelerated mixing through quantum walks, but their practical realisation remains challenging. In this work, we construct and simulate an explicit circuit level implementation of a quantum Metropolis-Hastings algorithm based on the framework introduced by Claudon \emph{et al.} (arXiv:2506.11576). We present the full quantum workflow required to prepare a stationary distribution, including a number of modifications required to make the algorithm implementable in a realistic quantum circuit model. Our results demonstrate that these modifications are essential to recover the correct stationary behaviour and highlight both the potential and current limitations of quantum Metropolis-Hastings algorithms, which are expected to become practically relevant in the fault tolerant quantum computing regime.
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.
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 ∼β\simβ∼β) 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.