關於量子計算，我們仍不知道它到底能做什麼
當前，量子計算領域蓬勃發展，卻仍面臨「它到底有什麼用」的本質問題。在本文作者來看，在這樣的環境下，正是大力推動量子算法的時刻，應降低對量子算法原有要求，尋找可驗證且實用的算法，呼籲理論家積極探索，推動量子計算突破瓶頸。值得一提的是，本文得到了理論物理學家John Preskill的推薦：「如果你對量子計算感興趣，我強烈推薦加州理工學院學生robbieking1000的這篇文章，呼籲採取‘更務實（scrappier）的方法’來尋找新的應用。」
本文來自微信公眾號：返樸 （ID：fanpu2019），作者：robbieking1000，翻譯：一二三，題圖來自：AI生成
量子計算正處在一個奇特的階段。技術層面上，經過數十億美元投資和數十年的研究，實用的量子計算機正逐步接近實現。但令人尷尬的是，如今人們對量子計算最常提出的問題，仍然和20年前一樣：量子計算機到底能做什麼？誠實的回答暴露了房間里的大象：我們至今也沒有完全的答案。對於像我這樣的理論家來說，這既是一種挑戰，也是一種行動的召喚。
技術動能
假設幾十年後我們仍未擁有實用的量子計算機，原因會是什麼？不太可能是因為遇到了無法踰越的工程障礙。量子糾錯的理論基礎是堅實的，目前已有多個平台接近或低於糾錯閾值（例如哈佛、耶魯、Google）。實驗家們相信，今天的技術有望將邏輯比特擴展到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]
過於強調傳統的難解性定義，可能反而妨礙新算法的發現，因為真正新穎的量子算法，很可能會引入全新的經典複雜性假設，與既有的假設有根本性不同。而這種提出新假設並攻破它的反復過程，本身就是幫我們尋找量子優勢的高效路徑。
此外，直接把目標瞄準為用量子算法「解決現有的實際問題」也可能是徒勞的。能夠實現量子優勢的基礎性計算任務非常特殊，數量也非常少，但它們必然最終會成為量子應用的基石。我們應該尋找更多這樣的基礎任務，再考慮它們與具體應用匹配。
當然，區分哪些量子算法未來可能具有實際計算意義是很重要的。在現實世界中，計算必須是可驗證或者至少可重覆的，否則它沒有實際意義。例如，一個用來計算物理中可觀測量的量子模擬算法，如果在兩台量子計算機上得到相同的結果，那麼我們就有信心這個結果是正確且有物理意義的。一些問題，如因式分解，自然容易經典驗證，但我們可以把標準定得更低：一個有效的量子算法的輸出至少應該能夠被另一個量子計算機重覆。
最後，還有一個至關重要的隱性第四要求，但常被忽視：如果明天你手上有一台量子計算機，你能立刻跑你的算法嗎？這意味著，你不僅要有量子算法，還需要定義好一組輸入分佈。經典難解性應該基於輸入分佈的平均情況，而不是最壞情況。
在本小節結束之際，我要特別提醒大家：很多以可觀測量的期望值為輸出的量子算法提案，最終都因失敗而告終。這類算法不具有經典難解性的常見原因是，期望值在輸入分佈上高度集中（即大多數輸入給出的結果都很接近），那麼對於一個簡單的經典算法，每次輸入後只需輸出常見值，就能複現量子算法的結果。因此，我們應尋找那些對輸入變化敏感、具有期望值輸出顯著波動的量子算法。
我們可以把以上優先級總結為以下挑戰：
挑戰
請找到一個量子算法及其輸入分佈，滿足以下特性：
可證明的正確性：量子算法本身是正確的；
經典難解性：在輸入分佈的平均情況下，量子算法比最優的經典算法實現超二次加速；
潛在的應用價值：輸出結果是可驗證的，或者至少是可重覆的。
示例與非示例
表1我們可以根據輸出類型將量子算法分類。搜索問題：它輸出滿足某種約束的比特串（如分解質因數、數據中隱藏特徵、優化問題解等）。計算一個數值：輸出某個物理量的近似值（如期望值）。量子性證明：通過隱藏密鑰設置的驗證問題，確認設備的量子性。采樣任務：從某個分佈中抽樣。
哈密頓量模擬（Hamiltonian simulation）或許是量子計算最廣為人知的應用。物理學與化學中有許多自然界輕鬆計算但經典計算機無法企及的問題，量子計算可以直接模擬大自然，這讓我們有充分的理由相信量子算法可以解決經典計算難解的問題。
已有一些例子顯示，量子計算可以幫助解決未解的科學問題，比如Hubbard模型的相圖或FeMoCo分子的基態能量。這些問題無疑具有科學價值。但它們是孤例，我們更希望有證據可以表明量子計算的可解問題是無窮無盡的。我們能否從強相關物理中獲得靈感，寫出一系列具體的哈密頓量模擬系統，其中存在經典難解的可觀測量？這將為量子模擬持續且廣泛的應用收集證據，也將幫助我們理解量子優勢在哪裡以及如何產生。
計算機科學界也做了大量關於「預言機分離」（oracle separation）的工作，如銲接樹（welded trees）、傅換關聯（forrelation），這增強了我們對量子計算機能力的信心。現在需要將這些oracle實例化為「明天就可以在真實設備上跑」的算法，這是初步測試算法所必需的。
除了哈密頓量模擬，還有其他幾個重要的量子算法門類：包括求解線性方程組與微分方程的量子算法；用於機器學習的變份量子算法；用於優化問題的量子算法。
這些框架有時帶有BQP完備性（即能模擬任何量子計算），但通常未指定輸入分佈。我們需要探索新的輸入集合，尋找真正的超二次加速。BQP完備性表明，人們已經將量子計算的概念轉換成了不同的語言，這使得人們可以將現有的量子算法（如Shor算法）嵌入到自己的框架中。但為了發現新的量子算法，你必須找到一組不來自Shor算法的BQP計算的綜合體系。
關於表1中提到的采樣任務，其本身並沒有實際意義，因為它們甚至不是量子可重覆的。人們會想，采樣任務能否以某種方式變得有用。畢竟，經典蒙地卡羅算法已經得到了廣泛應用（譯者註：該算法是一類基於隨機采樣的數值方法，廣泛應用於強關聯量子多體系統的模擬，例如凝聚態物理、核物理、冷原子物理等領域中的多體量子系統）。而采樣的應用通常使用樣本來提取有意義的信息或底層分佈的特定特徵，例如蒙特卡羅采樣可以用於計算貝葉斯推斷和統計物理中的積分。相比之下，從隨機量子電路獲得的樣本缺乏任何可辨別的特徵。但如果能從采樣中提取出難以經典計算的有意義信號，這些任務也可以轉變為數值計算類任務。
表1也指出量子性證明類應用沒有實用性，這並不完全正確。一個有潛在應用的例子是可認證隨機數生成，但這類應用通常屬於密碼學用途，而非計算用途。具體來說，量子性證明不能直接用來解決問題或者回答我們還不知道答案的問題。
最後，量子技術在傳感、通信、帶有量子記憶的學習、數據流處理等方面也有令人激動的應用前景。這些方向非常有趣，我希望在人類理解量子力學的第二個世紀能夠創造出各種各樣的能力。而眼下技術動力仍然集中在構建量子計算機以實現計算優勢上，因此這方面的突破將產生最大的即時影響。
不必太害怕
在每年舉辦的QIP（量子信息處理）會議上，數百篇論文中，只有極少數研究嘗試提出新的量子算法。鑒於其重要性，為什麼這個數量還是如此之低？一個常見的解釋是：量子算法研究太難了。不過，最近幾年量子算法領域實際上已經取得了不少實質進展。從2000年到2020年，具有實用潛力的算法寥寥無幾，而表格中列出的許多成果都是近5年內的突破。
在盲目樂觀與消極悲觀之間，採用一種「使命驅動」的探索心態，將能推動整個領域前進。我們應該允許自己採用更加探索性、務實的策略：在未被充分研究的問題上，或小數點後第三位的微妙信號中尋找量子優勢。
實現意義重大的進步，其實門檻比看起來要低得多，即使是微小的前進，也是寶貴的。不要太害怕！
註釋
[1]由於量子誤差校正的開銷，單純的二次加速（如Grover搜索）難以支撐實用量子優勢，因此需要超二次加速。
