讓我們假設(shè)你想發(fā)送一條私密信息、進(jìn)行秘密投票或是安全地簽署文件。如果你在電腦上執(zhí)行這些任務(wù)，就需要依靠加密來(lái)保證數(shù)據(jù)的安全。這種加密需要能夠抵御密碼破譯者用他們自己的計(jì)算機(jī)進(jìn)行的攻擊，因此現(xiàn)代加密方法依賴(lài)于這樣一種假設(shè)：哪些數(shù)學(xué)問(wèn)題對(duì)計(jì)算機(jī)而言是難以解決的？

但在20世紀(jì)80年代，當(dāng)密碼學(xué)家為這種信息安全方法奠定數(shù)學(xué)基礎(chǔ)時(shí)，一些研究人員發(fā)現(xiàn)，計(jì)算難度并不是守護(hù)秘密的唯一方法。量子理論起初是為了理解原子物理學(xué)而開(kāi)發(fā)、構(gòu)建，可事實(shí)證明，它竟然與信息和密碼學(xué)有著深刻的聯(lián)系。研究人員找到了一些方法，可以直接基于物理定律確保某些特定加密任務(wù)的安全性。但這些任務(wù)都屬于少見(jiàn)的特例——對(duì)于其他所有任務(wù)而言，除了經(jīng)典計(jì)算方法之外，似乎別無(wú)他法。

到了20世紀(jì)末，量子密碼學(xué)研究人員認(rèn)為這就是最后的答案了。但就在過(guò)去的幾年里，這個(gè)領(lǐng)域又發(fā)生了翻天覆地的變化。

“我們對(duì)量子密碼學(xué)可能實(shí)現(xiàn)的內(nèi)容有了重新的認(rèn)識(shí)。”美國(guó)哥倫比亞大學(xué)的量子信息理論家亨利·袁（Henry Yuen）說(shuō)。

在最近的一系列論文中，研究人員表明，即使在幾乎所有計(jì)算都變得很容易的假想世界中，大多數(shù)加密任務(wù)仍然可以安全地完成。真正關(guān)鍵的是一個(gè)有關(guān)量子理論本身的特殊計(jì)算問(wèn)題的難度。

“你所需要的假設(shè)可以非常、非常、非常弱，”位于美國(guó)加利福尼亞州伯克利的西蒙斯計(jì)算理論研究所的量子密碼學(xué)家費(fèi)米·馬（Fermi Ma）表示，“這讓我們對(duì)計(jì)算難度本身有了新的認(rèn)識(shí)?！?/p>

此信息將自動(dòng)銷(xiāo)毀

故事開(kāi)始于20世紀(jì)60年代末，當(dāng)時(shí)一位名叫史蒂芬·威斯納（Stephen Wiesner）的物理學(xué)研究生開(kāi)始思考量子理論中測(cè)量的破壞性。對(duì)任何受量子物理規(guī)則支配的系統(tǒng)進(jìn)行測(cè)量，都會(huì)改變從數(shù)學(xué)層面描述其構(gòu)形的量子狀態(tài)。對(duì)于大多數(shù)物理學(xué)家來(lái)說(shuō)，這種量子測(cè)量干擾都是一種障礙。但威斯納持有以信息為中心的非正統(tǒng)觀點(diǎn)，他開(kāi)始思考能否讓這種干擾變得有用?；蛟S它可以成為敏感數(shù)據(jù)的一種內(nèi)置防篡改保護(hù)。

但威斯納的想法過(guò)于超前，在研究生畢業(yè)后，他就離開(kāi)了學(xué)術(shù)界。幸運(yùn)的是，他曾與他的朋友、物理學(xué)家查爾斯·貝內(nèi)特（Charles Bennett）討論過(guò)這些想法，后者在長(zhǎng)達(dá)十年的時(shí)間里嘗試引起他人對(duì)此話(huà)題的興趣，始終未果。最后，1979年，貝內(nèi)特在波多黎各的一次會(huì)議期間，于海邊游泳時(shí)遇到了計(jì)算機(jī)科學(xué)家吉爾斯·布拉薩德（Gilles Brassard）。他們合作撰寫(xiě)了一篇開(kāi)創(chuàng)性的論文，描述了一種解決重要加密任務(wù)的新方法。他們的協(xié)議基于量子測(cè)量干擾，無(wú)需任何關(guān)于計(jì)算問(wèn)題難度的假設(shè)。

“量子信息在本質(zhì)上似乎就是加密的。”費(fèi)米·馬說(shuō)。

貝內(nèi)特和布拉薩德的突破讓研究人員變得樂(lè)觀起來(lái)，他們相信，其他加密任務(wù)也可以通過(guò)類(lèi)似的量子技術(shù)達(dá)到完美的安全性。研究人員主要關(guān)注一種名為比特承諾的任務(wù)，它不僅本身非常有用，還是大多數(shù)高級(jí)加密協(xié)議的關(guān)鍵組成部分。

要理解比特承諾背后的基本概念，可以想象一場(chǎng)雙人游戲。在這場(chǎng)游戲中，你必須做出一個(gè)秘密決定，這個(gè)決定需要在稍后揭示。一種方法是把決定寫(xiě)在紙條上，并放入密封的信封。這樣，你之后就無(wú)法更改決定，你的對(duì)手也無(wú)法偷看結(jié)果。

現(xiàn)在想象一下，你們?cè)诰W(wǎng)上玩同樣的游戲。為了讓作弊成為不可能，你需要把決定封在一個(gè)數(shù)字信封里，讓雙方都無(wú)法單獨(dú)打開(kāi)。這就是密碼學(xué)的用武之地。1981 年，計(jì)算機(jī)科學(xué)家先驅(qū)曼紐爾·布盧姆（Manuel Blum）構(gòu)建了第一個(gè)比特承諾協(xié)議——一種利用難解的計(jì)算問(wèn)題構(gòu)造不可破解信封的方法。

但“難解”具體有多難？計(jì)算復(fù)雜性理論領(lǐng)域的研究人員研究了許多不同類(lèi)型的難題，并非所有難題都對(duì)密碼學(xué)家有用。比特承諾和其他所有的加密協(xié)議都依賴(lài)于一類(lèi)被復(fù)雜性理論學(xué)家稱(chēng)為“NP”類(lèi)的問(wèn)題，這類(lèi)問(wèn)題的定義特征是很容易檢查候選解是否正確。

遺憾的是，研究人員尚未證明任何NP類(lèi)問(wèn)題都很難解。即使是看似最難的問(wèn)題，也可能存在某種尚未發(fā)現(xiàn)的巧妙程序或算法能夠?qū)⑵湟慌e解決。如果當(dāng)真存在這樣的程序，那么整個(gè)經(jīng)典密碼學(xué)都會(huì)崩潰。

這些考慮推動(dòng)著人們探索基于量子的安全保證。但在1997年，兩篇論文證明，完全基于量子物理定律的比特承諾方案永遠(yuǎn)不可能徹底安全。這兩篇論文暗示，幾乎所有加密任務(wù)都需要某種計(jì)算難度。

在接下來(lái)的近25年里，這成為量子比特承諾理論基礎(chǔ)的定論。然后，在2021年，一位名叫威廉·克雷其默（William Kretschmer）的研究生發(fā)表了一篇論文，促使研究人員面對(duì)一個(gè)從未有人想過(guò)的問(wèn)題。對(duì)于比特承諾和大多數(shù)其他形式的密碼學(xué)來(lái)說(shuō)，計(jì)算難度顯然是必要的，但究竟是哪一種難度呢？

答案比任何人預(yù)想的都要奇怪。

咨詢(xún)諭示

2021年的論文源于克雷其默想要努力理解一個(gè)概念上看似簡(jiǎn)單的問(wèn)題的特定版本：區(qū)分或判別兩種表面上相似的量子態(tài)到底有多難？克雷其默眼下是西蒙斯研究所的博士后研究員，而他最初對(duì)這個(gè)問(wèn)題產(chǎn)生興趣的原因與比特承諾無(wú)關(guān)。

“密碼學(xué)根本不在我的考慮范圍內(nèi)?！彼f(shuō)。

判別問(wèn)題之所以有趣，部分原因在于，人們甚至不清楚如何用熟悉的數(shù)學(xué)語(yǔ)言來(lái)描述它。傳統(tǒng)上，復(fù)雜性理論學(xué)家研究的問(wèn)題都有不同的可能輸入，這些輸入由位串（即0和1）表示。例如，對(duì)于將大數(shù)分解為質(zhì)因數(shù)的任務(wù)，輸入的位串就代表要分解的數(shù)。

即使在研究人員開(kāi)始研究如何利用量子物理進(jìn)行計(jì)算之后，他們?nèi)匀话阎攸c(diǎn)放在這種“經(jīng)典輸入”問(wèn)題上。典型的量子算法以普通的經(jīng)典位串為起始，然后使用量子技巧對(duì)其進(jìn)行處理。但在克雷其默研究的這類(lèi)“量子輸入”問(wèn)題中，輸入并非位串，而是容易被計(jì)算干擾的量子態(tài)（就和測(cè)量的干擾一樣）。

“我們無(wú)法使用傳統(tǒng)復(fù)雜性理論中用來(lái)描述量子計(jì)算的語(yǔ)言直接談?wù)撨@些問(wèn)題。”亨利·袁說(shuō)。

起初，克雷其默認(rèn)為他只需要把問(wèn)題翻譯成更標(biāo)準(zhǔn)的語(yǔ)言，但他想不出該怎么做。于是，他做了復(fù)雜性理論學(xué)家在走投無(wú)路時(shí)經(jīng)常做的事：求助于諭示。

在復(fù)雜性理論中，“諭示”（oracle）指的是一種可以即時(shí)解決特定問(wèn)題的假想設(shè)備。能夠訪(fǎng)問(wèn)諭示的計(jì)算機(jī)可能會(huì)通過(guò)咨詢(xún)諭示，將其作為算法的中間步驟，從而更輕松地解決其他問(wèn)題。當(dāng)然，諭示在現(xiàn)實(shí)世界中并不存在，但研究它們有助于復(fù)雜性理論學(xué)家理解不同問(wèn)題的難度級(jí)別之間的關(guān)系。

克雷其默想知道，什么樣的諭示可以輕松區(qū)分兩種量子態(tài)，即所謂的態(tài)判別問(wèn)題。他決定從一種特殊的諭示入手，這種諭示可以增強(qiáng)普通量子算法的能力，也就是那些利用量子技巧解決經(jīng)典位串輸入問(wèn)題的算法。這類(lèi)算法可以解決某些對(duì)經(jīng)典算法來(lái)說(shuō)太難的問(wèn)題，比如大數(shù)分解，但它們并非萬(wàn)能的，還有許多問(wèn)題超出了它們的能力范圍。

訪(fǎng)問(wèn)克雷其默的諭示可以讓這些算法解決現(xiàn)實(shí)中的量子計(jì)算機(jī)難以解決的某些經(jīng)典輸入問(wèn)題?？死灼淠疽詾檫@些算法用來(lái)解決他的問(wèn)題已經(jīng)綽綽有余，但令他驚訝的是，他證明了這些加強(qiáng)版量子算法仍然被態(tài)判別問(wèn)題難倒了。

“我完全被威廉的論文吸引了，”波士頓大學(xué)的密碼學(xué)研究生錢(qián)洛文（音譯）說(shuō)，“我當(dāng)時(shí)真的覺(jué)得它肯定錯(cuò)了，因?yàn)樗粗庇X(jué)了?！?/p>

錢(qián)洛文、亨利·袁等人很快證明，如果克雷其默的態(tài)判別問(wèn)題真的很難解決，那么安全的量子比特承諾方案就可能實(shí)現(xiàn)。這反過(guò)來(lái)又意味著許多更高級(jí)的加密協(xié)議也擁有了安全性。量子加密的范圍遠(yuǎn)比20世紀(jì)90年代的研究人員所意識(shí)到的要廣泛，而這一切都?xì)w結(jié)于一個(gè)問(wèn)題的難解程度。

能有多難？

克雷其默的結(jié)果有一個(gè)重大的前提——為了使證明成立，他不得不依賴(lài)一個(gè)只有量子算法才能咨詢(xún)的不尋常諭示。或許，一個(gè)更為熟悉的諭示會(huì)讓他的態(tài)判別問(wèn)題變得更容易，從而使安全的量子比特承諾失效？2022年，克雷其默和錢(qián)洛文開(kāi)始合作，研究他們能用一個(gè)人人都能理解的諭示證明出什么結(jié)論：一個(gè)可以瞬間解決任何NP問(wèn)題的諭示。在擁有這種諭示的世界里，所有的經(jīng)典加密都將失效。

克雷其默很快意識(shí)到，態(tài)判別問(wèn)題在數(shù)學(xué)上與量子復(fù)雜性理論中一個(gè)看似不同的問(wèn)題有著關(guān)聯(lián)，于是他請(qǐng)來(lái)了該領(lǐng)域的兩位專(zhuān)家——復(fù)雜性理論學(xué)家阿維謝·塔爾（Avishay Tal）和馬克蘭德·辛哈（Makrand Sinha）?！巴拖駛€(gè)經(jīng)理，而我們則是承包商?！彼栒f(shuō)。

四位研究人員通力合作，很快就證明，即使是對(duì)于能夠調(diào)用這個(gè)NP諭示的計(jì)算機(jī)，克雷其默的態(tài)判別問(wèn)題可能仍然是不可解的。這意味著，即使支撐起經(jīng)典加密的每一個(gè)問(wèn)題都變得容易，幾乎所有量子加密依然可以保持安全。經(jīng)典密碼學(xué)和量子密碼學(xué)越來(lái)越像兩個(gè)完全獨(dú)立于彼此的世界。

這個(gè)結(jié)果引起了費(fèi)米·馬的注意，他開(kāi)始琢磨，自己能把克雷其默開(kāi)創(chuàng)的研究方向推到多遠(yuǎn)。即使引入更離奇的諭示——那些可以瞬間解決遠(yuǎn)比NP難得多的計(jì)算問(wèn)題的諭示——量子加密是否仍能保持安全呢？“NP類(lèi)問(wèn)題并不是經(jīng)典問(wèn)題中最難的，”美國(guó)伊利諾伊大學(xué)厄巴納-香檳分校的密碼學(xué)家達(dá)克希塔·庫(kù)拉納（Dakshita Khurana）表示，“還有比它們更難的。”

費(fèi)米·馬與普林斯頓大學(xué)的密碼學(xué)家亞歷克斯·隆巴迪（Alex Lombardi）以及加州大學(xué)伯克利分校的量子計(jì)算研究員約翰·賴(lài)特（John Wright）集思廣益，思索如何以最佳方式解決這個(gè)問(wèn)題?！斑@個(gè)問(wèn)題真是太迷人、太令人費(fèi)解了，”賴(lài)特說(shuō)，“我立刻就被吸引住了?！?/p>

在思考了一段時(shí)間卻毫無(wú)進(jìn)展后，費(fèi)米·馬提出，他們應(yīng)當(dāng)考慮最極端的情況：一個(gè)可以瞬間解決任何經(jīng)典輸入計(jì)算問(wèn)題的諭示。這將囊括復(fù)雜性理論學(xué)家傳統(tǒng)上研究的一切問(wèn)題，甚至包括那些在現(xiàn)實(shí)世界中被認(rèn)為不可解的問(wèn)題。

“我覺(jué)得這聽(tīng)起來(lái)有點(diǎn)瘋?！甭“偷险f(shuō)。

但是，這個(gè)問(wèn)題卻取得了驚人的成果。經(jīng)過(guò)近一年的努力，他們終于發(fā)表了一項(xiàng)驚人的結(jié)果。在能且只能咨詢(xún)一次全能諭示的情況下，沒(méi)有任何一個(gè)算法可以區(qū)分兩種量子態(tài)，做不到這點(diǎn)，就無(wú)法破壞量子比特承諾方案。

只允許算法單次查詢(xún)的限制并不像聽(tīng)起來(lái)那么大，因?yàn)榱孔铀惴梢岳靡环N叫作疊加的現(xiàn)象，在實(shí)際上要求諭示同時(shí)解決多個(gè)問(wèn)題。能夠連續(xù)進(jìn)行多次查詢(xún)的算法可能會(huì)更強(qiáng)大，因?yàn)樗鼈兛梢岳们按尾樵?xún)的答案來(lái)決定下一次的查詢(xún)內(nèi)容。這些算法是否也會(huì)受到類(lèi)似的限制，仍然是一個(gè)懸而未決的問(wèn)題。

費(fèi)米·馬、隆巴迪和賴(lài)特的論文之所以意義重大，還有另一個(gè)原因。在這三位研究人員研究他們的問(wèn)題時(shí)，他們意識(shí)到它與復(fù)雜性理論學(xué)家斯科特 · 阿倫森（Scott Aaronson）和數(shù)學(xué)家格雷格·庫(kù)珀伯格（Greg Kuperberg）在16年前提出的一個(gè)重大未解問(wèn)題密切相關(guān)，該問(wèn)題涉及將一種量子態(tài)轉(zhuǎn)化為另一種量子態(tài)的難度。這篇新論文是解決該問(wèn)題的第一個(gè)重大進(jìn)展。

“這是一個(gè)非常強(qiáng)有力的結(jié)果，也是一個(gè)非常令人驚訝的結(jié)果?！本┒紲ɡ碚撐锢硌芯克牧孔用艽a學(xué)研究員森前智行表示。

一系列的最新成果表明，區(qū)分兩種量子態(tài)這個(gè)看似無(wú)害的問(wèn)題不僅很難，而且?guī)缀跏请y以想象的難——遠(yuǎn)遠(yuǎn)超出了普通甚至更離奇的量子算法的能力范圍。這對(duì)密碼學(xué)來(lái)說(shuō)是好消息，但對(duì)以量子態(tài)為輸入的計(jì)算問(wèn)題也有更廣泛的影響。傳統(tǒng)的復(fù)雜性理論似乎無(wú)法解決這些問(wèn)題。要真正理解這些問(wèn)題，可能需要一個(gè)全新的理論框架。

“感覺(jué)量子信息的行為方式有一些根本性的不同，”美國(guó)華盛頓大學(xué)的量子密碼學(xué)家安德烈亞·克拉丹杰洛（Andrea Coladangelo）說(shuō)，“它一定還與密碼學(xué)之外的領(lǐng)域存在聯(lián)系?！?/p>

資料來(lái)源 Quanta Magazine