里程碑！量子计算机超越经典计算机最新证据，量子霸权再进一步！

来源：Science等

转自：新智元

【导读】Science今天发表一篇IBM和慕尼黑工业大学研究人员的论文，论文严格证明了在相同限制条件下，量子计算机能击败经典计算机，这是量子计算领域一大突破，也指出一条更容易达到“量子霸权”的道路。

实现“量子霸权”又近了一步！

今天，来自IBM和德国慕尼黑工业大学的一组研究人员在Science上发表了一篇论文，严格证明了near-term量子计算机超过了经典计算机。

不过，前提条件是对量子计算机和经典计算机的能力都作了严格的限制，虽然还没有证明被大家疯狂追求的“量子霸权”（quantum supremacy）已经实现，但这是表明量子处理器有一天可能达到量子霸权的重要里程碑事件！

相同限制条件下，量子计算机被证明能击败经典计算机

量子计算机可能看起来更快，但要有严格的数学证明。目前，在理论上已经证明了量子计算能够超越经典计算。

今天的经典计算机可以将每个问题都转换成二进制代码串，由可以是0或1的位元表示。

量子计算机的量子比特（qubits）以一种全新的方式进行通信。量子比特可以在计算过程中取0和1之间的值，并以常规计算机位元无法做到的方式进行交互。 量子处理器仍然总是返回表示0和1的二进制字符串，但每个量子比特的最终值有一个固有的概率，这个概率基于在程序测量量子比特之前它的值与0或1的接近程度。量子比特也可以纠缠，在这种情况下，两个或两个以上的量子比特值的组合同时受到概率的影响。

目前，IBM和Rigetti等公司有一些基本形式的量子计算机，通常只有20或更少的量子比特。在构建这些设备的过程中，物理学家和计算机科学家正在开发量子算法，希望能比传统计算机更好地解决问题。

今天Science杂志刊登的论文，是IBM的科学家们去年设计的一个证明。这篇论文证明，在解决简单的线性代数问题时，有限的量子计算机总能击败经典计算机，但前提条件是经典计算机具有与量子计算机相同的限制。

这些限制即具有“shallow circuits”。计算机科学中将单个位元交互称为“逻辑门”（logic gates）。这些门基于一个或多个位元返回一个值。相反，量子门将量子比特的值移动到0或1之间的某个位置，或者改变一个纠缠的量子比特对的内置数值（built-in statistics）。“circuit”是一系列的门。“shallow quantum circuit（SQC）”是指每个量子比特只能在再次变为0或1之前只能执行有限数量的门，并且这些门最多只能包含另一个量子比特。如果两个门同时出现在处理器上不相关的量子比特对上，是没问题的。

经典与量子计算模型之间构成可证明的分离

目前，大多数的量子算法都超出了当前的实验能力：它们的实现需要一个包含错误修正的全功能量子计算机。虽然编码和操作量子数据容错的开销是渐近小的，但它仍然不适用于当前的技术。 因此，预计near-term量子计算机将缺乏纠错能力。

没有纠错的量子计算在量子比特解码（qubits decohere）和熵建立（entropy builds up）之前只能执行恒定数量的运算。当量子比特经历具有恒定退相干率（constant decoherence rate）的独立噪声时，无法实现无源量子存储（passive quantum memories）。 

在论文中，研究人员比较了SQC和它的经典计算机对应部分（即恒定深度经典电路）的计算能力。

他们提出一个简单的二元二次型相关的线性代数问题，它可以由一个由作用于2D网格的最近邻门组成的SQC确定地求解。这种设置反映了near-term的实验能力。

同时，研究人员证明了没有恒定深度的经典概率电路可以解决所考虑的问题，并且对于所有情况都具有足够小的误差概率。

经典电路在任何意义上都不必是几何局部的，并且可以访问从仅依赖于输入大小的任意概率分布中抽取的随机位元。唯一的要求是经典电路中的所有门必须具有有界扇入（bounded fan-in）（即每个门具有恒定数量的输入导线）。该结果提供了恒定深度量子和经典电路的功率之间的无条件分离。

量子计算领域一大突破，也指出一条更容易达到量子霸权的道路

尽管这项工作离实现“量子霸权”之路还有距离，但论文仍然是一个重要的里程碑。

华为量子计算软件与算法首席科学家翁文康教授表示，要证明量子霸权需要找出具体电路大小（包括量子比特数目和电路深度）是经典计算机在合理的时间内不能有效模拟的。

“ 他们找到一类量子算法，在物理实现上不需要太大的量子电路，就可以在理论上超越经典计算机的能力。但是如果要真正实现量子霸权的话，我们还要具体看经典计算机对这个新的量子算法的模拟能力。”

翁文康认为，这项研究结果虽然还不清楚能解决什么实际的问题，但是他们能严格证明量子计算机确实比经典计算机要强大，是量子计算领域的一大突破，同时也指出一条更容易达到量子霸权的道路。

马里兰大学的计算机科学家Andrew Childs认为，“能够对量子计算机和经典计算机之间的关系进行清晰陈述，这真是太好了。我们必须从某个地方开始探索，要在正确的方向上实现理论上的进步。”

麻省理工学院理论物理学教授Aram Harrow也认为，大多数之前描述的量子计算机在没有浅电路限制的情况下击败经典计算机的例子中，仍然需要对经典计算机的能力和实现内容做一些整体假设。换句话说，你可能会假设一位马拉松运动员不可能超越一只猎豹，但没有真正证明这一点。本次发表的论文不需要这样的假设。

量子霸权争夺战：IBM、谷歌都已开发出原型量子计算设备

“量子霸权”最早由加州理工学院量子理论学家John Preskill提出，之后受到了量子计算支持者的认同，部分人甚至认为量子霸权可能会2017年年底之前出现。

不过，也有部分人认为“量子霸权”它不是一个突然的边界，而是一个象征性的姿态：量子霸权是一个概念工具，可以在其上讨论与经典计算方法之间的差异。

尽管如此，对“量子霸权”的热情激励着学术和产业界。IBM和谷歌都已开发出原型量子计算设备。

IBM Q量子计算机内部

IBM已经将一个5比特的设备作为基于云的资源供公众使用，并于去年11月宣布它已经为商业用户提供了一个20比特的设备。同时，IBM的计算机科学家也当年报告说他们成功测试了50比特的电路。谷歌也正在开发具有49-50比特率的设备，并且，谷歌的研究人员还曾希望在2017年年底前展示量子霸权成果。

论文一作Sergey Bravyi表示，这项工作更重要的是，科学家们仍然要使用全功能的经典计算机来验证量子计算机是否能够取得正确的结果。这与谷歌的“量子霸权”的实验不同，后者是一个设计的问题，量子计算机在解决问题的速度上可能比模拟量子计算机的经典计算机有着指数级的优势。

但这篇新论文也并非完美无瑕。“它不是要解决实际问题，也没有人建议将其与实际问题联系起来，即使要面向实际问题，也会因为带来的运算速度提升太小，导致人们不会在实际应用中关注。如果量子计算机只比相同大小的经典计算机快那么一点，那么由于量子计算机难以构建，我们还是会选择经典算法。”Harrow说。

论文地址：

http://science.sciencemag.org/content/362/6412/308

参考资料：

https://gizmodo.com/theres-now-a-proven-way-for-quantum-computers-to-beat-c-1829844452

https://www.nature.com/news/race-for-quantum-supremacy-hits-theoretical-quagmire-1.22993

一网打尽系列文章，请回复以下关键词查看：

创新发展：习近平 | 创新中国 | 创新创业 | 科技体制改革 | 科技创新政策 | 协同创新 | 科研管理 | 成果转化 | 新科技革命 | 基础研究 | 产学研 | 供给侧

热点专题：军民融合 | 民参军 | 工业4.0 | 商业航天 | 智库 | 国家重点研发计划 | 基金 | 装备采办 | 博士 | 摩尔定律 | 诺贝尔奖 | 国家实验室 | 国防工业 | 十三五 | 创新教育 | 军工百强 | 试验鉴定 | 影响因子 | 双一流 | 净评估

预见未来：预见2016 |预见2020  | 预见2025 | 预见2030  | 预见2035 | 预见2045  | 预见2050

前沿科技：颠覆性技术 | 生物 | 仿生 | 脑科学 | 精准医学 | 基因 |  基因编辑 | 虚拟现实 | 增强现实 | 纳米 | 人工智能 | 机器人 | 3D打印 | 4D打印 | 太赫兹 | 云计算 | 物联网 | 互联网+ | 大数据 | 石墨烯 | 能源 | 电池 | 量子 | 超材料 | 超级计算机 | 卫星 | 北斗 | 智能制造 | 不依赖GPS导航 | 通信 | 5G | MIT技术评论 | 航空发动机 | 可穿戴 | 氮化镓 | 隐身 | 半导体 | 脑机接口 | 传感器

先进武器：中国武器 | 无人机 | 轰炸机 | 预警机 | 运输机 | 直升机 | 战斗机 | 六代机 | 网络武器 | 激光武器 | 电磁炮 | 高超声速武器 | 反无人机 | 防空反导 | 潜航器

未来战争：未来战争 | 抵消战略 | 水下战 | 网络空间战 | 分布式杀伤 | 无人机蜂群 | 太空战 | 反卫星

领先国家：美国 | 俄罗斯 | 英国 | 德国 | 法国 | 日本 | 以色列 | 印度

前沿机构：战略能力办公室 | DARPA | 快响小组 | Gartner | 硅谷 | 谷歌 | 华为 | 阿里 | 俄先期研究基金会 | 军工百强

前沿人物：钱学森 | 马斯克 | 凯文凯利 | 任正非 | 马云 | 奥巴马 | 特朗普

专家专栏：黄志澄 | 许得君 | 施一公 | 王喜文 | 贺飞 | 李萍 | 刘锋 | 王煜全 | 易本胜 | 李德毅 | 游光荣 | 刘亚威 | 赵文银 | 廖孟豪 | 谭铁牛 | 于川信 | 邬贺铨

全文收录：2018文章全收录 | 2017文章全收录 | 2016文章全收录 | 2015文章全收录 | 2014文章全收录

其他主题系列陆续整理中，敬请期待……