Quantum Query Complexity of Entropy Estimation
Quantum Query Complexity of Entropy Estimation
复制标题
熵估计的量子查询复杂度
DOI：
10.1109/tit.2018.2883306
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
Wu, Xiaodi
中科院分区：
文献类型：
--
作者：
Li, Tongyang;Wu, Xiaodi
未知离散分布的Shannon和Rényi熵的估计是统计性质检验中的一个基本问题。在这篇文章中，我们给出了估计α-Rényi熵(Shannon熵为1-Rényi)的第一个量子算法。特别地，我们证明了香农熵估计的二次量子加速比和α-Rényi熵估计的一般量子加速比对于所有的α≥0值，包括香农熵、哈特利熵(α=0)和碰撞熵(α=2)的紧界。我们还给出了估计最小熵(α=+∞)和Kullback-Leibler散度的量子上界。我们用α-Rényi熵估计的量子下界来补充我们的结果，所有的α≥0值。我们的方法的灵感来自Bravyi，Harrow和Hassidim(BHH)的开创性工作；然而，有了许多新的技术成分：1)我们通过微调的误差分析结合Montanaro的方法来估计α=0，1的量子子例程的期望输出，从而改善了BHH框架的误差相关性；2)我们针对一般的α≥0开发了一个类似于模拟退火中的冷却时间表的过程，以及3)在整数α≥2和α=+∞的情况下，我们分别将熵估计问题归结为α-区分性和[logn]-区分性问题。
Estimation of Shannon and Rényi entropies of unknown discrete distributions is a fundamental problem in statistical property testing. In this paper, we give the first quantum algorithms for estimating α-Rényi entropies (Shannon entropy being 1-Rényi entropy). In particular, we demonstrate a quadratic quantum speedup for Shannon entropy estimation and a generic quantum speedup for α-Rényi entropy estimation for all α ≥ 0 values, including tight bounds for the Shannon entropy, the Hartley entropy (α = 0), and the collision entropy (α = 2). We also provide quantum upper bounds for estimating min-entropy (α = +∞) as well as the Kullback-Leibler divergence. We complement our results with quantum lower bounds on α-Rényi entropy estimation for all α ≥ 0 values. Our approach is inspired by the pioneering work of Bravyi, Harrow, and Hassidim (BHH); however, with many new technical ingredients: 1) we improve the error dependence of the BHH framework by a fine-tuned error analysis together with Montanaro's approach to estimating the expected output of quantum subroutines for α = 0, 1; 2) we develop a procedure, similar to cooling schedules in simulated annealing, for general α ≥ 0, and 3) in the cases of integer α ≥ 2 and α = +∞, we reduce the entropy estimation problem to the α-distinctness and [log n]-distinctness problems, respectively.
登录
查看更多内容
影响因子：
1.6
作者：
Wojciech Rudno‐Rudziński;M. Syperek;J. Andrzejewski;A. Maryński;J. Misiewicz;A. Somers;S. Höfling;J. Reithmaier;G. Sȩk
通讯作者：
Wojciech Rudno‐Rudziński;M. Syperek;J. Andrzejewski;A. Maryński;J. Misiewicz;A. Somers;S. Höfling;J. Reithmaier;G. Sȩk
基于InGaN/GaN量子阱结构的发光二极管的量子效率和发射线的形成
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
N. Bochkareva;D. V. Tarkhin;Y. Rebane;R. Gorbunov;Y. Lelikov;I. Martynov;Y. Shreter
通讯作者：
Y. Shreter
DOI：
10.1073/pnas.1607774113
发表时间：
2016-11-22
影响因子：
11.1
作者：
Orlitsky, Alon;Suresh, Ananda Theertha;Wu, Yihong
通讯作者：
Wu, Yihong
m面GaN“双误切”衬底上蓝色InGaN量子阱的电致发光特性
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
L. Kuritzky;Daniel J. Myers;Joseph Nedy;Kathryn M. Kelchner;S. Nakamura;S. Denbaars;C. Weisbuch;J. Speck
通讯作者：
J. Speck
影响因子：
4
作者：
Lin, Yue;Zhang, Yong;Chen, Zhong
通讯作者：
Chen, Zhong