量子計算機可以做令人驚奇的事情：可惜它們還不存在。但這並沒有阻止物理學家為這些裝置設計新的演算法，這些裝置比普通計算機的計算速度快得多——實際上是指數級的快，在非常字面的意義上。一旦量子計算機投入使用，這些演算法可能成為需要大量數字運算的應用的關鍵部分，從工程到影片遊戲。
最新的量子演算法正在物理學家中引起轟動。它處理線性方程：諸如 3x + 2y = 7 之類的表示式，通常將未知數寫在一側，常數寫在另一側。許多高中生學習透過一次消除一個未知數來求解此類方程組的機械方法。當系統包含數十億個變數和數十億個方程時，速度變得至關重要，這在現代應用中（例如天氣和其他物理現象的模擬）中並不少見。高效的演算法可以透過計算機求解大型“N 乘 N”系統（具有 N 個線性方程和 N 個未知數的系統）。儘管如此，計算時間至少與 N 成正比增長：如果 N 增大 1,000 倍，則解決問題的時間將至少延長 1,000 倍，通常更長。
英格蘭布里斯托大學的 Aram W. Harrow 以及麻省理工學院的 Avinatan Hassidim 和 Seth Lloyd 現在提出的量子演算法採用了一個巧妙的捷徑。它可以返回關於解的最相關資訊，而無需完全計算解本身，從而用產生的資料量換取速度。（例如，在天氣預報的情況下，它可以返回一個城鎮的平均溫度，而不是按街區預測的溫度。）
關於支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保關於塑造我們今天世界的發現和想法的具有影響力的故事的未來。
像所有量子演算法一樣，他們的方法（在 10 月 9 日的《物理評論快報》中描述）將關於系統的所有相關資訊編碼到量子位元中。與普通的或“經典的”位元相反，量子位元可以同時以 0 和 1 存在——或者，正如物理學家所說，處於狀態的疊加態。該演算法將這些位元轉換為一種狀態，該狀態基本上編碼了系統所有可能解的疊加態，這意味著對於方程右側常數的所有可能值。從這個“通用解”中，人們可以提取關於特定解的相關資訊，而無需完全計算它們。
速度的提升是巨大的：產生通用解所需的時間僅隨 N 的位數增長。因此，如果 N 增大 1,000 倍，演算法花費的時間僅延長三倍（因為 N 增加了三位數），而不是延長 1,000 倍。即使寫下所有變數的結果，在經典情況下也需要 1,000 倍以上的步驟。“解決問題所花費的時間比讀取解決方案的時間呈指數級減少，”Lloyd 半開玩笑地說。
新加坡國立大學的 Artur Ekert 說：“與經典類似物相比，每個顯示出明顯加速的量子演算法仍然是一件大事。” 只有少數量子演算法可以誇耀這一成就——例如 1990 年代發明的用於將大數分解為素數或用於搜尋資料庫的演算法。
到目前為止，只存在實驗性量子計算機，其中僅包含少量位元。但德國烏爾姆大學的 Martin Plenio 說，在不久的將來，對新演算法的小型演示應該是可行的。“但是，要建造一臺足夠大的量子計算機來解決經典裝置無法解決的問題，還需要很多年，”他補充道。
Lloyd 說，如果某些應用利用光子的內在量子特性，則可能更快實現。例如，他提出，該演算法可以體現在“超成像裝置”中，該裝置可以消除望遠鏡中的光學畸變。望遠鏡測量的每個光子都將扮演方程常數項的角色，而畸變將對應於線性方程組。找到解意味著逆轉畸變，從而提高影像質量。