總算找到一個只能用量子計算機解決的問題了

100 人贊了文章

早期的量子計算機研究人員針對量子計算機設計了一個問題，這個問題只有強大的量子計算機才能得出答案。25年後的今天，這個問題被量子計算機解決了。就在今年5月底，計算機科學家Ran Raz和Avishay Tal在網上發表了一篇文章，證明了量子計算機的計算能力超過了目前所有的傳統計算機。

Ran Raz是一位普林斯頓大學和維茨曼科學學院的教授，Avishay Tal是斯坦福大學的一名博士後，他們一起定義了一種特殊的計算問題。由此他們證明了在特定情況下，量子計算機可以有效的解出這個問題的答案，而傳統計算機將在解題過程中陷入無限死循環。計算機學家從1993年起就開始尋找這樣的問題，之後他們將這類問題稱為「BQP」，用來表示只能由量子計算機才能解出答案。

從那時起，計算機學家就開始比較BQP問題和PH問題，後者指的是傳統計算機能解出的問題。科學家一直想要證明BQP問題不在PH問題的範圍內，現在Ran Raz和Avishay Tal證明了這個命題。但是這樣的結果並不表明量子計算機在實際應用方面已經超過了傳統計算機。理論上，量子計算機能夠解決所有傳統計算機的問題。科學家還在研究如何建造一台實用的量子計算機。現在Ran Raz和Avishay Tal理論上驗證了量子計算機和傳統計算機是兩個不同的類別。即使目前傳統計算機已經能解決幾乎所有的實際問題，但是量子計算機的能力遠比傳統計算機要強大。

量子計算機類別

理論計算機科學的一個基本任務是將問題按複雜化分類，複雜類別中的問題都可以在給定的一些前提下，例如時間或內存，然後計算出最後的答案。科學家發明了一個有效的演算法，例如為了驗證一個數是否是質數，但是目前還沒有能找到特別大的數中的質數因子的演算法，因此科學家相信這兩個問題屬於不同複雜程度的問題類別。目前最著名的兩大複雜問題類別是P和NP。P代表目前傳統計算機能夠快速計算出的問題答案，例如一個數是不是質數，這個問題就屬於P類別的問題；NP代表目前傳統計算機無法快速得出答案，但如果給出某個答案後能夠快速判斷正確與否，例如一個數中的質數因子是什麼，這個問題屬於NP類別。科學家認為這兩類問題是完全不同的，但是如何證明兩者的不同也是最難的。

1993年科學家Ethan Bernstein和Umesh Vazirani定義了一種新的問題類別BQP，全稱是有界誤差量子多項式時間。他們將量子計算機能解出的所有具有肯定答案的問題或是沒有答案的問題，都歸為這個類別。同時，他們還認為所有傳統計算機能解出的問題，量子計算機也能解出。也就是說，BQP中包括了所有P類別的問題。

用一個例子來解釋複雜類別問題：旅行商（TSP）基本路線規劃問題。當一個旅行商詢問，是否有一條比給定的路徑更短的捷徑可以穿過好幾個城市？這是一個NP類別問題，如果是更複雜的問題，那就是詢問穿過這些城市的最短路徑是不是就是給出的那條路徑？這個問題屬於PH類別問題，PH代表的含義是多項式譜。

但是他們無法確定BQP中的問題，是不是在PH類別問題中無法找到。PH類別問題是NP類別問題的總和，這說明只要問出的問題是屬於NP類別，如果在NP問題上加上一些限定詞，例如「一定存在」或「所有」，那麼就變成PH問題。傳統計算機無法解決所有PH類別的問題，不過將P類別等同於NP類別問題，那麼這時PH類別問題就都能被如今的傳統計算機解出。換句話說，BQP和PH的區別在於量子計算機是不是比如今已經很強大的傳統計算機還要強大？

德克薩斯大學奧斯汀分校的計算機科學家Scott Aaronson表示，PH類別是最基礎的經典複雜問題類別之一，現在的問題是量子計算機如何能在傳統複雜理論中佔有一席之地？最好的方法發就是能找到一個只能量子計算機才能解出答案的問題，而傳統計算機無法解出。而由於目前的基礎研究和技術的局限性，想要找到這樣的問題非常困難。如果想要找到一個屬於BQP類別的問題，但不屬於PH類別，就需要確定這樣的前提：傳統計算機無法有效驗證所提供的答案，更不能解出問題的答案，光是這點就能排除目前在計算機科學領域的很多問題。

假設現在有2個隨機數生成器，每個都會生成一些數字。那麼每個生成器生成的數字序列是否相互獨立？還是它們之間存在可能像是傅立葉變換式的聯繫？Scott Aaronson在2009年引入了「相關係數」的問題並且證明了這是一個BQP問題，那麼接下來的問題更難，需要證明相關係數不是PH類別問題。

而Ran Raz和Avishay Tal所著的論文，從某種意義上而言，是在BQP和PH類別之間放了一個「黑匣子」。這也是目前計算機科學研究中常用的一種方法，當目前的研究水平無法驗證時就會採用「黑箱」操作。實際最有效的區分BQP和PH類別問題的方法就是測量解題所需的計算時間，但是目前計算機科學家還沒有有效的方法來測量實際的計算時間。因此科學家採取了間接手段才測量計算時間，這種手段就是記錄計算機向「黑匣子」的請求次數。「黑匣子」就像神諭一樣，不知道怎麼會出現，但絕對可靠。

如果想要知道2串數列是否有關連，可以向「黑匣子」發出詢問請求：每個隨機數生成器生成的第6個數字是什麼？然後比較計算機根據提示所給出的計算結果，計算機的提示越多，速度越慢。Avishay Tal表示，通過這種模型可以告訴科學家更多有用的信息。他們的研究報告證明了量子計算機在計算相關係數問題時，比傳統計算機需要的提示更少，實際上只需要一個提示。即使可以輸入無限制次數的提示，傳統計算機也沒有更好的演算法解出答案。因此得出結論：相關係數問題屬於BQP而不是PH類別問題。

早在4年前，他們就快要得出這樣的結論，只是一直沒有完成證明過程。一個月前，Avishay Tal看到了一篇關於偽隨機數生成器的論文後意識到可以用來證明他倆的結論。這項研究嚴謹的證明了量子計算機和傳統計算機完全屬於兩個不同的範疇。即使是當P等於NP時，拿最基礎的旅行商路線規劃問題來說，他倆的研究成果表明這個問題只能由量子計算機才能解決。

Ref:

Finally, a Problem Only Quantum Computers Will Ever Be Able to Solve

WTT資訊-最新科技資訊，實時網安信息?

www.wttech.org

歡迎關注我們：

@W-Pwn