2009/10/09 by Tucci, Robert R.
#FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.0910.1647
We present an algorithm for doing Gibbs sampling on a quantum computer. The algorithm combines phase estimation for a Szegedy operator, and Grover's algorithm. For any ε>0, the algorithm will sample a probability distribution in \cal O((1)/(√δ)) steps with precision \cal O(ε). Here δ is the distance between the two largest eigenvalue magnitudes of the transition matrix of the Gibbs Markov chain used in the algorithm. It takes \cal O(\frac1δ) steps to achieve the same precision if one does Gibbs sampling on a classical computer.