如何知道量子計(jì)算機(jī)是否已經(jīng)完成了任何量子計(jì)算？

Urmila Mahadev在研究生院學(xué)習(xí)了八年，最終獨(dú)立解決了量子計(jì)算中最基本的問(wèn)題之一：如何知道量子計(jì)算機(jī)是否已經(jīng)完成了任何量子計(jì)算？

2017年春天，加州大學(xué)伯克利分校的博士研究生Urmila Mahadev突然發(fā)現(xiàn)自己成了他人眼中的傾佩對(duì)象。她解決了量子計(jì)算中的一個(gè)主要問(wèn)題，結(jié)合之前發(fā)表的論文，她儼然已經(jīng)成為學(xué)界一顆冉冉升起的新星。但28歲的她卻放棄了畢業(yè)，甚至壓根沒(méi)有考慮過(guò)畢業(yè)。

這是她在伯克利研究生院求學(xué)的第七年——很久之前，大多數(shù)學(xué)生都已經(jīng)不耐煩地畢業(yè)了。

Urmila Mahadev

早在五年前，她的目光就被一個(gè)與眾不同的研究問(wèn)題所吸引，Aaronson稱(chēng)之為“量子計(jì)算中你可以提出的最基本問(wèn)題之一”，即：如果你要求量子計(jì)算機(jī)執(zhí)行計(jì)算，那你該怎么判斷它是否按指示執(zhí)行了任務(wù)，甚至只是做了任何和量子計(jì)算有關(guān)的事？

現(xiàn)在這個(gè)問(wèn)題即將遠(yuǎn)離學(xué)界。在過(guò)去的幾年里，研究人員一直希望能把量子計(jì)算機(jī)用于科研，從研究黑洞周?chē)淖兓酱蟮鞍踪|(zhì)折疊，量子計(jì)算帶來(lái)的加速效果是指數(shù)級(jí)的。但是，一旦量子計(jì)算機(jī)真正執(zhí)行了經(jīng)典計(jì)算機(jī)無(wú)法做到的計(jì)算，那人類(lèi)該怎么確保計(jì)算結(jié)果的可信度？

如果我們不相信經(jīng)典計(jì)算機(jī)的結(jié)果，我們可以從頭開(kāi)始一步步驗(yàn)證，但量子系統(tǒng)是從根本上就抵制這種檢查的。首先，它們的內(nèi)部工作非常復(fù)雜：即便只用幾百個(gè)量子比特（或“量子位”）寫(xiě)下計(jì)算機(jī)內(nèi)部狀態(tài)的描述，那也需要一個(gè)比整個(gè)可見(jiàn)宇宙更大的硬盤(pán)。

其次，即便我們以某種方式記下這個(gè)描述，它也是難以理解的。量子計(jì)算機(jī)的內(nèi)部狀態(tài)通常是許多不同的非量子“經(jīng)典”狀態(tài)的疊加，如“薛定諤的貓”。但是，一旦你測(cè)量了一個(gè)量子態(tài)，它就會(huì)坍縮成這些經(jīng)典狀態(tài)中的一個(gè)。也就是說(shuō)，當(dāng)看著量子計(jì)算機(jī)里的300個(gè)量子比特時(shí)，我們基本上只能看到300個(gè)經(jīng)典比特——0和1。

“量子計(jì)算機(jī)非常強(qiáng)大，但它也非常隱秘。”

考慮到這些限制因素，計(jì)算機(jī)科學(xué)家們長(zhǎng)期以來(lái)一直想知道量子計(jì)算機(jī)是否能提供一些“鐵證”，證明自己已經(jīng)完成某些計(jì)算。這也是量子計(jì)算和古典計(jì)算進(jìn)行“對(duì)話(huà)”的橋梁。Mahadev被這個(gè)問(wèn)題迷住是在她讀研究生的第二年，在之后的幾年里，她一直反復(fù)嘗試驗(yàn)證方法，而在無(wú)數(shù)挫折中，她也展現(xiàn)了自己持久的耐心和決心。

經(jīng)過(guò)多年努力，現(xiàn)在她終于讓學(xué)界見(jiàn)證了她的成功。10月7日，計(jì)算機(jī)科學(xué)頂會(huì)FOCS 2018在法國(guó)巴黎正式召開(kāi)，這是理論計(jì)算機(jī)科學(xué)最大的會(huì)議之一。在會(huì)上，Mahadev帶來(lái)了論文Classical Verification of Quantum Computations，她提出了一種交互式協(xié)議，用密碼學(xué)為量子計(jì)算這批野馬安上了“馬鞍”。她的作品被授予會(huì)議“最佳論文”和“最佳學(xué)生論文”獎(jiǎng)，這是理論計(jì)算機(jī)科學(xué)家難得的榮譽(yù)。

一條漫長(zhǎng)的道路

Mahadev在洛杉磯的一個(gè)醫(yī)生家庭長(zhǎng)大，出于對(duì)成為醫(yī)生的抵觸心理，她在南加州大學(xué)求學(xué)期間聽(tīng)了RSA加密算法的創(chuàng)造者之一、計(jì)算機(jī)科學(xué)家Leonard Adleman教授的課程，并把專(zhuān)業(yè)改成了理論計(jì)算機(jī)科學(xué)。直到在向伯克利研究生院遞交申請(qǐng)之前，量子計(jì)算于她都是最陌生、最不了解的事情。

但是，到了伯克利，一切就完全不同了。她的博士生導(dǎo)師Umesh Vazirani向她介紹了一個(gè)問(wèn)題：找到一個(gè)驗(yàn)證量子計(jì)算的協(xié)議。這個(gè)問(wèn)題徹底激發(fā)了她的學(xué)術(shù)熱情。

有一個(gè)基礎(chǔ)事實(shí)是，也許量子計(jì)算機(jī)可以解決經(jīng)典計(jì)算機(jī)無(wú)法解決的問(wèn)題，但它的解決方案不一定是難以驗(yàn)證的。比如分解大數(shù)字，這是個(gè)經(jīng)典計(jì)算機(jī)無(wú)法計(jì)算而量子計(jì)算機(jī)可以高效解決的任務(wù)。雖然無(wú)法計(jì)算，可驗(yàn)證量子計(jì)算機(jī)的因子分解是否正確對(duì)經(jīng)驗(yàn)計(jì)算機(jī)來(lái)說(shuō)很容易——它只需要將這些因子相乘，看看它們是否能產(chǎn)生正確的答案。

然而，計(jì)算機(jī)科學(xué)家認(rèn)為量子計(jì)算機(jī)可以解決的許多問(wèn)題不具備上述特征。換句話(huà)說(shuō)，經(jīng)典計(jì)算機(jī)不僅無(wú)法解決它們，甚至也識(shí)別不了解決方案是否正確。鑒于此，2004年的時(shí)候，物理學(xué)家Daniel Gottesman把“量子驗(yàn)證”這個(gè)問(wèn)題拋給學(xué)界。

問(wèn)題提出的四年內(nèi)，一些量子計(jì)算研究人員得到了部分答案。兩個(gè)不同的團(tuán)隊(duì)證實(shí)確實(shí)存在一種能證明已經(jīng)完成量子計(jì)算的方法，他們的一個(gè)關(guān)鍵想法是利用交互性證明，即給定一定的計(jì)算，使得設(shè)備（以下稱(chēng)為“證明者”）具有執(zhí)行計(jì)算的能力，但是另一個(gè)實(shí)體（以下稱(chēng)為“驗(yàn)證者”）不具有。假設(shè)證明者是不受信任的，也可能會(huì)欺騙驗(yàn)證者，我們要找出一種方法，讓驗(yàn)證者從證明者手中拿到高度可信的正確答案。

這個(gè)框架起源于20世紀(jì)90年代的復(fù)雜性理論。其中最簡(jiǎn)單的方法是驗(yàn)證者可以自己執(zhí)行驗(yàn)證計(jì)算，直接檢查證明者的結(jié)果。第二種方法是驗(yàn)證者無(wú)法執(zhí)行計(jì)算，但證明者可以提供一個(gè)簡(jiǎn)短的“證據(jù)”，再由前者完全證明結(jié)果。交互式證明是一種協(xié)議，通過(guò)該協(xié)議，驗(yàn)證者可以和更強(qiáng)大但不可信的證明者進(jìn)行交互。

在Mahadev的成果出現(xiàn)之前，學(xué)界通過(guò)引入交互式模型，允許驗(yàn)證者使用非常有限的量子計(jì)算機(jī)，在“量子驗(yàn)證”這個(gè)問(wèn)題上取得了一定進(jìn)展。簡(jiǎn)而言之，如果采用上述第一種方法，就是讓驗(yàn)證者具備在它選擇的兩個(gè)可能的基礎(chǔ)中準(zhǔn)備單個(gè)量子比特的能力，一次一個(gè)，由它把量子比特發(fā)送給證明者；如果采用第二種方法，就是讓驗(yàn)證者可以一次一個(gè)地從證明者處接收單個(gè)量子比特，并在它選擇的兩個(gè)基礎(chǔ)之一中對(duì)它們進(jìn)行驗(yàn)證。

一般情況下，這兩種方法都能驗(yàn)證任意多項(xiàng)式時(shí)間量子計(jì)算，而其中的重點(diǎn)是驗(yàn)證者準(zhǔn)備量子比特的能力，使證明者可以檢測(cè)到“證據(jù)”與預(yù)先確定的“誠(chéng)實(shí)行為”是否存在偏差。

但問(wèn)題依然存在：十年了，對(duì)于量子計(jì)算機(jī)這個(gè)“證明者”，我們能否找到一個(gè)完全經(jīng)典的“驗(yàn)證者”？

2012年，包括Vazirani在內(nèi)的一組研究人員表明，如果一個(gè)量子計(jì)算機(jī)是由一對(duì)無(wú)法相互通信的量子計(jì)算機(jī)執(zhí)行的，那么一個(gè)完全經(jīng)典的驗(yàn)證器可以檢查量子計(jì)算。雖然這篇論文只討論了某種特定狀態(tài)，但它給Mahadev帶來(lái)了啟發(fā)：是否能找到一個(gè)“無(wú)條件”的結(jié)果，一個(gè)不假設(shè)量子計(jì)算機(jī)能做什么或不做什么的結(jié)果。

進(jìn)行了一段沒(méi)有進(jìn)展的研究后，這對(duì)師生把目光轉(zhuǎn)向了密碼學(xué)（各自研究不同的問(wèn)題）。由于大規(guī)模量子計(jì)算機(jī)在未來(lái)可能會(huì)出現(xiàn)，密碼學(xué)領(lǐng)域?yàn)榱碎_(kāi)發(fā)可抵抗量子攻擊的密碼架構(gòu)，提出了一種名為“后量子密碼學(xué)”的研究。2016年，他們和OpenAI的計(jì)算機(jī)科學(xué)家Paul Christiano達(dá)成合作，共同開(kāi)發(fā)了一種利用密碼學(xué)方法讓量子計(jì)算機(jī)構(gòu)建“secret state”（秘密狀態(tài)，）的方法。

所謂秘密狀態(tài)，就是一種已為人知的經(jīng)典驗(yàn)證者，但它不是量子計(jì)算機(jī)本身。

他們的程序依賴(lài)于所謂的“trapdoor”函數(shù)——一個(gè)易于執(zhí)行但難以反轉(zhuǎn)的函數(shù)，除非你有加密密鑰。這個(gè)函數(shù)需要“二對(duì)一”，也就是每個(gè)輸出對(duì)應(yīng)兩個(gè)不同的輸入。有了它，我們就能用“trapdoor”函數(shù)創(chuàng)建秘密狀態(tài)——首先，要求計(jì)算機(jī)建立一個(gè)函數(shù)所有可能輸入的疊加；其次，讓計(jì)算機(jī)將該函數(shù)應(yīng)用于此巨型疊加，創(chuàng)建一個(gè)新?tīng)顟B(tài)，該狀態(tài)是函數(shù)的所有可能輸出的疊加。這時(shí)輸入和輸出疊加將被糾纏，這意味著對(duì)其中一個(gè)進(jìn)行驗(yàn)證會(huì)立即影響另一個(gè)。

這之后，我們就能要求計(jì)算機(jī)檢查輸出狀態(tài)并匯報(bào)結(jié)果，它在檢查時(shí)可以把輸出狀態(tài)折疊成一個(gè)可能的輸出，由于輸入輸出是糾纏的，這時(shí)輸入也會(huì)被折疊。

2017年，Mahadev解決的那個(gè)量子計(jì)算主要問(wèn)題就是提出構(gòu)建“trapdoor”函數(shù)的加密方法：Learning With Errors（LWE）。她本可以憑借這個(gè)成果畢業(yè)，但面對(duì)還沒(méi)有解決的“量子驗(yàn)證”難題，她表示：

我從未想過(guò)畢業(yè)，因?yàn)槲业哪繕?biāo)從未畢業(yè)。

塵埃終落定

還是那個(gè)問(wèn)題：是否存在一個(gè)完全經(jīng)典的驗(yàn)證者。

從交互性證明到秘密狀態(tài)，Mahadev已經(jīng)試遍了所有方法，有一段時(shí)間，她甚至感到走投無(wú)路。但上天還是眷顧她的，一次，她突然萌生了一個(gè)新想法：研究人員已經(jīng)證實(shí)，如果驗(yàn)證者能夠檢查量子比特，那么它也可以檢查量子計(jì)算機(jī)。根據(jù)定義，經(jīng)典驗(yàn)證者不具備這種能力，但是如果經(jīng)典驗(yàn)證者能以某種方式迫使量子計(jì)算機(jī)自己執(zhí)行檢查并誠(chéng)實(shí)地報(bào)告呢？

這個(gè)問(wèn)題的難點(diǎn)是讓量子計(jì)算機(jī)承諾在驗(yàn)證者檢查之前，自己知道對(duì)方要測(cè)量的狀態(tài)，Mahadev將其稱(chēng)為量子比特承諾問(wèn)題。假設(shè)證明者聲稱(chēng)準(zhǔn)備了一個(gè)選擇的單量子比特狀態(tài)|φ>（驗(yàn)證者不知道），驗(yàn)證者向證明者詢(xún)問(wèn)執(zhí)行|φ>測(cè)量的結(jié)果。無(wú)論是在計(jì)算基礎(chǔ)上（Pauli Z的本征基礎(chǔ)），還是在Hadamard基礎(chǔ)上（Pauli X的本征基礎(chǔ)），是否存在一種協(xié)議，保證在協(xié)議結(jié)束時(shí)，驗(yàn)證者能夠產(chǎn)生與所選基礎(chǔ)中的測(cè)量結(jié)果相匹配的結(jié)果？

這個(gè)新協(xié)議具有以下屬性。首先，正如預(yù)期的那樣，對(duì)于任何量子計(jì)算，都有一個(gè)量子證明者可以使經(jīng)典驗(yàn)證者相信計(jì)算結(jié)果的正確性，此屬性稱(chēng)為協(xié)議的完整性。其次，沒(méi)有證據(jù)可以說(shuō)服經(jīng)典驗(yàn)證者接受錯(cuò)誤的結(jié)果，此屬性稱(chēng)為協(xié)議的健全性。在Mahadev的結(jié)果中，后者的屬性有一個(gè)轉(zhuǎn)折點(diǎn)：如果證明者不能破壞后量子加密（LWE），那么穩(wěn)健性就會(huì)保持不變。

該協(xié)議對(duì)LWE的依賴(lài)使得Mahadev的成果具有雙贏的風(fēng)格。量子計(jì)算機(jī)愚弄協(xié)議的唯一方法是量子計(jì)算世界中能有人想出如何破解LWE。但目前，LWE被廣泛認(rèn)為是后量子密碼學(xué)的主要候選者，它可能很快就會(huì)取代其他可能會(huì)被量子計(jì)算機(jī)破解的標(biāo)準(zhǔn)，被國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所采用作為其新的加密標(biāo)準(zhǔn)。破解難度可想而知。

在未來(lái)幾年內(nèi)，Mahadev的協(xié)議暫時(shí)還不太可能被部署進(jìn)真正的量子計(jì)算機(jī)中，因?yàn)閰f(xié)議所需算力太高了。根據(jù)專(zhuān)家推測(cè)，具體數(shù)字應(yīng)該至少會(huì)是5年。但現(xiàn)如今的科學(xué)發(fā)展是日新月異的，曾經(jīng)我們認(rèn)為有些難題可能需要幾十年才能解決，但它們紛紛只用一兩年就搞定了。

隨著量子計(jì)算機(jī)規(guī)模的擴(kuò)大和協(xié)議的不斷簡(jiǎn)化，相信我們會(huì)盡快看到這個(gè)理論成果落地的那一天。