量子计算结合了过去半个世纪以来两个最大的技术变革：信息技术和量子力学。如果我们使用量子力学的规则替换二进制逻辑来计算，某些难以攻克的计算任务将得到解决。追求通用量子计算机的一个重要目标是确定当前经典计算机无法承载的最小复杂度的计算任务。该交叉点被称为「量子霸权」边界，是在通向更强大和有用的计算技术的关键一步。
在 4 月底 Nature Physics 上发表的文章《Characterizing quantum supremacy in near-term devices》中，谷歌介绍了在近期设备中实际展示量子霸权的理论基础。它提出了从随机量子线路的输出中采样比特串的任务，可被看成是量子计算的「hello world」程序。争论的结果是，随机混沌系统（参见「蝴蝶效应」）运行的时间越长，这些系统输出变得难以预测的速度就越快。构建一个随机、混沌的量子比特系统，并测试经典系统模拟前者所需的时间，就可以获得量子计算机何时超越经典计算机的良好度量。可以说，这是证明经典和量子计算机之间的计算能力的指数式分离（exponential separation）的最强理论方案。
在随机量子线路中确定量子霸权边界迅速成为了一个令人激动的研究领域。一方面，通过优化经典算法来模拟量子线路的方案的目的是增加要达到量子霸权的量子线路的规模。这迫使实验的量子设备需要足够多的量子比特数、足够低的误差率来实现足够深度（即线路中量子门的层数）的线路，才能达到量子霸权。另一方面，我们现在更加理解用于构建随机量子线路的量子门的特定选择如何影响模拟成本，从而得到近期的量子霸权的优化基准（https://github.com/sboixo/GRCS），在某些情况下用经典计算机模拟的成本是该方案成本的二次方。
从随机量子线路采样是量子计算机的优秀校正基准，称为交叉熵基准测试。成功地利用随机线路的量子霸权实验将能展示大规模容错量子计算机的基础构建模块。此外，量子物理学中目前仍未测试过如此高度复杂的量子态。
量子电路计算的空间时间体积。量子模拟的计算成本随着量子电路体积的增加而增加，并且通常随着量子比特数量和电路深度的增加而呈指数增长。在量子比特的非对称网格中，计算空间-时间体积随深度的增长速度比对称网格慢，随电路呈现的指数级增长也更容易模拟。
在最近的 Science 文章《A blueprint for demonstrating quantum supremacy with superconducting qubits》中，来自 UCSB、谷歌、NASA 等研究机构的学者们展示了实现量子霸权的蓝图，并首次通过实验演示了其原理证明过程。本文讨论了量子霸权的两个关键因素：指数复杂性和精确计算。研究者首先在装置的 5~9 个量子比特的子部分上运行算法，发现经典的模拟成本随着量子比特数的增加呈指数增长。这些结果旨在提供这些装置指数幂的清晰示例。接下来，他们使用交叉熵基准来比较该结果与普通计算机的结果，结果表明，他们的计算是高度精确的。事实上，如果使用较大的量子处理器，误差率可以低到实现量子霸权。
在实现量子霸权的更高层面，量子平台还应提供明确的应用。在本文中，谷歌将算法应用于使用复杂的多量子比特门（相对于为具有表面代码纠错算法的数字量子处理器设计的两量子比特门）的量子统计力学中的计算问题。结果表明，该装置可以用来研究材料的基本特性，例如金属和绝缘体之间的微观差异。通过将这些结果扩展到具有大约 50 个比特的下一代设备，谷歌希望能够解决任何其他计算平台都无法解决的科学问题。
Charles Neill 和 Pedram Roushan 开发的两个 gmon 超导量子比特及其可调耦合器。
两篇文章介绍了近期量子霸权的现实提议，并首次展示了其原则证明过程。谷歌将探索继续降低误差率，增加量子处理器中量子比特的数量，以实现量子霸权，并为短期实用的应用开发量子算法。
Nature Physics 论文：Characterizing quantum supremacy in near-term devices
论文链接：https://www.nature.com/articles/s41567-018-0124-x
arXiv 链接：https://arxiv.org/abs/1608.00263
摘要：在近期内关于量子计算的一个关键问题是，没有误差校正的量子设备是否可以在执行良好定义的计算任务上超越超级计算机的能力。这样的展示被称为量子霸权，其需要对用经典方法求解的任务所需的资源进行可靠的评估。这里，我们提出了从随机量子线路的输出分布中采样的任务，作为量子霸权的展示。我们扩展了在计算复杂度上的之前的结果，以证明该采样任务在经典计算机中必然需要指数量级的时间复杂度。我们引入了交叉熵基准测试来获得复杂多比特动力学的实验保真度。其可被评估和推断来为量子霸权展示给出成功的指标。我们研究的相关经典算法的计算成本，并得出结论：量子霸权可以在 7×7 个量子比特和 40 个时钟周期的二维点阵线路上达到量子霸权。这需要两比特量子门的大约 0.5% 误差率（单比特量子门的 0.05% 误差率），并且它将展示容错量子计算机的基础构建模块。
Science 论文：A blueprint for demonstrating quantum supremacy with superconducting qubits
论文链接：http://science.sciencemag.org/content/360/6385/195
arXiv 链接：https://arxiv.org/abs/1709.06678
量子信息科学家距离构建量子计算机的梦想越来越近，它可以执行经典计算机无法完成的计算。据估计，这样一台计算机将需要大约 50 个量子比特，但是将现有的体系结构扩展到这个数字是很困难的。Neill 等人尝试将量子比特的数量从 5 个增加到 9 个，探索这种做法对超导量子比特设备输出质量的影响。随着量子比特数量进一步增加，如果误差继续以相同的速率增加，则利用当前技术打造具有约 60 个量子比特和合理精确度的量子计算机将成为可能。
摘要：证明量子系统能够解决物理、化学难题的关键一步是进行超越任何经典计算机能力的计算，从而实现所谓的量子霸权。在这项研究中，我们使用了九个超导量子比特展示了一条通往量子霸权的可行路径。通过单独调整量子比特参数，我们能够生成数千个不同的 Hamiltonian 演化，并探测输出概率。所测量的概率服从一种普遍分布，与均匀采样整个 Hilbert 空间的结果一致。随着量子比特数量的增加，系统继续探索数量呈指数增长的状态。将这些结果扩展到一个具有 50 个量子比特的系统，有可能解决超出任何经典计算机能力的科学问题。
原文链接：https://research.googleblog.com/2018/05/the-question-of-quantum-supremacy.html
