The quantum challenge to structural complexity theory
The quantum challenge to structural complexity theory
复制标题
对结构复杂性理论的量子挑战
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
G. Brassard
中科院分区：
文献类型：
--
作者：
A. Berthiaume;G. Brassard
最近的量子力学发现的非技术调查，挑战普遍接受的复杂性理论版本的丘奇-图灵论文提出。特别是，作者构建了一个oracle，相对于它存在一个可以在量子多项式时间（QP）中识别的集合，然而任何识别它的图灵机都需要指数时间，即使允许是概率的，前提是不能容忍错误。特别是，相对于该oracle， QP不包含在或不等于ZPP。此外，有一些加密任务显然是不可能用无限计算能力的概率交互车床实现的，但它们甚至可以在实践中通过量子力学设备实现
A nontechnical survey of recent quantum-mechanical discoveries that challenge generally accepted complexity-theoretic versions of the Church-Turing thesis is presented. In particular, the authors construct an oracle relative to which there exists a set that can be recognized in quantum polynomal time (QP), yet any Turing machine that recognizes it would require exponential time even if allowed to be probabilistic, provided that errors are not tolerated. In particular, QP is not contained in or equal to ZPP relative to this oracle. Furthermore, there are cryptographic tasks that are demonstrably impossible to implement with unlimited computing power probabilistic interactive turning machines, yet they can be implemented even in practice by quantum mechanical apparatus.<<ETX>>