量子计算机的研制成功将会颠覆当今加密体系。这也是量子计算机在全世界范围内引起高度重视的一个重要原因。

但到目前为止，通用型量子计算机仍然在研制当中，而且短期内实现的可能性不大。另一方面，经典计算机技术在一直不断的发展：芯片制造工艺不断提高，存储容量不断增大，更有效的算法不断被提出。当前，经典的超级计算机已经可以实现高达 81 量子比特的模拟。人们不禁提出疑问：量子计算机的优势究竟还剩下多少？量子计算科学家们急需找到量子计算的真正优势所在。

经典计算机遵循经典物理学规律，利用传统的存储单元——比特进行处理。每个比特的电压表争了比特的数值，N 个比特的系统，在某一时间内仅能表征一个数。

而量子计算机中，利用量子比特进行信息的存储和处理，一个量子比特可以同时处于 0 和 1 的叠加态。因此，针对 N 个量子比特的系统，量子计算可以同时输入 2N 个数据进行操作，而经典计算机必须依次读取。这是量子计算可以显著提高运算速度的一个重要原因。

最近，谷歌量子芯片 Bristlecone 的出现，似乎让人们看到证明量子优势就在眼前。据《麻省理工科技评论》证实，谷歌已与 NASA 在今年 7 月签署协议，要求 NASA “分析谷歌量子处理器上量子电路的运行结果，并与经典模拟进行对比，以及确立量子优势的基准。”

但即使是谷歌和 NASA 这样的公司联合，仍有人持有怀疑态度。南加州大学量子信息科学与技术中心主任 Daniel Lidar 表示，量子计算仍需要一些额外的错误抑制机制。

无论是对量子优势的证明还是证伪，两条路都可以说是长路漫漫。就在今年，参与讨论的科学家们观点也是见仁见智。除了证明或证伪两类观点，甚至还有学者认为量子计算机本身就不可能存在。DT 君在此复盘今年几次十分重要的量子计算、经典计算的“节点”，可以肯定的是，随着两方技术不断发展，这场讨论也呈现出越发激烈的态势。

而从 10 月的一次研究进展来看，量子优势又添新证据。

最新战果：量子计算优势首次获得无条件的证明

图 | Science 发布量子优势论文（来源：Science）

10 月 19 日，一篇发表在 Science 杂志的论文中，来自 IBM、滑铁卢大学和慕尼黑理工大学的研究者提出并证明，在恒定计算深度这一情况下，量子计算在解决特定线性代数问题上相比经典计算具有固有的优势，这也是首次对量子计算的优势进行无条件的证明。该证明同时指出，量子计算的这种优势来自于量子非局域性（quantum nonlocality）。

论文作者、来自慕尼黑理工大学的 Robert Konig 和他的同事开发了可以解决特定线性代数问题的量子电路。新电路具有十分简单的结构，电路在每个比特上只进行固定数目的操作。这一电路被认为具有恒定深度。在他们的研究中，研究人员证明了可以被量子计算机解决的问题不能通过经典恒定深度电路解决。他们还进一步回答了为什么量子算法能够与任何经典电路相媲美：量子算法开发了量子物理的非局域性。

论文中的证明依赖于研究者们所提出的恒定深度电路模型。在该模型中，针对每个量子比特所进行的操作是固定的。研究人员证明，由于量子非局域性的特质，某些代数难题可以被量子计算机解决但不能被经典的恒定深度电路解决。

“了解到这点很高兴，因为这一结果可以成为算法的一部分，”IBM Q 副主席 Bob Sutor 说，“它们将成为决定如何解决问题的一部分：哪些情况需要尝试经典算法？哪些情况需要尝试量子算法？它们之间如何交互？它们之间又是如何相互合作？”

（来源：Pixabay）

此外，证据显示，在这些情况下，量子算法可以在固定数量的步骤内解决问题，无论输入条件增加了多少。而经典计算机则会在输入增加后，增加更多步骤的运算才能将问题解决。这就是平行处理的优势。

“这篇论文主要的地方不是我们如何发现一些难以置信的重要量子算法，或对一些有趣问题的实践，”论文作者之一，来自 IBM 的 Bravyi 教授说，“我们在寻求是否我们可以在恒定深度电路情况下对量子计算与经典计算差别的区分。随着我们增加问题的大小，量子计算的运行时间维持不变，但操作的总次数却在增加。”

正如 Bravyi 指出的那样，这是一个新的证据，但并不能用于解决所有的计算问题。

但另一方面，“它给我们提供了了解是什么让量子计算更强大的窗口，”Bravyi 补充到，“乐观的话，在未来这将帮助指导更加实用的算法应用。”

目前，这些尚未开发完成的算法不是必须用在量子系统中，研究也可帮助经典-量子结合系统的开发。“我们现在可以讨论一些比之前更深的事情。我们可以帮助人们判断创造量子计算机需要什么、创造量子计算机软件需要什么以及创造算法需要什么。”

（来源：Pixabay）

Konig 认为，新结果主要是对复杂性理论有贡献。“我们的结果表明，量子信息处理确实提供了好处，而不必依赖未经证实的复杂性理论猜想。”除此之外，这项工作也是量子计算的新里程碑。由于其结构简单，新的量子电路或将成为近期量子算法实现的候选者。但此次证明仍只是为证明量子优势提供新的证据。仍有学者持不同观点。

先搁置究竟量子优势是否存在这一问题，首先，有学者认为，所谓的“量子计算机”本身就是海市蜃楼。

量子计算机原理上无法实现？

在 2018 年年初，数学家 Gil Kalai 曾表示，量子计算机即使在原理上也不可能有效。

Kalai 认为，所有的物理系统都是嘈杂的，因此叠加态的量子比特对环境十分敏感，会不可避免的被外界交互所破坏。降低噪音不仅仅是一个工程问题，这样做会违反某些基本的计算定理。

图 | Gil Kalai （来源：维基百科）

起初，Kalai 和所有人一样，在最初接触量子计算机时，被量子计算未来美好的前景所吸引。但后来，Kalai 接触了关于噪声敏感度和噪声稳定性等概念后，开始决定研究量子计算机的可行性。

噪声是计算过程中的误差。对噪声的敏感度是对噪声影响该过程结果的可能性的度量。量子计算和其他物理过程类似，都会有噪声、随机波动以及错误。当量子计算机执行操作时，量子比特在每个计算周期中都有可能被破坏。

这就要求我们对量子计算进行纠错。但这就需要更多的量子比特去帮助保证一个量子比特的高度准确。而创建的这一纠错代码本身的噪声，又需要低于某一个阈值。

而噪声和错误又经常是关联的。这有点像一句谚语“祸不单行”，即在交互系统中，错误之间会倾向于相互关联。也就是说，这些错误有概率在多个量子比特同时出现。

Kalai 在过去十年左右的时间里发现，即使在小规模或中等规模的情况下，噪音水平也无法有效的降低，因为它们的能量远高于量子纠错所需的能量。而若想达到量子优势就会产生更大的噪音，而在此基础上创建量子纠错代码就更加困难。

因此，基于纠错就与计算原理计算设备能力相矛盾，有一派说法认为，量子计算不可能实现。

不过，虽然得出这样的结论，但对于 Kalai 来说，他也期待量子计算机能有非常不同的结果呈现。毕竟，像 IBM、英特尔和微软这样的大公司在量子计算方面已投入巨资。

新大陆：科学家发现只有量子计算机才能解决的问题

但是，抛开量子计算机实现的问题，之前的研究中不乏一些证据证明，量子计算有着经典计算无法比拟的优势。

今年 5 月 31 日发表的一篇论文中，计算机科学家终于找到了只有量子计算机才能解决的问题，即“有限错误量子多项式时间”（bounded-error quantum polynomial time，BQP）”类问题。

理论计算机研究中的一个基本项目就是将问题根据复杂程度进行分类，也称复杂度分级（Complexity Classes），即根据解决问题所需资源（如时间和内存）的多少进行分类。

其中最着名的两个分类是“P”和“NP”，P 是传统计算可以快速解决的所有问题，如“这个数字是否是质数？”属于 P 类问题。NP 是传统计算机并不能迅速解决，但如果存在一个已知答案能够快速验证的问题，如“这个数的质因数有哪些？”属于 NP 问题。

BQP 问题是 1993 年计算机学家 Ethan Bernstein 和 Umesh Vazirani 提出的只有量子级计算才能解决的问题。该定义类中包含量子计算机可以高效解决的所有决策问题，即答案为是或否的问题。两位科学家同时还证明了量子计算机可以解决传统计算机可以解决的所有问题，也就是证明了 BQP 分类中包含了 P 分类。

图 | 几种问题的分类（来源：Quanta Magazine）

但 Ethan 和 Umesh 无法确定 BQP 中是否也包含“多项式层次结构（Polynomial Hierarchy）”类问题，也称 PH 类问题。PH 是 NP 的拓展，包含所有由 NP 类延伸出的问题，如“对于所有... 来说是否存在...”。当今的传统计算机无法解决 PH 中的大多数问题，但如果 P 等于 NP，则可以将 PH 看作是传统计算机可以解决的所有问题。换句话说，比较 BQP 和 PH 这两种问题分类，便是为了确定量子计算机是否真的较传统计算机具有优势。

区分出两个复杂类别的最好方法是，找到一个可被证明为仅属于其中一类的问题。也就是为“量子计算在能力上将远超一切传统计算”这一概念提供的科学证据。

该论文中，作者 Raz 和 Tal 实现了一种名为“Oracle”的 BQP 与 PH 区分方式。他们认为，区分 BQP 和 PH 的最佳方式是测量解决每个问题所需要的时间，比如，计算出计算机在解决问题的过程中询问“oracle”的次数。oracle 就像是一个提示，你不知道它是怎样产生的，但你知道它是可靠的。

你可以先询问 oracle 类似“每个发生器的第六个数字是什么？”的问题，然后，根据每种计算机所需的提示数量来比较计算能力（需要更多提示的计算机计算速度较慢）。

Raz 和 Tal 的这篇论文证明了量子计算机在解决 forrelation 问题时较经典计算机所需的提示更少。事实上，量子计算机只仅要一个提示就能解决问题，而即使有无限个提示，PH 中也没有可以解决问题的算法。这说明了 forrelation 问题在分类上属于 BQP 而不是 PH。

当然，发现只有量子计算机才能解决的问题还只是证明量子优势的一道开胃小菜。想要证明“量子霸权”，还需要对量子计算性能的进一步探索。

中科大光量子计算机有望超越经典计算？

在今年 6 月，中科大的研究通过展示量子计算所需的最小量子资源，为展示量子计算优势提供新证据。

潘建伟团队通过对玻色子采样的方法，发现在量子计算机中，即使光子从系统中泄露，计算机也会生成有用的输出。也就是说，当光子丢失时，研究人员不必“抛弃”采样实验的输出，这就为更快的计算提供可能，并帮助证明量子优势。

图 | 潘建伟（来源：维基百科）

在波色子采样过程中，主要涉及 3 个步骤：首先要准备若干个玻色子（通常为光子），然后制造一个光子之间的线性相互作用，最后测量这些相互作用后的玻色子的位置。虽然单个实验都提供了一个随机样品，但多个测量位置的统计分布取决于相互作用的性质。据估计，玻色子采样器仅需要约 100 个光子就可以生成统计结果，但对经典机器来说这很难实现。

2016 年，Scott Aaronson 和 Daniel Brod 曾证明，丢失了固定数量光子的玻色子采样分布依然是可以胜过经典设备的。潘建伟团队曾对这一原理进行小规模验证演示。

研究人员使用嵌入多层腔中的半导体量子点作为光子源。这些量子点类似人造原子，在被激光激发时会发射出单个光子，腔则改善了产生单光子的速率和质量。光子可以通过整合在一起的 16 个梯形光学元件阵列发送。这些阵列为光子创建了有效的通路网络，在不同的点处经历彼此的线性相互作用。最后网络出口处的单光子探测器确定到达光子的位置。这一网络设计中，大多数丢失的光子来自于光子源和探测器的低效率，网络本身设计防止了一些光子丢失。

而此次研究中，潘建伟团队通过调整光子进入光网络的方式，研究人员可以只准备更少的单光子。然后，他们通过统计测试评估检测到的光子的分布，确保采样任务正常进行，同时调整这些测试，用于更少光子到达探测器的情况。研究结果显示，许多这种丢失光子的样品依然有效，且大幅度提高了数据采集速率。例如，当允许 7 个光子中丢失 2 个时，团队可以每秒收集 1000 次样本，这就比仅收集无丢失样品快了至少 10000 倍。

就目前而言，虽然这一实验并没有产生一个经典计算机难以生成的输出，同时Aaronson 和 Brod 的想法是丢失固定数量的光子而不是固定比例。但未来对理论和实验的进一步优化，或将帮助研究人员进一步了解有损失的玻色子采样情况，进而帮助证明量子优势。

虽然量子计算“捷报”连连，但每一次的进步都未能完成对量子优势的证明，更不是对经典计算的否定。正相反，为了证明量子计算与经典计算之间的不同，这些工作促进了经典计算的探索，以及对其进一步的算法优化。

18岁天才少年“打脸”量子计算

在今年 6 月 10 日的 arXiv 预印本网站上，18 岁的 Ewin Tang 曾发布了一篇“打脸”量子优势验证方法的论文，证明了经典计算机能以与量子计算机相同的性能解决一种重要的计算问题——“推荐问题”（recommendation problem）。

图 | Ewin Tang （来源：Quanta Magazine）

“推荐问题”旨在为用户提供产品建议。比如对 Netflix 来说，它知道你看过哪部电影，它也知道其他数百万用户所观看过的内容，而 Netflix 需要根据这些信息为你做出影视推荐。

我们可以将这些数据想成一种信息量巨大的表格，表格的列为各部电影，表格的行为每个具体用户，而表格中每个数字格的值则用于量化用户对于某部电影的喜好程度。此时，一个好的算法可以通过快速准确地识别电影和用户之间的相似性来填充表格中的空白格，进而生成推荐。

2016 年，计算机学家 Iordanis Kerenidis 和 Anupam Prakash 联手发布了一种量子算法，该算法能以比任何已知的经典算法都快的速度解决“推荐问题”。具体来说，该算法通过简化问题实现这一“量子优势”：不用完成整个表格，而是将用户进行分类（如某一用户喜欢好莱坞大片还是小众电影），再对现有数据进行抽样，然后生成建议。

当时 Kerenidis 和 Prakash 的研究结果令人兴奋，因为它提供了一个可实际验证“量子优势”的可靠方法。

但它并不能证明经典算法达不到这样的速度。

在今年春天，Tang 与 Aaronson 合作在论文中阐明了证明快速经典算法存在过程中的关键步骤。

Tang 表示，Kerenidis 和 Prakash 所使用的量子采样方法可以在经典环境中予以复制。与 Kerenidis 和 Prakash 的算法一样，Tang 的算法在多对数时间（polylogarithmic time）内完成运算，与量子算法的速度相当，比任何此前已知的经典算法都快。同时，这一算法比任何此前已知的经典算法都要快。

虽然这并不意味着量子计算与经典计算相比没有优势，但新的研究成果打破了人们验证量子计算方法的经典手段，也打破了人们对于用“推荐问题”验证量子计算可行性和优越性的执着。

回顾这几次量子计算与经典计算的几次公开大比较，DT 君认为，与其说量子计算一定能超越经典计算，我们更倾向于量子计算与经典计算处于一种“相爱相杀”的状态：量子计算的发展离不开经典计算的支持，例如，超级计算机可以模拟量子计算机，为量子计算机的设计提供支持，当前主流量子计算的接入都是通过云技术；另一方面，量子计算的不断发展，在不断超越的过程中也启发、甚至激励了经典计算不断向前发展。

图 | EmTech China 会议期间 D-Wave 公司的 Vern Brownell 进行讲话（来源：DT 君）

正如今年年初，D-Wave 公司的 Vern Brownell 在 EmTech China 峰会上说的那样，未来，量子计算机与经典计算机很可能处于一种并存的模式，而不是取代。两种计算机将各自在其擅长的领域继续发挥其优势，更好的服务于未来的生活。