Quantum algorithms for multivariate Monte Carlo estimation

• URL: http://arxiv.org/abs/2107.03410v1
• Date: Wed, 7 Jul 2021 18:00:18 GMT
• Title: Quantum algorithms for multivariate Monte Carlo estimation
• Authors: Arjan Cornelissen, Sofiene Jerbi
• Abstract summary: We consider the problem of estimating the expected outcomes of Monte Carlo processes whose outputs are described by multidimensional random variables. We design quantum algorithms that provide a quadratic speed-up in query complexity with respect to the precision of the resulting estimates. We describe several applications of our algorithms, notably in the field of machine learning.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of estimating the expected outcomes of Monte Carlo processes whose outputs are described by multidimensional random variables. We tightly characterize the quantum query complexity of this problem for various choices of oracle access to the Monte Carlo process and various normalization conditions on its output variables and the estimates to be made. More specifically, we design quantum algorithms that provide a quadratic speed-up in query complexity with respect to the precision of the resulting estimates and show that these complexities are asymptotically optimal in each of our scenarios. Interestingly, we find that these speed-ups with respect to the precision come at the cost of a (up to exponential) slowdown with respect to the dimension of the Monte Carlo random variables, for most of the parameter settings we consider. We also describe several applications of our algorithms, notably in the field of machine learning, and discuss the implications of our results.

Related papers

• Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution [44.99833362998488]
  We analyze the accuracy and sample complexity of variational Monte Carlo approaches to simulate quantum systems classically. We prove that the most used scheme, the time-dependent Variational Monte Carlo (tVMC), is affected by a systematic statistical bias. We show that a different scheme based on the solution of an optimization problem at each time step is free from such problems.
  arXiv  Detail & Related papers  (2023-05-23T17:38:10Z)
• Optimisation of time-ordered processes in the finite and asymptotic regime [0.0]
  Many problems in quantum information theory can be formulated as optimizations over the sequential outcomes of dynamical systems. In this work, we introduce tractable relaxations of this class of optimization problems. We show that the maximum score of a sequential problem in the limit of infinitely many time steps is in general incomputable.
  arXiv  Detail & Related papers  (2023-02-06T16:47:24Z)
• 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)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• 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)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• The Variational Method of Moments [65.91730154730905]
  conditional moment problem is a powerful formulation for describing structural causal parameters in terms of observables. Motivated by a variational minimax reformulation of OWGMM, we define a very general class of estimators for the conditional moment problem. We provide algorithms for valid statistical inference based on the same kind of variational reformulations.
  arXiv  Detail & Related papers  (2020-12-17T07:21:06Z)
• A Framework for Sample Efficient Interval Estimation with Control Variates [94.32811054797148]
  We consider the problem of estimating confidence intervals for the mean of a random variable. Under certain conditions, we show improved efficiency compared to existing estimation algorithms.
  arXiv  Detail & Related papers  (2020-06-18T05:42:30Z)

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.