Quadratic Speed-up in Infinite Variance Quantum Monte Carlo
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910355788136448 |
|---|---|
| author | Blanchet, Jose Szegedy, Mario Wang, Guanyang |
| author_facet | Blanchet, Jose Szegedy, Mario Wang, Guanyang |
| contents | 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+δ)^{\text{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07497 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quadratic Speed-up in Infinite Variance Quantum Monte Carlo Blanchet, Jose Szegedy, Mario Wang, Guanyang Quantum Physics 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+δ)^{\text{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. |
| title | Quadratic Speed-up in Infinite Variance Quantum Monte Carlo |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2401.07497 |