机构名称：
¥ 4.0
我们在属性测试的设置中启动了 QMA 算法的系统研究，我们将其称为 QMA 邻近性证明 (QMAP)。这些是量子查询算法，它们可以显式访问亚线性大小的不受信任的证明，并且需要接受具有属性 Π 的输入并拒绝距离 Π ε 远的输入，同时仅探测其输入的极小部分。我们的算法结果包括一个通用定理，该定理可以实现量子加速，以测试一类富有表现力的属性，即那些可以简洁地分解的属性。此外，我们还展示了该系列之外的属性的量子加速，例如图二分性。我们还研究了该模型的复杂性格局，表明 QMAP 可以比经典邻近性证明和量子测试器强得多。为此，我们扩展了 Blais、Brody 和 Matulef（计算复杂性，2012）的方法，通过降低通信复杂性来证明量子属性测试下限，从而解决了 Montanaro 和 de Wolf（计算理论，2016）提出的问题。
接近度的量子证明
主要关键词
相关文件推荐
