Quantum speedup of Monte Carlo methods
From MaRDI portal
Publication:5363402
DOI10.1098/RSPA.2015.0301zbMATH Open1371.82053arXiv1504.06987OpenAlexW2164248509WikidataQ55019508 ScholiaQ55019508MaRDI QIDQ5363402FDOQ5363402
Authors: Ashley Montanaro 
Publication date: 29 September 2017
Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)
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 near-quadratic 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 multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
Full work available at URL: https://arxiv.org/abs/1504.06987
Recommendations
Cited In (28)
- Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
- Quantum Monte Carlo simulation
- Amplitude estimation without phase estimation
- Amplitude estimation via maximum likelihood on noisy quantum computer
- Title not available (Why is that?)
- The Significance of Relativistic Computation for the Philosophy of Mathematics
- Quantum Chebyshev's Inequality and Applications
- Quantum Monte Carlo for economics: stress testing and macroeconomic deep learning
- A Quantum Parallel Markov Chain Monte Carlo
- An introduction to quantum computing for statisticians and data scientists
- Quantum algorithm for the computation of the reactant conversion rate in homogeneous turbulence
- Engineering local optimality in quantum Monte Carlo algorithms
- Theory of Quantum Computation and Philosophy of Mathematics. Part II
- Optimal Control of the Keilson-Storer Master Equation in a Monte Carlo Framework
- Efficient Construction of Functional Representations for Quantum Algorithms
- Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture
- Provable dual attacks on learning with errors
- Quantum Monte Carlo on graphical processing units
- Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
- Collider events on a quantum computer
- Estimating quantum speedups for lattice sieves
- Quantum speedup of Monte Carlo integration with respect to the number of dimensions and its application to finance
- Quantum greedy algorithms for multi-armed bandits
- Quantum Bayesian inference for parameter estimation using quantum generative model
- MOCOKI: a Monte Carlo approach for optimal control in the force of a linear kinetic model
- Transport distance between Grover walks on graphs and coarse Ricci curvature
- Quantum algorithms for numerical differentiation of expected values with respect to parameters
- Quantum Algorithms for Classical Probability Distributions
This page was built for publication: Quantum speedup of Monte Carlo methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363402)
