新規更新October 23, 2019 at 02:47PM
【外部リンク】
量子優越性
HusOnFirst：翻譯英文 Quantum Supremacy 條目。
'''量子優越性'''（Quantum Supremacy）是指用[[量子计算机|量子電腦]]解決古典電腦實際上解決不了的問題，問題本身未必需要有實際應用。量子優勢（Quantum Advantage）則是指量子電腦在解決實務問題上能比古典電腦更快而帶來的優勢，從[[計算複雜性理論]]的角度來說，這通常代表量子電腦相對最佳古典演算法的加速是[[时间复杂度|超多項式]]的。<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 這個術語最初是由約翰·普里斯基爾（John Preskill）所提出，但量子計算優勢的概念（特別是用於模擬量子系統）可以追溯到[[尤里·马宁|尤里·馬寧]]（1980）<ref name="manin1980vychislimoe">Liquid error: wrong number of arguments (given 2, expected 1)
</ref> 和[[理查德·費曼|理察·費曼]]（1981）提出的量子計算建議。 <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
[[秀爾演算法]]能在量子電腦上以[[多項式時間]]執行整數的因數分解，和已知的古典演算法相比具有超多項式加速。<ref name=":2">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 一般認為使用古典資源分解整數很困難，然而嚴謹的證明尚未出現。缺乏古典計算困難度的證明，是難以明確展示量子優越性的主要原因。這影響了常見的量子優越性問題：Aaronson和Arkhipov的玻色子抽樣問題（boson sampling）、<ref name=":3">Liquid error: wrong number of arguments (given 1, expected 2)</ref> [[D-Wave 系统公司|D-Wave]]的specialized frustrated cluster loop problems、 以及隨機[[量子電路]]抽樣問題。
像整數分解一樣，基於合理的複雜度假設，用古典電腦對隨機量子電路的輸出分布進行抽樣是困難的。[[Google]]先前宣布，計劃在2017年底之前用含有49個超導量子位元的陣列解決這個問題，以展示量子優越性。<ref name=":9"></ref> 在那之後，Intel、IBM、Google分別宣布了49、53、72個量子位元的系統。<ref name=":11"></ref> 2017年10月，IBM在傳統的超級電腦上展示了56個量子位元的模擬，增加了量子優越性所需的量子位元數量。<ref name=":8"></ref> 2018年11月，Google宣布與[[NASA]]建立合作夥伴關係，「將分析在Google量子處理器上運行的量子電路的結果，並...與古典模擬比較，以驗證Google硬體並為量子優越性建立基礎。」<ref></ref> 2018年發表的理論工作提出，如果能將錯誤率降到夠低，那麼「具有7x7量子位元的二維點陣執行大約40個時鐘週期」應該可以實現量子優越性。<ref name="Boixo">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 《 [[科學美國人]]》於2019年6月21日提出，根據聶文定律（Neven's law），<ref>https://ift.tt/2FBcQ3g A New "Law" Suggests Quantum Supremacy Could Happen This Year]'', Scientific American, Daily Digest, June 21, 2019''</ref> 量子優越性可能在2019年發生。 2019年9月20日，英國《金融時報》報導：「 Google聲稱已經用54個量子位元的陣列（其中53個功能正常）達到了量子優越性，它們在200秒內執行一系列操作，相同運算將花費超級電腦大約10,000年才能完成」。<ref>''[https://www.ft.com/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17]'',Financial times, Sept 2019
</ref>
== 計算複雜度 ==
[[計算複雜性理論|複雜度]]理論研究解決計算問題所需的資源如何隨問題的大小變化，[[量子复杂性理论|量子複雜度理論]]延伸古典計算複雜度理論到[[量子圖靈機|通用量子電腦]]可以完成的工作上，對於建造量子電腦或處理[[量子退相干|退相干]]和雜訊的困難則忽略不計。<ref name=":5">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 由於[[量子資訊]]比古典資訊更廣義 ，很顯然量子電腦可以有效地模擬任何[[演算法|古典演算法]] 。
[[BQP (複雜度)|Bounded-error quantum polynomial time]]（BQP）這個複雜度類別包括通用量子電腦在多項式時間能解決的決策問題，它和古典複雜度類別的關係是<math>P\subseteq BPP\subseteq BQP\subseteq PSPACE</math> ， <ref name=":6"></ref> 這些子集關係之中有沒有真子集仍是未決問題。
與答案為是或否的決策問題不同，抽樣問題要求從[[機率分佈|機率分布]]中抽取樣本。<ref name=":7">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 如果有古典演算法可以有效地從任意量子電路的輸出中抽樣，則[[多項式譜系]]將崩潰到第三級，普遍認為這是極不可能的。 玻色子抽樣是較具體的提議，其古典困難度來自於計算具有複數元素的大矩陣其[[积和式|積和式]]的困難度，而那是P#-complete的問題。<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 用於得出此結論的論點也已擴展到IQP抽樣，<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 並只需假設問題的平均和最壞情況複雜度相同。
== 超多項式加速 ==
下列[[算法|演算法]]對已知的最好的古典演算法提供[[时间复杂度|超多項式]]加速：<ref></ref>
=== 秀爾整數分解演算法 ===
秀爾演算法用 <math>\tilde{O} (n^3)</math>時間分解n-位元整數，<ref name=":2" /> 而已知的最好的古典演算法需要<math>2^{O(n^{1/3})}</math>時間，複雜度的最佳上限是 <math>O(2^{n/3+o(1)})</math> 。 它還能加速任何可化簡成整數分解的問題。 <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
這個演算法在歷史上和實務上都對量子計算很重要，它是第一個用多項式時間解決困難古典計算問題的量子演算法。 <ref name=":2">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 對其困難度的信念強烈到當今最常見的加密協議[[RSA]]就是根據整數分解。 <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 能重複成功運行這種演算法的量子電腦有潛力破解這種加密系統。 <ref></ref> 需要避免迫在眉睫的這種風險被稱為Y2Q，名稱來自[[2000年問題]]的別名"Y2K"。
=== 玻色子抽樣 ===
這是基於一個古典計算問題：將全同[[光子]]穿過線性光學網絡用來解決某些抽樣和檢索的問題，在一些猜測性的假設下，對古典計算是很棘手的。 <ref name=":3">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 然而，已經有研究顯示，如果系統具有足夠大的失真和雜訊，古典電腦能夠有效率地模擬玻色子抽樣問題。 <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
迄今為止，最大的玻色子抽樣實驗能做到6個光學模式，一次最多可以處理6個光子。<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 對於包含 n 個光子 和 m 個輸出模式的系統，模擬玻色子抽樣的古典演算法最好的執行時間是 。 <ref name=":4">Liquid error: wrong number of arguments (given 1, expected 2)</ref> BosonSampling 是一個用 R 寫的開放源碼實作，估計需要50個光子才能達成玻色子抽樣的量子優越性。
=== 對隨機量子電路的輸出分佈抽樣 ===
在模擬任意隨機量子電路的演算法當中，已知最佳的演算法需要的時間隨量子位元個數指數式地上升，因此一個研究小組估計50個量子位元可能就足以達成量子優越性。<ref name="Boixo">Liquid error: wrong number of arguments (given 1, expected 2)</ref> Google已經宣布打算在2017年底前用49量子位元的晶片展示量子優越性，方法是對其輸出分布抽樣，這個抽樣用古典電腦將無法在合理時間內模擬。<ref name=":9"></ref> 然而56量子位元的量子電路模擬已經在[[超級電腦]]上完成， 這可能讓達成量子優越性所需的量子位元數增加。<ref name=":8"></ref>
== 懷疑論 ==
因為退相干和雜訊，量子電腦比古典電腦更容易受到資料錯誤的影響。 閾值定理指出，有雜訊的量子電腦只要每一步計算的錯誤率低於某個值，就可以用量子錯誤修正碼<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref><ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 模擬無雜訊的量子電腦 ，數值模擬的結果指出該閾值可以高達3%。<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
然而，錯誤修正所需的資源會如何隨量子位元數上升並不清楚。 懷疑論者指出，大型量子系統中未知的雜訊行為是成功實作量子電腦和達成量子優越性的潛在障礙。 <ref></ref>
== 參考資料 ==
<nowiki>
[[Category:計算複雜性理論]]
[[Category:量子計算]]</nowiki>
</ref> 和[[理查德·費曼|理察·費曼]]（1981）提出的量子計算建議。 <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
[[秀爾演算法]]能在量子電腦上以[[多項式時間]]執行整數的因數分解，和已知的古典演算法相比具有超多項式加速。<ref name=":2">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 一般認為使用古典資源分解整數很困難，然而嚴謹的證明尚未出現。缺乏古典計算困難度的證明，是難以明確展示量子優越性的主要原因。這影響了常見的量子優越性問題：Aaronson和Arkhipov的玻色子抽樣問題（boson sampling）、<ref name=":3">Liquid error: wrong number of arguments (given 1, expected 2)</ref> [[D-Wave 系统公司|D-Wave]]的specialized frustrated cluster loop problems、 以及隨機[[量子電路]]抽樣問題。
像整數分解一樣，基於合理的複雜度假設，用古典電腦對隨機量子電路的輸出分布進行抽樣是困難的。[[Google]]先前宣布，計劃在2017年底之前用含有49個超導量子位元的陣列解決這個問題，以展示量子優越性。<ref name=":9"></ref> 在那之後，Intel、IBM、Google分別宣布了49、53、72個量子位元的系統。<ref name=":11"></ref> 2017年10月，IBM在傳統的超級電腦上展示了56個量子位元的模擬，增加了量子優越性所需的量子位元數量。<ref name=":8"></ref> 2018年11月，Google宣布與[[NASA]]建立合作夥伴關係，「將分析在Google量子處理器上運行的量子電路的結果，並...與古典模擬比較，以驗證Google硬體並為量子優越性建立基礎。」<ref></ref> 2018年發表的理論工作提出，如果能將錯誤率降到夠低，那麼「具有7x7量子位元的二維點陣執行大約40個時鐘週期」應該可以實現量子優越性。<ref name="Boixo">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 《 [[科學美國人]]》於2019年6月21日提出，根據聶文定律（Neven's law），<ref>https://ift.tt/2FBcQ3g A New "Law" Suggests Quantum Supremacy Could Happen This Year]'', Scientific American, Daily Digest, June 21, 2019''</ref> 量子優越性可能在2019年發生。 2019年9月20日，英國《金融時報》報導：「 Google聲稱已經用54個量子位元的陣列（其中53個功能正常）達到了量子優越性，它們在200秒內執行一系列操作，相同運算將花費超級電腦大約10,000年才能完成」。<ref>''[https://www.ft.com/content/b9bb4e54-dbc1-11e9-8f9b-77216ebe1f17]'',Financial times, Sept 2019
</ref>
== 計算複雜度 ==
[[計算複雜性理論|複雜度]]理論研究解決計算問題所需的資源如何隨問題的大小變化，[[量子复杂性理论|量子複雜度理論]]延伸古典計算複雜度理論到[[量子圖靈機|通用量子電腦]]可以完成的工作上，對於建造量子電腦或處理[[量子退相干|退相干]]和雜訊的困難則忽略不計。<ref name=":5">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 由於[[量子資訊]]比古典資訊更廣義 ，很顯然量子電腦可以有效地模擬任何[[演算法|古典演算法]] 。
[[BQP (複雜度)|Bounded-error quantum polynomial time]]（BQP）這個複雜度類別包括通用量子電腦在多項式時間能解決的決策問題，它和古典複雜度類別的關係是<math>P\subseteq BPP\subseteq BQP\subseteq PSPACE</math> ， <ref name=":6"></ref> 這些子集關係之中有沒有真子集仍是未決問題。
與答案為是或否的決策問題不同，抽樣問題要求從[[機率分佈|機率分布]]中抽取樣本。<ref name=":7">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 如果有古典演算法可以有效地從任意量子電路的輸出中抽樣，則[[多項式譜系]]將崩潰到第三級，普遍認為這是極不可能的。 玻色子抽樣是較具體的提議，其古典困難度來自於計算具有複數元素的大矩陣其[[积和式|積和式]]的困難度，而那是P#-complete的問題。<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 用於得出此結論的論點也已擴展到IQP抽樣，<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 並只需假設問題的平均和最壞情況複雜度相同。
== 超多項式加速 ==
下列[[算法|演算法]]對已知的最好的古典演算法提供[[时间复杂度|超多項式]]加速：<ref></ref>
=== 秀爾整數分解演算法 ===
秀爾演算法用 <math>\tilde{O} (n^3)</math>時間分解n-位元整數，<ref name=":2" /> 而已知的最好的古典演算法需要<math>2^{O(n^{1/3})}</math>時間，複雜度的最佳上限是 <math>O(2^{n/3+o(1)})</math> 。 它還能加速任何可化簡成整數分解的問題。 <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
這個演算法在歷史上和實務上都對量子計算很重要，它是第一個用多項式時間解決困難古典計算問題的量子演算法。 <ref name=":2">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 對其困難度的信念強烈到當今最常見的加密協議[[RSA]]就是根據整數分解。 <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 能重複成功運行這種演算法的量子電腦有潛力破解這種加密系統。 <ref></ref> 需要避免迫在眉睫的這種風險被稱為Y2Q，名稱來自[[2000年問題]]的別名"Y2K"。
=== 玻色子抽樣 ===
這是基於一個古典計算問題：將全同[[光子]]穿過線性光學網絡用來解決某些抽樣和檢索的問題，在一些猜測性的假設下，對古典計算是很棘手的。 <ref name=":3">Liquid error: wrong number of arguments (given 1, expected 2)</ref> 然而，已經有研究顯示，如果系統具有足夠大的失真和雜訊，古典電腦能夠有效率地模擬玻色子抽樣問題。 <ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
迄今為止，最大的玻色子抽樣實驗能做到6個光學模式，一次最多可以處理6個光子。<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 對於包含 n 個光子 和 m 個輸出模式的系統，模擬玻色子抽樣的古典演算法最好的執行時間是 。 <ref name=":4">Liquid error: wrong number of arguments (given 1, expected 2)</ref> BosonSampling 是一個用 R 寫的開放源碼實作，估計需要50個光子才能達成玻色子抽樣的量子優越性。
=== 對隨機量子電路的輸出分佈抽樣 ===
在模擬任意隨機量子電路的演算法當中，已知最佳的演算法需要的時間隨量子位元個數指數式地上升，因此一個研究小組估計50個量子位元可能就足以達成量子優越性。<ref name="Boixo">Liquid error: wrong number of arguments (given 1, expected 2)</ref> Google已經宣布打算在2017年底前用49量子位元的晶片展示量子優越性，方法是對其輸出分布抽樣，這個抽樣用古典電腦將無法在合理時間內模擬。<ref name=":9"></ref> 然而56量子位元的量子電路模擬已經在[[超級電腦]]上完成， 這可能讓達成量子優越性所需的量子位元數增加。<ref name=":8"></ref>
== 懷疑論 ==
因為退相干和雜訊，量子電腦比古典電腦更容易受到資料錯誤的影響。 閾值定理指出，有雜訊的量子電腦只要每一步計算的錯誤率低於某個值，就可以用量子錯誤修正碼<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref><ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref> 模擬無雜訊的量子電腦 ，數值模擬的結果指出該閾值可以高達3%。<ref>Liquid error: wrong number of arguments (given 1, expected 2)</ref>
然而，錯誤修正所需的資源會如何隨量子位元數上升並不清楚。 懷疑論者指出，大型量子系統中未知的雜訊行為是成功實作量子電腦和達成量子優越性的潛在障礙。 <ref></ref>
== 參考資料 ==
<nowiki>
[[Category:計算複雜性理論]]
[[Category:量子計算]]</nowiki>
https://ift.tt/31zZoVv
