量子計算機：誤解帶來的樂觀與恐慌

我們用了之前四期的時間從工程，功耗，時空概念及複雜理論討論了計算機的極限以及面對這些極限科學家們所採取的措施。本期文章是討論計算機極限的最後一篇，我們將跳出傳統計算機的領域，從新興科技的角度入手，通過對其極限的討論，打破多年來人們對他們的誤解。

基於前四期所說到的傳統計算機所面臨的極限，當下計算機的研究越來越多地跳出了傳統計算機的範疇。其中最熱門的莫過於量子計算機。

對量子計算機的熱捧讓我們覺得量子計算機即將通過強大的計算能力取代傳統計算機並解決所有之前傳統計算機無法解決的問題。普通用戶漸漸地有了擁有一台量子計算機的願景。而傳統計算機架構師們漸漸地對量子計算機心生恐慌，害怕量子計算機的橫空出世讓自己多年的研究變得不值一提。

然而這項科技的的發展真會如我們所料給這個社會帶來翻天覆地的變化嗎？用百度高級架構師歐陽劍在2017年計算機體系結構會議ASPLOS上講的一句話來總結，當下這些科技發展確實快，然而之中有真切的發展，更有輿論的泡沫。那我們就來看看量子計算機到底在多大程度上影響了計算機的發展。（本文僅對量子計算機的極限作討論，對其原理的解釋和當下量子計算機發展的程度，讀者可參照往期原理的文章）

量子計算這一概念在1969年被史蒂芬·威斯納首先提出，並將其列入了他1983年發表的論文中[1]。論文發表的前一年，理查德·費曼在一次公開演講中也提出了利用量子體系實現通用計算的想法。而這一想法在1985年大衛·杜斯提出的量子圖靈機模型中首次得到了驗證[2]。當時人們研究量子計算機的初衷是為了模擬量子現象，服務於物理學。當使用計算機模擬量子現象時，由於龐大的希爾伯特空間所帶來的龐大數據分析使得一次模擬所需運算時間變得相當長，甚至可能窮科學家一生也看不到一次完整的結果。於是量子計算機的研究應運而生。

量子計算因其疊加和糾纏的特性對傳統計算做了極大的擴充。量子計算機對每一個疊加分量實現的變換相當於一種經典計算，所有這些傳統計算同時完成，並按一定的概率振幅疊加起來，給出量子計算機的輸出結果。這種計算稱為量子并行計算[3]。

從80年代的以理論推導為主的研究，到九十年代彼得·秀而提出量子質因式分解演算法[4]，到D-Wave公司發布的D-Wave One 量子模擬器，再到如今谷歌，IBM從上層編程語言到底層電路設計的一整套對通用量子計算機研究成果，量子計算機的研究可謂是飛速發展。

然而人們對其技術本身的誤解，在媒體的放大下給了人們一種量子計算機將無所不能的印象。經濟學人雜誌在2007年2月15日的期刊里曾說道：「量子計算機將通過并行處理所有可能性的方式在理論上可以有效解決NPC集合的問題（關於NPC集合問題的討論請參見《價值百萬美金的問題》）」。

D-Wave 公司在2009年時發布製造了128位的量子計算機的大新聞，很快受到了業界的反駁與指責[5][6]。就連2017年製造的光量子計算機在發布后也受到了褒貶不一的輿論。那麼量子計算機的極限到底在哪兒呢？本文將從有效計算和計算能力兩個方面來討論。

我們先來看量子計算機能夠有效（在多項式級時間裡）解決怎樣的問題。在《一個無法證明的邏輯問題》 一文中我們提到了圖靈機的概念。圖靈把所有問題分成了可判定（decidable) 和不可判定（undecidable) 兩種。而圖靈機只考慮可判定的問題集合。上一期中，我們把可判定的問題集合按照其複雜度分成了了P類，NP類和NPC類的問題。這些問題的關係可由圖一表示。

△ 圖一：複雜度問題的分類。

其中PSPACE類是指傳統計算機可以用多項式級複雜度的內存通過非多項式級複雜度的時間解決的問題集合(包括象棋對弈等）。現在能用傳統計算機有效解決的僅僅是P類問題，例如測試一個數是否是質數，或冒泡排序等。注意筆者所說的有效解決是指在多項式級時間內解決，並不代表傳統計算機只能解決該類問題。實際上作為圖靈機，傳統計算機可以解決所有的可判定問題（即PSPACE集合內所有的問題），只是所需時間的長短不同罷了。

那麼媒體所說的用量子計算機有效解決NPC問題是否可行呢？答案是否定的。其實時至今日，計算機科學家們能找到的通過量子計算的特點將NP類問題轉化為P類問題的演算法也是寥寥無幾，而其中最常見的就是階層的計算。也就是說，能利用到量子計算特性來有效解決傳統計算機無法有效解決的程序其實並不多。在量子計算機只能有效解決少數NP問題的當下，NPC問題並不能靠量子計算機得到有效地解決[5]。

原因很簡單，因為該類問題其實是一個黑匣子，而我們只能通過猜答案並驗證的方式來得到結果（而非對其進行直接計算）。舉個例子，如果一個問題有 s 種可能的答案，s 的大小隨著問題輸入的大小呈指數增長。我們在運氣逆天的情況下能一次猜中答案，而在人品欠佳的時候我們需要試 s 次之後得到答案。也就是說，傳統計算機需要平均 s/2 次試錯來解決這類問題。

現在我們把這類問題放到量子計算機上來。Lov Grover在1996年的論文中找出了用量子計算通過 √s 步來獲得該類問題答案的演算法[7]。從 s/2 次到 √s 次的試錯在很多情況下確實會帶來客觀的速度提升。比如在100萬可能性中我們可以從之前的平均50萬次試錯減少到1000次，但即便是 √s 也只是較簡單的指數級複雜度，並非是多項式級的複雜度（因為s仍然會隨著問題輸入的大小呈指數增長）。

而早在在2002年，Scott Aaronson就指出該類問題如果用上述的黑匣子試錯的方式解決，即便是量子計算機也無法在多項式級複雜度的時間裡解決[8]。正如上期文章中提到的，解決NPC類的演算法是否存在到現在仍未得到證實，但可以肯定的是，單用量子計算機的特性是無法有效解決這類問題的。於是Scott Aaronson在現有的複雜度理論上提出了一個新的集合，並命名為BQP類問題（Bounded-error, Quantum, Polynomial）。

△ 圖二：量子計算機能解決的BQP類問題。

如圖二所示，BQP類問題包含了所有P類問題和少數NP類問題，值得注意的是，BQP類的問題包含了一些非NP類的問題。也就是說有那麼一些問題用量子計算機解決所花的時間會比傳統計算機驗證該類問題所花的時間更少。但無論如何，解決BQP類問題，就是量子計算機所能達到的極限。支持P≠NP結論的計算機科學家們同理抱持著量子計算機無法解決NPC類問題的信念。

1998年Daniel Abrams在論文中提到如果在量子力學的公式中加入一項非線性的特性，量子算計機就能有效地解決NPC類的問題[9]。但如果加入的這一項非線性特徵如果成立，那麼海森堡的不確定性原理將就此被推翻，信息傳輸也將突破光速的限制。正如Daniel Abrams在文中提到，這一特性恐怕只能用來理解為什麼量子力學無法存在非線性特性了。換言之，這個理論也也從旁佐證了量子計算機解決NPC類問題的不可行性。

當然值得注意的是，雖然BQP類問題包含了所有P類問題，也就是說傳統計算機能解決的問題量子計算機都能解決，但這並不代表著量子計算機在所有程序的運行都能快過傳統計算機。只有適合用量子演算法的問題才能使量子計算機的運行速度超過傳統計算機。

再從計算能力來看量子計算機和傳統計算機的差別。這裡計算能力是指量子計算機是否能超越圖靈機，做到傳統計算機無法做到的事情。早在八十年代量子計算機理論還處在推到階段的時候，物理學界曾做過這樣一個關於封閉類時曲線（Closed Timelike Curve，CTC）的思想實驗。CTC實際可以看做成一個時間閉環，讓任何時間發展結果的時間點和其開始的時間點相重合。假設我們有一台計算機，能在無所謂多長但有限時間內完成計算之後將計算結果送回到計算開始的時間，那麼一切NPC甚至更複雜的問題都會迎刃而解。

當然這個思想實驗存在和「祖父悖論」相同的矛盾，例如如果在計算結果送回之後你關掉了計算機會出現什麼等等。雖然物理學家大衛·多伊奇（David Deutsch）在1991年通過對平行宇宙的解釋巧妙地避開了這個問題，對CTC的研究仍然停留在假想階段。然而假想的實驗並不能阻止計算機科學家們對量子計算機極限的探討。2008年Scott Aaronson再次發表論文[10]，在假設CTC存在的情況下得出量子計算機和傳統計算機等價的理論。也就是說即便是CTC存在，量子計算機的計算能力也無法解決超出PSPACE類問題。換句話說，量子計算機就其本質來說和圖靈機並無差別。

本文從計算的有效性及計算能力兩個方面討論了量子計算機的極限。總結來說，從計算有效性來看，量子計算機能夠有效解決一些傳統計算機無法有效解決的問題，比如階層的計算。但目前已知可歸納到這一類的問題並不多。而從計算能力來看，量子計算機的本質和圖靈機並無差別，並不能解決不可判定的問題。一切對新興科技過度的樂觀和不必要的恐慌都來自於對其本身的誤解。當然量子計算機的極限並沒有阻止科學家們對NPC問題的探究，如果計算機理論暫時無法解決這些複雜度的問題，希望物理學界能在未來的某一天對這些問題作出結論。

參考文獻：

[1]. Wiesner, S, 「Conjugate Coding」, Sigact news, 18: 78–88, 1983.

[2]. David Deutsch, 「Quantum theory, the Church-Turing principle and the Universal Quantum Computer」, Proc. R. Soc. Lond.

[3]. https://en.wikipedia.org/wiki/Quantum_computing

[4]. Shor, Peter W.（1997）, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26 (5): 1484–1509

[5]. Scott Aaronson, 「The Limit of Quantum,」 Scientific Amarican, 2008

[6]. Erico Guizzo, 「Loser: D-Wave Does Not Quantum Compute,」 IEEE Spectrum, Dec 2009.

[7]. Lov K Grover, 「A Fast Quantum Mechanical Algorithm for Database Search,」 Quantum Physics, v3, 1996.

[8]. Scott Aaronson, 「Forrelation: A Problem that Optimally Separates Quantum from Classical Computing,」 STOC』15, June 14–17, 2015, Portland, Oregon, USA.

[9]. Daniel S. Abrams and Seth Lloyd, 「Nonlinear Quantum Mechanics Implies Polynomial Solution for NP-complete and #P Problems,」 Quantum Physics, Phys.Rev.Lett. 81 (1998) 3992-3995.

[10]. Scott Aaronson and John Watrous, 「Closed Timelike Curves Make Quantum and Classical Computing Equivalent,」 Quantum Physics, arXiv:08082669.