Quantum speedup of Monte Carlo methods

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.

28 pages; v3 corrects error in complexity of total variation distance estimation algorithm

References in corpus (10)

• Hamiltonian simulation with nearly optimal dependence on all parameters
• Optimal Quantum Measurements of Expectation Values of Observables
• Quantum Simulations of Classical Annealing Processes
• Speed-up via Quantum Sampling
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• Quantum Sub-Gaussian Mean Estimator
• On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
• An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance
• A quantum algorithm for additive approximation of Ising partition functions
• Improving Monte Carlo randomized approximation schemes

Cited by in corpus (146)

• Quantum computing for finance: overview and prospects
• Continuous-variable quantum neural networks
• Quantum Risk Analysis
• Quantum computing for finance
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Amplitude estimation without phase estimation
• Option Pricing using Quantum Computers
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Quantum Approximate Counting, Simplified
• Koopman-von Neumann Approach to Quantum Simulation of Nonlinear Classical Dynamics
• A Threshold for Quantum Advantage in Derivative Pricing
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Biology and medicine in the landscape of quantum advantages
• Minimizing estimation runtime on noisy quantum computers
• Low depth algorithms for quantum amplitude estimation
• Quantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• Quantum walk approach to simulating parton showers
• Variational inference with a quantum computer
• Quantum unary approach to option pricing
• Efficient State Preparation for Quantum Amplitude Estimation
• Faster Amplitude Estimation
• Polymer Physics by Quantum Computing
• Prospects and challenges of quantum finance
• Variational quantum amplitude estimation
• Amplitude estimation via maximum likelihood on noisy quantum computer
• Quantum Algorithm for Fidelity Estimation
• Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Quantum algorithms for approximate function loading
• Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms
• Reduction of Qubits in Quantum Algorithm for Monte Carlo Simulation by Pseudo-random Number Generator
• Quantum Computing for Fusion Energy Science Applications
• A variational quantum algorithm for the Feynman-Kac formula
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Accelerated Quantum Monte Carlo with Probabilistic Computers
• Multivariate trace estimation in constant quantum depth
• Low-rank quantum state preparation
• Exact gate decompositions for photonic quantum computing
• Amplitude Estimation from Quantum Signal Processing
• The Problem with Grover-Rudolph State Preparation for Quantum Monte-Carlo
• Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
• The Cost of Improving the Precision of the Variational Quantum Eigensolver for Quantum Chemistry
• A Comparison of Quantum Walk Implementations on NISQ Computers
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
• Modified Grover operator for amplitude estimation
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Bootstrap Embedding on a Quantum Computer
• Quantum Monte Carlo for Economics: Stress Testing and Macroeconomic Deep Learning
• Quantum algorithm for credit valuation adjustments
• Derivative Pricing using Quantum Signal Processing
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• Quantum advantage for differential equation analysis
• Quantum Monte Carlo simulations for financial risk analytics: scenario generation for equity, rate, and credit risk factors
• A Silicon Surface Code Architecture Resilient Against Leakage Errors
• Quantum exploration algorithms for multi-armed bandits
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• Efficient option pricing with unary-based photonic computing chip and generative adversarial learning
• Optimal quantum algorithm for Gibbs state preparation
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• A Framework for Distributed Quantum Queries in the CONGEST Model
• Quantum Algorithms for Reinforcement Learning with a Generative Model
• Accelerated quantum circuit Monte-Carlo simulation for heavy quark thermalization
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Noisy quantum amplitude estimation without noise estimation
• Experimental demonstration of a high-fidelity virtual two-qubit gate
• Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions
• Quantum Fourier Iterative Amplitude Estimation
• A Quantum Algorithm for Shapley Value Estimation
• Quantum Amplitude Estimation in the Presence of Noise
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Quantum Quantitative Trading: High-Frequency Statistical Arbitrage Algorithm
• Quantum data encoding as a distinct abstraction layer in the design of quantum circuits
• Quantum algorithm for estimating volumes of convex bodies
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Quantum amplitude estimation algorithms on IBM quantum devices
• Quantum Encoding and Analysis on Continuous Time Stochastic Process with Financial Applications
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• The Prime state and its quantum relatives
• Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
• Observability of fidelity decay at the Lyapunov rate in few-qubit quantum simulations
• Lower Bounds for Parallel Quantum Counting
• Estimating Gibbs partition function with quantumClifford sampling
• Noise-Aware Quantum Amplitude Estimation
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
• Quantum mean estimation for lattice field theory
• Scalable quantum measurement error mitigation via conditional independence and transfer learning
• Quantum algorithms for powering stable Hermitian matrices
• Quantum algorithms for multivariate Monte Carlo estimation
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
• Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Assisted quantum simulation of open quantum systems
• Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal
• Computational Notions of Quantum Min-Entropy
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Quantum Computing for Data Centric Engineering and Science
• Learning parameter dependence for Fourier-based option pricing with tensor trains
• The State Preparation of Multivariate Normal Distributions using Tree Tensor Network
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
• Conditions for a quadratic quantum speedup in nonlinear transforms with applications to energy contract pricing
• Quantum-enhanced Markov Chain Monte Carlo for systems larger than your Quantum Computer
• Adaptive measurement strategy for noisy quantum amplitude estimation with variational quantum circuits
• Improving semi-device-independent randomness certification by entropy accumulation
• Quantum algorithms for spectral sums
• Bayesian Quantum Amplitude Estimation
• Quantum-assisted variational Monte Carlo
• Quantum Bayesian Neural Networks
• A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations
• Efficient Gaussian State Preparation in Quantum Circuits
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations
• Quadratic speed-ups in quantum kernelized binary classification
• Quantum clustering and jet reconstruction at the LHC
• Efficient Sparse State Preparation via Quantum Walks
• Conditional Generative Models for Learning Stochastic Processes
• Quantum query complexity of entropy estimation
• Entanglement Properties of Quantum Superpositions of Smooth, Differentiable Functions
• Quantum Computational Insurance and Actuarial Science
• Quantum and Randomised Algorithms for Non-linearity Estimation
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation
• Low bit-flip rate probabilistic error cancellation
• Quantum circuit to estimate pi using quantum amplitude estimation
• Efficient quantum algorithm for weighted partial sums and numerical integration
• Recurrence in discrete-time quantum stochastic walks
• Efficient Syndrome Decoder for Heavy Hexagonal QECC via Machine Learning
• A general approach to quantum integration of cross sections in high-energy physics
• Classical post-processing approach for quantum amplitude estimation
• Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Quantum Chebyshev's Inequality and Applications
• Efficient Construction of Functional Representations for Quantum Algorithms
• Quantum algorithm for copula-based risk aggregation using orthogonal series density estimation
• On the bias in iterative quantum amplitude estimation
• Neighborhood-History Quantum Walk
• Quantum Speedup of Monte Carlo Integration with respect to the Number of Dimensions and its Application to Finance
• Every Classical Sampling Circuit is a Quantum Sampling Circuit
• Quantum Encoding of Structured Data with Matrix Product States
• Quantum Speedups for Multiproposal MCMC
• Monte Carlo particle transport on quantum computers
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$
• Quantum algorithm for solving McKean-Vlasov stochastic differential equations
• Comprehensive Study on Heisenberg-limited Quantum Algorithms for Multiple Observables Estimation
• Post-Moore Technologies for Plasma Simulation: A Community Roadmap