机构名称：
¥ 2.0
不可能性证明，如 BQP 在 PP 中的包含 [2, 15]、量子比特承诺的不可能性 [27]，以及预言机和黑盒问题的存在，相对于这些问题，量子计算机的能力有限 [1, 5, 6, 7, 15]。在本文中，我们考虑零知识证明系统的量子变体的潜在优势。零知识证明系统最早由 Goldwasser、Micali 和 Rackooff[20] 于 1985 年定义，此后在复杂性理论和密码学中得到了广泛的研究。本文假设您熟悉零知识证明系统的基础知识。有关零知识的最新调查，请参阅 Goldreich [16]。已经研究了几种零知识概念，但在本文中我们只考虑统计零知识。此外，我们将重点关注诚实验证者统计零知识，这意味着只需一个多项式时间模拟器就可以近似地模拟遵循指定协议的验证者的观点（而不是为了获取知识而故意偏离指定协议的验证者的观点）。在经典情况下，Goldreich、Sahai 和 Vadhan [18] 证明了任何诚实验证者统计零知识证明系统都可以转化为针对任何验证者的统计零知识证明系统。具有统计零知识证明系统的语言类表示为 SZK；已知 SZK 在补集下是封闭的 [32]，SZK ⊆ AM [4, 14]，并且 SZK 具有自然的完全承诺问题 [19, 34]。已知几个有趣的问题（例如图同构和二次剩余）包含在 SZK 中，但不包含在 BPP 中 [17, 20]。有关统计零知识的全面讨论，请参阅 Vadhan [38]。据我们所知，文献中之前没有出现过量子零知识证明系统的正式定义。然而，量子信息是否允许扩展具有零知识证明的问题类别的问题已经被一些研究人员解决了。例如，研究量子比特承诺可能性的动机之一是它对零知识证明系统的适用性。缺乏正式定义的主要原因似乎是当以最直接的方式将零知识的经典定义转换为量子设置时会出现困难。有关这些问题的进一步讨论，请参阅 van de Graaf [21]。本文的目的不是试图解决这些困难，也不是提出一个从密码学角度令人满意的量子零知识定义。相反，我们的目标是研究基于诚实验证者概念的量子零知识简单定义的复杂性理论方面。我们考虑这个定义的主要动机是：
量子统计零知识能力的限制
主要关键词
相关文件推荐
![应用统计与概率 [3 1 0 4] 基础知识...](/simg/1/135d2c0830996f68e452dd4874aafe89f7642a8d.webp)
