Quantum speedup of Monte Carlo methods
From MaRDI portal
Publication:5363402
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.
Recommendations
Cited in
(32)- An introduction to quantum computing for statisticians and data scientists
- Engineering local optimality in quantum Monte Carlo algorithms
- Monte Carlo sampling from the quantum state space. I
- Quantum algorithms for numerical differentiation of expected values with respect to parameters
- Quantum Monte Carlo for economics: stress testing and macroeconomic deep learning
- A Quantum Parallel Markov Chain Monte Carlo
- Theory of quantum computation and philosophy of mathematics. II
- Quantum algorithm for the computation of the reactant conversion rate in homogeneous turbulence
- MOCOKI: a Monte Carlo approach for optimal control in the force of a linear kinetic model
- Amplitude estimation without phase estimation
- Collider events on a quantum computer
- Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
- Transport distance between Grover walks on graphs and coarse Ricci curvature
- Quantum Monte Carlo simulation
- Amplitude estimation via maximum likelihood on noisy quantum computer
- Estimating quantum speedups for lattice sieves
- The significance of relativistic computation for the philosophy of mathematics
- Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
- Quantum Chebyshev's Inequality and Applications
- Quantum Monte Carlo on graphical processing units
- Quantum computation and quantum information
- Optimal Control of the Keilson-Storer Master Equation in a Monte Carlo Framework
- scientific article; zbMATH DE number 6789291 (Why is no real title available?)
- Permutation matrix representation quantum Monte Carlo
- Provable dual attacks on learning with errors
- Quantum Bayesian inference for parameter estimation using quantum generative model
- Quantum Algorithms for Classical Probability Distributions
- Monte Carlo sampling from the quantum state space. II
- Quantum mixing of Markov chains for special distributions
- Efficient Construction of Functional Representations for Quantum Algorithms
- 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
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)
