物理可计算理论

摘要：

近年来,将物理过程本身看作计算、用物理过程代替Turing机算法的想法,伴随着量子计算和其他一些非传统计算模式（例如DNA计算）的研究得到了一定程度的发展.然而由于概念上的不明晰,使得关于这类计算理论的复杂性评估一直处于含糊不清、模棱两可的状态.本文对输入／输出进行了统一，对物理实验的三个关键步骤：制备、演化和测量作了数学上的刻画，并由此引出物理可计算的形式定义（包括确定性的和非确定性的）．在此基础上给出了资源复杂性的概念，本文的资源是指一个物理过程消耗的总资源，不但包括了时间和空间，还包括了质量和能量．对于某个物理计算方法，相应的复杂性则描述了资源关于输入长度的增长情况．在这套形式理论中，以往非形式的“物理可计算”的例子可以在其中得到形式化地表达、且可作严格的复杂度分析．作为例子，考察了均值的统计力学求法、DNA计算和量子计算．在经典Church-Turing论题方面，对于前人试图用物理方法超越经典Turing机计算能力的著名例子，本文也在上述的理论框架下对它们的能行性进行了考察．我们认定：现有的这些例子因不能在有穷资源的限制内得到计算结果，从而都是无效的．

关键词：量子计算、物理可计算、计算复杂度

所属期刊栏目：58

分类号：TP301(计算技术、计算机技术)

资助基金：江苏省自然科学基金资助项目BK2010374

在线出版日期：2012-06-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：73-80