论文部分内容阅读
由于量子计算和量子通信在原则上是可行的,并有一天可能会在物理上完全实现(现在已经能够部分实现,尤其是量子保密通信),因此,看看它们能够如何改变我们的生活是一件非常有趣的事情;特别地,随着安全性在我们的日常生活中变地越来越重要,看看量子特性能够提供给我们一个怎样的安全保障显得格外引人注目。众所周知,经典的密码学有时在量子攻击下是不安全的,这也迫使我们去考虑量子密码学:我们能否利用量子机制去抵抗同样由量子机制带来的攻击?零知识证明是经典密码学中的一个基本概念,可以用它来构造许多有用的密码协议,例如,身份认证方案。因此,把零知识证明推广到量子情形,考虑量子零知识证明,是有意义的。这篇论文的主题就是用计算复杂性理论的方法对量子零知识交互证明展开研究。这里,用“计算复杂性理论的方法”的含义是,我们把具有量子零知识交互证明的语言(或许诺问题)看作一个复杂性类,然后用计算复杂性理论中发展的各种思想和方法来对其进行研究。具体如下。我们首先详细地讨论量子零知识证明的形式化定义,解释该定义如何从经典定义中推广而来并且符合我们的直观。据我们了解,在此之前还没有文献对量子零知识证明的定义做过系统的总结和讨论。我们接下来研究量子完美零知识证明,并且构造了对应的复杂性类的第一个完全问题。我们需要指出,这个结果依赖于量子特性,因此没有经典的对应结果。事实表明,我们的完全问题在研究完美零知识量子证明中有很多应用。操作迹距离是研究量子统计和完美零知识证明的一个基本工具。在这篇论文中,我们发现了一个有趣的逆转迹距离的方法。特别地,该方法有两个引人注目的特性:首先,我们的构造利用了量子纠缠;它的底层思想与一种称作退相干的普遍量子现象非常相似。其次,我们的构造有非黑盒的意味。