2024/01/15 by José Blanchet, Márió Szegedy, Blanchet, Jose +3 · 1 citation
Computer Science · Mathematics · #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2401.07497
openalex publication_date 2024/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (1+δ)th 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.