Southwest Quantum Information and Technology

Quantum algorithms for Gibbs sampling and hitting-time estimation

Presenting Author: Anirban Narayan Chowdhury, Center for Quantum Information and Control
Contributing Author(s): 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 that is polylogarithmic in the precision parameter, exponentially improving the precision dependence over known quantum algorithms. It also polynomially improves dependence on parameters such as system size and inverse temperature. The second algorithm estimates the hitting time of a classical Markov chain. For a sparse stochastic matrix, it provides quadratic improvement in complexity over a natural classical algorithm to estimate the hitting time. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.

Read this article online: https://arxiv.org/abs/1603.02940

(Session 5 : Thursday from 5:00pm - 7:00pm)