當前，量子計算領域蓬勃發展，卻仍面臨“它到底有什么用”的本質問題。在本文作者來看，在這樣的環境下，正是大力推動量子算法的時刻，應降低對量子算法原有要求，尋找可驗證且實用的算法，呼吁理論家積極探索，推動量子計算突破瓶頸。值得一提的是，本文得到了理論物理學家John Preskill的推薦：“如果你對量子計算感興趣，我強烈推薦加州理工學院學生robbieking1000的這篇文章，呼吁采取‘更務實（scrappier）的方法’來尋找新的應用。”

撰文| robbieking1000

翻譯| 一二三

量子計算正處在一個奇特的階段。技術層面上，經過數十億美元投資和數十年的研究，實用的量子計算機正逐步接近實現。但令人尷尬的是，如今人們對量子計算最常提出的問題，仍然和20年前一樣： 量子計算機到底能做什么？ 誠實的回答暴露了房間里的大象：我們至今也沒有完全的答案。對于像我這樣的理論家來說，這既是一種挑戰，也是一種行動的召喚。

技術動能

假設幾十年后我們仍未擁有實用的量子計算機，原因會是什么？不太可能是因為遇到了無法逾越的工程障礙。量子糾錯的理論基礎是堅實的，目前已有多個平臺接近或低于糾錯閾值（例如哈佛、耶魯、谷歌）。實驗家們相信，今天的技術有望將邏輯比特擴展到100個并實現10^6次門操作——進入所謂的“兆量子位時代”（megaquop era）（譯者注：該說法由John Preskill提出，即量子處理器能夠執行百萬級或十億級量子操作的時代。這里的'mega'并非精確指代一百萬，而是表示百萬量級的近似范圍）。如果我們在接下來的幾十年中投入1000億美元，很可能會建成一臺大型量子計算機。

但更令人擔憂的可能是：量子計算缺乏足夠的應用動力，無法為如此巨大的研發和基礎設施投資提供正當性。這可以與核聚變作個比較，和量子計算一樣，核聚變面臨著巨大的科學和工程挑戰。但如果核聚變實驗室成功建成反應堆，其應用價值將是顯而易見的。反觀量子計算，它更像是一把尋找釘子的鐵錘。

盡管如此，量子計算領域的產業投資目前正在加速增長。為了維持這種動能，必須在投資增長和硬件進步的同時，推進算法能力的發展。 發現量子算法的時機，就是現在。

賦能理論家

理論研究具有前瞻性和預測性。比如Geoffrey Hinton的工作為今天的人工智能革命奠定了基礎。而幾十年后，隨著硬件資源的豐富，AI已成為一門更偏向實證性的學科。我期待量子硬件也能早日步入繁榮，但現在還未到時候。

今天的量子計算，仍是理論家擁有巨大影響力的領域。Peter Shor幾頁數學推導，激勵了數以千計的研究者、工程師和投資人投身此領域。也許讀這篇文章的人中，有人能再寫幾頁新的論文，由此奠定行業未來變革的基礎。很少有地方像這里一樣，數學能夠發揮如此巨大的實際影響。整個實驗家、工程師和企業界群體，都在期待理論家的新思路。

挑戰

傳統上，人們認為理想的量子算法應具備三大特性：

1.可證明的正確性：確保可靠執行量子電路即可得到正確結果；

2.經典難解性：量子算法的輸出，經典算法難以在合理時間內復現；

3.實用性：有潛力解決現實世界中的有意義問題。

Shor算法幾乎滿足了這三條標準。但在實際探索中，絕對堅持三條標準反而可能適得其反。

可證明的正確性很重要，因為目前我們尚不能在大規模硬件上直接驗證量子算法。但對于“經典難解性”，我們應要求到什么程度呢？畢竟，要嚴格證明一個問題經典難解，需要解決P vs NP這樣的重大開放問題，這是不現實的。我們可以采用“軟證明”，比如將問題規約（reduction）到已有的經典復雜性假設。

我認為我們應該將“可證明經典難解”這一理想替換為更加務實的標準：只要量子算法在平均情況下，相比已知最優的經典算法，取得超二次加速（super-quadratic speedup）即可。[注1]

過于強調傳統的難解性定義，可能反而妨礙新算法的發現，因為真正新穎的量子算法，很可能會引入全新的經典復雜性假設，與既有的假設有根本性不同。而這種提出新假設并攻破它的反復過程，本身就是幫我們尋找量子優勢的高效路徑。

此外，直接把目標瞄準為用量子算法“解決現有的實際問題”也可能是徒勞的。能夠實現量子優勢的基礎性計算任務非常特殊，數量也非常少，但它們必然最終會成為量子應用的基石。我們應該尋找更多這樣的基礎任務，再考慮它們與具體應用匹配。

當然，區分哪些量子算法未來可能具有實際計算意義是很重要的。在現實世界中，計算必須是可驗證或者至少可重復的，否則它沒有實際意義。例如，一個用來計算物理中可觀測量的量子模擬算法，如果在兩臺量子計算機上得到相同的結果，那么我們就有信心這個結果是正確且有物理意義的。一些問題，如因式分解，自然容易經典驗證，但我們可以把標準定得更低：一個有效的量子算法的輸出至少應該能夠被另一個量子計算機重復。

最后，還有一個至關重要的隱性第四要求，但常被忽視：如果明天你手上有一臺量子計算機，你能立刻跑你的算法嗎？這意味著，你不僅要有量子算法，還需要定義好一組輸入分布。經典難解性應該基于輸入分布的平均情況，而不是最壞情況。

在本小節結束之際，我要特別提醒大家：很多以可觀測量的期望值為輸出的量子算法提案，最終都因失敗而告終。這類算法不具有經典難解性的常見原因是，期望值在輸入分布上高度集中（即大多數輸入給出的結果都很接近），那么對于一個簡單的經典算法，每次輸入后只需輸出常見值，就能復現量子算法的結果。因此，我們應尋找那些對輸入變化敏感、具有期望值輸出顯著波動的量子算法。

我們可以把以上優先級總結為以下挑戰：

挑戰

請找到一個量子算法及其輸入分布，滿足以下特性：

• 可證明的正確性 ：量子算法本身是正確的；

• 經典難解性 ：在輸入分布的平均情況下，量子算法比最優的經典算法實現 超二次加速 ；

• 潛在的應用價值 ：輸出結果是可驗證的，或者至少是可重復的。

示例與非示例

分類

可經典驗證

可量子重復

潛在有用性

可證明經典難解

示例

搜索問題

Shor’99，Regev的歸約，CLZ22，YZ24，Jor+24，Has20，SOKB24

計算一個數值

凝聚態物理？量子化學？

量子性證明

是（有密鑰）

是（相對于密鑰）

是（基于加密假設）

BCMVV21

采樣任務

幾乎是（基于復雜性假設）

BJS10，AA11，Google’20

表1 我們可以根據輸出類型將量子算法分類。 搜索問題 ：它輸出滿足某種約束的比特串（如分解質因數、數據中隱藏特征、優化問題解等）。 計算 一個 數值 ：輸出某個物理量的近似值（如期望值）。 量子性證明 ：通過隱藏密鑰設置的驗證問題，確認設備的量子性。 采樣 任務 ：從某個分布中抽樣。

哈密頓量模擬 （Hamiltonian simulation） 或許是量子計算最廣為人知的應用。物理學與化學中有許多自然界輕松計算但經典計算機無法企及的問題，量子計算可以直接模擬大自然，這讓我們有充分的理由相信量子算法可以解決經典計算難解的問題。

已有一些例子顯示，量子計算可以幫助解決未解的科學問題，比如Hubbard模型的相圖或FeMoCo分子的基態能量。這些問題無疑具有科學價值。但它們是孤例，我們更希望有證據可以表明量子計算的可解問題是 無窮無盡 的。我們能否從強相關物理中獲得靈感，寫出一系列具體的哈密頓量模擬系統，其中存在經典難解的可觀測量？這將為量子模擬持續且廣泛的應用收集證據，也將幫助我們理解量子優勢在哪里以及如何產生。

計算機科學界也做了大量關于“預言機分離”（oracle separation）的工作，如焊接樹（welded trees）、傅換關聯（forrelation），這增強了我們對量子計算機能力的信心。現在需要將這些oracle實例化為“明天就可以在真實設備上跑”的算法，這是初步測試算法所必需的。

除了哈密頓量模擬，還有其他幾個重要的量子算法門類：包括求解線性方程組與微分方程的量子算法；用于機器學習的變分量子算法；用于優化問題的量子算法。

這些框架有時帶有BQP完備性（即能模擬任何量子計算），但通常未指定輸入分布。我們需要探索新的輸入集合，尋找真正的超二次加速。BQP 完備性表明，人們已經將量子計算的概念轉換成了不同的語言，這使得人們可以將現有的量子算法（如 Shor 算法）嵌入到自己的框架中。但為了發現新的量子算法，你必須找到一組不來自 Shor 算法的 BQP 計算的綜合體系。

關于表1中提到的采樣任務，其本身并沒有實際意義，因為它們甚至不是量子可重復的。人們會想，采樣任務能否以某種方式變得有用。畢竟，經典蒙特卡洛算法已經得到了廣泛應用（譯者注：該算法是一類基于隨機采樣的數值方法，廣泛應用于強關聯量子多體系統的模擬，例如凝聚態物理、核物理、冷原子物理等領域中的多體量子系統）。而采樣的應用通常使用樣本來提取有意義的信息或底層分布的特定特征，例如蒙特卡羅采樣可以用于計算貝葉斯推斷和統計物理中的積分。相比之下，從隨機量子電路獲得的樣本缺乏任何可辨別的特征。但如果能從采樣中提取出 難以經典計算的有意義信號 ，這些任務也可以轉變為數值計算類任務。

表1也指出量子性證明類應用沒有實用性，這并不完全正確。一個有潛在應用的例子是可認證隨機數生成，但這類應用通常屬于 密碼學用途 ，而非 計算用途 。具體來說，量子性證明不能直接用來解決問題或者回答我們還不知道答案的問題。

最后，量子技術在 傳感 、 通信 、帶有量子記憶的學習 、數據 流處 理 等方面也有令人激動的應用前景。這些方向非常有趣，我希望在人類理解量子力學的第二個世紀能夠創造出各種各樣的能力。而眼下技術動力仍然集中在構建量子計算機以實現 計算優勢 上，因此這方面的突破將產生最大的即時影響。

不必太害怕

在每年舉辦的QIP（量子信息處理）會議上，數百篇論文中，只有極少數研究嘗試提出新的量子算法。鑒于其重要性，為什么這個數量還是如此之低？一個常見的解釋是： 量子算法研究太難了 。不過，最近幾年量子算法領域實際上已經取得了不少實質進展。從2000年到2020年，具有實用潛力的算法寥寥無幾，而表格中列出的許多成果都是近5年內的突破。

在盲目樂觀與消極悲觀之間，采用一種“使命驅動”的探索心態，將能推動整個領域前進。我們應該允許自己采用更加探索性、務實的策略： 在未被充分研究的問題上 ，或小數點后第三位的微妙信號中 尋找量子優勢 。

實現意義重大的進步，其實門檻比看起來要低得多， 即使是微小的前進，也是寶貴的。不要太害怕！

注釋

[1] 由于量子誤差校正的開銷，單純的二次加速（如Grover搜索）難以支撐實用量子優勢，因此需要超二次加速。

本文基于知識共享許可協議（CC BY-NC）譯自robbieking1000, Quantum Algorithms: A Call To Action.

原文地址：https://quantumfrontiers.com/2025/04/20/quantum-algorithms-a-call-to-action/

本文轉載自《返樸》微信公眾號

《物理》50年精選文章