2008/04/30 by Paweł Wocjan, Pawel Wocjan, Anura Abeyesinghe · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Quantum Computing Algorithms and Architecture #Quantum many-body systems #quant-ph
paper · pdf · doi:10.1103/physreva.78.042336
8 pages, fixed some minor typos
arxiv created 2008/09/08 · openalex publication_date 2008/10/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.