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.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, 20250 citations

Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature

Štěpán Šmíd, Richard J. Meister, Mario Berta +1 more

Recently, there have been several advancements in quantum algorithms for Gibbs sampling. These algorithms simulate the dynamics generated by an artificial Lindbladian, which is meticulously constructed to obey a detailed-balance condition with the Gibbs state of interest, ensuring it is a stationary point of the evolution, while simultaneously having efficiently implementable time steps. The overall complexity then depends primarily on the mixing time of the Lindbladian, which can vary drastically, but which has been previously bounded in the regime of high enough temperatures [Rouzé et al. arXiv:2403.12691 and arXiv:2411.04885]. In this work, we calculate the spectral gap of the Lindbladian for free fermions using third quantisation, and also prove a logarithmic bound on its mixing time by analysing corresponding covariance matrices. Then we prove a constant gap of the perturbed Lindbladian corresponding to interacting fermions up to some maximal coupling strength. This is achieved by using theorems about stability of the gap for lattice fermions. Our methods apply at any constant temperature and independently of the system size. The gap then provides an upper bound on the mixing time, and hence on the overall complexity of the quantum algorithm, proving that the purified Gibbs state of weakly interacting (quasi-)local fermionic systems of any dimension can be prepared in $\widetilde{\mathcal{O}} (n^3 \operatorname{polylog}(1/ε))$ time on $\mathcal{O}(n)$ qubits, where $n$ denotes the size of the system and $ε$ the desired accuracy. As an application, we explain how to calculate partition functions for the considered systems. We provide exact numerical simulations for small system sizes supporting the theory and also identify different suitable jump operators and filter functions for the sought-after regime of intermediate coupling in the Fermi-Hubbard model.Recently, there have been several advancements in quantum algorithms for Gibbs sampling. These algorithms simulate the dynamics generated by an artificial Lindbladian, which is meticulously constructed to obey a detailed-balance condition with the Gibbs state of interest, ensuring it is a stationary point of the evolution, while simultaneously having efficiently implementable time steps. The overall complexity then depends primarily on the mixing time of the Lindbladian, which can vary drastically, but which has been previously bounded in the regime of high enough temperatures [Rouzé et al. arXiv:2403.12691 and arXiv:2411.04885]. In this work, we calculate the spectral gap of the Lindbladian for free fermions using third quantisation, and also prove a logarithmic bound on its mixing time by analysing corresponding covariance matrices. Then we prove a constant gap of the perturbed Lindbladian corresponding to interacting fermions up to some maximal coupling strength. This is achieved by using theorems about stability of the gap for lattice fermions. Our methods apply at any constant temperature and independently of the system size. The gap then provides an upper bound on the mixing time, and hence on the overall complexity of the quantum algorithm, proving that the purified Gibbs state of weakly interacting (quasi-)local fermionic systems of any dimension can be prepared in $\widetilde{\mathcal{O}} (n^3 \operatorname{polylog}(1/ε))$ time on $\mathcal{O}(n)$ qubits, where $n$ denotes the size of the system and $ε$ the desired accuracy. As an application, we explain how to calculate partition functions for the considered systems. We provide exact numerical simulations for small system sizes supporting the theory and also identify different suitable jump operators and filter functions for the sought-after regime of intermediate coupling in the Fermi-Hubbard model.

arXiv:2501.01412Jan 2, 20250 citations

Rapid Quantum Ground State Preparation via Dissipative Dynamics

Yongtao Zhan, Zhiyan Ding, Jakob Huhn +4 more

Inspired by natural cooling processes, dissipation has become a promising approach for preparing low-energy states of quantum systems. However, the potential of dissipative protocols remains unclear beyond certain commuting Hamiltonians. This work provides significant analytical and numerical insights into the power of dissipation for preparing the ground state of noncommuting Hamiltonians. For quasi-free dissipative dynamics, including certain 1D spin systems with boundary dissipation, our results reveal a new connection between the mixing time in trace distance and the spectral properties of a non-Hermitian Hamiltonian, leading to an explicit and sharp bound on the mixing time that scales polynomially with system size. For more general spin systems, we develop a tensor network-based algorithm for constructing the Lindblad jump operator and for simulating the dynamics. Using this algorithm, we demonstrate numerically that dissipative ground state preparation protocols can achieve rapid mixing for certain 1D local Hamiltonians under bulk dissipation, with a mixing time that scales logarithmically with the system size. We then prove the rapid mixing result for certain weakly interacting spin and fermionic systems in arbitrary dimensions, extending recent results for high-temperature quantum Gibbs samplers to the zero-temperature regime. Together, these results show that dissipation can be a powerful tool for ground state preparation, with potential applications across condensed matter physics, quantum materials science, and beyond.Inspired by natural cooling processes, dissipation has become a promising approach for preparing low-energy states of quantum systems. However, the potential of dissipative protocols remains unclear beyond certain commuting Hamiltonians. This work provides significant analytical and numerical insights into the power of dissipation for preparing the ground state of noncommuting Hamiltonians. For quasi-free dissipative dynamics, including certain 1D spin systems with boundary dissipation, our results reveal a new connection between the mixing time in trace distance and the spectral properties of a non-Hermitian Hamiltonian, leading to an explicit and sharp bound on the mixing time that scales polynomially with system size. For more general spin systems, we develop a tensor network-based algorithm for constructing the Lindblad jump operator and for simulating the dynamics. Using this algorithm, we demonstrate numerically that dissipative ground state preparation protocols can achieve rapid mixing for certain 1D local Hamiltonians under bulk dissipation, with a mixing time that scales logarithmically with the system size. We then prove the rapid mixing result for certain weakly interacting spin and fermionic systems in arbitrary dimensions, extending recent results for high-temperature quantum Gibbs samplers to the zero-temperature regime. Together, these results show that dissipation can be a powerful tool for ground state preparation, with potential applications across condensed matter physics, quantum materials science, and beyond.

arXiv:2503.15827Physical Review XNov 7, 202520 citations

Quantum algorithms for Gibbs sampling and hitting-time estimation

Anirban Narayan Chowdhury, Rolando D. Somma

We present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in $\sqrt{N β/{\cal Z}}$ and polynomial in $\log(1/ε)$ , where $N$ is the Hilbert space dimension, $β$ is the inverse temperature, ${\cal Z}$ is the partition function, and $ε$ is the desired precision of the output state. Our quantum algorithm exponentially improves the dependence on $1/ε$ and quadratically improves the dependence on $β$ of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix $P$ , it runs in time almost linear in $1/(εΔ^{3/2})$ , where $ε$ is the absolute precision in the estimation and $Δ$ is a parameter determined by $P$ , and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the dependence on $1/ε$ and $1/Δ$ of the analog classical algorithm for hitting-time estimation. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.We present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in $\sqrt{N β/{\cal Z}}$ and polynomial in $\log(1/ε)$, where $N$ is the Hilbert space dimension, $β$ is the inverse temperature, ${\cal Z}$ is the partition function, and $ε$ is the desired precision of the output state. Our quantum algorithm exponentially improves the dependence on $1/ε$ and quadratically improves the dependence on $β$ of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix $P$, it runs in time almost linear in $1/(εΔ^{3/2})$, where $ε$ is the absolute precision in the estimation and $Δ$ is a parameter determined by $P$, and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the dependence on $1/ε$ and $1/Δ$ of the analog classical algorithm for hitting-time estimation. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.

arXiv:1603.02940Mar 9, 201637 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.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.09207Nov 15, 202312 citations

Polynomial-time thermalization and Gibbs sampling from system-bath couplings

Samuel Slezak, Matteo Scandi, Álvaro M. Alhambra +2 more

Many physical phenomena, including thermalization in open quantum systems and quantum Gibbs sampling, are modeled by Lindbladians approximating a system weakly coupled to a bath. Understanding the convergence speed of these Lindbladians to their steady states is crucial for bounding algorithmic runtimes and thermalization timescales. We study two such families of processes: one characterizing a repeated-interaction Gibbs sampling algorithm, and another modeling open many-body quantum thermalization. We prove that both converge in polynomial time for several non-commuting systems, including high-temperature local lattices, weakly interacting fermions, and 1D spin chains. These results demonstrate that simple dissipative quantum algorithms can prepare complex Gibbs states and that Lindblad dynamics accurately capture thermal relaxation. Our proofs rely on a novel technical result that extrapolates spectral gap lower bounds from quasi-local Lindbladians to the non-local generators governing these dynamics.Many physical phenomena, including thermalization in open quantum systems and quantum Gibbs sampling, are modeled by Lindbladians approximating a system weakly coupled to a bath. Understanding the convergence speed of these Lindbladians to their steady states is crucial for bounding algorithmic runtimes and thermalization timescales. We study two such families of processes: one characterizing a repeated-interaction Gibbs sampling algorithm, and another modeling open many-body quantum thermalization. We prove that both converge in polynomial time for several non-commuting systems, including high-temperature local lattices, weakly interacting fermions, and 1D spin chains. These results demonstrate that simple dissipative quantum algorithms can prepare complex Gibbs states and that Lindblad dynamics accurately capture thermal relaxation. Our proofs rely on a novel technical result that extrapolates spectral gap lower bounds from quasi-local Lindbladians to the non-local generators governing these dynamics.

quant-pharXiv:2601.16154Jan 23, 20260 citations

\widetilde{\mathcal{O}} (n^3 \operatorname{polylog}(1/ε))

time on

\mathcal{O}(n)

qubits, where

n

denotes the size of the system and

ε

the desired accuracy. As an application, we explain how to calculate partition functions for the considered systems. We provide exact numerical simulations for small system sizes supporting the theory and also identify different suitable jump operators and filter functions for the sought-after regime of intermediate coupling in the Fermi-Hubbard model.

We present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in

\sqrt{N β/{\cal Z}}

and polynomial in

\log(1/ε)

, where

N

is the Hilbert space dimension,

β

is the inverse temperature,

{\cal Z}

is the partition function, and

ε

is the desired precision of the output state. Our quantum algorithm exponentially improves the dependence on

1/ε

and quadratically improves the dependence on

β

of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix

P

, it runs in time almost linear in

1/(εΔ^{3/2})

, where

ε

is the absolute precision in the estimation and

Δ

is a parameter determined by

P

, and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the dependence on

1/ε

and

1/Δ

of the analog classical algorithm for hitting-time estimation. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.

β

, 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.