QUANTUM-THEORY, THE CHURCH-TURING PRINCIPLE AND THE UNIVERSAL QUANTUM COMPUTER
QUANTUM-THEORY, THE CHURCH-TURING PRINCIPLE AND THE UNIVERSAL QUANTUM COMPUTER
复制标题
DOI：
10.1098/rspa.1985.0070
复制
发表时间：
1985-01-01
期刊：
影响因子：
--
通讯作者：
DEUTSCH, D
中科院分区：
文献类型：
--
作者：
DEUTSCH, D
有人认为，潜在的丘奇-图灵假说有一个隐含的物理断言。在这里，这个断言被明确地作为一个物理原理提出：“每个可实现的物理系统都可以被一个通过有限手段运行的通用模型计算机完美地模拟”。经典物理学和通用图灵机，因为前者是连续的，后者是离散的，不服从原理，至少在上面的强形式中是这样。描述了一类模型计算机器，它是图灵机类的量子推广，并表明量子理论和“通用量子计算机”与该原理是兼容的。原则上，类似于通用量子计算机的计算机器可以被建造出来，并且具有许多图灵机无法复制的显着特性。这些不包括非递归函数的计算，但它们确实包括“量子并行”，一种方法，通过这种方法，通用量子计算机可以比任何经典限制更快地执行某些概率任务。对这些性质的直观解释对量子理论的所有解释都造成了无法忍受的压力，除了埃弗雷特的解释。量子计算理论和物理学的其余部分之间的许多联系进行了探讨。量子复杂性理论允许物理系统中的“复杂性”或“知识”的物理上比经典复杂性理论更合理的定义。
It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.