Logical Approaches to Computational Barriers

The quantum complexity of Markov chain Monte Carlo

Speaker:
| Peter Richter |

Author(s): |
Peter Richter |

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 |