Abbreviated Journal Title
Phys. Rev. A
Keywords
Optics; Physics; Atomic; Molecular & Chemical
Abstract
We present a quantum algorithm based on classical fully polynomial randomized approximation schemes (FPRASs) for estimating partition functions that combine simulated annealing with the Monte Carlo Markov chain method and use nonadaptive cooling schedules. We achieve a twofold polynomial improvement in time complexity: a quadratic reduction with respect to the spectral gap of the underlying Markov chains and a quadratic reduction with respect to the parameter characterizing the desired accuracy of the estimate output by the FPRAS. Both reductions are intimately related and cannot be achieved separately. First, we use Grover's fixed-point search, quantum walks, and phase estimation to efficiently prepare approximate coherent encodings of stationary distributions of the Markov chains. The speed up we obtain in this way is due to the quadratic relation between the spectral and phase gaps of classical and quantum walks. The second speed up with respect to accuracy comes from generalized quantum counting used instead of classical sampling to estimate expected values of quantum observables.
Journal Title
Physical Review A
Volume
80
Issue/Number
2
Publication Date
1-1-2009
Document Type
Article
Language
English
First Page
8
WOS Identifier
ISSN
1050-2947
Recommended Citation
Wocjan, Pawel; Chiang, Chen-Fu; Nagaj, Daniel; and Abeyesinghe, Anura, "Quantum algorithm for approximating partition functions" (2009). Faculty Bibliography 2000s. 2323.
https://stars.library.ucf.edu/facultybib2000/2323