Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

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

Edit abstract data

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 Valid HTML 4.01! Valid CSS!