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
(41)- Quantum computation and quantum information
- Quantum Algorithms for Classical Probability Distributions
- Dataflows and Computational Patterns for Hybrid Quantum-Classical Scientific Computing
- Quantum algorithms for stochastic differential equations: a Schrödingerisation approach
- Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
- Quantum Monte Carlo simulation
- Permutation matrix representation quantum Monte Carlo
- Amplitude estimation without phase estimation
- A partially random Trotter algorithm for quantum Hamiltonian simulations
- Amplitude estimation via maximum likelihood on noisy quantum computer
- scientific article; zbMATH DE number 6789291 (Why is no real title available?)
- Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
- Application of quantum Monte Carlo integration to Markovian backward stochastic differential equations
- Quantum Chebyshev's Inequality and Applications
- Quantum Monte Carlo for economics: stress testing and macroeconomic deep learning
- Quantum advantage for multi-option portfolio pricing and valuation adjustments
- A Quantum Parallel Markov Chain Monte Carlo
- Quantum algorithm for the computation of the reactant conversion rate in homogeneous turbulence
- An introduction to quantum computing for statisticians and data scientists
- Engineering local optimality in quantum Monte Carlo algorithms
- Quantum speedups for linear programming via interior point methods
- Quantum non-identical mean estimation: efficient algorithms and fundamental limits
- Optimal Control of the Keilson-Storer Master Equation in a Monte Carlo Framework
- Efficient Construction of Functional Representations for Quantum Algorithms
- Quantum Monte Carlo on graphical processing units
- Provable dual attacks on learning with errors
- The significance of relativistic computation for the philosophy of mathematics
- Monte Carlo sampling from the quantum state space. II
- Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
- A quadratic sample complexity reduction for agnostic learning via quantum algorithms
- Quantum mixing of Markov chains for special distributions
- Collider events on a quantum computer
- Estimating quantum speedups for lattice sieves
- Monte Carlo sampling from the quantum state space. I
- 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
- Theory of quantum computation and philosophy of mathematics. II
- 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
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)
