Blanchet, J., Szegedy, M., & Wang, G. (2024). Quadratic Speed-up in Infinite Variance Quantum Monte Carlo. ArXiv. /abs/2401.07497

View Publication

Abstract

In this study, we give an extension of Montanaro's arXiv/archive:1504.06987 quantum Monte Carlo method, tailored for computing expected values of random variables that exhibit infinite variance. This addresses a challenge in analyzing heavy-tailed distributions, which are commonly encountered in various scientific and engineering fields. Our quantum algorithm efficiently estimates means for variables with a finite moment, where lies between 0 and 1. It provides a quadratic speedup over the classical Monte Carlo method in both the accuracy parameter and the specified moment of the distribution. We establish both classical and quantum lower bounds, showcasing the near-optimal efficiency of our algorithm among quantum methods. Our work focuses not on creating new algorithms, but on analyzing the execution of existing algorithms with available additional information about the random variable. Additionally, we categorize these scenarios and demonstrate a hierarchy in the types of supplementary information that can be provided.

Authors
Jose Blanchet, Mario Szegedy, Guanyang Wang
Publication date
2024/1/15
Journal
arXiv preprint arXiv:2401.07497