科學(xué)家們過去一直在尋找只有量子計(jì)算機(jī)才能解決的問題。現(xiàn)在他們終于找到了。

早在量子計(jì)算研究剛剛興起時，科學(xué)家們就知道這種未來主義的機(jī)器蘊(yùn)含著某種無限的潛能。而在今年 5 月發(fā)表的一篇論文中，計(jì)算機(jī)科學(xué)家 Ran Raz(普林斯頓大學(xué)兼魏茨曼科學(xué)研究院教授) 和 Avishay Tal(斯坦福大學(xué)博士后研究員)為“量子計(jì)算在能力上將遠(yuǎn)超一切傳統(tǒng)計(jì)算”這一概念提供了科學(xué)證據(jù)。

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

雖然論文對于實(shí)際構(gòu)建一臺量子計(jì)算機(jī)的工作來說沒有任何實(shí)際意義，但它確實(shí)地證明了“成熟的量子計(jì)算將會在量級上完虐傳統(tǒng)計(jì)算”這一概念。

理論計(jì)算機(jī)研究中的一個基本項(xiàng)目就是將問題根據(jù)復(fù)雜程度進(jìn)行分類，也稱復(fù)雜度分級(Complexity Classes)，即根據(jù)解決問題所需資源(如時間和內(nèi)存)的多少進(jìn)行分類。

其中最著名的兩個分類是“P”和“NP”，P 是傳統(tǒng)計(jì)算可以快速解決的所有問題。 (“這個數(shù)字是否是質(zhì)數(shù)?”屬于 P)NP 是傳統(tǒng)計(jì)算機(jī)并不能迅速解決，但如果存在一個已知答案能夠快速驗(yàn)證的問題(如“這個數(shù)的質(zhì)因數(shù)有哪些?”屬于 NP)。計(jì)算機(jī)科學(xué)家認(rèn)為 P 和 NP 是不同的類別，但證明 P 與 NP 不同卻是該領(lǐng)域最難以及最重要的問題之一。

1993 年，計(jì)算機(jī)科學(xué)家 Ethan Bernstein 和 Umesh Vazirani 為復(fù)雜度分類創(chuàng)造了一個新的類別，“有限錯誤量子多項(xiàng)式時間”類(bounded-error quantum polynomial time)”，即上文中所提到過的 BQP 問題。該定義類中包含量子計(jì)算機(jī)可以高效解決的所有決策問題，即答案為是或否的問題。兩位科學(xué)家同時還證明了量子計(jì)算機(jī)可以解決傳統(tǒng)計(jì)算機(jī)可以解決的所有問題，也就是證明了 BQP 分類中包含了 P 分類(這里分類看為數(shù)學(xué)中集合的概念)。

但 Ethan 和 Umesh 無法確定 BQP 中是否也包含“多項(xiàng)式層次結(jié)構(gòu)(Polynomial Hierarchy)”類問題，也稱 PH 類問題。PH 是 NP 的拓展，包含所有由 NP 類延伸出的問題，如通過添加“對于所有...來說是否存在...”。 當(dāng)今的傳統(tǒng)計(jì)算機(jī)無法解決 PH 中的大多數(shù)問題，但如果 P 等于 NP，則可以將 PH 看作是傳統(tǒng)計(jì)算機(jī)可以解決的所有問題。換句話說，比較 BQP 和 PH 這兩種問題分類，便是為了確定量子計(jì)算機(jī)是否真的較傳統(tǒng)計(jì)算機(jī)具有優(yōu)勢。

關(guān)于不同復(fù)雜度類別的問題可以參考“旅行推銷員問題(TSP)”。“是否存在通過若干個城市的一些路徑比另一些路徑更短”是一個 NP 問題。而一個 PH 問題則是“是否通過這幾個城市的最短路徑就是某個特定距離”。

德克薩斯大學(xué)的計(jì)算機(jī)科學(xué)家 Scott Aaronson 說:“PH 是最基本的古典復(fù)雜度分類之一。而我們想知道，量子計(jì)算在古典復(fù)雜度分類的標(biāo)準(zhǔn)中處于什么樣的位置。”

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

Aaronson 說，如果你想找到一個僅屬于 BQP 而不屬于 PH 的問題，你必須找到一個從定義上傳統(tǒng)計(jì)算機(jī)不能有效證明答案的問題，這樣的問題“傳統(tǒng)計(jì)算機(jī)甚至不能有效地驗(yàn)證答案，更別說找到它了。這就排除了我們在計(jì)算機(jī)科學(xué)中所考慮的許多問題。”

假如你現(xiàn)在有兩個隨機(jī)數(shù)字序列生成器，而你需要解決這樣一個問題:這兩組序列是完全獨(dú)立的，還是以某種隱藏的形式相關(guān)聯(lián)的(比如一組是另一組序列的“傅里葉變換”)。Aaronson 在 2009 年首次提出了這種“關(guān)系(forrelation)”問題，并證明它屬于 BQP。但解決該問題的第二步將更為困難，因?yàn)槟阈枰C明該關(guān)系不屬于 PH 類的集合。

Raz 和 Tal 這篇論文的成就便是實(shí)現(xiàn)了一種名為“Oracle(也稱“黑匣子”)”的 BQP 與 PH 的區(qū)分方式。 區(qū)分 BQP 和 PH 的最佳方式是測量解決每個問題所需的計(jì)算時間。但多倫多大學(xué)的計(jì)算機(jī)科學(xué)家 Henry Yuen 認(rèn)為，目前我們對計(jì)算所需時間的認(rèn)識還不足以讓人們得出某一問題所需的計(jì)算時間。

圖 | 普林斯頓大學(xué)理論計(jì)算機(jī)科學(xué)家 Ran Raz

正如 Yuen 所說的那樣，計(jì)算機(jī)科學(xué)家一般會測量一些其他的量來衡量計(jì)算所需的時間，比如計(jì)算出計(jì)算機(jī)在解決問題的過程中詢問“oracle”的次數(shù)。oracle 就像是一個提示，你不知道它是怎樣產(chǎn)生的，但你知道它是可靠的。

回到解決兩組數(shù)列是否相關(guān)的問題上，你可以先詢問 oracle 類似“每個發(fā)生器的第六個數(shù)字是什么?”的問題，然后，根據(jù)每種計(jì)算機(jī)所需的提示數(shù)量來比較計(jì)算能力(需要更多提示的計(jì)算機(jī)計(jì)算速度較慢)。

Tal 說:“從某種意義上來說，我們更好地理解了這個模型。 模型更多涉及到的是信息而不是計(jì)算。”

圖 | 斯坦福大學(xué)理論計(jì)算機(jī)科學(xué)家 Avishay Tal

Raz 和 Tal 的這篇論文證明了量子計(jì)算機(jī)在解決 forrelation 問題時較傳統(tǒng)計(jì)算機(jī)所需的提示更少。 事實(shí)上，量子計(jì)算機(jī)只僅要一個提示就能解決問題，而即使有無限個提示，PH 中也沒有可以解決問題的算法。Raz 說: “這意味著有一個非常有效的量子算法能夠解決這類問題，即那些傳統(tǒng)算法無法解決的問題。這說明了 forrelation 問題在分類上屬于 BQP 而不是 PH。”

Raz 和 Tal 在四年前就已接近證明出這一結(jié)論，但他們無法完成證明中的重要一步。 然后就在論文發(fā)表的一個月前，Tal 看到一篇關(guān)于偽隨機(jī)數(shù)列產(chǎn)生器的論文，意識到這篇論文中的技術(shù)正是他和Raz的證明所需要的，于是才有了這篇論文的發(fā)表。

BQP 和 PH 得以區(qū)分的消息迅速傳遍了學(xué)界。在論文發(fā)表的第二天，喬治亞理工學(xué)院的計(jì)算機(jī)科學(xué)家 Lance Fortnow 便寫下 “量子復(fù)雜性分類層級真是搖擺不定。” 以示感慨。

該論文為量子計(jì)算的優(yōu)越性提供了一個保證，即存在只有量子計(jì)算機(jī)才能解決問題。“即使 P 等于 NP，甚至存在更強(qiáng)的假設(shè)，傳統(tǒng)計(jì)算也無法達(dá)到量子計(jì)算級別。” Fortnow 說。

總結(jié)

以上是生活随笔為你收集整理的关于量子计算机论文,终于，科学家们找到了只有量子计算机才能解决的问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。