Quantum speedup of Monte Carlo methods
From MaRDI portal
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 algorithms for learning Walsh spectra of multi-output Boolean functions
- Quantum algorithms for numerical differentiation of expected values with respect to parameters
- Engineering local optimality in quantum Monte Carlo algorithms
- Quantum computation and quantum information
- Amplitude estimation without phase estimation
- Amplitude estimation via maximum likelihood on noisy quantum computer
- Quantum Bayesian inference for parameter estimation using quantum generative model
- Collider events on a quantum computer
- Quantum speedup of Monte Carlo integration with respect to the number of dimensions and its application to finance
- Estimating quantum speedups for lattice sieves
- Quantum greedy algorithms for multi-armed bandits
- The significance of relativistic computation for the philosophy of mathematics
- Optimal Control of the Keilson-Storer Master Equation in a Monte Carlo Framework
- Quantum algorithm for the computation of the reactant conversion rate in homogeneous turbulence
- Quantum Algorithms for Classical Probability Distributions
- Quantum Chebyshev's Inequality and Applications
- Monte Carlo sampling from the quantum state space. I
- 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
- Theory of quantum computation and philosophy of mathematics. II
- scientific article; zbMATH DE number 6789291 (Why is no real title available?)
- Permutation matrix representation quantum Monte Carlo
- Quantum Monte Carlo for economics: stress testing and macroeconomic deep learning
- MOCOKI: a Monte Carlo approach for optimal control in the force of a linear kinetic model
- A Quantum Parallel Markov Chain Monte Carlo
- Quantum Monte Carlo simulation
- 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
- An introduction to quantum computing for statisticians and data scientists
- Provable dual attacks on learning with errors
- Quantum speedups for linear programming via interior point methods
- Quantum non-identical mean estimation: efficient algorithms and fundamental limits
- A quadratic sample complexity reduction for agnostic learning via quantum algorithms
- Quantum algorithms for stochastic differential equations: a Schrödingerisation approach
- A partially random Trotter algorithm for quantum Hamiltonian simulations
- 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 Monte Carlo on graphical processing units
- Quantum advantage for multi-option portfolio pricing and valuation adjustments
- Uniformity testing when you have the source code
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)
