Non-linear Quantum Monte Carlo
- URL: http://arxiv.org/abs/2502.05094v1
- Date: Fri, 07 Feb 2025 17:13:27 GMT
- Title: Non-linear Quantum Monte Carlo
- Authors: Jose Blanchet, Yassine Hamoudi, Mario Szegedy, Guanyang Wang,
- Abstract summary: Quantum computing provides a quadratic speedup over classical Monte Carlo methods for mean estimation.
We propose a quantum-inside-quantum Monte Carlo algorithm that achieves such a speedup for a broad class of non-linear estimation problems.
- Score: 1.237454174824584
- License:
- Abstract: The mean of a random variable can be understood as a $\textit{linear}$ functional on the space of probability distributions. Quantum computing is known to provide a quadratic speedup over classical Monte Carlo methods for mean estimation. In this paper, we investigate whether a similar quadratic speedup is achievable for estimating $\textit{non-linear}$ functionals of probability distributions. We propose a quantum-inside-quantum Monte Carlo algorithm that achieves such a speedup for a broad class of non-linear estimation problems, including nested conditional expectations and stochastic optimization. Our algorithm improves upon the direct application of the quantum multilevel Monte Carlo algorithm introduced by An et al.. The existing lower bound indicates that our algorithm is optimal up polylogarithmic factors. A key innovation of our approach is a new sequence of multilevel Monte Carlo approximations specifically designed for quantum computing, which is central to the algorithm's improved performance.
Related papers
- Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
We propose quantum algorithms for linear differential equations.
The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.
The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
arXiv Detail & Related papers (2024-12-19T14:04:11Z) - Quantum Monte Carlo Integration for Simulation-Based Optimisation [34.96100129498306]
We investigate the feasibility of integrating quantum algorithms as subroutines of simulation-based optimisation problems.
We conduct a thorough analysis of all systematic errors arising in the formulation of quantum Monte Carlo integration.
We study the applicability of quantum Monte Carlo integration for fundamental financial use cases.
arXiv Detail & Related papers (2024-10-04T21:05:32Z) - Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm [0.0]
Two-stage programming is a problem formulation for decision-making under uncertainty.
This work uses a quantum algorithm to estimate the expected value function with a speedup.
arXiv Detail & Related papers (2024-02-23T00:07:34Z) - Quadratic Speed-up in Infinite Variance Quantum Monte Carlo [1.2891210250935148]
We give an extension of Montanaro's arXiv/archive:1504.06987 quantum Monte Carlo method.
It is tailored for computing expected values of random variables that exhibit infinite variance.
arXiv Detail & Related papers (2024-01-15T06:31:36Z) - A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo
Integration and Beyond [7.060988518771793]
We focus on the potential to obtain a quantum advantage in the computational speed of Monte Carlo procedures using quantum circuits.
We revisit the quantum algorithms that could replace classical Monte Carlo and then consider both the existing quantum algorithms and the potential quantum realizations.
arXiv Detail & Related papers (2023-03-08T23:39:49Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications.
This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
arXiv Detail & Related papers (2023-01-30T15:46:39Z) - Quantum Adversarial Learning in Emulation of Monte-Carlo Methods for
Max-cut Approximation: QAOA is not optimal [0.0]
We apply notions of emulation to Variational Quantum Annealing and the Quantum Approximate Algorithm Optimization (QAOA)
Our Variational Quantum Annealing schedule is based on a novel parameterization that can be optimized in a similar gradient-free way as QAOA, using the same physical ingredients.
In order to compare the performance of ans"atze types, we have developed statistical notions of Monte-Carlo methods.
arXiv Detail & Related papers (2022-11-24T19:02:50Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
We analyze and optimize an improved quantum algorithm for topological data analysis.
We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation.
We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
arXiv Detail & Related papers (2022-09-27T17:56:15Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data.
We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem.
In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
arXiv Detail & Related papers (2020-06-11T19:40:38Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.