Speed-up via Quantum Sampling Export

@misc{citeulike:2733390, abstract = {The Markov Chain Monte Carlo method is at the heart of most fully-polynomial randomized approximation schemes for \#P-complete problems such as estimating the permanent or the value of a polytope. It is therefore very natural and important to determine whether quantum computers can speed-up classical mixing processes based on Markov chains. To this end, we present a new quantum algorithm, making it possible to prepare a quantum sample, i.e., a coherent version of the stationary distribution of a reversible Markov chain. Our algorithm has a significantly better running time than that of a previous algorithm based on adiabatic state generation. We also show that our methods provide a speed-up over a recently proposed method for obtaining ground states of (classical) Hamiltonians. In an upcoming article, we will show that they yield speed-ups of classical algorithms for approximately evaluating the permanent.}, archivePrefix = {arXiv}, author = {Abeyesinghe, Anura and Wocjan, Pawel}, citeulike-article-id = {2733390}, citeulike-linkout-0 = {http://arxiv.org/abs/0804.4259}, citeulike-linkout-1 = {http://arxiv.org/pdf/0804.4259}, day = {26}, eprint = {0804.4259}, keywords = {abc}, month = {Apr}, posted-at = {2008-12-06 10:02:17}, priority = {2}, title = {Speed-up via Quantum Sampling}, url = {http://arxiv.org/abs/0804.4259}, year = {2008} }

TY - ELEC ID - citeulike:2733390 L3 - citeulike-article-id:2733390 N2 - The Markov Chain Monte Carlo method is at the heart of most fully-polynomial randomized approximation schemes for #P-complete problems such as estimating the permanent or the value of a polytope. It is therefore very natural and important to determine whether quantum computers can speed-up classical mixing processes based on Markov chains. To this end, we present a new quantum algorithm, making it possible to prepare a quantum sample, i.e., a coherent version of the stationary distribution of a reversible Markov chain. Our algorithm has a significantly better running time than that of a previous algorithm based on adiabatic state generation. We also show that our methods provide a speed-up over a recently proposed method for obtaining ground states of (classical) Hamiltonians. In an upcoming article, we will show that they yield speed-ups of classical algorithms for approximately evaluating the permanent. TI - Speed-up via Quantum Sampling KW - abc AU - Abeyesinghe, Anura AU - Wocjan, Pawel PY - 2008/Apr/26/ UR - http://arxiv.org/abs/0804.4259 ER -