Physical Review Letters

量子计算机探幽

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

量子计算的概念，最早是由费恩曼提出的，从那以后计算机科学家们已经在这个领域里有了不小的进展。量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。量子计算机的基本特征之一，就是它使用的信息单元不是比特，而是量子比特（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们学的全都是量子算法。

等待量子计算机

现在或许还无法准确预测“量子计算时代”何时到来，但在科学家看来，已经没有什么原则性的困难可以阻挡这种革命性产品的问世了

　　【网络版专稿/《财经》杂志记者 于达维】在世界各大银行的技术部门里，总有一群人在日以继夜地研制新一代的密码。他们共同的“终极”目标，就是能有一套不被破解的密码。
　　当然，也许现在所有的密码对于未来的量子计算机来说，都显得不堪一击。因为即使与目前最先进的巨型计算机相比，它的功能也显得异乎寻常的强大，几乎相当于后者的10亿倍。
　　正是由于其梦幻般的性能，从上世纪60年代起，全球的物理学家和数学家就开始以巨大的热情，在理论上以及通过实验探讨量子计算机的可行性。
　　不过，到底什么时候实现突破，大家心里似乎也没有底。国际量子计算研究先驱、奥地利因斯布鲁克大学皮特·祖勒（Peter Zoller）教授就曾经有些无奈地表示，“量子计算机的出现，可能要10年，也可能要1000年；谁也不知道。除非有什么石破天惊的突破”。
　　2007年11月8日出版的英国《自然》杂志，破天荒的同时刊登了两个类似的发现——来自法国和瑞士的两个研究小组都找到了利用不同量子状态的光子操纵铷原子团的方法。或许，这将在人类实现量子计算机的梦想之路上，迈出决定性的一步。

并行致胜
　　对于我们目前正使用的计算机而言，其计算原则是非常简单的，那就是通过控制电位的高低，来决定一个数据到底是0还是1。
　　而量子计算机与之最大的区别在于，它的每个数据位用微观的量子态表示。量子态同我们肉眼所见的经典状态有很大不同，根据量子力学的原理，量子态可以处于不同本征量子态的叠加。因此，如果说经典计算机存储数据的最小单位是比特的话，那么量子计算机存储数据的最小单位就是量子比特。量子比特可以处于0和1两种状态的叠加。
　　“所以量子计算没有一个确定的输入，也没有一个确切的结果。但是，根据这些概率性的输出，人们可以找到自己想要的答案。”中国科技大学量子信息重点实验室副主任周正威对《财经》表示。不过，由于这种叠加状态的存在，量子计算机就可以同时进行很多条路径的计算，然后给出一个大致的结果。
　　比如用4个量子比特，可以同时描述16种状态，输入的数据就是16种可能的叠加状态，输出的结果也是16种结果的叠加状态。量子计算的特性，就是可以在很短的时间内得到大致的结果；只要再重复几次，就能得到大致精确的结果。
　　短到什么程度？从理论上说，1个400位长的数分解成素数乘积，如果采用巨型机需10亿年，而用量子计算机只要一年便可得出结果。
　　目前世界上最流行的RSA加密体系，依赖的就是选择两个100位以上的素数，得到它们的乘积。要破解这个密码，就要根据这个乘积找到原始的两个乘数。用经典计算机进行因数分解时，这个数每增加一位，寻找它的因数的时间就要增加大约一倍；而用量子计算机的话，每增加一位计算机所需的时间增量则是一个常量。
　　目前的传统计算机能够实现的大数因子分解只能达到140位，对200位以上的大数尚无能为力。但对于量子计算机来说，简直不费吹灰之力。有了它，现在全球大多数的民用保密系统都可以轻易攻破。

低温光陷阱
　　量子计算机成为现实需要克服的最大障碍，或许就是如何让宏观世界的我们去操作微观世界的粒子。因为从理论上说，只有尺度到了10的负10次方米以下，粒子才能明显出现量子特性；当然，最理想的是能够操作单个原子。
　　目前可以作为量子研究对象的，包括原子和光腔相互作用、冷阱束缚离子、电子或核自旋共振、量子点操纵、超导量子干涉等。 描述量子状态的方式，可以是粒子自旋的方向，或者能级的高低。现在从理论上研究量子计算机的物理实现的体系有几十种，作为实验研究方向的有十余种。
　　由法国和瑞士科学家所实现的量子操作，是用不同能量的光子，照射束缚在有相对的反射镜构成的光陷阱中的低温铷原子团；原子团的能级被改变，就是“写”操作，因为这些原子由于玻色－爱因斯坦凝聚而呈相同的状态。
　　瑞士苏黎世量子电动力学研究所的蒂尔曼·艾斯林格（Tilman Esslinger）解释说，在低温玻色－爱因斯坦凝聚下，铷原子团不存在热漂移，所以它存储的数据能够维持更长的时间。他们所设计的光陷阱只有0.04微米宽，是利用激光蒸发金属附着在光纤表面构成。
　　当然，目前被应用更广泛的方法还是利用电场或磁场操作电子自旋状态，来实现量子操作。
　　今年11月1日，荷兰代夫特技术大学科学家在美国科学促进会《科学快报》网站上，发布研究结果称，他们利用电场成功地控制了单个电子的自旋，这种方法相比用磁场控制电子自旋更加简便。
　　目前，量子计算机还有几大障碍难以跨越：一是如何让粒子长时间保持量子状态，即保持相干性；二是如何让尽量多的粒子实现共同计算，即实现可集成性。
　　因为处于量子状态的粒子，往往由于与周围环境的相互作用而失去量子特性，这一过程称为“退相干”。中国科学技术大学量子信息重点实验室主任郭光灿院士对《财经》记者表示，基于量子光学的量子计算，包括操作束缚在腔、离子阱中的原子和离子或者原子、离子的能级等，可以解决相干性的问题，却难以实现集成。
　　而包括超导量子干涉或半导体材料量子点的操作，自旋、能级、磁通量、相位都可以作为可操作的目标的固态量子计算，虽然容易扩充形成纠缠，但相干性又不好。

何时实现？
　　量子编码是迄今发现的克服退相干最有效的方法。主要的几种量子编码方案，包括量子纠错码、量子避错码和量子防错码等。所谓纠错码技术，就是在粒子退相干发生在一定限度内的时候，改正退相干造成的错误，让量子计算继续下去。
　　为了让尽量多的粒子实现共同计算，就要让这些粒子保持纠缠状态，而这是相当困难的。因为量子的纠缠状态极易溃散，且粒子数量越多越难实现量子的纠缠。
　　早在2000年，IBM和斯坦福大学就联合实现个5个量子比特的量子计算机雏形，并利用它成功找出一个函数的周期。2001年年底，他们又实现了7个量子比特的量子计算机，并成功把15分解成了3和5两个素数的乘积。
　　2007年2月，加拿大D波（D-Wave）系统公司声称制造出了首个商业量子计算机——具有16个量子字节的猎户计算机（Orion Computer），它由铝和铌超导材料制成，可以对数据库进行简单的搜索，该公司计划2008年开始出售这款计算机。
　　D波公司声称，他们成功地通过绝热量子计算技术将退相干（Decoherence）效应降到了最低程度，从而使得量子计算机能够缓慢而连续地工作。
　　不过，在中国科技大学量子信息重点实验室副主任周正威看来，在该公司的成果被正式的同行评议接受之前，还不能确定他们是否真的实现。“当然，如果是真的，那真得很了不起”，周正威说。
　　但“绝热量子计算”与标准的量子计算机模型还有差别，虽然在大规模下两者的能力是相同的，但是，绝热量子计算的硬件规模要数倍于标准量子计算模型。于是，可扩展性依然是个问题。
　　今年10月26日，中科院量子信息重点实验室郭光灿院士领导的研究小组在美国《物理评论快报》上发表文章，证明“量子开关”可以被局域识别，为研究量子计算和量子通信的可重复性给出了理论证明。
　　当时有媒体曾经报道了郭的预测，称15年内量子计算机将会实用化。但郭光灿在接受《财经》采访时表示，现在预测是没什么价值的，谁也不能保证。肯定不至于要1000年，因为“现在已经没什么原则性困难了”。
　　按照目前对于传统计算机的预测，摩尔定律在10年后就要失效。要进一步提高计算能力，除增加更多的核进行多核计算之外，量子计算机仍然是最值得期待的“革命者”。■