A Quantum Algorithm for Estimating Hitting Times of Markov Chains

We present a quantum algorithm to estimate the hitting time of a reversible Markov chain faster than classically possible. To this end, we show that the hitting time is given by an expected value of the inverse of a Hermitian matrix. To obtain this expected value, our algorithm combines three important techniques developed in the literature. One such a technique is called spectral gap amplification and we use it to amplify the gap of the Hermitian matrix or reduce its condition number. We then use a new algorithm by Childs, Kothari, and Somma to implement the inverse of a matrix, and finally use methods developed in the context of quantum metrology to reduce the complexity of expected-value estimation for a given precision.