Computability in Europe 2006
Logical Approaches to Computational Barriers


Special Session Talk:
The quantum complexity of Markov chain Monte Carlo


Speaker: Peter Richter
Author(s): Peter Richter

Abstract

Markov chain Monte Carlo (MCMC) is the widely-used classical method of random
sampling from a probability distribution pi by simulating a Markov chain which
``mixes'' to pi at equilibrium.  Despite the success quantum walks
have been shown to have in speeding up random walk algorithms for search
problems (``hitting'') and simulated annealing, it remains to prove a
general speedup theorem for MCMC sampling algorithms.  We review the progress
toward this end, in particular using decoherent quantum walks.

websites: Arnold Beckmann 2008-01-07