量子计算(二)量子计算

量子计算依靠量子计算机,但是当前我们可以看到的未来,量子计算机并不能取代经典计算机。量子计算不能解决经典计算机不能解决的数学难题,并且量子计算能解决的问题是有局限性的,经典问题不一定能利用量子计算机解决(如本博客上一篇所属,其优势在于依靠状态叠加来穷举)。量子计算固然速度快,但是如果把这些数据存入导出是严峻的问题。并且量子计算存在噪声影响,所以可纠错的量子计算机才具有商用价值(换句话说,量子计算机在未来相当长的一段时间内都没有商用价值)。与量子计算配套的算法和软件都需要重新设计,会是崭新的方向。博主摘抄一篇文章,看完之后会对量子计算的现状和未来有大致的了解和认知。

来源:博客丨政策管理

作者:贺飞(北京大学)

量子计算:前途光明  道路曲折(一)

本周,美国国家科学院、工程院和医学院的一个由13名量子计算专家组成研究小组向公众发布了长达205页的题为“Quantum Computing: Progress and Prospects”(量子计算:进展和前景)报告,认为“鉴于量子计算的当前状态和最近的进展速度,在未来十年里建造出能够危及RSA 2048或类似的基于离散对数的公钥密码系统的量子计算机,将是高度意外的事。

这份报告共分为七章,其中第1章介绍了半个多世纪以来计算领域的发展历史以及量子计算机的优势。第2章介绍了量子力学的原理如何使得量子计算的实现与众不同和富有挑战,并将其与当前“经典计算机”的运算进行比较。本章介绍了三种不同类型的量子计算:模拟量子、数字噪声中尺度量子(数字NISQ)和全纠错量子计算机。第3章深入j研究了量子算法。包括用于完全纠错机器的已知基本算法及其纠错开销(overhead)、模拟和数字NISQ计算机能达到实用的潜在算法等。第4章讨论了如何应对量子计算机的肖尔(Shor)算法对当前非对称密码的挑战。第5章和第6章则分别讨论了量子计算所需的一般体系结构和迄今为止在构建必要的硬件和软件组件方面的进展。第7章是关于量子计算取得重大进展所需的技术准备和其他因素的评估,介绍了几种评估工具,并展望了该领域未来发展。

这个名为“量子计算的可行性和影响技术评估委员会”的研究小组成员包括来自加州大学圣巴巴拉分校的John Martinis,他领导着谷歌量子方面的研究工作;芝加哥大学的David Awschalom,他曾在UCSB领导自旋电子学和量子计算中心;以及加州大学伯克利分校量子信息与计算中心共同主管Umesh Vazirani。此外,来自小组外的成员,如美国达尔格伦海军水面作战研究中心的杰克·法林霍尔特(Jake Farinholt)对量子计算及相关领域的研究提供了文献计量分析;欧洲委员会驻美代表团Mary Kavanagh博士和澳大利亚驻华盛顿大使馆Anthony Murfett先生提供了欧盟和澳大利亚量子科技研究信息。

 

1.摩尔定律失效?量子计算成为热门话题

 

上个世纪70年代前后,英特尔(Intel)创始人之一戈登·摩尔(Gordon Moore)提出了摩尔定律,这个定律告诉我们:当价格不变时,集成电路上可容纳的元器件的数目,约每隔18-24个月便会增加一倍,性能也将提升一倍。换言之,每一美元所能买到的电脑性能,将每隔18-24个月翻一倍以上。但在部分原因是因为人们越来越担忧半导体技术进展速度有放缓的趋势。尽管这一定律揭示的技术进展趋势已持续半个多世纪,但它毕竟只是推测,而非自然或物理法则。

近年来,国际半导体技术进展速度放缓,以致于有人预计摩尔定律到2020年前后将会失效。对摩尔定律失效的担心,人们对替代计算的兴趣越来越浓厚,量子计算和量子计算机在过去几年里成了一个全球热门话题。而在十多年前,我们当中的大多数人对此还一无所知。近年来关于量子计算机独特的计算能力的讨论,以及其底层硬件、软件和算法的研究进展,更是使大家“脑洞大开”。

在量子计算机之前,我们所有已知的现存计算设备都满足“广义邱奇-图灵论题”(the extended Church-Turing thesis)。这一理论认为,任何构建计算设备的能力只能比普通的“通用”计算机多项式地(polynomially)更快,也就是说,任何相对的加速都只能根据幂律(a power law)按比例放大。这些“经典”计算设备的设计者,通过更快的运算(增加时钟频率)以及提升每一时钟周期里完成的运算数,可将计算能力提升许多数量级。虽然这些改变能将计算性能提升许多数量级,但结果仅是比通用计算设备更快的(大)常数因子。伯恩斯坦等人在1993年揭示,量子计算机能违反广义邱奇-图灵论题。1994年,Peter Shor展示了分解大数能力的一个实例:量子计算机可以比经典计算机以指数方式更快地解决这个问题。虽然这一结果令人兴奋,但当时无人知道如何构建一台量子计算机最基本的元素,量子比特(a quantum bit),或“量子位”(qubit),更不用说一台完整的量子计算机了。

【邱奇-图灵论题是计算机科学中以数学家阿隆佐·邱奇(Alonzo Church)和阿兰·图灵命名的论题。该论题最基本的观点表明,所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机,反之任何一台图灵机也都可以翻译成大部分编程语言大程序.该论题和以下说法等价:常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真,也被称为邱奇论题或邱奇猜想和图灵论题。】

 

但情况最近发生了变化。有两项技术,一是使用俘获电离原子(trapped ionized atoms)(俘获离子),二是使用微型超导电路(miniature superconducting circuits),已发展到能让一些研究小组构建小型演示量子计算系统的地步,一些研究小组已取得了成功。这些最新进展使得全世界对量子计算的兴趣激增;然而,研究界对量子计算的潜力及其当前状态的兴趣越来越高的同时,难免也会有炒作和混淆视听的成分。有关量子计算将如何实现计算机性能的持续扩展(它不会)的文章很多,或改变计算机工业的文章也并不罕见(短期影响很小,长期影响未知)。

量子计算可行性和影响技术评估委员会的主要任务是研究通用量子计算机当前技术状态、可能的进展及其影响,重点聚焦理解量子计算硬件、软件和算法的当前发展态势,以及需要什么进展来构建能部署肖尔(Shor)算法的可扩展的(scalable)基于门的量子计算机,厘清量子计算的理论特征和局限性,同时纠正公众对该领域的误解。

委员会试图整合多学科观点,并从系统的视角来思考如何构建实用量子计算机。先后开了三次面对面的会议、一系列电话会以及远程合作。委员会在其工作之初意识到,当前的工程方法不能直接扩展到构建这种可扩展的、完全纠错的量子计算机。于是便集中精力寻找发展里程碑,提出测度这一领域进展的指标。

需要说明的是,相关研究基于公开信息完成,不涉及敏感保密渠道信息。小组成员的专业素养和经验、公开会议上收集的数据、与外部专家的一对一访谈以及来自许多公共领域的信息等都是研究的重要依靠。因此,这一研究毕竟是基于不完整信息,不排除来自公开渠道之外的研究进展(如机密渠道)会改变研究结论。

 

2.量子计算横空出世

 

量子力学是描述非常小粒子行为的物理学子领域,它为新的计算范式提供了基础。量子计算是一种遵循量子力学规律调控量子信息单元进行计算的新型计算模式。我们知道,传统的通用计算机的理论模型是通用图灵机;而通用的量子计算机的理论模型是用量子力学规律重新诠释的通用图灵机。从可计算的问题来看,量子计算机只能解决传统计算机所能解决的问题,但是从计算的效率上,由于量子力学叠加性的存在,目前某些已知的量子算法在处理问题时速度要快于传统的通用计算机。

量子计算(Quantum. computing,QC)的概念最早由美国阿贡国家实验室的P. Benioff于1980年代初期提出,他提出二能阶的量子系统可用来仿真数字计算;稍后费曼也对这个问题产生兴趣而着手研究,并在1981年于麻省理工学院举行的First Conference on Physics of Computation中给了一场演讲,勾勒出以量子现象实现计算的愿景。1985年,牛津大学的D. Deutsch提出量子图灵机(quantum Turing machine)的概念,量子计算才开始具备了数学的基本型式。但以上量子计算研究多半局限于探讨计算的物理本质,停留在相当抽象的层次,尚未跨入发展算法的阶段。

量子计算提出之初是作为一种改进非常小(“量子”)物理系统行为的计算模型的方法。到了20世纪90年代,随着肖尔(Shor)算法的引入,人们对其兴趣日益增长。1994年,贝尔实验室的应用数学家P. Shor指出,相对于传统电子计算器,利用量子计算可以在更短的时间内将一个很大的整数分解成质因子的乘积。这个结论开启量子计算的一个新阶段:有别于传统计算法则的量子算法(quantum algorithm)确实有其实用性,绝非科学家口袋中的戏法。相对于当今的计算机来说,量子计算机是可提供指数加速的唯一已知的计算模型。量子计算机如果能实现,将会以指数方式加速分析一些重要密码,潜在地威胁到用于保护政府和民间通信和数据存储的一些密码方法。

自此之后,新的量子算法陆续的被提出来,而物理学家接下来所面临的重要的课题之一,就是如何去建造一部真正的量子计算机来运行这些量子算法。许多量子系统都曾被点名做为量子计算机的基础架构,例如光子的偏振(photon polarization)、腔量子电动力学(cavity quantum electrodynamics,CQED)、离子阱(ion trap)以及核磁共振(nuclear magnetic resonance,NMR)等等。当前,考虑到系统可扩展性和操控精度等因素,离子阱与超导系统走在了前面。

 

3. 量子计算的基本原理

 

量子力学态叠加原理使得量子信息单元状态可处于多种可能性的叠加状态,从而导致量子信息处理从效率上相比于经典信息处理具有更大潜力。普通计算机中的2位寄存器在某一时间仅能存储4个二进制数(00、01、10、11)中的一个,而量子计算机中的2位量子位(qubit)寄存器可同时存储这四种状态的叠加状态。随着量子比特数目的增加,对于n个量子比特而言,量子信息可以处于2种可能状态的叠加,配合量子力学演化的并行性,可以展现比传统计算机更快的处理速度。

如果把量子考虑成磁场中的电子,电子的旋转可能与磁场一致,称为上旋转状态,或者与磁场相反,称为下旋状态。如果我们能在消除外界影响的前提下,用一份能量脉冲能将下自旋态翻转为上自旋态;那么,我们用一半的能量脉冲,将会把下自旋状态制备到一种下自旋与上自旋叠加的状态上(处在每种状态上的几率为二分之一)。对于n个量子比特而言,它可以承载2的n次方个状态的叠加状态。而量子计算机的操作过程被称为幺正演化,幺正演化将保证每种可能的状态都以并行的方式演化。这意味着量子计算机如果有500个量子比特,则量子计算的每一步会对2^500种可能性同时做出了操作。2^500是一个可怕的数,它比地球上已知的原子数还要多(这是真正的并行处理,当今的经典计算机,所谓的并行处理器仍然是一次只做一件事情)。

虽然这些结果在1990年代非常令人兴奋,但人们的兴趣却只是停留在理论上,因为无人知道用量子系统构建计算机的方法。量子计算将有可能使计算机的计算能力大大超过今天的计算机,但仍存在很多障碍。大规模量子计算的问题是在提高所需量子装置的准确性上存在困难,即如何长时间地保持足够多的量子比特的量子相干性,同时又能够在这个时间段之内做出足够多的具有超高精度的量子逻辑运算。

 

量子计算:前途光明  道路曲折(二)

挑战仍然很大

经典计算机使用位来表示它所运算的值;量子计算机使用量子比特(quantum bits)或量子位(qubits)。位可以是0或1,而量子位可以表示值0或1,或者同时表示值0或1的某种组合(称为“叠加”)。虽然经典计算机的状态是由比特集的二进制值决定的,但是在任何单个时间点,具有相同数量量子比特的量子计算机的状态可以跨越相应经典计算机的所有可能状态,从而以指数形式在更大的问题空间工作。然而,利用这个空间的能力要求所有的量子位都具有内在的相互联系(“纠缠”),与外部环境完全隔离,并且非常精确地控制。

量子位(qubit)是量子计算的理论基石。在常规计算机中,信息单元用二进制的 1 个位来表示,它不是处于 0 态就是处于 1 态. 在二进制量子计算机中,信息单元称为量子位,它除了处于 0 态或 1 态外,还可处于叠加态(superposed state)。叠加态是 0 态和 1 态的任意线性叠加,它既可以是 0 态又可以是 1 态, 0 态和 1 态各以一定的概率同时存在. 通过测量或与其它物体发生相互作用而呈现出 0 态或 1 态.任何两态的量子系统都可用来实现量子位,例如氢原子中的电子的基态(ground state)和第 1 激发态(first excited state)、 质子自旋在任意方向的+ 1/ 2 分量和- 1/ 2 分量、 圆偏振光的左旋和右旋等。一个量子系统包含若干粒子,这些粒子按照量子力学的规律运动,称此系统处于态空间的某种量子态。

过去25年,许多创新使研究人员能构建物理系统,并为量子计算提供所需的隔离和控制。2018年,量子计算机中多数使用了两种技术(被捕获的离子和由超导电路产生的人造“原子”),目前还在探索许多不同的技术,来实现量子位的基本物理实现,即“物理量子位’。这一领域正快速发展中,还有很多需要改进的地方,现在下注于一种量子计算技术还为时过早。因为即便人们可制造高质量的量子位,构建和利用这些量子计算机(QC)也会存在一系列新挑战。它们使用与经典计算机完全不同的一组运算,需要新的算法、软件、控制技术和硬件抽象。

实现量子计算的六大难关

 

首先,量子位不能固有地拒绝噪声。

经典计算机和量子计算机的主要区别之一在于它如何处理系统中不想要的小变化或噪声。因为一个经典比特要么是1,要么是0,即使该值稍微偏离(系统中的一些噪声),对该信号的运算也很容易去除该噪声。事实上,经典门运算在比特上用于创建计算机,具有非常大的噪声裕度——它们可以拒绝输入中的大变化,并且仍然产生干净、无噪声的输出。但由于量子位可是1和0的任意组合,所以量子位和量子门不能轻易地拒绝物理电路中出现的小错误(噪声)。结果是,在产生期望的量子运算或耦合到物理系统中的任何杂散信号时的小误差,最终会导致在计算中出现错误的输出。因此,对于在物理量子位上运算的系统,最重要的设计参数之一是它们的错误率。低错误率很难实现;即使在2018年年中,在具有5个或更多个量子位的系统上进行2量子位运算的错误率也超过几个百分点。

其次,无误差QC需要量子纠错。

尽管物理量子位运算对噪声敏感,但在物理量子计算机上运行量子纠错(quantum error correction ,QEC)算法以仿真无噪声或“完全纠错”的量子计算机是可能的。如果没有QEC,一个复杂的量子程序,比如实现肖尔算法的程序,就不可能在量子计算机上正确运行。虽然QEC对将来创建无错误的量子计算机必不可少,但其过于资源密集,在短期内无法使用,量子计算机在短期内可能存在错误。这类机器被称为有噪声的中尺度量子(NISQ)计算机。

第三,大数据输入不能有效地加载到QC中。

虽然量子计算机可使用少量的量子位来表示指数级更大的数据量,但目前还没有一种方法将大量经典数据快速转换为量子状态(如果数据能以算法方式生成,则不适用)。虽然有人建议量子随机存取存储器(QRAM)可以执行这一功能,但还没有实现。对于需要大量输入的问题,创建输入量子态所需的时间量通常将支配计算时间,并且极大地降低量子优势。

第四,量子算法设计具有挑战性。

为了实现量子计算机的好处,量子算法必须利用独特的量子特性,如干涉和纠缠,以获得最终的经典结果。因此,实现量子加速需要全新的算法设计原理和非常巧妙的算法设计。量子算法的发展是该领域的一个关键。

第五,量子计算机需要一个新的软件栈。

与所有计算机一样,构建有用的设备要比创建和调试特定于QC的软件所需的硬件工具复杂得多。由于量子程序不同于经典计算机程序,需要研究和开发软件工具栈。由于这些软件工具驱动硬件,硬件和软件工具链的同时开发将缩短有用量子计算机的开发时间。

最后,量子计算机的中间状态不能直接测量。

调试量子硬件和软件的方法至关重要。当前经典计算机的调试方法依赖于内存和中间机器状态的读取。这两种方法在量子计算机中都不可能。量子态不能简单地被复制(根据所谓的非克隆定理)以供随后研究,任何对量子态的测量都会将其折叠为一组经典比特,从而使计算停止。发展新的调试方法是开发大型量子计算机所必需的。

量子计算何时能实现?

要创建能够运行Shor算法以在1024位RSA加密消息中查找私钥的量子计算机,需要构建一台大于5个数量级的机器,并且具有比当前机器好大约两个数量级的错误率,还要开发软件开发环境来支持这台机器。弥合这一差距所需的进展使得我们不可能为大型纠错量子计算机规划时间框架,尽管在这些领域持续取得重大进展,但不能保证所有这些挑战都能被克服。弥合这一差距的过程可能暴露出意想不到的挑战,需要尚未发明的技术,或是由于基础科学研究的新进展而改变我们对量子世界的理解。因此,当前无法预测量子计算实现的时间框架,只能提出若干监测该领域进展的指标和里程碑事件。

在快速发展的领域,存在许多未知和困难的问题,总体发展速度取决于学术界吸收利用新方法和新见解的能力。对于研究结果保密或专有的领域要慢更多。鉴于量子计算机的独特特性和挑战,它们不太可能直接替代经典计算机。事实上,它们需要许多经典计算机来控制其运算,并执行计算来完成量子纠错。因此,它们目前被设计为与经典处理器互补操作的专用设备,类似于协处理器或加速器。

此外,一项技术的进步取决于其投入的资源,包括人力和资本。尽管许多人认为系统中,量子位的数目会有摩尔定律类型的标度。但重要的是要记住,摩尔定律源于良性循环,技术改进能产生指数增长的收入,并且回报研发,吸引新的人才和企业,以帮助技术创新到下一个水平高度。如果像硅一样,摩尔定律类型的量子位的持续指数增长,需要无限增长的投资,那么维持这种投资,量子计算机也需要类似的良性循环,因为较小的机器如果在商业上足够成功,整个领域便会增加投资。在产生商业收入的中间进展缺位的情况下,进展将取决于政府机构继续增加这一领域的投资。

考虑到QEC的开销,近期机器几乎肯定会是噪声中尺度量子(NISQ)计算机。虽然大型纠错量子计算机有许多有趣的应用,但NISQ计算机的实际应用目前并不存在。为NISQ计算机创建实际应用是一个相对较新的研究领域,需要研究新的量子算法。在2020年代初开发商用NISQ计算机应用,对于启动新一轮良性投资周期至关重要。因此,研究和开发噪声中尺度量子计算机的实际商业应用,是当前该领域的一个紧迫问题。这项工作的结果将对大规模量子计算机的发展速度以及量子计算机商业市场的规模和鲁棒性产生深远的影响。

量子计算机可分为三大类型。“模拟量子计算机”直接操纵量子位之间的相互作用,而不将这些作用分解为基本门运算。“数字NISQ计算机”通过在物理量子位利用原始门运算执行感兴趣的算法来运算。这两种机器都存在噪声,这意味着质量(通过错误率和量子位相干时间测量)将限制这些机器所能解决的问题的复杂性。“完全纠错量子计算机”是基于门的量子计算机的版本,通过部署量子纠错(QEC)而变得更加鲁棒,QEC使有噪声的物理量子位能够仿真稳定的逻辑量子位,从而计算机能够可靠地进行任何计算。

QC发展的几个重要里程碑

QC发展的第一个里程碑是简单原理证明的模拟和数字系统。小型数字NISQ计算机在2017年问世,其中数十个量子位的误差太高而无法校正。此外,证明 “量子霸权(quantum supremacy)”也是一大挑战。“量子霸权”(quantum supremacy)这个术语是由加州理工量子理论学家John Preskill在2012年创造的,指的是当量子计算机发展到50量子位的时候,其计算能力将超过世界上任何计算机,能解决任何计算机解决不了的问题。当前,虽然有若干团队集中精力实现,但尚未取得成功。

另一个重要的里程碑是创造一台商业上实用的量子计算机,它需要一个比任何经典计算机更有效率地执行至少一个实际任务的QC。虽然这个里程碑在理论上比实现量子霸权更难,因为所讨论的应用必须比现有的经典方法更好,更有用。证明量子霸权也许是困难的,特别是对于模拟QC。因此,在量子霸权被证明之前,有可能出现有用的应用。另一个主要里程碑是在QC上部署QEC以创建错误率显著降低的逻辑量子位, 这也是创建完全错误校正机器的第一步。

监测领域进展的指标

通过跟踪定义量子处理器质量的关键属性,可以监控基于门的量子计算的进展:单量子位和双量子位运算的有效错误率,量子位之间的连接性,以及包含在单个硬件模块中的量子位的数目。现在预测可扩展量子计算机的时间进展还为时过早。相反,可通过以恒定的平均门错误率监视物理量子位的扩展率(the scaling rate),在短期内跟踪进展,如使用随机基准评估一样,并在长期内通过监视系统所表示的逻辑(纠错)量子位的有效数量来跟踪进展。跟踪逻辑量子位的大小和扩展率将提供对未来里程碑事件的更好估计。

保持投入是关键

如果量子计算机近期不能在商业成功,政府资助对于防止这一领域研发显著下降是必不可少的。显然,全世界正在努力开发量子计算机和其他量子技术。量子信息科学和技术现在是一个全球领域。一些国家最近作出了巨大的资源承诺,如果想保持领导地位,提供支持至关重要。此外,还需要大规模协调一致、跨越多学科的工作,包括基础科学进展和工程上的新策略。

量子计算机与密码学

密码学依赖于难以计算的问题来保护数据,量子计算将对密码学产生重大影响,但鉴于其当前发展状态,在未来十年内预计难以实现能危害RSA 2048或可比较的基于离散对数的公钥密码系统的量子计算机。但运行在大型量子计算机上的肖尔(Shor)算法将大大减少非对称密码中提取私钥所需的计算(工作因子)。因此,需要尽快着手应对后量子密码时代的到来。

因此,即使能够解密当前密码的量子计算机要等到十多年才能诞生,但其危害实在太大,并且过渡到新的安全协议也有很大的不确定性,因此,优先开发、标准化和部署后量子时代密码技术,对于最小化潜在的安全和隐私灾难风险至关重要。事实上,各国也正在积极努力开发量子后密码学,即量子计算机无法破解的非对称密码。这也许会在2020年代成为标准。

量子计算的风险与收益

实现QC仍存在重大的技术障碍,并且不能保证能克服。构建和使用QC,不仅需要设备工程,而且需要会聚许多学科的基础进展——从计算机科学和数学到物理、化学和材料科学。量子计算对于推动基础研究是有价值的,,QC研发能够推动基础学科的进展,例如,物理学进展(在量子重力领域)和经典计算机科学进展(经典算法的改进)。

创建一个大的、纠错的量子计算机面临的挑战是显然的。成功的量子计算将需要对量子相干性的空前控制,通过改进现有的工具和技术,或者甚至通过开发新的工具和技术,来推动可能的边界。同样依赖于量子相干控制的相关技术,例如量子传感和量子通信,也可以推动进展。

量子计算除了有潜在的知识进步和社会效益,其对国家安全也有影响。任何拥有大规模、实用的量子计算机的实体都可以打破当今的不对称密码系统。各国已经意识到这种风险,纷纷开始努力创建和部署对量子密码分析具有鲁棒性的密码系统。历史上,经典计算对整个社会产生了革命性的影响。虽然将量子算法应用于工业和研究应用的潜力才刚刚开始探索,但显然量子计算具有超越当前计算边界的潜力。从这个意义上来说,支持强大的QC研究具有战略价值。

结论

基于对迄今为止有关量子计算进展的公开可得信息,我们有理由相信人们可构建大型容错量子计算机。然而,在构建这样一个系统,并将其部署到实际优势以完成一项有价值的任务的道路上,仍然存在重大的技术挑战。但不论何时、不论是否能实现大型纠错量子计算机,很显然,量子计算和量子技术的持续研发将极大地推动人类知识进步,改变我们对宇宙的认知。

发表评论