1994 年，一位數學家想出了怎樣讓量子計算機完成普通經典計算機無法做到的事情。這項工作表明，原則上，一臺基于量子力學規則的機器可以有效地將大量數字分解為其主要因素——對于經典計算機而言，這是一項非常困難的任務，它構成了當今大部分互聯網安全的基礎。

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

但進展停滯不前。「這有點令人失望?！箍▋然仿〈髮W的 Ryan O’Donnell 說，「人們會說，『這太棒了，我相信我們會得到各種其他驚人的算法』，事實是沒有。」 科學家們僅在稱為 NP 的標準集中發現了單一、狹窄類別問題的顯著加速，這意味著他們有有效的可驗證解決方案——比如因式分解。

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

「有一種興奮感?！孤槭±砉W院的計算機科學家 Vinod Vaikuntanathan 說，「許多人都在思考外面還有什么?！?/p>

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

它們可能具有隨機行為，假如輸入在某個隨機范圍內（比如，12 到 67）輸出「是」，否則輸出「否」。亦或它們可能是周期性的，故此 1 到 10 之間的輸入返回「是」，11 到 20 產生「否」，21 到 30 再次產生「是」，依此類推。

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

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

Shor 繼續發現他可以調整 Simon 的算法來計算預言機的周期，假如它有的話。然后他意識到他可以再次調整算法，求解一個行為類似于周期性預言的方程：描述因式分解的方程，它是周期性的。

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

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

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

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

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

Yamakawa 和 Zhandry 調整了設置。他們修改了這些起跑的力量，使它們更容易預測。他們還使風由一個隨機的神諭確定，故此在某些情況下它甚至更加隨機，但在其他情況下則完全休眠。

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

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

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

該結果提供了第一個在非結構化 NP 問題上具有顯著量子優勢的例子。量子世界會不會有很多其他問題從近乎無法解決變為可以解決？現在有更多的理由這么認為?！高@在一定程度上顛覆了我們對量子計算機擅長解決哪些問題的看法?！筄’Donnell 說。