时间机器上的计算 - Quantum Computing Since Democritus 19th
来源：Scott Aaronson的Quantum Computing Since Democritus的第19次课程。Aaronson是MIT的年青教授，也是理论计算机届的Terry Tao。美国大学课程的开放性和创造性由这门课程便可看出。
注：此文不是翻译，加入作者本人之理(误)解以及大量删减；略去很多物理背景（我也不懂），有兴趣者可阅读课程笔记原文（英文）。
人们想知道在计算中，NP问题，比如哈密尔顿回路问题（判断一个图是否有圈经过每个顶点恰好一次），是否可以在多项式时间内被解决。即使引入量子计算后，这个问题也一直悬而未决，成为千禧年七大问题之首。
如果我们在时间本身上做手脚呢？
比如在相对论中，不同物体的时间流逝不一样，如果我们能让计算机在时间流逝上快很多，那我们也变相得解决了这个问题，不是么？
很可惜，根据相对论原理，
要使计算机进行指数级的加速，必须让速度指数级接近于光速，这也意味着所需要的能量指数级增长，而因为能量密度不可能大于黑洞，这也意味着计算机的大小必须指数级增长，某种程度上来说就是EXPSPACE，这是不可取的(建造指数级数量的计算机同时计算可达到同样效果)。
但更进一步的，如果我们允许时间旅行呢？
时间旅行，时空空间的闭圈，简记为CTCs（closed timelike curves），在现有物理理论中，还是相容的。我们假设CTC是可行的（量子计算理论的研究也要大大早于真正的量子计算机的出现），我们能解决什么样的问题？
一个很自然的想法就是让计算机持续计算，直到算出结果后再把结果发回来。但这样并没有改变真实计算时间。这好像你透支你的信用卡的钱一样，只不过提前支取罢了。
所以一个不那么naive的方法是把让计算机以一段时间比如1小时为限，算满1小时后把结果和进度发回来，然后计算机接着算。这样也貌似可以解决一切问题？
而这个的正确性不是那么显然的。在分析这个算法之前，我们必须讨论如果CTC存在，会是什么样子。
时间旅行的一大悖论就是祖父悖论，想想一个人回到过去杀死自己的祖父，会发生什么？这也是时间旅行理论的最大挑战。我们这里采取David Deutsch提出的理论。这个理论认为在量子机制框架下，CTC是自洽的。简单的解释下，就是这个世界是个概率空间，以markov过程的方式进行运作，如果每次新的概率分布和原来的一样，就可以避免祖父悖论了。
Deutsch在这个理论中需要causal consistency，在CTC的运行中，一切都将自洽(consistency)：新的概率分布总和原来保持一致。在经典理论中，这是不可能的。但在概率模型里面，markov过程的稳定分布则是一组解。在祖父模型中，如果你出生的概率是1/2，而且如果出生的话，则会去杀死祖父，那么你出生的概率仍然是1/2，没有任何矛盾。
接下来就是纯粹理论计算机上的结果了，记PCTC 为允许时间旅行的多项式时间可计算的问题，BQPCTC是时间旅行机器结合量子计算机时多项式时间可计算的问题。那么有意思的是：
PCTC = BQPCTC = PSPACE
也就是说它们的能力是可以被精确确定的，而且远达不到无限。
注：详细证明和描述见原文。
习题：
- 如果有时间旅行机器的帮助，但这个机器的能力极为有限，每次只允许发回一个bit(0和1)的信息。问这台机器对于计算的帮助有多大？ 它能帮助解决NP问题吗？
的计算及纪录
呃，连时间都弄进来了啊:-) How desperate are they?
看得不是很懂……
觉得有点虚幻
时间旅行这种东西八字还没一撇呢……我不认为相对论已经给时间旅行提供了清晰的解释
量子场论就允许逆时间旅行。它对反粒子的描述就是逆时而行的原来的粒子。
相对论里面的论述我觉着有问题，事实上随速度增加而飚涨的是质量，理解成能量也可，就是我们推动计算机加速作的功，应该与大小无关。事实上高速行进时尺度会缩小。质量的增加也和造更多的计算机不等同，事实上做功很简单，要做出很多计算机就难了。而且我们无须把计算机加速到趋近光速，只要大一点即可，比如v=根号3/2，相对论因子就是1/2了。
考虑一下高速飞行的运算，假如我们假定计算机最后要回到你身边，就是你要回收发出去的它，那么就跟广义相对论中的双生子佯谬差不多，这个已经用miu子的环路实验证实，高速飞出而后又回到你身边的东西时间的运行会变慢，也就是说实际上不仅没加速计算，反而慢了。。。
如果采取发射光子来交换信息的方法，我计算了一下也是不行的，更慢。
进不了英文的原文连接，不知道原文是怎么讲这个的。。。
欢迎拍砖。
物理的东西我也不太懂。但关于那个能量我是这样理解的：要把计算机加速到指数级接近于光速，必须要指数级的能量供应。但是物理上已经知道（？）“燃料”的能量密度是有限的（上限就是黑洞的能量密度），所以这台计算机必须使用指数级的能量箱，也就是文中所说大小为指数级别的，而不是说相对论效应的大小。
至于你后面所说的，我不太懂
英文原文我在香港可以看，难道是被封了么？文中有公式和图片，我也没法贴。你用破墙软件试试看？
燃料的话，假定的是象火箭一样自身携带，但实际上我们可以用外在的力来推动。夸张的说，让计算机带点电荷然后让加速器来加速也未尝不可（理论上，基本粒子和计算机没什么不同）。。不过无论如何，相对论的时间变换方式应该不可能让指数级运算变为多项式的。。。
顺便问句：陆品燕是您的同学么？我算是他学弟，来自同一中学的同一个班。。。
这么巧 :) 他是我同级同学，而且他的research做得可好了，在我们这里顶尖的。生日那个帖子留言里的alvin就是他。
那个燃料问题，无论你用什么来提供能量，能量箱都必须要指数级大小，无论你放在哪，本质上没有区别。
呵呵。。。他在我们学校已经成为近乎神话的存在。我也来自10班，我们学校一贯的理科班，只是比他低了7届。不知有何方法能联系他？
能量那个我是错了，不过似乎不应该跟黑洞类比，黑洞是无穷大，而我们需要的是正常物质中密度最大的，而现在看来密度是有极限的（中子星）然后此设想就废了。