学界 | 南科大翁文康：「量子霸权」的基础概念和可行方案

选自NSR

作者：翁文康

机器之心编译

参与：Panda

《国家科学评论》（NSR）近日发表了南方科技大学物理系副教授翁文康撰写的短篇综述论文《量子霸权：一些基本概念》，讨论了量子霸权相关的一些基础概念和可行方案。机器之心对该论文进行了全文编译。

论文：Quantum supremacy: some fundamental concepts

原文地址：https://doi.org/10.1093/nsr/nwy072

三十多年前，费曼设想只有利用量子计算才能有效解决量子问题 [1]。问题在于，我们如何证明量子计算相比于经典计算具有优势？在比较量子计算机与经典计算机时，一个常见误解是：量子比特可以表达一个包含指数数量状态的叠加态，这是经典比特无法实现的。这种表述虽然是正确的，但却没告诉我们全部信息，具体来说：究竟量子计算机能有效求解哪些经典计算机不能求解的问题？事实上，正是基于费曼发明的路径积分技术，任意量子线路的输出，比如跃迁幅度（transition amplitude），都存在一个经典的计算方法只需使用以多项式数量增长的内存去得到（尽管时间成本会呈指数增长）。因此，任意量子计算都可以用经典的方式模拟，关键的是时间上的效率问题。

目前已经有很多研究，试图利用计算复杂性理论来判断量子计算机的能力。尤其需要指出，可通过量子计算机有效求解的计算（决策）问题的类别被称为 BQP（有界误差量子多项式时间）；对应的经典计算机能有效求解的问题被称为 P（多项式时间）。当然，BQP 不会弱于 P；理论上量子计算机可以有效模拟经典计算机。但关键的问题是，如果无法证明 BQP 严格超过 P（即 BQP≠P），则量子计算的优越性基础无法确立。从这个意义上看，这个问题就跟证明 P≠NP（非确定性多项式时间）这一著名难题一样重要。

大数分解问题是一个著名的 NP 问题；Shor 的量子算法能够在多项式时间内进行大数分解，而迄今为止人类发现的最好的经典算法也无法完成这一任务。严格来说，能有效进行大数分解的经典算法也许存在，但是我们仍然不能严格排除这一可能性。同样，尽管没有证明，人们还是普遍相信量子计算机也无法求解某些 NP 问题。事实上，这个猜想（如果成立）的证明能提供 P≠NP 的可行证明途径。

或许一类更容易解决的问题是：我们考虑量子计算机何时能够执行某些明确（但不一定跟任何实际问题有关）的计算任务，这些任务在某个合理的时间内不能被当前任何经典计算机解决？这一状态的实现被称为「量子霸权（quantum supremacy）」[2]。有人可能会问，能提供平方加速的 Grover 搜索算法如何？我们能说 Grover 算法实现了量子霸权吗？问题在于，量子霸权并不是取 大 N 极限，而是要求我们确定需要多少个量子比特和量子门，经典计算机才没有办法在合理时间内模拟。

为了进一步阐述，我们先来谈论两个经典模拟的概念，即「强模拟（strong simulation）」和「弱模拟（weak simulation）」。强模拟是指在多项式时间内高精度地计算跃迁概率（或可观测量的期望值）。弱模拟则要求精确地重现概率分布，这涉及到从量子器件的输出结果中采样。某些量子线路虽然不能用经典的方法作有效的强模拟，但也许能进行有效的弱模拟。[3]

然而，我们应该注意模拟任务中的精度要求。比如说，对于很多决策问题而言，将跃迁幅度计算到加法误差而非乘法误差内可能就足够了。换句话说，量子计算问题的经典可模拟性取决于精度要求。

目前，实现量子霸权有三种常见的模型（参见图 1），即（i）玻色采样 [4]，（ii）IQP 线路采样 [5]，（iii）混沌量子线路采样 [6]。这些方法的共同点在于，不同比特串或光子数的分布都是从量子器件中采样的。此外，它们全都假设经典计算机无法有效计算跃迁振幅，和/或重现（或近似）执行采样的量子器件的分布。这在强模拟和弱模拟两方面都是如此。

图 1：三种实现量子霸权的不同方法。（a）玻色采样，（b）IQP 线路，（c）混沌量子线路

在玻色采样中，多个单光子被注入线性光学网络的不同模（mode）中，目标是确定输出的光子分布。玻色采样的关键特征是，跃迁振幅与复矩阵的积和式相关，而要准确计算或者把积和式近似到一个乘法误差内一般来说是很难的——#P-hard 复杂度级别的难。此外，对玻色采样的有效弱模拟被认为是不可能的，除非多项式层级（Polynomial Hierarchy）坍缩到第三级。但是，近期一项数值研究表明，要使用玻色采样实现量子霸权，将需要同时生成至少 50 或更多个单光子，而这仍然是个很大的技术挑战。

在玻色采样的设定中，一个有趣的问题是：线性光学能否被应用于求解决策问题？在这种情况下，跃迁振幅可能只需要被确定到一个加法误差。但是，我们发现，有一大类与玻色采样相关的决策问题都可被经典计算机模拟 [7]，这解决了 Aaronson 和 Hance 提出了一个开放问题 [9]。

IQP 线路代表着一种简化的量子线路模型。线路的初始量子态都为零态： |000...0>，之后每个量子比特都被作用一个 Hadamard 门。接着，在这些量子比特上作用对角的门，最后再次在每个量子比特上作用 Hadamard 门。IQP 线路的经典复杂度证明与玻色采样的情况类似。实际上，玻色采样的复杂度证明是受 IQP 线路的复杂度结果启发而得到的。当受到噪声影响时，IQP 线路可能可以用经典方式模拟 [8]。

最后，混沌量子线路是指按特定规则作用两比特门，以及随机从某个集合中抽取并作用单比特门。这类线路的输出概率接近所谓的 Porter-Thomas 分布，这是量子混沌的一个特征。近期已经出现了一些数值研究，旨在探索经典计算在模拟低深度量子线路中的极限。在理想情况下，为了对量子霸权进行基准评测，既需要考虑量子比特数，还需要考虑线路深度。然而，在有噪声存在的情况下，高深度混沌量子线路也可能通过经典方式模拟 [10]。

最后，除了这三种方法，人们应该还能预见量子霸权可能在很多实际应用上实现，比如量子化学或量子机器学习。这一天什么时候才会到来呢？耐心等待吧！

参考文献：

[1] Feynman, R. P. Quantum mechanical computers. Found. Phys. 16, 507531 (1986).

[2] Preskill, J. Quantum computing and the entanglement frontier. arXiv:1203.5813 (2012).

[3] Nest, M. Van den. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quant. Inf. Comp. 10, 258-0271 (2010)

[4] Aaronson, S. & Arkhipov, A. The computational complexity of linear optics. Theory Comput. 9, 143252 (2013).

[5] Bremner, M. J., Jozsa, R. & Shepherd, D. J. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A 467, 459 (2011).

[6] Boixo, S. et al. Characterizing quantum supremacy in near-term devices. Nat. Phys. 14, 595 (2018).

[7] Yung, M.-H., Gao, X. & Huh, J. Universal Bound on Sampling Bosons in Linear Optics. arXiv:1608.00383 (2017).

[8] Bremner, M. J., Montanaro, A. & Shepherd, D. J. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum 1, 8 (2017).

[9] Aaronson, S. & Hance, T. Generalizing and Derandomizing Gurvitss Approximation Algorithm for the Permanent. Quant. Inf. Comp. 14, 541 (2012)

[10] Yung, M.-H. & Gao, X. Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise? arXiv:1706.08913 (2017).

作者简介：

翁文康，2002 和 2004 年在中国香港中文大学获得物理学士与物理硕士学位。2003 年暑假到美国加州理工学院 (Caltech) 学习关于量子信息理论的基础。2004 年受邀请到英国牛津大学 (Oxford) 的材料系参加量子信息的研发项目。随后前往美国伊利诺伊大学 (UIUC) 进修物理学博士，并得到诺贝尔物理学奖得奖者 Anthony Leggett 教授指导博士论文，进行包含物理学与信息科学的跨学科研究。毕业后三年多的时间在哈佛大学 (Harvard) 进行有关量子信息和物理化学的博士后研究工作。2013 年 9 月回国并在清华大学 (Tsinghua) 交叉信息研究院任职助理教授，并入选中组部青年千人计划。2016 年 1 月任职南方科技大学 (SUSTech) 物理系副教授。 翁文康的学术工作主要集中于量子算法的设计和量子模拟的研究，并取得了一系列重要的成果。其中以（共同）第一作者、或（共同）通讯作者身份在 Nature Photonics，Physical Review Letters，PNAS，Nature Communications，Science Advances 等国际著名刊物发表学术论文，并获邀为 Ann. Rev. Phys. Chem，Advances in Chemical Physics 等权威杂志撰写综述性文章。其中关于量子绝热的研究结果 [Li&Yung (共同通讯作者) NJP 2014] 被 IOP Publishing 选为「IOPSelect」和被 New Journal of Physics 选为「Highlights of 2014」。

本文为机器之心编译，转载请联系本公众号获得授权。