量子计算机

　　理论背景

　　有趣的量子理论

　　量子论的一些基本论点显得并不“玄乎”，但它的推论显得很“玄”。我们假设一个“量子”距离也就是最小距离的两个端点A和B。按照量子论，物体从A不经过A和B中的任何一个点就能直接到达B。换句话说，物体在A点突然消失，与此同时在B点出现。除了神话，你无法在现实的宏观世界找到一个这样的例子。量子论把人们在宏观世界里建立起来的“常识”和“直觉”打了个七零八落。

　　薛定谔之猫是关于量子理论的一个理想实验。实验内容是：这只猫十分可怜，它被封在一个密室里，密室里有食物有毒药。毒药瓶上有一个锤子，锤子由一个电子开关控制，电子开关由放射性原子控制。如果原子核衰变，则放出α粒子，触动电子开关，锤子落下，砸碎毒药瓶，释放出里面的氰化物气体，猫必死无疑。这个残忍的装置由奥地利物理学家埃尔温·薛定谔所设计，所以此猫便叫做薛定谔猫。量子理论认为：如果没有揭开盖子，进行观察，我们永远也不知道猫是死是活，它将永远处于非死非活的叠加态，这与我们的日常经验严重相违。

　　瑞典皇家科学院2012年10月9日宣布，将2012年诺贝尔物理学奖授予法国物理学家塞尔日·阿罗什和美国物理学家戴维·瓦恩兰，以表彰他们在量子物理学方面的卓越研究。他说，这两位物理学家用突破性的实验方法使单个粒子动态系统可被测量和操作。他们独立发明并优化了测量与操作单个粒子的实验方法，而实验中还能保持单个粒子的量子物理性质，这一物理学研究的突破在之前是不可想象的。

　　研究历史

　　量子计算机，早先由理查德·费曼提出，一开始是从物理现象的模拟而来的。可他发现当模拟量子现象时，因为庞大的希尔伯特空间使资料量也变得庞大，一个完好的模拟所需的运算时间变得相当可观，甚至是不切实际的天文数字。理查德·费曼当时就想到，如果用量子系统构成的计算机来模拟量子现象，则运算时间可大幅度减少。量子计算机的概念从此诞生。

　　量子计算机，或推而广之——量子资讯科学，在1980年代多处于理论推导等纸上谈兵状态。一直到1994年彼得·秀尔（Peter Shor）提出量子质因子分解算法[3] 后，因其对通行于银行及网络等处的RSA加密算法破解而构成威胁后，量子计算机变成了热门的话题。除了理论之外，也有不少学者着力于利用各种量子系统来实现量子计算机。

　　20世纪60年代至70年代，人们发现能耗会导致计算机中的芯片发热，极大地影响了芯片的集成度，从而限制了计算机的运行速度。研究发现，能耗来源于计算过程中的不可逆操作。那么，是否计算过程必须要用不可逆操作才能完成呢？问题的答案是：所有经典计算机都可以找到一种对应的可逆计算机，而且不影响运算能力。既然计算机中的每一步操作都可以改造为可逆操作，那么在量子力学中，它就可以用一个幺正变换来表示。早期量子计算机，实际上是用量子力学语言描述的经典计算机，并没有用到量子力学的本质特性，如量子态的叠加性和相干性。在经典计算机中，基本信息单位为比特，运算对象是各种比特序列。与此类似，在量子计算机中，基本信息单位是量子比特，运算对象是量子比特序列。所不同的是，量子比特序列不但可以处于各种正交态的叠加态上，而且还可以处于纠缠态上。这些特殊的量子态，不仅提供了量子并行计算的可能，而且还将带来许多奇妙的性质。与经典计算机不同，量子计算机可以做任意的幺正变换，在得到输出态后，进行测量得出计算结果。因此，量子计算对经典计算作了极大的扩充，在数学形式上，经典计算可看作是一类特殊的量子计算。量子计算机对每一个叠加分量进行变换，所有这些变换同时完成，并按一定的概率幅叠加起来，给出结果，这种计算称作量子并行计算。除了进行并行计算外，量子计算机的另一重要用途是模拟量子系统，这项工作是经典计算机无法胜任的。

　　1994年，贝尔实验室的专家彼得·秀尔（Peter Shor）证明量子计算机能完成对数运算，而且速度远胜传统计算机。这是因为量子不像半导体只能记录0与1，可以同时表示多种状态。如果把半导体计算机比成单一乐器，量子计算机就像交响乐团，一次运算可以处理多种不同状况，因此，一个40位元的量子计算机，就能解开1024位元的电子计算机花上数十年解决的问题。

　　随着计算机科学的发展，史蒂芬·威斯纳在1969年最早提出“基于量子力学的计算设备”。而关于“基于量子力学的信息处理”的最早文章则是由亚历山大·豪勒夫（1973）、帕帕拉维斯基（1975）、罗马·印戈登（1976）和尤里·马尼（1980）年发表。史蒂芬·威斯纳的文章发表于1983年[8]。1980年代一系列的研究使得量子计算机的理论变得丰富起来。1982年，理查德·费曼在一个著名的演讲中提出利用量子体系实现通用计算的想法。紧接着1985年大卫·杜斯提出了量子图灵机模型 [9]。人们研究量子计算机最初很重要的一个出发点是探索通用计算机的计算极限。当使用计算机模拟量子现象时，因为庞大的希尔伯特空间而数据量也变得庞大。一个完好的模拟所需的运算时间则变得相当可观，甚至是不切实际的天文数字。理查德·费曼当时就想到如果用量子系统所构成的计算机来模拟量子现象则运算时间可大幅度减少，从而量子计算机的概念诞生。

　　算法理论

　　经典算法

　　量子计算机在1980年代多处于理论推导状态。1994年彼得·秀尔（Peter Shor）提出量子质因子分解算法后，因其对于通行于银行及网络等处的RSA加密算法可以破解而构成威胁之后，量子计算机变成了热门的话题，除了理论之外，也有不少学者着力于利用各种量子系统来实现量子计算机。

　　半导体靠控制集成电路来记录及运算信息，量子计算机则希望控制原子或小分子的状态，记录和运算信息。 1994年，贝尔实验室的专家彼得·秀尔（Peter Shor）证明量子计算机能做出离散对数运算[11]，而且速度远胜传统计算机。因为量子不像半导体只能记录0与1，可以同时表示多种状态。如果把半导体比成单一乐器，量子计算机就像交响乐团，一次运算可以处理多种不同状况，因此，一个40比特的量子计算机，就能在很短时间内解开1024位计算机花上数十年解决的问题。

　　通用计算

　　量子计算机，顾名思义，就是实现量子计算的机器。是一种使用量子逻辑进行通用计算的设备。不同于电子计算机（或称传统电脑），量子计算用来存储数据的对象是量子比特，它使用量子算法来进行数据操作。

　　要说清楚量子计算，首先看经典计算机。经典计算机从物理上可以被描述为对输入信号序列按一定算法进行变换的机器，其算法由计算机的内部逻辑电路来实现。

　　1.其输入态和输出态都是经典信号，用量子力学的语言来描述，也即是：其输入态和输出态都是某一力学量的本征态。如输入二进制序列0110110，用量子记号，即|0110110>。所有的输入态均相互正交。对经典计算机不可能输入如下叠加态：C1|0110110 >+ C2|1001001>。

　　2.经典计算机内部的每一步变换都演化为正交态，而一般的量子变换没有这个性质，因此，经典计算机中的变换（或计算）只对应一类特殊集。

　　相应于经典计算机的以上两个限制，量子计算机分别作了推广。量子计算机的输入用一个具有有限能级的量子系统来描述，如二能级系统（称为量子比特（qubits）），量子计算机的变换（即量子计算）包括所有可能的幺正变换。

　　1.量子计算机的输入态和输出态为一般的叠加态，其相互之间通常不正交；

　　2量子计算机中的变换为所有可能的幺正变换。得出输出态之后，量子计算机对输出态进行一定的测量，给出计算结果。

　　　由此可见，量子计算对经典计算作了极大的扩充，经典计算是一类特殊的量子计算。量子计算最本质的特征为量子叠加性和量子相干性。量子计算机对每一个叠加分量实现的变换相当于一种经典计算，所有这些经典计算同时完成，量子并行计算。

　　无论是量子并行计算还是量子模拟计算，本质上都是利用了量子相干性。遗憾的是，在实际系统中量子相干性很难保持。在量子计算机中，量子比特不是一个孤立的系统，它会与外部环境发生相互作用，导致量子相干性的衰减，即消相干（也称“退相干”）。因此，要使量子计算成为现实，一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干最有效的方法。主要的几种量子编码方案是：量子纠错码、量子避错码和量子防错码。量子纠错码是经典纠错码的类比，是目前研究的最多的一类编码，其优点为适用范围广，缺点是效率不高。

　　正如大多数人所了解的，量子计算机在密码破解上有着巨大潜力。当今主流的非对称（公钥）加密算法，如RSA加密算法，大多数都是基于于大整数的因式分解或者有限域上的离散指数的计算这两个数学难题。他们的破解难度也就依赖于解决这些问题的效率。传统计算机上，要求解这两个数学难题，花费时间为指数时间（即破解时间随着公钥长度的增长以指数级增长），这在实际应用中是无法接受的。而为量子计算机量身定做的秀尔算法可以在多项式时间内（即破解时间随着公钥长度的增长以k次方的速度增长，其中k为与公钥长度无关的常数）进行整数因式分解或者离散对数计算，从而为RSA、离散对数加密算法的破解提供可能。但其它不是基于这两个数学问题的公钥加密算法，比如椭圆曲线加密算法，量子计算机还无法进行有效破解 。

　　针对对称（私钥）加密，如AES加密算法，只能进行暴力破解，而传统计算机的破解时间为指数时间，更准确地说，是 ，其中 为密钥的长度。而量子计算机可以利用Grover算法进行更优化的暴力破解，其效率为 ，也就是说，量子计算机暴力破解AES-256加密的效率跟传统计算机暴力破解AES-128是一样的。

　　更广泛而言，Grover算法是一种量子数据库搜索算法，相比传统的算法，达到同样的效果，它的请求次数要少得多。对称加密算法的暴力破解仅仅是Grover算法的其中一个应用。

　　在利用EPR对进行量子通讯的实验中科学家发现，只有拥有EPR对的双方才可能完成量子信息的传递，任何第三方的窃听者都不能获得完全的量子信息，正所谓解铃还需系铃人，这样实现的量子通讯才是真正不会被破解的保密通讯。

　　此外量子计算机还可以用来做量子系统的模拟，人们一旦有了量子模拟计算机，就无需求解薛定谔方程或者采用蒙特卡罗方法在经典计算机上做数值计算，便可精确地研究量子体系的特征。

　　研发情况

　　发展趋势

　　用原子实现的量子计算机只有5个q-bit，放在一个试管中而且配备有庞大的外围设备，只能做1+1=2的简单运算，正如Bennett教授所说，“现在的量子计算机只是一个玩具，真正做到有实用价值的也许是5年，10年，甚至是50年以后”，我国量子信息专家中国科技大学的郭光灿教授则宣称，他领导的实验室将在5年之内研制出实用化的量子密码，来服务于社会！科学技术的发展过程充满了偶然和未知，就算是物理学泰斗爱因斯坦也决不会想到，为了批判量子力学而用他的聪明大脑假想出来的EPR态，在六十多年后不仅被证明是存在的，而且还被用来做量子计算机。在量子的状态下不需要任何计算过程，计算时间，量子进行空间跳跃。可以说量子芯片，是终极的芯片

　　外国进展

　　1920年，奥地利人埃尔温·薛定谔、爱因斯坦、德国人海森伯格和狄拉克，共同创建了一个前所未有的新学科——量子力学。量子力学的诞生为人类未来的第四次工业革命打下了基础。在它的基础上人们发现了一个新的技术，就是量子计算机。

　　量子计算机的技术概念最早由理查得·费曼提出，后经过很多年的研究这一技术已初步见成效。

　　美国的洛斯阿拉莫斯和麻省理工学院、IBM、和斯坦福大学、武汉物理教学所、清华大学四个研究组已实现7个量子比特量子算法演示。

　　2001年，科学家在具有15个量子位的核磁共振量子计算机上成功利用秀尔算法对15进行因式分解。

　　2005年，美国密歇根大学的科学家使用半导体芯片实现离子囚笼（ion trap）。

　　2007年2月，加拿大D-Wave系统公司宣布研制成功16位量子比特的超导量子计算机，但其作用仅限于解决一些最优化问题，与科学界公认的能运行各种量子算法的量子计算机仍有较大区别。

　　2009年，耶鲁大学的科学家制造了首个固态量子处理器。

　　2009年11月15日，世界首台可编程的通用量子计算机正式在美国诞生。同年，英国布里斯托尔大学的科学家研制出基于量子光学的量子计算机芯片，可运行秀尔算法。

　　2010年3月31日，德国于利希研究中心发表公报：德国超级计算机成功模拟42位量子计算机，该中心的超级计算机JUGENE成功模拟了42位的量子计算机，在此基础上研究人员首次能够仔细地研究高位数量子计算机系统的特性。

　　2011年4月，一个成员来自澳大利亚和日本的科研团队在量子通信方面取得突破，实现了量子信息的完整传输。[8] 2011年5月11日, 加拿大的D-Wave System Inc. 发布了一款号称 “全球第一款商用型量子计算机”的计算设备“D-Wave One”。该量子设备是否真的实现了量子计算还没有得到学术界广泛认同。同年9月，科学家证明量子计算机可以用冯·诺依曼架构来实现。同年11月，科学家使用4个量子位成功对143进行因式分解。

　　2012年2月，IBM声称在超导集成电路实现的量子计算方面取得数项突破性进展。 同年4月，一个多国合作的科研团队研发出基于金刚石的具有两个量子位的量子计算机，可运行Grover算法，在95%的数据库搜索测试中，一次搜索即得到正确答案。该研究成果为小体积、室温下可正常工作的量子计算机的实现提供可能。同年9月，一个澳大利亚的科研团队实现基于单个硅原子的量子位，为量子储存器的制造提供了基础。 同年11月，首次观察到宏观物体中的量子跃迁现象。

　　2013年5月D-Wave System Inc宣称NASA和Google共同预定了一台采用512量子位的D-Wave Two量子计算机。

　　国内突破

　　2013年6月8日，由中国科学技术大学潘建伟院士领衔的量子光学和量子信息团队首次成功实现了用量子计算机求解线性方程组的实验。相关成果发表在2013年6月7日出版的《物理评论快报》上，审稿人评价“实验工作新颖而且重要”，认为“这个算法是量子信息技术最有前途的应用之一”。据介绍，线性方程组广泛应用于几乎每一个科学和工程领域。日常的气象预报，就需要建立并求解包含百万变量的线性方程组，来实现对大气中温度、气压、湿度等物理参数的模拟和预测。而高准确度的气象预报则需要求解具有海量数据的方程组，假使求解一个亿亿亿级变量的方程组，即便是用现在世界上最快的超级计算机也至少需要几百年。[1] 美国麻省理工学院教授塞斯·罗伊德等提出了用于求解线性方程组的量子算法，利用GHz时钟频率的量子计算机将只需要10秒钟。该研究团队发展了世界领先的多光子纠缠操控技术。实验的成功标志着我国在光学量子计算领域保持着国际领先地位。

　　工作原理

　　普通的数字计算机在0和1的二进制系统上运行，称为“比特”（bit）。但量子计算机要远远更为强大。它们可以在量子比特（qubit）上运算，可以计算0和1之间的数值。假想一个放置在磁场中的原子，它像陀螺一样旋转，于是它的旋转轴可以不是向上指就是向下指。常识告诉我们：原子的旋转可能向上也可能向下，但不可能同时都进行。但在量子的奇异世界中，原子被描述为两种状态的总和，一个向上转的原子和一个向下转的原子的总和。在量子的奇妙世界中，每一种物体都被使用所有不可思议状态的总和来描述。

　　想象一串原子排列在一个磁场中，以相同的方式旋转。如果一束激光照射在这串原子上方，激光束会跃下这组原子，迅速翻转一些原子的旋转轴。通过测量进入的和离开的激光束的差异，我们已经完成了一次复杂的量子“计算”，涉及了许多自旋的快速移动。

　　从数学抽象上看，量子计算机执行以集合为基本运算单元的计算，普通计算机执行以元素为基本运算单元的计算（如果集合中只有一个元素，量子计算与经典计算没有区别）。

　　以函数y=f(x)，x∈A为例。量子计算的输入参数是定义域A，一步到位得到输出值域B，即B=f(A)；经典计算的输入参数是x，得到输出值y，要多次计算才能得到值域B，即y=f(x)，x∈A，y∈B。[1]

　　量子计算机有一个待解决的问题，即输出值域B只能随机取出一个有效值y。虽然通过将不希望的输出导向空集的方法，已使输出集B中的元素远少于输入集A中的元素，但当需要取出全部有效值时仍需要多次计算。

　　实际运用

　　D-Wave 量子计算机-首台商用量子计算机

　　在2007年，加拿大计算机公司D-Wave展示了全球首台量子计算机“Orion（猎户座）”，它利用了量子退火效应来实现量子计算。该公司此后在2011年推出具有128个量子位的D-Wave One型量子计算机并在2013年宣称NASA与谷歌公司共同预定了一台具有512个量子位的D-Wave Two量子计算机。

　　NSA加密破解计划

　　2014年1月3日，美国国家安全局（NSA）正在研发一款用于破解加密技术的量子计算机，希望破解几乎所有类型的加密技术。投入巨资 投入4.8亿进行“渗透硬目标”[1]

　　首台编程通用量子计算机

　　2009年11月15日，世界首台可编程的通用量子计算机正式在美国诞生。不过根据初步的测试程序显示，该计算机还存在部分难题需要进一步解决和改善。科学家们认为，可编程量子计算机距离实际应用已为期不远。

　　单原子量子信息存储首次实现

　　2013年5月，德国马克斯普朗克量子光学研究所的科学家格哈德·瑞普领导的科研小组，首次成功地实现了用单原子存储量子信息——将单个光子的量子状态写入一个铷原子中，经过180微秒后将其读出。最新突破有望助力科学家设计出功能强大的量子计算机，并让其远距离联网构建“量子网络”。

　　首次实现线性方程组量子算法

　　2013年6月8日，由中国科学技术大学潘建伟院士领衔的量子光学和量子信息团队的陆朝阳、刘乃乐研究小组，在国际上首次成功实现了用量子计算机求解线性方程组的实验。该研究成果发表在6月7日出版的《物理评论快报》上。

　　金刚石建成世界上首台量子计算机

　　2015年12月，以杜教授为首的中国科技大学研究人员小组建立了一个新的系统，这个系统可以使用相应的方式退出体系结构。比起普通二进制计算机，这一系统使得能够进行更为大量的计算。通常，这种系统都需要带有气候检测的特别装备实验室，而这一新模型却能够在普通的房屋内也能够安全存放。其量子计算能够在普通室温的条件下工作，这是借助于金刚石中少量的氮来完成的。

　　研究意义

　　迄今为止，世界上还没有真正意义上的量子计算机。但是，世界各地的许多实验室正在以巨大的热情追寻着这个梦想。如何实现量子计算，方案并不少，问题是在实验上实现对微观量子态的操纵确实太困难了。已经提出的方案主要利用了原子和光腔相互作用、冷阱束缚离子、电子或核自旋共振、量子点操纵、超导量子干涉等。还很难说哪一种方案更有前景，只是量子点方案和超导约瑟夫森结方案更适合集成化和小型化。将来也许现有的方案都派不上用场，最后脱颖而出的是一种全新的设计，而这种新设计又是以某种新材料为基础，就像半导体材料对于电子计算机一样。研究量子计算机的目的不是要用它来取代现有的计算机。量子计算机使计算的概念焕然一新，这是量子计算机与其他计算机如光计算机和生物计算机等的不同之处。量子计算机的作用远不止是解决一些经典计算机无法解决的问题。