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:quant-ph/9810063 · Physical Review A

Problem of equilibration and the computation of correlation functions on a quantum computer

Barbara M. Terhal, David Peter Divincenzo

Published Jan 4, 2000• 206 citations
arXivHTMLPDF

Abstract

We address the question of how a quantum computer can be used to simulate experiments on quantum systems in thermal equilibrium. We present two approaches for the preparation of the equilibrium state on a quantum computer. For both approaches, we show that the output state of the algorithm, after long enough time, is the desired equilibrium. We present a numerical analysis of one of these approaches for small systems. We show how equilibrium (time-)correlation functions can be efficiently estimated on a quantum computer, given a preparation of the equilibrium state. The quantum algorithms that we present are hard to simulate on a classical computer. This indicates that they could provide an exponential speedup over what can be achieved with a classical device.

DOI
10.1103/physreva.61.022301

Related papers

Preparing thermal states on noiseless and noisy programmable quantum processors

Oles Shtanko, Ramis Movassagh

Nature is governed by precise physical laws, which can inspire the discovery of new computer-run simulation algorithms. Thermal states are the most ubiquitous for they are the equilibrium states of matter. Simulating thermal states of quantum matter has applications ranging from quantum machine learning to better understanding of high-temperature superconductivity and quantum chemistry. The computational complexity of this task is hopelessly hard for classical computers. The existing quantum algorithms come with caveats: most either require quantum phase estimation rendering them impractical for current noisy hardware, or are variational which face obstacles such as initialization, barren plateaus, and a general lack of provable guarantee. We provide two quantum algorithms with provable guarantees to prepare thermal states on (near-term) quantum computers that avoid these drawbacks. The first algorithm is inspired by the natural thermalization process where the ancilla qubits act as the infinite thermal bath. This algorithm can potentially run in polynomial time to sample thermal distributions of ergodic systems -- the vast class of physical systems that equilibrate in isolation with respect to local observables. The second algorithm works for any system and in general runs in exponential time. However, it requires significantly smaller quantum resources than previous such algorithms. In addition, we provide an error mitigation technique for both algorithms to fight back decoherence, which enables us to run our algorithms on the near-term quantum devices. To illustration, we simulate the thermal state of the hardcore Bose-Hubbard model on the latest generation of available quantum computers.

arXiv:2112.14688•Dec 29, 2021•74 citations

Polynomial-time classical and quantum simulation of quantum impurity models

Jiaqing Jiang, Nathan Ju, Ojas Parekh +2 more

Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating impurity models, delineating the boundary between classical and quantum tractability for this class of problems. Our main finding is that static properties of quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical algorithms that (1) estimate the ground-state energy to additive precision $δ$ in time $\mathrm{poly}(n,δ^{-1})$, and (2) estimate the partition function at inverse temperature $β$ to relative precision $δ$ in time $\mathrm{poly}(n,β,δ^{-1})$, where $n$ is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to polynomial time, while establishing for the first time rigorous polynomial-time guarantees for simulating impurity models in thermal equilibrium. On the other hand, we find that simulating dynamical properties of impurity models is hard for classical computers but easy on a quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial quantum speedups for computing static properties, but provide an avenue for quantum advantage in simulating impurity physics out of equilibrium.

quant-pharXiv:2610.02167•Oct 2, 2026•2 citations

Quantum Algorithms with Applications to Simulating Physical Systems

Anirban Ch Narayan Chowdhury

The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.

•Jan 1, 2019•0 citations

Quantum simulation of dynamical response functions of equilibrium states

Esther Cruz, Dominik S. Wild, Mari Carmen Bañuls +1 more

The computation of dynamical response functions is central to many problems in condensed matter physics. Owing to the rapid growth of quantum correlations following a quench, classical methods face significant challenges even if an efficient description of the equilibrium state is available. Quantum computing offers a promising alternative. However, existing approaches often assume access to the equilibrium state, which may be difficult to prepare in practice. In this work, we present a method that circumvents this by using energy filter techniques, enabling the computation of response functions and other dynamical properties in both microcanonical and canonical ensembles. Our approach only requires the preparation of states that have significant weight at the desired energy. The dynamical response functions are then reconstructed from measurements after quenches of varying duration by classical postprocessing. We illustrate the algorithm numerically by applying it to compute the dynamical conductivity of a free-fermion model, which unveils the energy-dependent localization properties of the model.

arXiv:2505.05411•Physical Review A•Aug 5, 2025•3 citations

Quantum mechanical evolution towards thermal equilibrium

Noah Linden, Sandu Popescu, Anthony J. Short +1 more

The circumstances under which a system reaches thermal equilibrium, and how to derive this from basic dynamical laws, has been a major question from the very beginning of thermodynamics and statistical mechanics. Despite considerable progress, it remains an open problem. Motivated by this issue, we address the more general question of equilibration. We prove, with virtually full generality, that reaching equilibrium is a universal property of quantum systems: almost any subsystem in interaction with a large enough bath will reach an equilibrium state and remain close to it for almost all times. We also prove several general results about other aspects of thermalization besides equilibration, for example, that the equilibrium state does not depend on the detailed microstate of the bath.

arXiv:0812.2385•Physical Review E•Jun 4, 2009•637 citations

A Quantum Mechanical Analog of Hamiltonian Monte Carlo

Matthew Hagan

The simulation of quantum systems is the most promising candidate for computational advantagesof large scale, fault-tolerant quantum computers over classical computers. Two fundamental prob- lems that appear when simulating quantum systems on quantum computers are the preparation of good input states to the simulation and the problem of decomposing the time evolution operator ???? into primitive gates that are available on the quantum computer. This thesis presents two new algorithms for solving these problems. The first is a time evolution algorithm that approximates the time evolution operator by combining two previously developed techniques. We bound the error of this composite approach and determine analytic conditions on when this can lead to cost savings of the overall simulation. These savings are then verified through extensive numerics. This simulation algorithm can then be used as a subroutine to prepare thermal states, which are typical input states that have a high overlap with the ground state. Our algorithm is inspired by Hamiltonian Monte Carlo, which is a classical sampling algorithm that utilizes Hamiltonian dynamics to sample from arbitrary probability distributions. We bound the cost of our quantum thermal state preparation algorithm in terms of the total amount of time needed to simulate the Hamiltonian of the system in four scenarios: single qubit systems, truncated harmonic oscillators, non-degenerate systems where one knows the eigenvalues, and non-degenerate systems where no eigenvalue knowledge is present. We numerically demonstrate that this algorithm works as guaranteed and can significantly outperform analytic worst-case bounds.

•Oct 1, 2025•0 citations
We address the question of how a quantum computer can be used to simulate experiments on quantum systems in thermal equilibrium. We present two approaches for the preparation of the equilibrium state on a quantum computer. For both approaches, we show that the output state of the algorithm, after long enough time, is the desired equilibrium. We present a numerical analysis of one of these approaches for small systems. We show how equilibrium (time-)correlation functions can be efficiently estimated on a quantum computer, given a preparation of the equilibrium state. The quantum algorithms that we present are hard to simulate on a classical computer. This indicates that they could provide an exponential speedup over what can be achieved with a classical device.
Nature is governed by precise physical laws, which can inspire the discovery of new computer-run simulation algorithms. Thermal states are the most ubiquitous for they are the equilibrium states of matter. Simulating thermal states of quantum matter has applications ranging from quantum machine learning to better understanding of high-temperature superconductivity and quantum chemistry. The computational complexity of this task is hopelessly hard for classical computers. The existing quantum algorithms come with caveats: most either require quantum phase estimation rendering them impractical for current noisy hardware, or are variational which face obstacles such as initialization, barren plateaus, and a general lack of provable guarantee. We provide two quantum algorithms with provable guarantees to prepare thermal states on (near-term) quantum computers that avoid these drawbacks. The first algorithm is inspired by the natural thermalization process where the ancilla qubits act as the infinite thermal bath. This algorithm can potentially run in polynomial time to sample thermal distributions of ergodic systems -- the vast class of physical systems that equilibrate in isolation with respect to local observables. The second algorithm works for any system and in general runs in exponential time. However, it requires significantly smaller quantum resources than previous such algorithms. In addition, we provide an error mitigation technique for both algorithms to fight back decoherence, which enables us to run our algorithms on the near-term quantum devices. To illustration, we simulate the thermal state of the hardcore Bose-Hubbard model on the latest generation of available quantum computers.
Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating impurity models, delineating the boundary between classical and quantum tractability for this class of problems. Our main finding is that static properties of quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical algorithms that (1) estimate the ground-state energy to additive precision δδδ in time poly(n,δ−1)\mathrm{poly}(n,δ^{-1})poly(n,δ−1), and (2) estimate the partition function at inverse temperature βββ to relative precision δδδ in time poly(n,β,δ−1)\mathrm{poly}(n,β,δ^{-1})poly(n,β,δ−1), where nnn is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to polynomial time, while establishing for the first time rigorous polynomial-time guarantees for simulating impurity models in thermal equilibrium. On the other hand, we find that simulating dynamical properties of impurity models is hard for classical computers but easy on a quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial quantum speedups for computing static properties, but provide an avenue for quantum advantage in simulating impurity physics out of equilibrium.
The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.
The computation of dynamical response functions is central to many problems in condensed matter physics. Owing to the rapid growth of quantum correlations following a quench, classical methods face significant challenges even if an efficient description of the equilibrium state is available. Quantum computing offers a promising alternative. However, existing approaches often assume access to the equilibrium state, which may be difficult to prepare in practice. In this work, we present a method that circumvents this by using energy filter techniques, enabling the computation of response functions and other dynamical properties in both microcanonical and canonical ensembles. Our approach only requires the preparation of states that have significant weight at the desired energy. The dynamical response functions are then reconstructed from measurements after quenches of varying duration by classical postprocessing. We illustrate the algorithm numerically by applying it to compute the dynamical conductivity of a free-fermion model, which unveils the energy-dependent localization properties of the model.
The circumstances under which a system reaches thermal equilibrium, and how to derive this from basic dynamical laws, has been a major question from the very beginning of thermodynamics and statistical mechanics. Despite considerable progress, it remains an open problem. Motivated by this issue, we address the more general question of equilibration. We prove, with virtually full generality, that reaching equilibrium is a universal property of quantum systems: almost any subsystem in interaction with a large enough bath will reach an equilibrium state and remain close to it for almost all times. We also prove several general results about other aspects of thermalization besides equilibration, for example, that the equilibrium state does not depend on the detailed microstate of the bath.
The simulation of quantum systems is the most promising candidate for computational advantagesof large scale, fault-tolerant quantum computers over classical computers. Two fundamental prob- lems that appear when simulating quantum systems on quantum computers are the preparation of good input states to the simulation and the problem of decomposing the time evolution operator ???? into primitive gates that are available on the quantum computer. This thesis presents two new algorithms for solving these problems. The first is a time evolution algorithm that approximates the time evolution operator by combining two previously developed techniques. We bound the error of this composite approach and determine analytic conditions on when this can lead to cost savings of the overall simulation. These savings are then verified through extensive numerics. This simulation algorithm can then be used as a subroutine to prepare thermal states, which are typical input states that have a high overlap with the ground state. Our algorithm is inspired by Hamiltonian Monte Carlo, which is a classical sampling algorithm that utilizes Hamiltonian dynamics to sample from arbitrary probability distributions. We bound the cost of our quantum thermal state preparation algorithm in terms of the total amount of time needed to simulate the Hamiltonian of the system in four scenarios: single qubit systems, truncated harmonic oscillators, non-degenerate systems where one knows the eigenvalues, and non-degenerate systems where no eigenvalue knowledge is present. We numerically demonstrate that this algorithm works as guaranteed and can significantly outperform analytic worst-case bounds.