維基百科

量子計算優越性

量子计算机解决经典计算机解决不了的问题

量子計算優越性（英文：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）. 

外部連結

編輯
取自 "https://zh.wikipedia.org/w/index.php?title=量子计算优越性&oldid=79897693"