Quantum Speedups for Markov Chain Monte Carlo Methods with Application to Optimization

Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi +1

We propose quantum algorithms that provide provable speedups for Markov Chain Monte Carlo (MCMC) methods commonly used for sampling from probability distributions of the form $π\p…