一個只有量子計算機才能解決的問題

55 人贊了文章

作者：Kevin Hong

翻譯：Nothing

審校：山寺小沙彌

科學家為了尋找一類只能用量子計算機解決而不能用經典計算機解決的問題花了很多年。現在，他們找到了這樣的問題。

在量子計算機研究的早期，計算機科學家提出一個問題，它的答案將揭示這種來自未來的機器的威力。25年後，這個問題已經幾乎被解決了。五月初在線發表的一篇論文中，科學家Ran Raz 和 Avishav Tal 拿出了量子計算機具有經典計算機不具備的計算能力的證據。

Raz是普林斯頓大學和威茨曼科學研究學院的教授，Tal 是斯坦福大學的博士後，他們設計了一類特殊的計算問題。他們證明，量子計算機可以有效地解決這類問題但傳統計算機卻無能為力。1993年，計算機科學家第一次定義了一系列被稱為「BQP」的問題，BQP包含所有量子計算機可以解決的問題，從那時起計算機科學家就在尋找這個問題。

從那以後，計算機科學家希望將一類被稱為「PH」的問題與BQP進行對比，PH是理論上可以用經典計算機解決的問題，即使可能需要大大推進我們現有的技術才能做到。要做這種對比就要找到一種屬於BQP但是不屬於PH的問題。現在，Raz和Tal已經找到了它。

這個結果並不能在任何應用的意義上把量子計算機的地位提升的比經典計算機還高。舉例來說，理論計算機科學家已經知道量子計算機可以解決任何經典計算機可以解決的問題。並且工程師都競相組建有用的量子機器。但是Raz和Tal的文章提到量子和經典計算機是不同的類別——即使在經典計算機可以完成所有工作的領域，量子計算機仍然不可取代。

複雜度分類

理論計算機科學家的基本任務就是將不同的問題進行複雜度分類。一個複雜度分類包含所有可以用給定資源預算解決的問題，資源包含時間和儲存空間等。

計算機科學家已經找到一個有效的演算法，例如，檢驗一個數是不是素數。但是他們沒有找到將一個巨大的數分解成質因數的有效演算法。因此，計算機學家相信兩種問題分屬不同的複雜度分類。

兩個最著名的複雜度分類是「P」和「NP」，P代表可以被經典計算機快速解決的問題。（如「判斷一個數是不是質數屬於P」）NP代表不可能被經典計算機快速解決的問題，但是如果可以給出答案，經典計算機可以快速的驗證答案。（尋如「尋找一個數的所有質因數」）。計算機學家相信，P和NP不是同一種類型的問題，但是證明它們之間的不同是這個領域中最困難最重要的開放性問題。

1993年，計算機學家Ethan Bernstein 和 Umesh Vazirani 定義了一個新的叫做「BQP(bounded-error quantum polynomial time)」的複雜度分類。他們定義這個分類包含量子計算機可以有效解決的決策性問題，也就是答案是「是」或「否」的問題。在大約相同的時間，他們證明了量子計算機可以解決經典計算機可以解決的所有問題。也就是說，BQP包含P中的所有問題。

但他們不能確定BQP是否包含不存在於PH中的問題，PH是「polynomial hierarchy.」。PH是NP的推廣，它包含所有對NP中的所有問題所做的某些推廣，這些推廣包括增加「存在」和「對所有情況」等陳述。比較BQP和PH是為了確定量子計算機相比經典計算機是否更具優勢（即便是在經典計算機的計算能力比現在大大增強之後）。

「PH是最基礎的經典複雜度分類之一，」Scott Aaronson說，它是奧斯汀德克薩斯大學的計算機學家。「因此我們想知道的是，在經典複雜度理論中量子計算處於什麼位置。」

區分兩個複雜度分類的最好的辦法就是找到一個處於其中一個但不在另外一個中的問題。但是由於基礎理論和技術上的障礙，尋找這樣的問題是一個巨大挑戰。

如果你想找到一個屬於BQP但不屬於PH的問題，你必須找到「一個經典計算機無法解決，甚至無法驗證的問題」Aaronson說。「這排除了很多計算機領域我們思考過的問題。」

尋找不屬於PH的BQP

想像你有兩個隨機數生成器，每一個生成器產生一列數據。對於計算機來說問題是：這兩列數據是相互獨立的嗎，或者它們是否以隱藏的方式相互聯繫（其中一列數是另一列的傅里葉變換）？Aaronson在2009年提出這種「forrelation」問題並證明它屬於BQP。這留下了更加困難的第二步，也就是證明它不屬於PH。

在某種意義上講，這就是Raz和Tal所做的。他們實現了被稱為「預言（oracle）」（或「黑盒子（black box）」）的BQP和PH之間的分辨。

實際上最好的區分BQP和PH這種複雜度分類的方法是測量在每一類中解決一個問題需要的時間。但是計算機學家「對於真實的計算時間沒有成熟的理解，也沒有能力測量精確地時間。」Henry Yuen說。

因此，代替方案是，計算機學家測量那些可以幫助他們加深對計算時間理解的量：他們利用計算機運行「Oracl」得到答案的時間。Orale像一個提示者。你不知道它如何給出提示，但是你知道它們是可信的。

如果你的問題是指出兩個隨機數生成器是否有隱藏關聯，你可以問這樣的問題：「從每個生成器中產生的第六個數是什麼？」然後可以通過每種計算機解決問題需要的提示多少來判斷誰的計算能力強。需要提示多的計算機更慢一些。

「某種意義上說，我們對這種模型的理解要好得多。它和信息而非計算更加相關。」Tal說。

在Raz和Tal新的論文中，他們證明量子計算機相比經典計算機需要少得多的提示來解決forrelation問題。實際上，量子計算機僅需要一個提示，而PH無論有多少個提示都無法解決這類問題。「這意味著存在解決這個問題的非常高效的量子演算法，」Raz說。「但是如果你只是考慮經典演算法，即便是非常高端的經典演算法，也解決不了這個問題。」這證明了forrelation問題屬於BQP而不是PH。

Raz和Tal四年前差點就得到這個結果，但他們沒能完成最後一步證明。僅僅一個月之後，Tal聽到一篇關於偽隨機數生成器的文章的討論並意識到文章中的技術正是他們所需要的。「這正是缺失的一環」Tal說。

區分BQP和PH的新聞傳播的非常快。「量子複雜性世界被震動了。」Lance Fortnow寫到。

這個工作證明了量子計算機存在於和經典計算機不同的範疇內。儘管是P和NP相等的領域，Raz和Tal的證明說明了仍然存在只有量子計算機可以解決的問題。

原文地址：

https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/