終於，科學家們找到了只有量子計算機才能解決的問題

科學家們過去一直在尋找只有量子計算機才能解決的問題。現在他們終於找到了。

早在量子計算研究剛剛興起時，科學家們就知道這種未來主義的機器蘊含著某種無限的潛能。而在今年 5 月發表的一篇論文中，計算機科學家 Ran Raz（普林斯頓大學兼魏茨曼科學研究院教授） 和 Avishay Tal（斯坦福大學博士後研究員）為「量子計算在能力上將遠超一切傳統計算」這一概念提供了科學證據。

1993 年時，計算機學家將那些傳統計算望塵莫及，只有量子級計算才能解決的問題定義為 BQP 問題。而自 BQP 概念問世以來，計算機科學家們就一直在尋找夠格的 BQP 問題，他們將可能的 BQP 問題與那些傳統計算能解決的問題（也稱 PH 問題）進行對比，以此來判定某一特定問題是否屬於 BQP 問題。而在於 5 月發表的這篇論文中，Raz 和 Tal 已經成功的找到了第一個合格的 BQP 問題。

雖然論文對於實際構建一台量子計算機的工作來說沒有任何實際意義，但它確實地證明了「成熟的量子計算將會在量級上完虐傳統計算」這一概念。

量子級計算

理論計算機研究中的一個基本項目就是將問題根據複雜程度進行分類，也稱複雜度分級（Complexity Classes），即根據解決問題所需資源（如時間和內存）的多少進行分類。

其中最著名的兩個分類是「P」和「NP」，P 是傳統計算可以快速解決的所有問題。 （「這個數字是否是質數？」屬於 P）NP 是傳統計算機並不能迅速解決，但如果存在一個已知答案能夠快速驗證的問題（如「這個數的質因數有哪些？」屬於 NP）。計算機科學家認為 P 和 NP 是不同的類別，但證明 P 與 NP 不同卻是該領域最難以及最重要的問題之一。

1993 年，計算機科學家 Ethan Bernstein 和 Umesh Vazirani 為複雜度分類創造了一個新的類別，「有限錯誤量子多項式時間」類（bounded-error quantum polynomial time）」，即上文中所提到過的 BQP 問題。該定義類中包含量子計算機可以高效解決的所有決策問題，即答案為是或否的問題。兩位科學家同時還證明了量子計算機可以解決傳統計算機可以解決的所有問題，也就是證明了 BQP 分類中包含了 P 分類（這裡分類看為數學中集合的概念）。

但 Ethan 和 Umesh 無法確定 BQP 中是否也包含「多項式層次結構（Polynomial Hierarchy）」類問題，也稱 PH 類問題。PH 是 NP 的拓展，包含所有由 NP 類延伸出的問題，如通過添加「對於所有...來說是否存在...」。 當今的傳統計算機無法解決 PH 中的大多數問題，但如果 P 等於 NP，則可以將 PH 看作是傳統計算機可以解決的所有問題。換句話說，比較 BQP 和 PH 這兩種問題分類，便是為了確定量子計算機是否真的較傳統計算機具有優勢。

關於不同複雜度類別的問題可以參考「旅行推銷員問題（TSP）」。「是否存在通過若干個城市的一些路徑比另一些路徑更短」是一個 NP 問題。而一個 PH 問題則是「是否通過這幾個城市的最短路徑就是某個特定距離」。

德克薩斯大學的計算機科學家 Scott Aaronson 說：「PH 是最基本的古典複雜度分類之一。而我們想知道，量子計算在古典複雜度分類的標準中處於什麼樣的位置。」

區分出兩個複雜類別的最好方法是，找到一個可被證明為僅屬於其中一類的問題。 然而，由於基礎研究上的不足以及技術上的障礙，一直沒人能找到符合這種要求的問題。

Aaronson 說，如果你想找到一個僅屬於 BQP 而不屬於 PH 的問題，你必須找到一個從定義上傳統計算機不能有效證明答案的問題，這樣的問題「傳統計算機甚至不能有效地驗證答案，更別說找到它了。這就排除了我們在計算機科學中所考慮的許多問題。」

BQP 和 PH

假如你現在有兩個隨機數字序列生成器，而你需要解決這樣一個問題：這兩組序列是完全獨立的，還是以某種隱藏的形式相關聯的（比如一組是另一組序列的「傅里葉變換」）。Aaronson 在 2009 年首次提出了這種「關係（forrelation）」問題，並證明它屬於 BQP。但解決該問題的第二步將更為困難，因為你需要證明該關係不屬於 PH 類的集合。

Raz 和 Tal 這篇論文的成就便是實現了一種名為「Oracle（也稱「黑匣子」）」的 BQP 與 PH 的區分方式。 區分 BQP 和 PH 的最佳方式是測量解決每個問題所需的計算時間。但多倫多大學的計算機科學家 Henry Yuen 認為，目前我們對計算所需時間的認識還不足以讓人們得出某一問題所需的計算時間。

圖 | 普林斯頓大學理論計算機科學家 Ran Raz

正如 Yuen 所說的那樣，計算機科學家一般會測量一些其他的量來衡量計算所需的時間，比如計算出計算機在解決問題的過程中詢問「oracle」的次數。oracle 就像是一個提示，你不知道它是怎樣產生的，但你知道它是可靠的。

回到解決兩組數列是否相關的問題上，你可以先詢問 oracle 類似「每個發生器的第六個數字是什麼？」的問題，然後，根據每種計算機所需的提示數量來比較計算能力（需要更多提示的計算機計算速度較慢）。

Tal 說：「從某種意義上來說，我們更好地理解了這個模型。 模型更多涉及到的是信息而不是計算。」

圖 | 斯坦福大學理論計算機科學家 Avishay Tal

Raz 和 Tal 的這篇論文證明了量子計算機在解決 forrelation 問題時較傳統計算機所需的提示更少。 事實上，量子計算機只僅要一個提示就能解決問題，而即使有無限個提示，PH 中也沒有可以解決問題的演算法。Raz 說： 「這意味著有一個非常有效的量子演算法能夠解決這類問題，即那些傳統演算法無法解決的問題。這說明了 forrelation 問題在分類上屬於 BQP 而不是 PH。」

Raz 和 Tal 在四年前就已接近證明出這一結論，但他們無法完成證明中的重要一步。 然後就在論文發表的一個月前，Tal 看到一篇關於偽隨機數列產生器的論文，意識到這篇論文中的技術正是他和Raz的證明所需要的，於是才有了這篇論文的發表。

BQP 和 PH 得以區分的消息迅速傳遍了學界。在論文發表的第二天，喬治亞理工學院的計算機科學家 Lance Fortnow 便寫下 「量子複雜性分類層級真是搖擺不定。」 以示感慨。

該論文為量子計算的優越性提供了一個保證，即存在只有量子計算機才能解決問題。「即使 P 等於 NP，甚至存在更強的假設，傳統計算也無法達到量子計算級別。」 Fortnow 說。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！