關(guān)于量子計(jì)算，我們?nèi)圆恢浪降啄茏鍪裁矗?

當(dāng)前，量子計(jì)算領(lǐng)域蓬勃發(fā)展，卻仍面臨“它到底有什么用”的本質(zhì)問(wèn)題。在本文作者來(lái)看，在這樣的環(huán)境下，正是大力推動(dòng)量子算法的時(shí)刻，應(yīng)降低對(duì)量子算法原有要求，尋找可驗(yàn)證且實(shí)用的算法，呼吁理論家積極探索，推動(dòng)量子計(jì)算突破瓶頸。值得一提的是，本文得到了理論物理學(xué)家John Preskill的推薦：“如果你對(duì)量子計(jì)算感興趣，我強(qiáng)烈推薦加州理工學(xué)院學(xué)生robbieking1000的這篇文章，呼吁采取‘更務(wù)實(shí)（scrappier）的方法’來(lái)尋找新的應(yīng)用?！?/p>

撰文 | robbieking1000

翻譯 | 一二三

量子計(jì)算正處在一個(gè)奇特的階段。技術(shù)層面上，經(jīng)過(guò)數(shù)十億美元投資和數(shù)十年的研究，實(shí)用的量子計(jì)算機(jī)正逐步接近實(shí)現(xiàn)。但令人尷尬的是，如今人們對(duì)量子計(jì)算最常提出的問(wèn)題，仍然和20年前一樣：量子計(jì)算機(jī)到底能做什么？誠(chéng)實(shí)的回答暴露了房間里的大象：我們至今也沒(méi)有完全的答案。對(duì)于像我這樣的理論家來(lái)說(shuō)，這既是一種挑戰(zhàn)，也是一種行動(dòng)的召喚。

技術(shù)動(dòng)能

假設(shè)幾十年后我們?nèi)晕磽碛袑?shí)用的量子計(jì)算機(jī)，原因會(huì)是什么？不太可能是因?yàn)橛龅搅藷o(wú)法逾越的工程障礙。量子糾錯(cuò)的理論基礎(chǔ)是堅(jiān)實(shí)的，目前已有多個(gè)平臺(tái)接近或低于糾錯(cuò)閾值（例如哈佛、耶魯、谷歌）。實(shí)驗(yàn)家們相信，今天的技術(shù)有望將邏輯比特?cái)U(kuò)展到100個(gè)并實(shí)現(xiàn)10^6次門操作——進(jìn)入所謂的“兆量子位時(shí)代”（megaquop era）（譯者注：該說(shuō)法由John Preskill提出，即量子處理器能夠執(zhí)行百萬(wàn)級(jí)或十億級(jí)量子操作的時(shí)代。這里的'mega'并非精確指代一百萬(wàn)，而是表示百萬(wàn)量級(jí)的近似范圍）。如果我們?cè)诮酉聛?lái)的幾十年中投入1000億美元，很可能會(huì)建成一臺(tái)大型量子計(jì)算機(jī)。

但更令人擔(dān)憂的可能是：量子計(jì)算缺乏足夠的應(yīng)用動(dòng)力，無(wú)法為如此巨大的研發(fā)和基礎(chǔ)設(shè)施投資提供正當(dāng)性。這可以與核聚變作個(gè)比較，和量子計(jì)算一樣，核聚變面臨著巨大的科學(xué)和工程挑戰(zhàn)。但如果核聚變實(shí)驗(yàn)室成功建成反應(yīng)堆，其應(yīng)用價(jià)值將是顯而易見(jiàn)的。反觀量子計(jì)算，它更像是一把尋找釘子的鐵錘。

盡管如此，量子計(jì)算領(lǐng)域的產(chǎn)業(yè)投資目前正在加速增長(zhǎng)。為了維持這種動(dòng)能，必須在投資增長(zhǎng)和硬件進(jìn)步的同時(shí)，推進(jìn)算法能力的發(fā)展。發(fā)現(xiàn)量子算法的時(shí)機(jī)，就是現(xiàn)在。

賦能理論家

理論研究具有前瞻性和預(yù)測(cè)性。比如Geoffrey Hinton的工作為今天的人工智能革命奠定了基礎(chǔ)。而幾十年后，隨著硬件資源的豐富，AI已成為一門更偏向?qū)嵶C性的學(xué)科。我期待量子硬件也能早日步入繁榮，但現(xiàn)在還未到時(shí)候。

今天的量子計(jì)算，仍是理論家擁有巨大影響力的領(lǐng)域。Peter Shor幾頁(yè)數(shù)學(xué)推導(dǎo)，激勵(lì)了數(shù)以千計(jì)的研究者、工程師和投資人投身此領(lǐng)域。也許讀這篇文章的人中，有人能再寫幾頁(yè)新的論文，由此奠定行業(yè)未來(lái)變革的基礎(chǔ)。很少有地方像這里一樣，數(shù)學(xué)能夠發(fā)揮如此巨大的實(shí)際影響。整個(gè)實(shí)驗(yàn)家、工程師和企業(yè)界群體，都在期待理論家的新思路。

挑戰(zhàn)

傳統(tǒng)上，人們認(rèn)為理想的量子算法應(yīng)具備三大特性：

1. 可證明的正確性：確?？煽繄?zhí)行量子電路即可得到正確結(jié)果；

2. 經(jīng)典難解性：量子算法的輸出，經(jīng)典算法難以在合理時(shí)間內(nèi)復(fù)現(xiàn)；

3. 實(shí)用性：有潛力解決現(xiàn)實(shí)世界中的有意義問(wèn)題。

Shor算法幾乎滿足了這三條標(biāo)準(zhǔn)。但在實(shí)際探索中，絕對(duì)堅(jiān)持三條標(biāo)準(zhǔn)反而可能適得其反。

可證明的正確性很重要，因?yàn)槟壳拔覀兩胁荒茉诖笠?guī)模硬件上直接驗(yàn)證量子算法。但對(duì)于“經(jīng)典難解性”，我們應(yīng)要求到什么程度呢？畢竟，要嚴(yán)格證明一個(gè)問(wèn)題經(jīng)典難解，需要解決P vs NP這樣的重大開放問(wèn)題，這是不現(xiàn)實(shí)的。我們可以采用“軟證明”，比如將問(wèn)題規(guī)約（reduction）到已有的經(jīng)典復(fù)雜性假設(shè)。

我認(rèn)為我們應(yīng)該將“可證明經(jīng)典難解”這一理想替換為更加務(wù)實(shí)的標(biāo)準(zhǔn)：只要量子算法在平均情況下，相比已知最優(yōu)的經(jīng)典算法，取得超二次加速（super-quadratic speedup）即可。[注1]

過(guò)于強(qiáng)調(diào)傳統(tǒng)的難解性定義，可能反而妨礙新算法的發(fā)現(xiàn)，因?yàn)檎嬲路f的量子算法，很可能會(huì)引入全新的經(jīng)典復(fù)雜性假設(shè)，與既有的假設(shè)有根本性不同。而這種提出新假設(shè)并攻破它的反復(fù)過(guò)程，本身就是幫我們尋找量子優(yōu)勢(shì)的高效路徑。

此外，直接把目標(biāo)瞄準(zhǔn)為用量子算法“解決現(xiàn)有的實(shí)際問(wèn)題”也可能是徒勞的。能夠?qū)崿F(xiàn)量子優(yōu)勢(shì)的基礎(chǔ)性計(jì)算任務(wù)非常特殊，數(shù)量也非常少，但它們必然最終會(huì)成為量子應(yīng)用的基石。我們應(yīng)該尋找更多這樣的基礎(chǔ)任務(wù)，再考慮它們與具體應(yīng)用匹配。

當(dāng)然，區(qū)分哪些量子算法未來(lái)可能具有實(shí)際計(jì)算意義是很重要的。在現(xiàn)實(shí)世界中，計(jì)算必須是可驗(yàn)證或者至少可重復(fù)的，否則它沒(méi)有實(shí)際意義。例如，一個(gè)用來(lái)計(jì)算物理中可觀測(cè)量的量子模擬算法，如果在兩臺(tái)量子計(jì)算機(jī)上得到相同的結(jié)果，那么我們就有信心這個(gè)結(jié)果是正確且有物理意義的。一些問(wèn)題，如因式分解，自然容易經(jīng)典驗(yàn)證，但我們可以把標(biāo)準(zhǔn)定得更低：一個(gè)有效的量子算法的輸出至少應(yīng)該能夠被另一個(gè)量子計(jì)算機(jī)重復(fù)。

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

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

我們可以把以上優(yōu)先級(jí)總結(jié)為以下挑戰(zhàn)：

挑戰(zhàn)

請(qǐng)找到一個(gè)量子算法及其輸入分布，滿足以下特性：

可證明的正確性：量子算法本身是正確的；
經(jīng)典難解性：在輸入分布的平均情況下，量子算法比最優(yōu)的經(jīng)典算法實(shí)現(xiàn)超二次加速；
潛在的應(yīng)用價(jià)值：輸出結(jié)果是可驗(yàn)證的，或者至少是可重復(fù)的。
示例與非示例

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

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

已有一些例子顯示，量子計(jì)算可以幫助解決未解的科學(xué)問(wèn)題，比如Hubbard模型的相圖或FeMoCo分子的基態(tài)能量。這些問(wèn)題無(wú)疑具有科學(xué)價(jià)值。但它們是孤例，我們更希望有證據(jù)可以表明量子計(jì)算的可解問(wèn)題是無(wú)窮無(wú)盡的。我們能否從強(qiáng)相關(guān)物理中獲得靈感，寫出一系列具體的哈密頓量模擬系統(tǒng)，其中存在經(jīng)典難解的可觀測(cè)量？這將為量子模擬持續(xù)且廣泛的應(yīng)用收集證據(jù)，也將幫助我們理解量子優(yōu)勢(shì)在哪里以及如何產(chǎn)生。

計(jì)算機(jī)科學(xué)界也做了大量關(guān)于“預(yù)言機(jī)分離”（oracle separation）的工作，如焊接樹（welded trees）、傅換關(guān)聯(lián)（forrelation），這增強(qiáng)了我們對(duì)量子計(jì)算機(jī)能力的信心。現(xiàn)在需要將這些oracle實(shí)例化為“明天就可以在真實(shí)設(shè)備上跑”的算法，這是初步測(cè)試算法所必需的。

除了哈密頓量模擬，還有其他幾個(gè)重要的量子算法門類：包括求解線性方程組與微分方程的量子算法；用于機(jī)器學(xué)習(xí)的變分量子算法；用于優(yōu)化問(wèn)題的量子算法。

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

關(guān)于表1中提到的采樣任務(wù)，其本身并沒(méi)有實(shí)際意義，因?yàn)樗鼈兩踔敛皇橇孔涌芍貜?fù)的。人們會(huì)想，采樣任務(wù)能否以某種方式變得有用。畢竟，經(jīng)典蒙特卡洛算法已經(jīng)得到了廣泛應(yīng)用（譯者注：該算法是一類基于隨機(jī)采樣的數(shù)值方法，廣泛應(yīng)用于強(qiáng)關(guān)聯(lián)量子多體系統(tǒng)的模擬，例如凝聚態(tài)物理、核物理、冷原子物理等領(lǐng)域中的多體量子系統(tǒng)）。而采樣的應(yīng)用通常使用樣本來(lái)提取有意義的信息或底層分布的特定特征，例如蒙特卡羅采樣可以用于計(jì)算貝葉斯推斷和統(tǒng)計(jì)物理中的積分。相比之下，從隨機(jī)量子電路獲得的樣本缺乏任何可辨別的特征。但如果能從采樣中提取出難以經(jīng)典計(jì)算的有意義信號(hào)，這些任務(wù)也可以轉(zhuǎn)變?yōu)閿?shù)值計(jì)算類任務(wù)。

表1也指出量子性證明類應(yīng)用沒(méi)有實(shí)用性，這并不完全正確。一個(gè)有潛在應(yīng)用的例子是可認(rèn)證隨機(jī)數(shù)生成，但這類應(yīng)用通常屬于密碼學(xué)用途，而非計(jì)算用途。具體來(lái)說(shuō)，量子性證明不能直接用來(lái)解決問(wèn)題或者回答我們還不知道答案的問(wèn)題。

最后，量子技術(shù)在傳感、通信、帶有量子記憶的學(xué)習(xí)、數(shù)據(jù)流處理等方面也有令人激動(dòng)的應(yīng)用前景。這些方向非常有趣，我希望在人類理解量子力學(xué)的第二個(gè)世紀(jì)能夠創(chuàng)造出各種各樣的能力。而眼下技術(shù)動(dòng)力仍然集中在構(gòu)建量子計(jì)算機(jī)以實(shí)現(xiàn)計(jì)算優(yōu)勢(shì)上，因此這方面的突破將產(chǎn)生最大的即時(shí)影響。

不必太害怕

在每年舉辦的QIP（量子信息處理）會(huì)議上，數(shù)百篇論文中，只有極少數(shù)研究嘗試提出新的量子算法。鑒于其重要性，為什么這個(gè)數(shù)量還是如此之低？一個(gè)常見(jiàn)的解釋是：量子算法研究太難了。不過(guò)，最近幾年量子算法領(lǐng)域?qū)嶋H上已經(jīng)取得了不少實(shí)質(zhì)進(jìn)展。從2000年到2020年，具有實(shí)用潛力的算法寥寥無(wú)幾，而表格中列出的許多成果都是近5年內(nèi)的突破。

在盲目樂(lè)觀與消極悲觀之間，采用一種“使命驅(qū)動(dòng)”的探索心態(tài)，將能推動(dòng)整個(gè)領(lǐng)域前進(jìn)。我們應(yīng)該允許自己采用更加探索性、務(wù)實(shí)的策略：在未被充分研究的問(wèn)題上，或小數(shù)點(diǎn)后第三位的微妙信號(hào)中尋找量子優(yōu)勢(shì)。

實(shí)現(xiàn)意義重大的進(jìn)步，其實(shí)門檻比看起來(lái)要低得多，即使是微小的前進(jìn)，也是寶貴的。不要太害怕！

注釋

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

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

特 別 提 示

1. 進(jìn)入『返樸』微信公眾號(hào)底部菜單“精品專欄“，可查閱不同主題系列科普文章。

2. 『返樸』提供按月檢索文章功能。關(guān)注公眾號(hào)，回復(fù)四位數(shù)組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。

版權(quán)說(shuō)明：歡迎個(gè)人轉(zhuǎn)發(fā)，任何形式的媒體或機(jī)構(gòu)未經(jīng)授權(quán)，不得轉(zhuǎn)載和摘編。轉(zhuǎn)載授權(quán)請(qǐng)?jiān)凇阜禈恪刮⑿殴娞?hào)內(nèi)聯(lián)系后臺(tái)。