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

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

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

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

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

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

它們可能具有隨機行為，如果輸入在某個隨機范圍內(nèi)（例如，12 到 67）輸出「是」，否則輸出「否」?；蛘咚鼈兛赡苁侵芷谛缘?，因此 1 到 10 之間的輸入返回「是」，11 到 20 產(chǎn)生「否」，21 到 30 再次產(chǎn)生「是」，依此類推。

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

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

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

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

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

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

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

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

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

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

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

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

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