西蒙算法在量子计算机上“跑”得更快

浏览数：20 / 时间：2015年06月08日

来自南非的一组研究团队近日成功地在量子计算机上运行了西蒙算法(Simon’s algorithm),且这一算法在量子计算机上的运行表现比电子计算机表现得更好。相关论文刊登在《物理评论快报》上。量子计算机是一种基于量子力学的计算设备,用来存储数据的对象是量子比特而非经典计算机的电子比特。

科学界普遍认为,由于量子计算机能够利用量子纠缠和叠加等独特的量子物理属性,在运行某些特定算法时,它会比现有计算机更为快速和高效。遗憾的是,到目前为止,还没有办法在量子计算机上运行这些量子算法来检验这一理论。

西蒙算法便是适用于量子计算机算法中的一种,它由丹尼尔·西蒙20年前提出,认为这种算法能够挖掘量子计算机的加速潜力。西蒙算法的目的,是为了解决量子黑箱问题,即将执行计算任务的一段程序或者一个公式看作黑箱,看黑箱是否对每一个可能的输入给出一个唯一的输出。

据物理学家组织网11月18日(北京时间)报道,研究团队在一台量子计算机上运行了该算法的最简单版本,仅仅用了六个量子比特,量子计算机完成这一任务仅用了两次迭代,而普通计算机得用三次。这种区别似乎不算什么,但人们相信,如果增加更多量子比特,量子计算机和普通计算机运算能力的差别就会拉大,这也意味着,量子计算机能更快、更高效地解决此类算法问题。不过,还是要泼一盆冷水,到目前为止,能够运行西蒙算法并没有什么实际价值,该实验的唯一目的是证明量子计算机在一种算法上能够做得更好。

不过,也别太灰心,证明了类似算法在量子计算机上运行得更快,科研人员或可以期待,像肖尔算法(可被用来进行大数质因数分解,这是加密机制的重要组成部分)这样的量子算法在量子计算机上同样能“跑”得更快。

总编辑圈点

万事开头难。我们现在用量子计算机尝试“1+1”的小儿科,是期望有一天它能执行“消尔”算法,解开一切密码。量子计算机跟可控核聚变一样,属于概念上好理解,也有一点小小进展,但要实用就难上加难的科研项目。还好,量子计算机研究的门槛不像核聚变那么高,全世界的研究机构都可投身其中。如今还说不来,它究竟是镜花水月,还是会像手机那样迅速普及?十年后再看吧。