量子计算机探幽

量子计算机是一个令人神往的东西，虽然目前还没有实际制成量子计算机，但是他却成了我一直翘首以待的产品。量子计算机可以算是不同于我们现在的普通计算机的下一代计算机，它可以解决许多传统计算机没法有效解决的问题。

量子计算的概念，最早是由费恩曼提出的，从那以后计算机科学家们已经在这个领域里有了不小的进展。量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。量子计算机的基本特征之一，就是它使用的信息单元不是比特，而是量子比特（qubit）。量子比特可以是电子那样的粒子。可以让自旋向上代表1，自旋向下代表0。与传统计算机不同的是，电子可以处于自旋向上和向下的叠加态，即1和0的叠加态。处于叠加态的少量粒子可以携带大量信息。假如我们可以控制仅仅1000个量子比特，那我们也可以用之表示出从1到2^1000的所有数字，并且可以同时对所有数字进行操作，也就是所谓的并行计算。虽然当我们最终读取量子状态时，只能从2^1000个状态中随机的读取其中的一个，而其他的状态都会消失，但是我们可以通过对粒子进行巧妙的处理，用量子计算机求解一些普通计算机没法有效求解的问题，例如对大数分解质因数。用现有的计算机需要花10亿年才能算出来的题，可能用量子计算机花不到一年的就能成功解决。

正是因为用量子计算机可以非常有效的解决对大数分解质因数的问题，现在的密码安全将在不久的将来量子计算机问世的时候轰然瓦解。现在最常用的加密方法当属RSA公钥算法，这个算法就是基于“把两个大质数相乘极为简单，但是要把这个乘积分解为这两个大质数则几乎无法做到”这一事实，具体的算法可以参见《算法导论》有关章节。有了量子计算机的话，我们就不得不重新设计一种量子计算机也无法完成的运算了。

很多人对量子计算机有所误解，认为它可以解决一切困难的数学问题。事实不是如此，量子计算机能解决的问题，也仅仅是一小部分特殊问题。计算机科学家已经证明了，传统计算机能够有效解决的所有问题，用量子计算机同样能够有效解决。但是，对于计算机科学领域里的一类非常重要的问题——NPC问题，量子计算机和普通计算机一样是无能为力的。生活和生产中有很多极为重要的问题不幸属于NPC类。虽然我们还没有真正证明量子计算机不能胜任，正如我们还无法证明P到底等不等于NP一样，但是无数失败的尝试表明，量子计算机在这类问题上比普通计算机好不到哪里去。（如果你第一次听说P、NP、NPC，那么我建议你看一看Matrix67的这篇文章，那里有比较详细系统的介绍。简单来说：P是多项式级时间复杂度能找到解的问题，即所说的普通计算机能够“有效解决”的问题；NP是多项式时间复杂度内可以验证解的正确性的问题，但不一定能在多项式级时间复杂度内找到解；所有的NP问题都可以归约到NPC问题，即一旦解决了一个NPC问题则所有NP问题随之解决）。我们称量子计算机能够有效解决的问题为BQP类问题，这几类问题之间的关系如下图：



量子计算机似乎代表着人类计算能力的极限，除非有全新的物理定律在将来被发现。有趣的是，通过量子计算机不能有效解决NPC问题，有人甚至类比于超光速通讯不可能实现和热力学第二定律，说NPC问题无法有效解决是一条基本的不可逾越的物理定律！

尽管量子计算机不像人们期盼的那样属于万能计算机，尽管他也有很多力不从心的时候，但量子计算机依然是一个很有前途的研究方向。用量子计算机，我们可以击毁敌国的安全系统，可以模拟量子物理系统，可以为芯片的研究提供重要价值，可以更深刻的理解量子理论，或许还有很多我们未曾期待的应用（正如当时建造第一个计算机时没人想得到现在繁荣的信息化社会）……

实际在建造量子计算机的过程中，遇到的困难是难以想象的。甚至曾经有很多人以为这是不可能完成的事情。但是，经过无数科学家、工程师的努力，目前的进展还是可喜的。虽然目前还没有一台计算机算是严格意义上的量子计算机，但是，IBM公司2001年构建了可以操作7个量子比特的“量子计算机”，2008年D-Wave公司的首席技术官Geordie Rose在他的blog上宣布他们将展示一个具有16个qubit的量子计算机。道路是曲折的，但前途是光明的！

真希望等我长大的时候，家家都有量子计算机，OIer们学的全都是量子算法。