1994 年，一位數(shù)學(xué)家想出了如何讓量子計(jì)算機(jī)完成普通經(jīng)典計(jì)算機(jī)無法做到的事情。這項(xiàng)工作表明，原則上，一臺(tái)基于量子力學(xué)規(guī)則的機(jī)器可以有效地將大量數(shù)字分解為其主要因素——對(duì)于經(jīng)典計(jì)算機(jī)而言，這是一項(xiàng)非常困難的任務(wù)，它構(gòu)成了當(dāng)今大部分互聯(lián)網(wǎng)安全的基礎(chǔ)。

隨之而來的是一股樂觀情緒。也許，研究人員認(rèn)為，我們將能夠發(fā)明可以解決大量不同問題的量子算法。

但進(jìn)展停滯不前。「這有點(diǎn)令人失望。」卡內(nèi)基梅隆大學(xué)的 Ryan O’Donnell 說，「人們會(huì)說，『這太棒了，我相信我們會(huì)得到各種其他驚人的算法』，事實(shí)是沒有。」 科學(xué)家們僅在稱為 NP 的標(biāo)準(zhǔn)集中發(fā)現(xiàn)了單一、狹窄類別問題的顯著加速，這意味著他們有有效的可驗(yàn)證解決方案——例如因式分解。

近三年來都是如此。然后在 4 月，研究人員發(fā)明了一種全新的問題，量子計(jì)算機(jī)應(yīng)該能夠比經(jīng)典計(jì)算機(jī)更快地解決該問題。它涉及僅基于其混亂的輸出來計(jì)算復(fù)雜數(shù)學(xué)過程的輸入。這個(gè)問題是單獨(dú)存在的，還是許多其他問題中的第一個(gè)問題尚待確定。

「有一種興奮感。」麻省理工學(xué)院的計(jì)算機(jī)科學(xué)家 Vinod Vaikuntanathan 說，「很多人都在思考外面還有什么。」

計(jì)算機(jī)科學(xué)家試圖通過研究代表它們的數(shù)學(xué)模型，來了解量子計(jì)算機(jī)在哪些方面做得更好。通常，他們想象一個(gè)量子或經(jīng)典計(jì)算機(jī)的模型與稱為預(yù)言機(jī)的理想計(jì)算機(jī)配對(duì)。預(yù)言機(jī)就像簡單的數(shù)學(xué)函數(shù)或計(jì)算機(jī)程序，接受輸入并輸出預(yù)定的輸出。

它們可能具有隨機(jī)行為，如果輸入在某個(gè)隨機(jī)范圍內(nèi)（例如，12 到 67）輸出「是」，否則輸出「否」。或者它們可能是周期性的，因此 1 到 10 之間的輸入返回「是」，11 到 20 產(chǎn)生「否」，21 到 30 再次產(chǎn)生「是」，依此類推。

假設(shè)您有這些周期性預(yù)言之一，但您不知道周期。你所能做的就是給它輸入數(shù)字，看看它輸出了什么。在這些限制條件下，計(jì)算機(jī)能以多快的速度找到周期？1993 年，當(dāng)時(shí)在蒙特利爾大學(xué)的 Daniel Simon 發(fā)現(xiàn)，量子算法可以比任何經(jīng)典算法更快地計(jì)算出密切相關(guān)問題的答案。

這一結(jié)果使 Simon 能夠確定量子計(jì)算機(jī)在哪些方面具有顯著優(yōu)勢的最初跡象之一。但是當(dāng)他將他的論文提交給一個(gè)主要會(huì)議時(shí)，它被拒絕了。然而，這篇論文確實(shí)引起了會(huì)議項(xiàng)目委員會(huì)的一名初級(jí)成員——Peter Shor 的興趣，他當(dāng)時(shí)在新澤西州的貝爾實(shí)驗(yàn)室工作。

Shor 繼續(xù)發(fā)現(xiàn)他可以調(diào)整 Simon 的算法來計(jì)算預(yù)言機(jī)的周期，如果它有的話。然后他意識(shí)到他可以再次調(diào)整算法，求解一個(gè)行為類似于周期性預(yù)言的方程：描述因式分解的方程，它是周期性的。

Shor 的結(jié)果是歷史性的。他發(fā)現(xiàn)的量子算法可以迅速將巨大的數(shù)字簡化為它們的組成素因數(shù)，這是任何已知的經(jīng)典算法都無法做到的。在隨后的幾年里，研究人員發(fā)現(xiàn)了其他有效的量子算法。其中一些，比如 Shor 的算法，甚至提供了指數(shù)優(yōu)勢，但沒有人能證明在任何非周期性的 NP 問題上具有顯著的量子優(yōu)勢。

由于缺乏進(jìn)展，德克薩斯大學(xué)奧斯汀分校的 Scott Aaronson 和拉脫維亞大學(xué)的 Andris Ambainis 兩位計(jì)算機(jī)科學(xué)家進(jìn)行了觀察。量子優(yōu)勢的證明似乎總是依賴于具有某種非隨機(jī)結(jié)構(gòu)的預(yù)言，例如周期性。2009 年，他們推測隨機(jī)或非結(jié)構(gòu)化的 NP 問題不會(huì)有顯著的加速；誰也找不到例外。

他們的猜想限制了量子計(jì)算機(jī)的能力。但它只說對(duì)于特定類型的非結(jié)構(gòu)化 NP 問題——那些回答是或否的問題——沒有顯著的加速。如果一個(gè)問題涉及找出更具體、定量的答案，也就是所謂的搜索問題，那么這個(gè)猜想就不適用了。

考慮到這一點(diǎn)，NTT 社會(huì)信息學(xué)實(shí)驗(yàn)室的研究人員 Takashi Yamakawa 以及 NTT Research 和普林斯頓大學(xué)的 Mark Zhandry 決定對(duì)一個(gè)由 Oded Regev 于 2005 年提出的特定搜索問題進(jìn)行試驗(yàn)。

想象一組都指向同一個(gè)方向的風(fēng)向標(biāo)。給他們每個(gè)人一個(gè)有節(jié)制的推，然后讓陣風(fēng)影響他們的方向。Regev 想根據(jù)他們的最終方向確定他們最初指向的位置。像這樣的問題后來被稱為「錯(cuò)誤學(xué)習(xí)」，因?yàn)橥屏惋L(fēng)就像是原始方向上的隨機(jī)誤差源。有證據(jù)表明，經(jīng)典算法和量子算法都很難解決。

Yamakawa 和 Zhandry 調(diào)整了設(shè)置。他們修改了這些起跑的力量，使它們更容易預(yù)測。他們還使風(fēng)由一個(gè)隨機(jī)的神諭確定，因此在某些情況下它甚至更加隨機(jī)，但在其他情況下則完全休眠。

通過這些修改，研究人員發(fā)現(xiàn)量子算法可以有效地找到初始方向。他們還證明，任何經(jīng)典算法都必須以指數(shù)因子變慢。與 Shor 一樣，他們隨后調(diào)整了算法來解決問題的現(xiàn)實(shí)版本，用實(shí)際的數(shù)學(xué)方程代替了預(yù)言。

計(jì)算機(jī)科學(xué)家仍在努力理解和解決這個(gè)問題。Vaikuntanathan 將其與進(jìn)行數(shù)據(jù)壓縮時(shí)出現(xiàn)的不同情況進(jìn)行了比較：當(dāng)信息被壓縮時(shí)，兩個(gè)位可能會(huì)意外地?cái)D到同一個(gè)地方，從而覆蓋它們。提前預(yù)測這些碰撞以便避免它們的問題有一些相似之處。「這是一類基本上看起來像這樣的問題。」他說，「也許這些問題可以在量子上解決。」

人們希望，即使在當(dāng)今剛剛起步的量子計(jì)算機(jī)版本上，像新問題這樣的非結(jié)構(gòu)化問題也可以解決，從而提供一種測試它們的方法。當(dāng)時(shí)的想法是，非結(jié)構(gòu)化問題可能需要更少的資源來編程，或者對(duì)噪聲不太敏感，因?yàn)樗鼈円呀?jīng)是隨機(jī)的。但到目前為止，對(duì)于現(xiàn)有的量子計(jì)算機(jī)來說，這個(gè)新問題似乎仍然太先進(jìn)了，無法解決。「這是一個(gè)奇怪的問題。我沒想過要定義它。」Aaronson 說，「但回想起來，它有一些非常好的功能。」

該結(jié)果提供了第一個(gè)在非結(jié)構(gòu)化 NP 問題上具有顯著量子優(yōu)勢的例子。量子世界會(huì)不會(huì)有許多其他問題從幾乎無法解決變?yōu)榭梢越鉀Q？現(xiàn)在有更多的理由這么認(rèn)為。「這在一定程度上顛覆了我們對(duì)量子計(jì)算機(jī)擅長解決哪些問題的看法。」O’Donnell 說。