Abbreviated Journal Title
Phys. Rev. A
Keywords
PERMANENT; ALGORITHM; MATRIX; Optics; Physics, Atomic, Molecular & Chemical
Abstract
The Markov-chain Monte Carlo method is at the heart of efficient approximation schemes for a wide range of problems in combinatorial enumeration and statistical physics. 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 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 greater speedup over a recently proposed method for obtaining the ground states of (classical) Hamiltonians.
Journal Title
Physical Review A
Volume
78
Issue/Number
4
Publication Date
1-1-2008
Document Type
Article
Language
English
First Page
8
WOS Identifier
ISSN
1050-2947
Recommended Citation
Wocjan, Pawel and Abeyesinghe, Anura, "Speedup via quantum sampling" (2008). Faculty Bibliography 2000s. 1137.
https://stars.library.ucf.edu/facultybib2000/1137
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu