A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation
IEEE Transactions on Information Theory · 2024-05 · 70 (5) · 3399-3426
DOI: 10.1109/tit.2024.3382037 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2024-05. Verfasst von Xinzhao Wang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 54 Literaturangaben. Gefördert von: startup fund from Peking University, Advanced Institute of Information Technology, Peking University.
Abstract (Originalsprache)
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 $\alpha >1$ and $0 , our algorithm framework estimates $\alpha $ -Rényi entropy $H_{\alpha }(p)$ to within additive error $\epsilon $ with probability at least 2/3 using $\widetilde {\mathcal {O}}\left({n^{1-\frac {1}{2\alpha }}/\epsilon + \sqrt {n}/\epsilon ^{1+\frac {1}{2\alpha }}}\right)$ and $\widetilde {\mathcal {O}}\left({n^{\frac {1}{2\alpha }}/\epsilon ^{1+\frac {1}{2\alpha }}}\right)$ queries, respectively. This improves the best known dependence in $\epsilon $ as well as the joint dependence between n and $1/\epsilon $ . 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.
Förderung
- startup fund from Peking University
- Advanced Institute of Information Technology, Peking University
Zitieren
APA
Wang, X., Zhang, S., & Li, T. (2024). A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation. IEEE Transactions on Information Theory, 70(5), 3399-3426. https://doi.org/10.1109/tit.2024.3382037
Vancouver
Wang X, Zhang S, Li T. A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation. IEEE Transactions on Information Theory. 2024;70(5):3399-3426. doi:10.1109/tit.2024.3382037
BibTeX
@article{Wang2024,
author = {Wang, Xinzhao and Zhang, Shengyu and Li, Tongyang},
title = {A Quantum Algorithm Framework for Discrete Probability Distributions With Applications to Rényi Entropy Estimation},
journal = {IEEE Transactions on Information Theory},
year = {2024},
volume = {70},
number = {5},
pages = {3399--3426},
doi = {10.1109/tit.2024.3382037}
}
EUVIMED