A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911824809558016 |
|---|---|
| author | Wang, Xinzhao Zhang, Shengyu Li, Tongyang |
| author_facet | Wang, Xinzhao Zhang, Shengyu Li, Tongyang |
| contents | Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating Rényi entropies as specific examples. In particular, given a quantum oracle that prepares an $n$-dimensional quantum state $\sum_{i=1}^{n}\sqrt{p_{i}}|i\rangle$, for $α>1$ and $0<α<1$, our algorithm framework estimates $α$-Rényi entropy $H_α(p)$ to within additive error $ε$ with probability at least $2/3$ using $\widetilde{\mathcal{O}}(n^{1-\frac{1}{2α}}/ε+ \sqrt{n}/ε^{1+\frac{1}{2α}})$ and $\widetilde{\mathcal{O}}(n^{\frac{1}{2α}}/ε^{1+\frac{1}{2α}})$ queries, respectively. This improves the best known dependence in $ε$ as well as the joint dependence between $n$ and $1/ε$. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_01571 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation Wang, Xinzhao Zhang, Shengyu Li, Tongyang Quantum Physics Data Structures and Algorithms Information Theory Estimating statistical properties is fundamental in statistics and computer science. In this paper, we propose a unified quantum algorithm framework for estimating properties of discrete probability distributions, with estimating Rényi entropies as specific examples. In particular, given a quantum oracle that prepares an $n$-dimensional quantum state $\sum_{i=1}^{n}\sqrt{p_{i}}|i\rangle$, for $α>1$ and $0<α<1$, our algorithm framework estimates $α$-Rényi entropy $H_α(p)$ to within additive error $ε$ with probability at least $2/3$ using $\widetilde{\mathcal{O}}(n^{1-\frac{1}{2α}}/ε+ \sqrt{n}/ε^{1+\frac{1}{2α}})$ and $\widetilde{\mathcal{O}}(n^{\frac{1}{2α}}/ε^{1+\frac{1}{2α}})$ queries, respectively. This improves the best known dependence in $ε$ as well as the joint dependence between $n$ and $1/ε$. Technically, our quantum algorithms combine quantum singular value transformation, quantum annealing, and variable-time amplitude estimation. We believe that our algorithm framework is of general interest and has wide applications. |
| title | A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation |
| topic | Quantum Physics Data Structures and Algorithms Information Theory |
| url | https://arxiv.org/abs/2212.01571 |