XiaoMi-AI文件搜索系统
World File Search System下界
非局部量子计算的秩下界
非局部量子计算 (NLQC) 用一轮同时进行的通信和共享纠缠取代了两个量子系统之间的相互作用。我们研究了两类 NLQC，f -routing 和 f -BB84，它们与经典信息论密码学和量子位置验证相关。我们给出了两种设置中纠缠的第一个非平凡下界，但仅限于具有完美正确性的下界协议。在这种情况下，我们给出了完成给定函数 f ( x, y ) 的这些任务的任何纠缠态的 Schmidt 秩的下界，其矩阵 g ( x, y ) 的秩为当 f ( x, y ) = 0 时其元素为零，否则严格为正。这也导致了 Schmidt 秩的下界，以 f ( x, y ) 的非确定性量子通信复杂度为依据。由于 f 路由与信息论密码学中研究的条件秘密披露 (CDS) 原语之间的关系，我们获得了一种降低 CDS 随机性复杂度的新技术。
通过信息理论实现量子学习的最佳下界*
摘要 尽管在某些情况下使用量子样本可能比使用经典样本更有效地学习概念类，但 Arunachalam 和 de Wolf [3] 证明，在量子 PAC 和不可知论学习模型中，量子学习者的渐近效率并不比经典学习者更高。他们通过量子态识别和傅里叶分析建立了样本复杂度的下限。在本文中，我们通过信息论方法推导出 PAC 和不可知论模型中量子样本复杂度的最佳下限。证明可以说更简单，相同的想法可用于推导出量子学习理论中其他问题的最佳界限。然后，我们转向优惠券收集器问题的量子类似物，这是概率论中的一个经典问题，在 PAC 学习研究中也具有重要意义。Arunachalam、Belovs、Childs、Kothari、Rosmanis 和 de Wolf [1] 将该问题的量子样本复杂度表征为常数因子。首先，我们证明了上述信息论方法无法得出最佳下限。作为副产品，我们得到了任意高维纯态的自然集合，这些纯态不易（同时）区分，而集合具有接近最大的 Holevo 信息。其次，我们发现信息论方法为该问题的近似变体得出了渐近最佳界限。最后，我们通过广义 Holevo-Curlander 集合可区分性界限，推导出具有精确领先阶项的量子优惠券收集器问题的尖锐下限。我们研究的量子优惠券收集器问题的所有方面都取决于相关 Gram 矩阵的谱的属性，这可能是独立的兴趣所在。