Quantum algorithms for multivariate Monte Carlo estimation
arXiv:2107.03410
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.
arXiv comment48 pages, 5 figures
References in corpus (13)
- Quantum Circuit Learning
- Quantum speedup of Monte Carlo methods
- Negative weights make adversaries stronger
- Optimal Quantum Measurements of Expectation Values of Observables
- Quantum agents in the Gym: a variational quantum algorithm for deep Q-learning
- Efficient estimation of Pauli observables by derandomization
- Tomography and Generative Data Modeling via Quantum Boltzmann Training
- Quantum query complexity of state conversion
- Fast quantum algorithm for numerical gradient estimation
- Quantum Speed-up for Approximating Partition Functions
- Generative training of quantum Boltzmann machines with hidden units
- How many functions can be distinguished with k quantum queries?
- Quantum gradient estimation of Gevrey functions