  Markov chain Monte Carlo algorithms have important applications in counting
problems and in machine learning problems, settings that involve estimating
quantities that are difficult to compute exactly. How much can quantum
computers speed up classical Markov chain algorithms? In this work we consider
the problem of speeding up simulated annealing algorithms, where the stationary
distributions of the Markov chains are Gibbs distributions at temperatures
specified according to an annealing schedule.
  We construct a quantum algorithm that both adaptively constructs an annealing
schedule and quantum samples at each temperature. Our adaptive annealing
schedule roughly matches the length of the best classical adaptive annealing
schedules and improves on nonadaptive temperature schedules by roughly a
quadratic factor. Our dependence on the Markov chain gap matches other quantum
algorithms and is quadratically better than what classical Markov chains
achieve. Our algorithm is the first to combine both of these quadratic
improvements. Like other quantum walk algorithms, it also improves on classical
algorithms by producing "qsamples" instead of classical samples. This means
preparing quantum states whose amplitudes are the square roots of the target
probability distribution.
  In constructing the annealing schedule we make use of amplitude estimation,
and we introduce a method for making amplitude estimation nondestructive at
almost no additional cost, a result that may have independent interest. Finally
we demonstrate how this quantum simulated annealing algorithm can be applied to
the problems of estimating partition functions and Bayesian inference.
