  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 \beta/{\cal Z}}$ and
polynomial in $\log(1/\epsilon)$, where $N$ is the Hilbert space dimension,
$\beta$ is the inverse temperature, ${\cal Z}$ is the partition function, and
$\epsilon$ is the desired precision of the output state. Our quantum algorithm
exponentially improves the dependence on $1/\epsilon$ and quadratically
improves the dependence on $\beta$ 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/(\epsilon
\Delta^{3/2})$, where $\epsilon$ is the absolute precision in the estimation
and $\Delta$ 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/\epsilon$ and $1/\Delta$ 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.

Quantum Physics