量子计算优越性

量子计算优越性（英文：Quantum Advantage）[1]，或称量子霸权（英语：quantum supremacy），是指用量子计算机解决古典电脑难以解决的问题，问题本身未必需要有实际应用。量子计算优越性则是指量子电脑在解决实务问题上能比古典电脑更快而带来的优势，从计算复杂性理论的角度来说，这通常代表量子电脑相对最佳古典算法的加速是超多项式的。[2] 这个术语最初是由约翰·普雷斯基尔所提出，[3]但量子计算优势的概念（特别是用于模拟量子系统）可以追溯到尤里·马宁（1980）[4] 和理察·费曼（1981）提出的量子计算建议。 [5]

秀尔算法能在量子电脑上以多项式时间执行整数的因数分解，和已知的古典算法相比具有超多项式加速。[6] 一般认为使用古典资源分解整数很困难，然而严谨的证明尚未出现。缺乏古典计算困难度的证明，是难以明确展示量子优越性的主要原因。这影响了常见的量子优越性问题：Aaronson和Arkhipov的玻色子抽样问题（boson sampling）、[7] D-Wave的specialized frustrated cluster loop problems、 以及随机量子电路抽样问题。

像整数分解一样，基于合理的复杂度假设，用古典电脑对随机量子电路的输出分布进行抽样是困难的。Google先前宣布，计划在2017年底之前用含有49个超导量子比特的数组解决这个问题，以展示量子优越性。[8] 在那之后，Intel、IBM、Google分别宣布了49、53、72个量子比特的系统。[9]

2020年12月4日，中国科学技术大学发布使用76个光子的量子计算机“九章”，并宣布实现量子优越性，使中国成为全球第二个实现“量子优越性”的国家。[10]

计算复杂度

复杂度理论研究解决计算问题所需的资源如何随问题的大小变化，量子复杂度理论延伸古典计算复杂度理论到通用量子电脑可以完成的工作上，对于建造量子电脑或处理退相干和噪声的困难则忽略不计。[11] 由于量子信息比古典信息更广义 ，很显然量子电脑可以有效地模拟任何古典算法 。

有限错误量子多项式时间（BQP）这个复杂度类包括通用量子电脑在多项式时间能解决的决策问题，它和古典复杂度类的关系是  ， [12] 这些子集关系之中有没有真子集仍是未决问题。

与答案为是或否的决策问题不同，抽样问题要求从几率分布中抽取样本。[13] 如果有古典算法可以有效地从任意量子电路的输出中抽样，则多项式谱系将崩溃到第三级，普遍认为这是极不可能的。 玻色子抽样是较具体的提议，其古典困难度来自于计算具有复数元素的大矩阵其积和式的困难度，而那是P#-complete的问题。[14] 用于得出此结论的论点也已扩展到IQP抽样，[15] 并只需假设问题的平均和最坏情况复杂度相同。

超多项式加速

下列算法对已知的最好的古典算法提供超多项式加速：[16]

秀尔整数分解算法

秀尔算法用  时间分解n-比特整数，[6] 而已知的最好的古典算法需要 时间，复杂度的最佳上限是   。 它还能加速任何可化简成整数分解的问题。 [17]

这个算法在历史上和实务上都对量子计算很重要，它是第一个用多项式时间解决困难古典计算问题的量子算法。 [6] 对其困难度的信念强烈到当今最常见的加密协议RSA就是根据整数分解。 [18] 能重复成功运行这种算法的量子电脑有潜力破解这种加密系统。 [19] 需要避免迫在眉睫的这种风险被称为Y2Q，名称来自2000年问题的别名"Y2K"。

玻色子抽样

这是基于一个古典计算问题：将全同光子穿过线性光学网络用来解决某些抽样和检索的问题，在一些猜测性的假设下，对古典计算是很棘手的。 [7] 然而，已经有研究显示，如果系统具有足够大的有损和噪声，古典电脑能够有效率地模拟玻色子抽样问题。 [20]

迄今为止，最大的玻色子抽样实验能做到6个光学模式，一次最多可以处理6个光子。[21] 对于包含 n 个光子 和 m 个输出模式的系统，模拟玻色子抽样的古典算法最好的执行时间是 。 [22] BosonSampling 是一个用 R 写的开放源码实现，估计需要50个光子才能达成玻色子抽样的量子优越性。

对随机量子电路的输出分布抽样

在模拟任意随机量子电路的算法当中，已知最佳的算法需要的时间随量子比特个数指数式地上升，因此一个研究小组估计50个量子比特可能就足以达成量子优越性。[23] Google已经宣布打算在2017年底前用49量子比特的芯片展示量子优越性，方法是对其输出分布抽样，这个抽样用古典电脑将无法在合理时间内模拟。[8] 然而56量子比特的量子电路模拟已经在超级电脑上完成， 这可能让达成量子优越性所需的量子比特数增加。[24]

怀疑论

因为退相干和噪声，量子电脑比古典电脑更容易受到资料错误的影响。 阈值定理指出，有噪声的量子电脑只要每一步计算的错误率低于某个值，就可以用量子错误修正码[25][26] 模拟无噪声的量子电脑 ，数值模拟的结果指出该阈值可以高达3%。[27]

然而，错误修正所需的资源会如何随量子比特数上升并不清楚。 怀疑论者指出，大型量子系统中未知的噪声行为是成功实现量子电脑和达成量子优越性的潜在障碍，要太多的量子比特用以纠错最后会成为一堵高墙无法翻越。[28]

实现面争议

2017年10月，IBM在传统的超级电脑上展示了56个量子比特的模拟，增加了量子优越性所需的量子比特数量。[24] 2018年11月，Google宣布与NASA创建合作伙伴关系，“将分析在Google量子处理器上运行的量子电路的结果，并...与古典模拟比较，以验证Google硬件并为量子优越性创建基础。”[29] 2018年发表的理论工作提出，如果能将错误率降到够低，那么“具有7x7量子比特的二维点阵执行大约40个时钟周期”应该可以实现量子优越性。[23]

2019年1月8日，IBM在消费电子展上展示了已开发的世界首款商业化量子计算机IBM Q System One[30]但其基本只有实验研究价值，没有超越传统电脑的实用性。而6月份开始一直有媒体传言谷歌实现量子霸权的文章在流转，《科学美国人》于2019年6月21日提出，根据聂文定律（英语：Neven's law），[31] 量子优越性可能在2019年发生。

2019年9月20日，英国《金融时报》基于一篇在NASA网站上短暂出现的文章报导：“Google声称已经用54个量子比特的数组（其中53个功能正常）的量子电脑原型机悬铃木[32]达到了量子优越性，它们在200秒内执行一系列操作，相同运算将花费超级电脑大约10,000年才能完成”。[33]

2019年10月21日IBM于arXiv发布一篇文章，[34][35] 指出若能有效率使用Summit超级电脑的硬盘和并行计算资源，估计可以将10,000年时间降低至2.5天，计算53和54个量子比特分别需要64PiB和128PiB的硬盘空间。[36]

2019年10月23日自然期刊刊登了Google实现量子优越性的学术论文[37][38]，各种学者和人士对此各种议论纷纷，莫衷一是：

  • 美国总统川普女儿伊万卡在社交媒体上称美国正式实现量子霸权，谷歌的项目是与特朗普政府、以及加州大学圣塔芭芭拉分校合作进行的。[39]
  • 谷歌首席首席执行官 Sundar Pichai 受访时也对此事进行回应，用委婉的譬喻称Google 的实验就是像是莱特兄弟首次飞行，虽第一架飞机只飞行了 12 秒钟，并没有真的实际应用性，但这仍然表明飞机的概念是可行的。[40]
  • 美国德州大学奥斯汀分校的理论计算机科学家斯科特 阿伦森（Scott Aaronson）则保守性中立认为，虽谷歌上述成果实际应用有限“但假设它是成立的，那么科学象征成就是巨大的。”因为代表量子电脑取代传统电脑有其可能。[40]
  • 澳大利亚新南威尔士大学量子物理学家米歇尔 西蒙斯（Michelle Simmons）说谷歌给了我们一种实验证据，证明量子加速在真实世界的系统中是有可能的。[40]
  • 而值得关注是量子霸权此一名词提出者约翰·普里斯基尔在同一时期虽没对具体案例发言[36]，但发表一种广泛性观察称目前这霸权名词被滥用“加剧了对量子技术现状的过度炒作”，并且已经有迹象政治化“通过与白人至上（white supremacy）概念的联系，唤起了一种令人厌恶的政治立场。”

参考文献

  1. ^ 澎湃新闻. 潘建伟团队实现量子优越性：特定问题比顶级超算快百万亿倍. finance.sina.com.cn. 2020-12-04 [2020-12-12]. 
  2. ^ Papageorgiou, Anargyros; Traub, Joseph F. Measures of quantum computing speedup. Physical Review A. 2013-08-12, 88 (2): 022316. Bibcode:2013PhRvA..88b2316P. ISSN 1050-2947. arXiv:1307.7488  . doi:10.1103/PhysRevA.88.022316. 
  3. ^ Preskill, John. "Quantum computing and the entanglement frontier". 2012-03-26. arXiv:1203.5813  . 
  4. ^ Manin, Yu. I. Vychislimoe i nevychislimoe [Computable and Noncomputable]. Sov.Radio. 1980: 13–15 [2013-03-04]. （原始内容存档于2013-05-10） （俄语）. 
  5. ^ Feynman, Richard P. Simulating Physics with Computers. International Journal of Theoretical Physics. 1982-06-01, 21 (6–7): 467–488. Bibcode:10.1.1.45.9310 请检查|bibcode=值 (帮助). ISSN 0020-7748. doi:10.1007/BF02650179. 
  6. ^ 6.0 6.1 6.2 Shor, P. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review. 1999-01-01, 41 (2): 303–332. Bibcode:1999SIAMR..41..303S. ISSN 0036-1445. arXiv:quant-ph/9508027  . doi:10.1137/S0036144598347011. 
  7. ^ 7.0 7.1 Aaronson, Scott; Arkhipov, Alex. The Computational Complexity of Linear Optics. Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing. STOC '11 (New York, NY, USA: ACM). 2011: 333–342. ISBN 9781450306911. arXiv:1011.3245  . doi:10.1145/1993636.1993682. 
  8. ^ 8.0 8.1 Google Plans to Demonstrate the Supremacy of Quantum Computing. IEEE Spectrum: Technology, Engineering, and Science News. [2018-01-11]. （原始内容存档于2021-04-25）. 
  9. ^ CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy. IEEE Spectrum: Technology, Engineering, and Science News. [2017-07-22]. （原始内容存档于2021-03-23）. 
  10. ^ 最快！我国量子计算机实现算力全球领先. 新华网. [2020-12-04]. （原始内容存档于2020-12-12）. 
  11. ^ Watrous, John. Meyers, Robert A. , 编. Quantum Computational Complexity. Springer New York. 2009: 7174–7201. ISBN 9780387758886. doi:10.1007/978-0-387-30440-3_428. 
  12. ^ Vazirani, Umesh. A Survey of Quantum Complexity Theory (PDF). Proceedings of Symposia in Applied Mathematics. [2019-10-23]. （原始内容存档 (PDF)于2021-05-07）. 
  13. ^ Lund, A. P.; Bremner, Michael J.; Ralph, T. C. Quantum sampling problems, BosonSampling and quantum supremacy. Npj Quantum Information. 2017-04-13, 3 (1): 15 [2019-10-23]. Bibcode:2017npjQI...3...15L. ISSN 2056-6387. arXiv:1702.03061  . doi:10.1038/s41534-017-0018-2. （原始内容存档于2021-03-08）. 
  14. ^ Gard, Bryan T.; Motes, Keith R.; Olson, Jonathan P.; Rohde, Peter P.; Dowling, Jonathan P. From Atomic to Mesoscale: the Role of Quantum Coherence in Systems of Various Complexities. World Scientific. August 2015: 167–192. ISBN 978-981-4678-70-4. arXiv:1406.6767  . doi:10.1142/9789814678704_0008. 
  15. ^ Bremner, Michael J.; Montanaro, Ashley; Shepherd, Dan J. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters. 2016-08-18, 117 (8): 080501. Bibcode:2016PhRvL.117h0501B. ISSN 0031-9007. PMID 27588839. arXiv:1504.07999  . doi:10.1103/PhysRevLett.117.080501. 
  16. ^ Jordan, Stephen. Quantum Algorithm Zoo. math.nist.gov. [2017-07-29]. （原始内容存档于2018-04-29）. 
  17. ^ Babai, László; Beals, Robert; Seress, Ákos. Polynomial-time Theory of Matrix Groups. Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing. STOC '09 (New York, NY, USA: ACM). 2009: 55–64. Bibcode:10.1.1.674.9429 请检查|bibcode=值 (帮助). ISBN 9781605585062. doi:10.1145/1536414.1536425. 
  18. ^ Rivest, R. L.; Shamir, A.; Adleman, L. A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Commun. ACM. February 1978, 21 (2): 120–126. Bibcode:10.1.1.607.2677 请检查|bibcode=值 (帮助). ISSN 0001-0782. doi:10.1145/359340.359342. 
  19. ^ Bernstein, Daniel. Post-Quantum Cryptography. Springer. 2009 [2019-10-23]. ISBN 9783540887010. （原始内容存档于2021-05-11） （英语）. 
  20. ^ Rahimi-Keshari, Saleh; Ralph, Timothy C.; Caves, Carlton M. Sufficient Conditions for Efficient Classical Simulation of Quantum Optics. Physical Review X. 2016-06-20, 6 (2): 021039. Bibcode:2016PhRvX...6b1039R. arXiv:1511.06526  . doi:10.1103/PhysRevX.6.021039. 
  21. ^ Carolan, Jacques; Harrold, Christopher; Sparrow, Chris; Martín-López, Enrique; Russell, Nicholas J.; Silverstone, Joshua W.; Shadbolt, Peter J.; Matsuda, Nobuyuki; Oguma, Manabu. Universal linear optics. Science. 2015-08-14, 349 (6249): 711–716 [2019-10-23]. ISSN 0036-8075. PMID 26160375. arXiv:1505.01182  . doi:10.1126/science.aab3642. （原始内容存档于2020-12-16）. 
  22. ^ Neville, Alex; Sparrow, Chris; Clifford, Raphaël; Johnston, Eric; Birchall, Patrick M.; Montanaro, Ashley; Laing, Anthony. No imminent quantum supremacy by boson sampling. Nature Physics. 2017-10-02, 13 (12): 1153–1157 [2019-10-23]. ISSN 1745-2473. arXiv:1705.00686  . doi:10.1038/nphys4270. （原始内容存档于2020-08-06）. 
  23. ^ 23.0 23.1 Boixo, Sergio; Isakov, Sergei V.; Smelyanskiy, Vadim N.; Babbush, Ryan; Ding, Nan; Jiang, Zhang; Bremner, Michael J.; Martinis, John M.; Neven, Hartmut. Characterizing quantum supremacy in near-term devices. Nature Physics. 2018-04-23, 14 (6): 595–600. arXiv:1608.00263  . doi:10.1038/s41567-018-0124-x. 
  24. ^ 24.0 24.1 Google's quantum computing plans threatened by IBM curveball. 2017-10-20 [2017-10-22]. （原始内容存档于2021-01-25）. 
  25. ^ Shor, Peter W. Scheme for reducing decoherence in quantum computer memory. Physical Review A. 1995-10-01, 52 (4): R2493–R2496. Bibcode:1995PhRvA..52.2493S. doi:10.1103/PhysRevA.52.R2493. 
  26. ^ Steane, A. M. Error Correcting Codes in Quantum Theory. Physical Review Letters. 1996-07-29, 77 (5): 793–797. Bibcode:1996PhRvL..77..793S. PMID 10062908. doi:10.1103/PhysRevLett.77.793. 
  27. ^ Knill, E. Quantum computing with realistically noisy devices. Nature. 2005-03-03, 434 (7029): 39–44 [2019-10-23]. Bibcode:2005Natur.434...39K. ISSN 0028-0836. PMID 15744292. arXiv:quant-ph/0410199  . doi:10.1038/nature03350. （原始内容存档于2009-06-28）. 
  28. ^ Dyakonov, M. I. Is Fault-Tolerant Quantum Computation Really Possible?. 2006. arXiv:quant-ph/0610117  . 
  29. ^ Harris, Mark. Google has enlisted NASA to help it prove quantum supremacy within months. MIT Technology Review. [2018-11-30]. （原始内容存档于2020-03-10） （英语）. 
  30. ^ IBM unveils world's first commercial quantum computer （页面存档备份，存于互联网档案馆） The Telegraph 2019年1月8日
  31. ^ A New "Law" Suggests Quantum Supremacy Could Happen This Year. Quanta Magazine. 2019-06-21 [2019-10-23]. （原始内容存档于2021-03-02） –通过Scientific American, Daily Digest. 
  32. ^ 中國量子電腦原型機「九章」問世　速度快Google「懸鈴木」百億倍. [2020-12-04]. （原始内容存档于2020-12-04）. 
  33. ^ Google claims to have reached quantum supremacy. Financial times. 2019-09-21 [2019-10-23]. （原始内容存档于2021-04-29）.  
  34. ^ Pednault, Edwin. Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits. 2019-10-22. arXiv:1910.09534   [quant-ph]. 
  35. ^ On “Quantum Supremacy”. IBM Research Blog. 2019-10-22 [2019-10-27]. （原始内容存档于2021-11-11） （美国英语）. 
  36. ^ 36.0 36.1 谷歌声索“量子霸权”，IBM不服. 腾讯新闻. [2019-10-27]. （原始内容存档于2020-12-04）. 
  37. ^ Arute, Frank; et al. Quantum supremacy using a programmable superconducting processor. 自然期刊. 23 October 2019, 574: 505–510 [25 October 2019]. doi:10.1038/s41586-019-1666-5. （原始内容存档于2019-10-23）. 
  38. ^ John Martinis. Quantum Supremacy Using a Programmable Superconducting Processor. 2019-10-23. （原始内容存档于2019-10-23）. 
  39. ^ Ivanka Trump Congratulates US on Achieving 'Quantum Supremacy'. sputniknews.com. [2019-10-27]. （原始内容存档于2021-01-02） （英语）. 
  40. ^ 40.0 40.1 40.2 观察者网. 谷歌声索"量子霸权" IBM不服:尚未实现吧. finance.sina.com.cn. 2019-10-24 [2019-10-27]. （原始内容存档于2019-10-24）. 

外部链接