“哈加物理學家開發出‘量子便褲’”，諷刺週刊《洋蔥報》的頭條新聞寫道。文章解釋說，透過利用一種奇異的“薛定諤的褲子”二元性，這些非牛頓褲子可以同時表現得像正裝和休閒裝。《洋蔥報》的作者顯然是在惡搞那些充斥著大眾科學媒體十年的關於量子計算的令人興奮的文章。
一個常見的錯誤——例如 2007 年 2 月 15 日的《經濟學人》雜誌——是聲稱原則上量子計算機可以快速解決一組特別困難的數學難題，稱為 NP 完全問題，即使是最好的現有計算機也無法快速解決（就目前所知）。量子計算機本應透過擁有能夠同時處理每個可能答案的硬體來實現這一壯舉，而不是同時具有正裝和休閒裝的特性。
如果我們真的可以製造出一臺能夠輕鬆解決 NP 完全問題的神奇計算機，世界將會變得非常不同：我們可以要求我們的神奇計算機尋找可能存在於股票市場資料、天氣記錄或大腦活動記錄中的任何模式。與今天的計算機不同，找到這些模式將完全是例行公事，並且不需要對問題的主題有詳細的瞭解。這臺神奇的計算機還可以自動化數學創造力。對於任何數學聖盃——例如哥德巴赫猜想或黎曼猜想，這兩個猜想都已經一百多年沒有得到解決——我們可以簡單地要求我們的計算機搜尋所有可能的證明和反證，最多包含比如十億個符號。（如果證明比這長得多，我們甚至不清楚我們是否想閱讀它。）
支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保有關塑造我們當今世界的發現和想法的具有影響力的故事的未來。
如果量子計算機承諾如此強大的數學能力，也許我們應該期望它們與曲速引擎發生器和反重力盾牌大約在同一時間出現在商店貨架上。但是，儘管我們不應該接受通常的炒作，但在我看來，將量子計算視為科幻小說同樣是誤導。相反，我們應該找出量子計算機的侷限性，以及如果我們擁有它們，它們真正能做什麼。
自從物理學家理查德·費曼首次提出量子計算的概念以來的 26 年裡，計算機科學家在弄清楚量子計算機擅長解決哪些問題方面取得了巨大進展。根據我們目前的理解，它們將為少數特定問題提供顯著的加速，例如破解廣泛用於網際網路貨幣交易的密碼。然而，對於其他問題，例如下棋、安排航班和證明定理，現在的證據強烈表明，量子計算機將遭受與當今經典計算機相同的許多演算法限制。這些限制完全獨立於構建量子計算機的實際困難，例如退相干（量子計算機與其環境之間不希望有的相互作用，這會引入錯誤）。特別是，即使物理學家設法構建了一臺完全沒有退相干的量子計算機，對計算機可以程式設計執行的數學可能性的限制仍然適用。
難、更難、最難
量子計算機為何可以在某些問題（例如破解程式碼）上提供加速，但在其他問題上卻不能？難道更快的計算機不就是更快的計算機嗎？答案是否定的，要解釋原因，需要直接深入計算機科學的智力核心。對於計算機科學家來說，問題的關鍵在於解決問題所需的時間隨著問題規模的增加而增長的速度有多快。時間以演算法達到解決方案所需的基步驟數來衡量。例如，使用小學方法，我們可以在時間量級與數字平方成正比的時間內，即 n 2 （時間量級被稱為“n 的多項式”）內，將兩個 n 位數字相乘。但是對於將一個數字分解為素數，即使是最先進的已知方法也需要時間量級與數字位數呈指數增長的時間（特別是，像 2 的 n 的立方根次方）。因此，因式分解似乎本質上比乘法更難——當我們達到數千位數字時，這種差異比 Commodore 64 和超級計算機之間的差異重要得多。
計算機可以在合理的時間內解決的問題型別，即使對於較大的 n 值，也是那些我們有演算法可以使用步數與 n 的固定冪（例如 n、n 2 或 n 2.5 ）成正比增長的問題。計算機科學家稱這種演算法為高效演算法，而可以透過高效演算法解決的問題被稱為屬於複雜度類 P，其中 P 代表“多項式時間”。
P 類問題的一個簡單示例是：給定一張公路地圖，是否每個城鎮都可以從其他每個城鎮到達？P 類也包含一些高效解決方案不太明顯的問題，例如：給定一個整數，它是素數（如 13）還是合數（如 12）？給定一份男人和女人彼此願意結婚的名單，是否有可能將每個人與一位願意的伴侶配對？
但是，假設現在給你各種尺寸的盒子，你想要一種將它們裝進後備箱的方法。或者假設給你一張地圖，你想用紅色、藍色或綠色為每個國家著色，以便沒有兩個相鄰的國家顏色相同。或者給你一份由橋樑連線的島嶼列表，你想要一次訪問每個島嶼的遊覽。儘管已知對於這些問題存在比嘗試每種可能的解決方案稍好的演算法，但尚不知有從根本上更好的演算法。每個已知的演算法都需要時間量級隨著問題規模呈指數增長的時間。
事實證明，我剛剛列出的這三個問題具有一個非常有趣的特性：它們都是“相同”的問題，因為其中任何一個問題的有效演算法都將意味著所有其他 NP 問題的有效演算法。多倫多大學的斯蒂芬·A·庫克、加州大學伯克利分校的理查德·卡普和現任波士頓大學的列昂尼德·列文在 20 世紀 70 年代得出了這個非凡的結論，當時他們發展了 NP 完全性理論。
NP 代表“nondeterministic polynomial time”（非確定性多項式時間）。不要擔心那是什麼意思。基本上，NP 是這樣一類問題，對於這類問題，一旦找到解決方案，就可以在多項式時間內（類似於 n 2 等）識別為正確——即使解決方案本身可能很難找到。例如，如果您獲得一張包含數千個島嶼和橋樑的地圖，可能需要數年時間才能找到一次訪問每個島嶼的遊覽。然而，如果有人向您展示一次遊覽，則很容易檢查此人是否成功解決了問題。當一個問題具有此屬性時，我們說它屬於 NP 類。NP 類捕獲了大量具有實際意義的問題。請注意，所有 P 類問題也是 NP 類問題，或者換句話說，P 類包含在 NP 類中。如果您可以快速解決一個問題，您也可以快速驗證解決方案。
NP 完全問題本質上是最難的 NP 問題。它們是庫克、卡普和列文發現的具有以下特性的問題：如果找到其中任何一個問題的有效演算法，就可以將其調整為解決所有其他 NP 問題。
NP 完全問題的有效演算法將意味著計算機科學家目前對 P 類、NP 類和 NP 完全類的看法完全錯誤，因為它將意味著每個 NP 問題（包括所有 NP 完全問題）實際上都是 P 類問題。換句話說，P 類將等於 NP 類，這寫為 P = NP。
這樣的演算法存在嗎？P 等於 NP 嗎？這確實是一個價值百萬美元的問題——它獲得了馬薩諸塞州劍橋市克萊數學研究所 1,000,000 美元的獎勵——並且它至少在三個電視節目（《辛普森一家》、《飛出個未來》和《數字追兇》）中扮演了客串角色。
自從這個問題被認識到以來的半個世紀裡，沒有人為 NP 完全問題找到有效的演算法。因此，即使我們還不夠聰明，無法理解為什麼會這樣或將其證明為定理，但如今的計算機科學家幾乎普遍認為 P 不等於 NP，或者 P ≠ NP。
量子能做什麼
如果我們承認 P ≠ NP，那麼解決 NP 完全問題的多項式時間的唯一希望仍然存在：即擴大我們對“計算機”的理解。乍一看，量子力學似乎提供了所需的資源。量子力學使得在相對少量粒子的狀態中儲存和操縱大量資訊成為可能。為了瞭解這是如何發生的，假設我們有 1,000 個粒子，並且每個粒子在測量時都可以被發現是向上或向下旋轉。就我們的目的而言，粒子向上或向下旋轉意味著什麼並不重要；重要的是粒子具有某種特性，在測量時具有兩個值之一。
為了描述這組粒子的量子態，必須為測量粒子的每個可能結果指定一個數字。這些數字被稱為可能結果的幅度，並且與每個結果的機率有關，但與機率不同，量子幅度可以是正數或負數（實際上，它們是複數）。例如，需要一個幅度來表示所有 1,000 個粒子將被發現向上旋轉的可能性，另一個幅度表示發現前 500 個粒子向上旋轉，而後 500 個粒子向下旋轉的可能性，依此類推。有 2 1,000 種可能的結果，或大約 10 300 種，這就是需要的數字數量——比可見宇宙中的原子還多！這種情況的技術術語是，這 1,000 個粒子處於這 10 300 個狀態的疊加態。
換句話說，我們可以同時在我們的 1,000 個粒子上儲存 10 300 個數字。然後，透過對粒子和一些輔助粒子執行各種操作——也許用一系列雷射脈衝或無線電波擊打它們——我們可以執行一種演算法，該演算法同時轉換所有 10 300 個數字（每個數字都是一個潛在的解決方案）。如果在執行完此操作後，我們可以準確地讀出粒子的最終量子態，那麼我們真的會擁有一臺神奇的計算機：它將能夠檢查 10 300 個問題的可能解決方案，並且在最後我們可以快速識別出正確的解決方案。
不幸的是，這裡有一個陷阱。當測量粒子時（這是讀取其最終狀態所必需的），量子力學的規則規定，測量將隨機挑選出 10 300 種可能性中的一種，而所有其他可能性都將消失。（回到哈加開發的量子便褲，如果你嘗試穿上它們，你會發現自己要麼穿著正裝，要麼穿著休閒裝，而不是兩者都穿。）我們似乎並沒有比使用經典計算機並嘗試一個隨機選擇的可能解決方案更好——在任何一種情況下，我們最終只瞭解一個這樣的可能解決方案。
令人高興的是，我們仍然可以玩一些技巧，從量子粒子中榨取一些優勢。當正幅度與負幅度結合時，幅度可以相互抵消，這種現象稱為相消干涉。因此，一個好的量子計算機演算法將確保導致錯誤答案的計算路徑將以這種方式抵消。它還將確保導致正確答案的路徑都具有相同符號的幅度——這會產生相長干涉，從而提高了在最後測量粒子時找到它們的機率。
對於哪些計算問題，我們可以編排這種干涉，使用比經典方法解決問題所需的步驟更少的步驟？
1994 年，現任麻省理工學院的彼得·肖爾發現了第一個量子演算法示例，該演算法可以顯著加速解決實際問題的速度。特別是，肖爾展示了量子計算機如何使用步數僅以約 n 2 的速度增長的方式分解 n 位數字——換句話說，在多項式時間內。如前所述，已知的經典計算機的最佳演算法使用的步數呈指數增長。
黑盒
因此，至少對於因式分解，使用量子方法確實可以比已知的經典演算法獲得指數級的加速。但是，儘管人們普遍誤解，但因式分解問題既不是已知的也不是被認為是 NP 完全問題。為了建立他的演算法，肖爾利用了合數及其因子的某些數學特性，這些特性特別適合產生量子計算機可以蓬勃發展的相長干涉和相消干涉型別。NP 完全問題似乎不具有這些特殊屬性。直到今天，研究人員只發現了少數其他量子演算法，這些演算法似乎可以為問題提供從指數時間到多項式時間的加速。
因此，問題仍然沒有答案：是否存在解決 NP 完全問題的有效量子演算法？儘管進行了很多嘗試，但尚未找到這樣的演算法——儘管毫不奇怪，計算機科學家無法證明它不存在。畢竟，我們甚至無法證明不存在解決 NP 完全問題的多項式時間經典演算法。
我們可以說的是，能夠有效解決 NP 完全問題的量子演算法，就像肖爾的演算法一樣，必須利用問題的結構，但方式遠遠超出當今的技術。不能透過將問題視為無結構的“黑盒”來獲得指數級的加速，該黑盒由要並行測試的指數數量的解決方案組成。然而，仍然可以從這種黑盒方法中擠出一些加速，計算機科學家已經確定了這種加速有多好——以及有多有限。產生加速的演算法是第二大量子演算法。
黑盒方法可以透過假裝您正在尋找一個難題的解決方案來說明，而您唯一知道如何執行的操作是猜測一個解決方案並檢視它是否有效。假設有 S 個可能的解決方案，其中 S 隨著問題規模 n 的增加而呈指數增長。您可能會很幸運，第一次嘗試就猜對了解決方案，但在最壞的情況下，您將需要 S 次嘗試，平均而言，您將需要 S/2 次嘗試。
現在假設您可以詢問量子疊加中的所有可能解決方案。1996 年，貝爾實驗室的洛夫·格羅弗開發了一種演算法，在這種情況下，僅使用約 √—S 步即可找到正確的解決方案。從 S/2 到 √—S 的加速對於某些問題來說是一個有用的進步——如果有一百萬個可能的解決方案，您將需要大約 1,000 步而不是 500,000 步。但是平方根不會將指數時間轉換為多項式時間；它只是產生一個較小的指數。而格羅弗的演算法對於這種黑盒搜尋來說已經是最好了：1994 年，研究人員已經表明，任何黑盒量子演算法至少需要 √—S 步。
在過去的十年中，研究人員已經表明，類似的適度加速是除搜尋列表之外的許多其他問題的極限，例如計算選舉中的選票、在地圖上查詢最短路線以及玩國際象棋或圍棋等策略遊戲。一個特別困難的問題是所謂的碰撞問題，即在一個長列表中查詢兩個相同或“碰撞”的專案的問題。如果有一種快速的量子演算法來解決這個問題，那麼許多安全的電子商務基本構建模組在量子計算機世界中將變得毫無用處。
在一個列表中搜索一個專案就像大海撈針，而搜尋碰撞就像尋找兩塊相同的乾草，這為問題提供了一種量子計算機可以潛在利用的結構。儘管如此，我在 2002 年表明，在黑盒模型中，任何量子演算法都需要指數時間才能解決碰撞問題。
誠然，這些黑盒限制並沒有排除發現解決 NP 完全問題甚至更難問題的有效量子演算法的可能性。然而，如果存在這樣的演算法，它們將不得不以與我們所見過的任何演算法不同的方式利用問題的結構，這與解決相同問題的有效經典演算法必須做到的方式非常相似。量子魔法本身不會奏效。基於這種洞察力，許多計算機科學家現在不僅推測 P ≠ NP，而且量子計算機無法在多項式時間內解決 NP 完全問題。
神奇的理論
我們所知道的一切都與量子計算機是終點線的可能性一致——也就是說，它們是與物理定律相容的最通用的計算機型別。但是物理學家還沒有最終的物理理論，因此不能排除未來理論有一天可能會揭示一種物理手段來有效解決 NP 完全問題。正如您所預料的那樣，人們推測了更強大的計算機型別，其中一些計算機將使量子計算機看起來像自動售貨機一樣平庸。然而，它們都將依賴於對物理定律的推測性改變。
量子力學的核心特徵之一是稱為線性的數學性質。1998 年，當時都在麻省理工學院的丹尼爾·S·艾布拉姆斯和塞思·勞埃德表明，如果在量子力學方程中新增一個小的非線性項，量子計算機將能夠有效地解決 NP 完全問題。在您過於興奮之前，您應該意識到，如果存在這樣的非線性項，那麼人們也可以違反海森堡不確定性原理併發送速度超過光速的訊號。正如艾布拉姆斯和勞埃德指出的那樣，也許對這些結果的最佳解釋是它們有助於解釋為什麼量子力學是線性的。
另一種推測型別的機器將透過在有限的時間內塞入無限數量的步驟來實現奢華的計算能力。不幸的是，根據物理學家目前的理解，時間似乎會退化為量子漲落的海洋——有點像泡沫而不是均勻的光滑線——在 10 –43 秒（普朗克時間）的尺度上，這似乎使這種機器成為不可能。
如果時間不能被任意薄地切割，那麼也許另一種有效解決 NP 完全問題的方法是利用時間旅行。研究這個問題的物理學家談論的不是時間機器，而是閉合類時曲線 (CTC)。本質上，CTC 是物質或能量可以沿著它行進以在過去與自身相遇的空間和時間路線，形成一個閉環。目前的物理理論對於 CTC 是否可以存在尚無定論，但這不妨礙我們詢問，如果 CTC 確實存在，那麼對於計算機科學來說會產生什麼後果。
似乎很明顯，人們可以如何使用 CTC 來加速計算：對您的計算機進行程式設計，使其花費解決問題所需的任何時間，然後將答案及時傳送回您自己，時間點在計算機啟動之前。唉，這個簡單的想法行不通，因為它忽略了著名的祖父悖論，即你回到過去殺死你自己的祖父（但那樣你就永遠不會出生，所以你永遠不會回到過去，因此你的祖父仍然活著生兒育女，然後你出生了，但是然後……）。在我們的環境中，如果您在收到來自未來的答案後關閉計算機，會發生什麼？
1991 年，牛津大學的物理學家大衛·多伊奇定義了一個使用 CTC 的計算模型，該模型避免了這種困難。在多伊奇的模型中，自然將確保當事件沿著構成 CTC 的圓形時間線展開時，永遠不會出現悖論，這一事實可以用來對在 CTC 內部迴圈以解決難題的計算機進行程式設計。
事實上，透過使用 CTC，我們可以有效地解決不僅是 NP 問題，甚至是表面上更大的類 PSPACE 中的問題。PSPACE 是可以在傳統計算機上使用多項式數量的記憶體解決但可能需要指數級時間的問題類。實際上，CTC 將使時間和空間成為可互換的計算資源。（直到現在我才不得不提及多項式記憶體約束，因為對於 P 類和 NP 類問題，計算機是否可以訪問超過多項式記憶體的記憶體無關緊要。）最近，安大略省滑鐵盧大學的約翰·沃特羅斯和我表明，在 CTC 中使用量子計算機而不是傳統計算機並不能有效地解決 PSPACE 之外的任何問題。換句話說，如果 CTC 存在，那麼量子計算機並不比經典計算機強大。
計算氪石
物理學家不知道未來的理論是否會允許任何這些非凡的機器出現。然而，在不否認我們無知的情況下，我們可以從不同的角度看待這種無知。與其從物理理論開始，然後詢問它們的計算含義，不如從假設 NP 完全問題很難開始，然後研究該假設對物理學的影響。例如，如果 CTC 可以讓我們有效地解決 NP 完全問題，那麼從 NP 完全問題難以解決的假設開始，我們可以得出結論，CTC 不可能存在。
在某些人看來，這種方法似乎過於教條。對我來說，這與假設熱力學第二定律或不可能進行超光速通訊沒有什麼不同——這是對技術的兩個早期限制，隨著時間的推移，它們贏得了物理原理的地位。是的，第二定律可能會在明天被實驗證偽——但在那之前，物理學家發現假設它是正確的，然後使用這個假設來研究從汽車發動機到黑洞的一切都更有用。我預測，NP 完全問題的難度有一天會被視為相同的：作為描述我們宇宙本質一部分的基本原理。無法預知未來應用這種基本原理會帶來什麼樣的理論啟示或實際後果。
與此同時，我們知道不要對量子計算機抱有幻想。對於某些人來說，量子計算機的明顯侷限性可能會令人失望。然而，人們可以給這些相同的侷限性一個更樂觀的解讀。它們意味著，儘管某些密碼在擁有量子計算機的世界中可能會被破解，但其他密碼可能仍將保持安全。它們增加了我們對量子計算完全有可能實現的信心——因為一種擬議的技術聽起來越像科幻漫畫，我們就應該越懷疑。（您更傾向於相信誰：是提供一種從量子真空中產生無限自由能源的裝置的銷售人員，還是提供一種比去年的型號更高效的冰箱的銷售人員？）最後，這些限制確保了計算機科學家將繼續努力設計新的量子演算法。就像沒有腳後跟的阿喀琉斯或沒有氪石的超人一樣，一臺沒有任何限制的計算機很快就會變得乏味。