量子科技中心_量科网

该论文通过量子算法在熵估计中的应用，揭示了一个从信息论到逼近理论的全新概念性联系。具体而言，研究者们证明了单项式xⁿ的近似度存在信息论下界Ω(n½)——相较于Newman和Rivlin（《数学方程》1976）通过傅里叶分析、以及Sachdeva和Vishnoi（《理论计算机科学前沿》2014）借助马尔可夫兄弟不等式建立的解析下界，该工作通过将单项式的多项式逼近与量子Tsallis熵估计相关联实现了这一突破。 这一发现进一步催生了一种新型量子算法：对于未知概率分布p或未知量子态ρ，该算法能以加性误差ε估计其整数阶q（q≥2）Tsallis熵，仅需调用量子预言机（用于生成p的样本或制备ρ的副本）Θ̃(1/(√q ε))次。此结果显著改进了由Ekert、Alves等学者（《物理评论快报》2002）通过移位测试提出的先前最优结果O(1/ε)。据我们所知，这是首个对所有参数同时实现最优查询复杂度（至多包含多对数因子）的量子熵估计器。