作者：杨超
本文地址：http://sokoban.ws/blog/?p=3757
量子计算机常被大众媒体描述得十分神奇，甚至有科学家也添油加醋，如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗？我在读了David Deutsch的书后，对此问题颇感兴趣。这个月，阅读了不少相关文献，找到了答案。答案是否定的。
首先，制造出通用的量子计算机仍然有极大的工程技术困难。
第二，再看看理论上，量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法，这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出（Shor因此获得哥德尔奖Godel Prize），历史也没有太长。想要知道这一算法与传统计算机算法有何不同，可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年，才36岁，是德州大学奥斯汀分校的教授，在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律，量子算法恰恰能更好地利用这一规律，一定程度上避免了暴力穷举。
要注意的是，整数分解并非特别难的问题。在基于传统计算机（图灵机）的计算复杂度理论中，整数分解被认为不属于P，但也只是比P问题略难一些，介于P和NP-Complete之间，且更靠近P。因此，量子算法能快速分解大数也只是情理之中。
知道量子算法是怎么做的，能做什么，就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话，澄清大众对量子计算的误解：
If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.
这句话翻译过来就是：如果你想从我的博客中只学一样东西，那就是量子计算机无法通过同时尝试所有可能来求解困难的搜索问题。
这句话简直是针对本文开头的问题的完美回答。就算大规模的量子计算机制造出来了，NP完全问题也不可能有快速算法，更不用说比NP完全问题更难的推箱子（PSPACE完全问题）了。
第三，有和没有快速算法（efficient algorithm）的分界线在哪里呢？Scott Aaronson在NP-complete Problems and Physical Reality一文（发表在2005年ACM SIGACT News）中也有深刻独特的见解。除了量子计算，他还逐一考察了蛋白质计算等若干未来可能有物理实现的计算机模型。文章最后，他给出了如下的一条分界线：
基于图灵机提出的P问题类也许未能很好的刻画有快速算法问题全体。具有快速算法的问题应该更广泛些，包含整数分解和图同构等。这也许是一条深刻的物理规律。