Projects per year
Abstract
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomised or quantum subroutine with bounded variance, achieving a nearquadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiplestage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
Original language  English 

Article number  20150301 
Number of pages  20 
Journal  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 
Volume  471 
Issue number  2181 
Early online date  19 Aug 2015 
DOIs  
Publication status  Published  8 Sep 2015 
Bibliographical note
Accepted: 21 July 2015Keywords
 Monte Carlo methods
 quantum algorithms
 partition functions
Fingerprint
Dive into the research topics of 'Quantum speedup of Monte Carlo methods'. Together they form a unique fingerprint.Projects
 2 Finished
Profiles

Professor Ashley M R Montanaro
 School of Mathematics  Professor of Quantum Computation
 The Bristol Centre for Nanoscience and Quantum Information
 Theory and Algorithms
 Mathematical Physics
 Quantum Information Theory
Person: Academic , Member, Group lead