XiaoMi-AI文件搜索系统
World File Search System下界
通过信息理论实现量子学习的最佳下界*
摘要 尽管在某些情况下使用量子样本可能比使用经典样本更有效地学习概念类，但 Arunachalam 和 de Wolf [3] 证明，在量子 PAC 和不可知论学习模型中，量子学习者的渐近效率并不比经典学习者更高。他们通过量子态识别和傅里叶分析建立了样本复杂度的下限。在本文中，我们通过信息论方法推导出 PAC 和不可知论模型中量子样本复杂度的最佳下限。证明可以说更简单，相同的想法可用于推导出量子学习理论中其他问题的最佳界限。然后，我们转向优惠券收集器问题的量子类似物，这是概率论中的一个经典问题，在 PAC 学习研究中也具有重要意义。Arunachalam、Belovs、Childs、Kothari、Rosmanis 和 de Wolf [1] 将该问题的量子样本复杂度表征为常数因子。首先，我们证明了上述信息论方法无法得出最佳下限。作为副产品，我们得到了任意高维纯态的自然集合，这些纯态不易（同时）区分，而集合具有接近最大的 Holevo 信息。其次，我们发现信息论方法为该问题的近似变体得出了渐近最佳界限。最后，我们通过广义 Holevo-Curlander 集合可区分性界限，推导出具有精确领先阶项的量子优惠券收集器问题的尖锐下限。我们研究的量子优惠券收集器问题的所有方面都取决于相关 Gram 矩阵的谱的属性，这可能是独立的兴趣所在。
非局部量子计算的秩下界
非局部量子计算 (NLQC) 用一轮同时进行的通信和共享纠缠取代了两个量子系统之间的相互作用。我们研究了两类 NLQC，f -routing 和 f -BB84，它们与经典信息论密码学和量子位置验证相关。我们给出了两种设置中纠缠的第一个非平凡下界，但仅限于具有完美正确性的下界协议。在这种情况下，我们给出了完成给定函数 f ( x, y ) 的这些任务的任何纠缠态的 Schmidt 秩的下界，其矩阵 g ( x, y ) 的秩为当 f ( x, y ) = 0 时其元素为零，否则严格为正。这也导致了 Schmidt 秩的下界，以 f ( x, y ) 的非确定性量子通信复杂度为依据。由于 f 路由与信息论密码学中研究的条件秘密披露 (CDS) 原语之间的关系，我们获得了一种降低 CDS 随机性复杂度的新技术。
CS 39000ATA 课程公告
○ 对偶性和极小极大定理；凸优化 ○ 最大流/最小割 ● 下界技术和问题简化 ● NP 完全性 ● 近似算法 ● 从在线学习、交互式证明、大图/社交网络上的算法、并行/高性能计算、量子计算中选择的主题。
协变量子纠错的新视角
协变码是一种量子码，逻辑系统上的对称变换可以通过物理系统上的对称变换来实现，通常具有有限的量子纠错能力（一个重要的例子是 Eastin-Knill 定理）。理解协变量子纠错极限的需求出现在物理学的各个领域，包括容错量子计算、凝聚态物理和量子引力。在这里，我们从量子计量和量子资源理论的角度探索了连续对称性的协变量子纠错，在这些以前分散的领域之间建立了牢固的联系。我们证明了协变量子纠错不保真度的新的、强大的下界，这不仅扩展了以前不行的结果的范围，而且比现有界限有了很大的改进。为擦除和去极化噪声推导出了明确的下界。我们还提出了一种几乎饱和这些下界的协变码。
贝叶斯长冈林开往 ...
在通信过程中估计信号时，自然需要利用对未知参数的先验知识进行贝叶斯参数估计 [1]。量子通信是一种很有前途的近期通信技术，它可以比传统协议更安全、更有效地传输信息。关于如何在给定的噪声量子信道上忠实地传输经典和/或量子信息，已经有很多研究，例如 [2]–[4]。量子贝叶斯估计是有效解码量子态中编码的经典信息的关键因素。量子贝叶斯估计在量子传感和量子计量领域也得到了极大关注 [5]–[8]。量子贝叶斯估计大约半个世纪前由 Personick [9]，[10] 发起。由于量子估计理论的最新进展，量子贝叶斯估计问题重新引起了人们的关注。针对贝叶斯风险，提出了几种量子贝叶斯界，例如 [9]–[17]。然而，它们中的大多数都没有捕捉到真正的量子性质，因为已知的下界几乎都是基于经典贝叶斯界的直接翻译。特别是，先前提出的下界是通过对算子空间上的内积的某个选择应用柯西-施瓦茨型不等式推导出来的。Holevo 在一般统计决策问题的背景下发起了对量子估计的非平凡下界的研究 [18]。他还基于量子 Fisher 信息矩阵分析了贝叶斯风险的下界 [19]–[21]。特别是，他对高斯移位进行了彻底的分析
两种渐近最优的策略证明机制...
我们考虑在度量空间中定位设施以服务于一组自私代理的问题。代理的成本是她自己的位置与最近设施之间的距离。社会成本是代理的总成本。我们感兴趣的是设计无需支付的策略验证机制，该机制的社会成本近似率较小。机制是一种（可能是随机的）算法，它将代理报告的位置映射到设施的位置。如果在任何配置下没有代理可以从错误报告其位置中获益，则机制是策略验证的。这种设置最早由 Procaccia 和 Tennenholtz [21] 研究。他们专注于代理和设施位于实线上的设施博弈。Alon 等人研究了一般度量空间中设施博弈的机制 [1]。然而，他们专注于只有一个设施的游戏。在本文中，我们研究了一般度量空间中的双设施博弈，这扩展了之前的两个模型。我们首先证明确定性策略证明机制的社会成本近似比的 Ω(n) 下界。我们的下界甚至对线度量空间也成立。这显著改善了之前的常数下界 [21, 17]。请注意，线度量空间中有一个匹配的线性上限 [21]。接下来，我们提供了第一个常数近似比为 4 的随机化策略证明机制。我们的机制适用于一般度量空间。对于随机化策略证明机制，之前的最佳上限为 O(n)，仅适用于线度量空间。
关联相对熵、最优传输和 Fisher 信息：量子 HWI 不等式
摘要。量子马尔可夫半群表征了一类重要的开放量子系统的时间演化。研究这种半群的收敛性质并确定其不变态的集中性质一直是许多研究的重点。函数不等式的量子版本（如修正的对数 Sobolev 和 Poincar'e 不等式）和所谓的运输成本不等式已被证明对于此目的至关重要。经典函数和运输成本不等式被认为是从称为 Ricci 下界的单个几何不等式通过它们之间的插值不等式产生的。后者称为 HWI 不等式，其中字母 I、W 和 H 分别是 Fisher 信息（出现在修改的对数 Sobolev 不等式中）、所谓的 Wasserstein 距离（出现在运输成本不等式中）和出现在两者中的相对熵（或 Boltzmann H 函数）的首字母缩写。因此，从经典角度来看，上述不等式及其之间的蕴涵构成了一幅非凡的图景，它将来自不同数学领域的元素联系起来，例如黎曼几何、信息论、最优传输理论、马尔可夫过程、测度集中和凸性理论。在这里，我们考虑了 Carlen 和 Maas 引入的 Ricci 下界的量子版本，并证明它意味着量子 HWI 不等式，量子函数和运输成本不等式由此而来。因此，我们的结果表明，经典设置的统一图景可以延续到量子设置。
量子相对熵的积分公式意味着数据处理不等式
建立了量子相对熵以及冯·诺依曼熵的方向二阶和高阶导数的积分表示，并用于给出基本已知数据处理不等式的简单证明：量子通信信道传输的信息量的 Holevo 界限，以及更一般地，在迹保持正线性映射下量子相对熵的单调性——映射的完全正性不必假设。后一个结果首先由 Müller-Hermes 和 Reeb 基于 Beigi 的工作证明。对于这种单调性的简单应用，我们考虑在量子测量下不增加的任何“散度”，例如冯·诺依曼熵的凹度或各种已知的量子散度。使用了 Hiai、Ohya 和 Tsukada 的优雅论证来表明，具有规定迹距的量子态对上这种“散度”的下界与二元经典态对上相应的下界相同。还讨论了新的积分公式在信息论的一般概率模型中的应用，以及经典 Rényi 散度的相关积分公式。
印度统计学院学生手册
集合和函数的语言 - 可数集和不可数集。实数 - 最小上界和最大下界。序列 - 序列的极限点、收敛序列；有界和单调序列、序列的上极限和下极限。柯西序列和 R 的完备性。级数 - 级数的收敛和发散、绝对收敛和条件收敛。黎曼重排定理。级数收敛的各种测试。（积分测试将推迟到分析 II 中引入黎曼积分之后。）无穷级数与实数的十进制展开、三进制、二进制展开之间的联系。柯西积、无限积。