經典計算的天花板：科學家找到只有量子計算才能解決的問題

選自QuantaMagazine

作者：Kevin Hartnett

機器之心編譯

參與：Huiyuan Zhuo、劉曉坤

在量子計算機研究的早期，計算機科學家提出了一個問題，他們知道這個問題的答案將會揭曉這些未來機器的強大力量背後的秘密。25 年過去了，問題仍然沒有解決。在 5 月底在線發布的一篇論文中《Oracle Separation of BQP and PH》，計算機科學家 Ran Raz 和 Avishay Tal 提供了強有力的證據，證明量子計算機具有超越任何傳統計算機能夠達到的計算能力。Raz 是普林斯頓大學和魏茨曼科學研究員的教授，Tal 是斯坦福大學博士後，他們定義了一類特定的計算問題。他們在一定程度上證明了量子計算機能夠有效解決這個問題，而傳統計算機卻永遠無法解決。自 1993 年以來，計算機科學家一直在找尋這樣一個問題，在當時他們首次定義了一類被稱為「BQP」的問題，它涵蓋了量子計算機可以解決的所有問題。

Oracle Separation of BQP and PH：https://eccc.weizmann.ac.il/report/2018/107/

計算機科學家希望將 BQP 與一類被稱為「PH」的問題進行對比，PH 涵蓋了任何可能的傳統計算機（甚至是一些未來文明所設計的不可思議的先進計算機）所能解決的問題。能否進行對比取決於能否找到一個被證明是 BQP 卻不是 PH 的問題。現在，Raz 和 Tal 做到了。

這一成果並沒有使量子計算機在任何實際意義上超越傳統計算機。比如，理論計算機科學家已經知道量子計算機可以解決傳統計算機所能解決的任何問題。同時，工程師仍在努力構建有用的量子計算機。但是 Raz 和 Tal 的論文證明了量子計算機和傳統計算機其實是不同的類別——即使在傳統計算機超越所有現實的世界中，量子計算機仍然會超越它們。

量子類別

理論計算機科學的基本任務是將問題按複雜度等級分類。一個複雜類包含在給定資源預算內所能解決的所有問題，其中資源可能是指時間或內存。

計算機科學家已經找到了一種有效的演算法，例如用於測試一個數字是否是素數。然而，他們仍沒有找到一個有效的演算法來計算大數的素數因子。因此，計算機科學家認為（但無法證明）這兩個問題屬於不同的複雜度等級。

兩個最著名的複雜度等級是「P」和「NP」。P 是傳統計算機可以快速解決的所有問題。（「這個數字是否是素數？」屬於 P。）NP 是傳統計算機不能迅速解決的所有問題，但可以快速驗證一個答案。（「哪些數是這個數的素數因子？」屬於 NP。）計算機科學家認為 P 和 NP 是不同的類別，但事實上證明它們的不同是該領域最難和最重要的開放性問題。

P∈NP∈PH，BQP 覆蓋所有的 P 問題和部分的 NP、PH 問題（未證明）；現在人們終於找到了屬於 BQP 而不屬於 PH 的問題。圖源：Lucy Reading-Ikkanda / Quanta Magazine

1993 年計算機科學家 Ethan Bernstein 和 Umesh Vazirani 為「有界誤差量子多項式時間」定義了一個新的複雜度等級，他們稱之為 BQP。他們定義的類包含量子計算機可以有效解決的所有決策問題——問題的答案為是或否。同時他們也證明了量子計算機可以解決傳統計算機可以解決的所有問題。也就是說，BQP 包含 P 中的所有問題。

但是他們無法確定 BQP 是否包含另一個重要的類「PH」（即「多項式分層」）中找不到的問題。PH 是 NP 的一個推廣。這意味著如果你從 NP 中的一個問題出發，並通過「存在」和「任意」這樣的限定語句進行分層以使其更為複雜，PH 也包含了所有你遇到的問題。現今傳統計算機無法解決 PH 中的大多數問題，但如果 P 被證明等價於 NP，則可以將 PH 看作是傳統計算機可以解決的所有問題的類。換言之，比較 BQP 和 PH 是為了確定是否量子計算機優於傳統計算機，那麼即使傳統計算機能（出乎意料地）解決比現在的量子計算機更多的問題，量子計算機仍能存在。德克薩斯大學奧斯汀分校的計算機科學家 Scott Aaronson 說：「PH 是最基本的傳統複雜度等級之一。所以我們想知道量子計算機如何適應傳統複雜度理論？」

當談到複雜度等級時，舉個例子會很有幫助。「旅行推銷員問題」詢問是否存在一條途經一些城市且短於給定距離的路徑。這是個 NP 問題。一個更複雜的問題是，通過這些城市的最短路徑是否等於給定距離。這個問題是 PH。

區分兩個複雜度等級的最好方法是找到一個問題，其能夠被證明屬於一個類而不屬於另一個類。然而由於基礎和技術上的障礙，找到這樣一個問題很有挑戰性。

如果你想要找到一個在 BQP 但不在 PH 中的問題，你必須確定一些東西，也就是 Aaronson 說的：「根據定義，一個傳統計算機甚至無法有效驗證答案，更別說找到答案了。這就排除了我們在計算機科學中考慮的許多問題。」

詢問 oracle

問題是這樣的。設想你有兩個隨機數字生成器，每個生成器產生一個數字序列。你的計算機得到的問題是這樣的：這兩個序列是否完全獨立，還是以某種隱秘的方式相關（例如，一個序列是另一個序列的「傅立葉變換」）？Aaronson 在 2009 年介紹了這種「forrelation」問題並證明其屬於 BQP。更難的第二步是證明 forrelation 不在 PH 中。

普林斯頓大學的理論計算機科學家 Ran Raz 找到一種分離兩個計算類的方法。

從特定的意義上來說，這正是 Raz 和 Tal 所做的。他們的論文實現了 BQP 和 PH 之間的分離，被稱為「oracle」（或「黑箱」）分離。這是計算機科學中常見的一種結果，當研究人員真正想證明的事情超出他們的理解範圍時，他們會採取這種方法。

區分像 BQP 和 PH 這樣的複雜度等級的最佳方法實際上是測量解決每個問題所需的計算時間。但如多倫多大學的計算機科學家 Henry Yuen 所說：「計算機科學家對實際的計算時間沒有充足的理解或測量能力。」因此，計算機科學家測量了其它一些他們希望可以側面反映無法測量的計算時間的東西：他們計算出計算機需要諮詢 oracle 以便得出答案所需的次數。oracle 就像一位提示者。你不知道它的提示如何產生的，但你知道它們是可靠的。

如果你的問題是要弄清楚兩個隨機數字生成器是否潛在相關，那麼你可以向 oracle 提問，比如說：「每個生成器的第六個數字是什麼？」然後你根據每種計算機解決問題所需的提示數量比較它們的計算能力。需要更多提示的計算機速度更慢。

Tal 說：「從某種意義上來說，我們能更好地理解模型。它傳遞更多的是信息而不是計算。」

斯坦福大學的理論計算機科學家 Avishay 使用 oracle 分離來區分 BQP 和 PH。

Raz 和 Tal 的新論文證明了，量子計算機需要比傳統計算機少得多的提示來解決 forrelation 問題。事實上，量子計算機僅需要一個提示。而即使有無窮多的提示，PH 中也沒有可以解決問題的演算法。Raz 說：「這意味著存在一個非常有效的量子演算法可以解決這個問題。但如果你僅考慮傳統演算法，即使你擁有很高等級的傳統演算法，它們也無法解決。」這表明，對於 oracle 而言，forrelation 問題在 BQP 而不是 PH 中。

差不多 4 年以前，Raz 和 Tal 幾乎達成了這一結果，但他們無法在證明中完成一個步驟。然後就在一個月前，Tal 聽到一篇關於偽隨機數生成器的新論文《Pseudorandom Generators from Polarizing Random Walks》，並意識到這篇論文中的技術正是他和 Raz 需要完成的。Tal 說：「這正是我們缺失的一塊拼圖。」

Pseudorandom Generators from Polarizing Random Walks：https://eccc.weizmann.ac.il/report/2018/015/

BQP 和 PH 分離的消息迅速傳了開來。Raz 和 Tal 發表證明的第二天，喬治亞理工大學的計算機科學家，Lance Fortnow 寫道：「量子複雜度的世界搖擺不定。」

這項工作提供了一個鐵證，那就是相比於傳統計算機（至少相對於 oracle 而言），量子計算機存在於一個不同的計算領域。甚至在 P 等價於 NP 的世界裡（其中「旅行推銷員問題」就像在電子表格上找到最合適的線一樣簡單），Raz 和 Tal 的證明仍然表明存在著只有量子計算機才能解決的問題。

Fortnow 說：「即使 P 等價於 NP，甚至做出了強有力的假設，仍然不足以掌握量子計算。」

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

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