隨機(jī)性是現(xiàn)代社會的重要支柱，確保了彩票和陪審團(tuán)選拔的公平性。還用于數(shù)字通信，以確保加密中使用的私鑰是秘密的和不可預(yù)測的。在組織中，實(shí)施差異隱私機(jī)器學(xué)習(xí)協(xié)議也需要隨機(jī)性。

作為確定性系統(tǒng)，傳統(tǒng)計(jì)算機(jī)無法按需創(chuàng)建真正的隨機(jī)性。因此，為了在傳統(tǒng)計(jì)算中提供真正的隨機(jī)性，我們經(jīng)常求助于從不可預(yù)測的物理源中獲取熵的專用硬件，例如，通過觀察鼠標(biāo)移動、觀察溫度波動、監(jiān)測熔巖燈的運(yùn)動，或者在極端情況下檢測宇宙輻射。這些措施笨重、難以擴(kuò)展且缺乏嚴(yán)格的保證，限制了我們驗(yàn)證其輸出是否真正隨機(jī)的能力。

讓挑戰(zhàn)雪上加霜的是，目前還沒有辦法測試一個比特序列是否真正隨機(jī)。鑒于獲取和驗(yàn)證隨機(jī)性的困難，我們只能依靠信任：我們必須相信硬件能夠生成新的隨機(jī)性。

然而，當(dāng)互不信任的各方使用隨機(jī)性來做出決策時，信任要求就會成為一個問題，例如當(dāng)競爭對手訴諸拋硬幣來解決爭端時。誰來拋硬幣？如果各方遠(yuǎn)程參與，如何驗(yàn)證是否真的拋過硬幣？

理想的解決方案是具有以下三個特征的隨機(jī)性：

1. 它來自可驗(yàn)證的可靠來源。
2. 它具有嚴(yán)格的數(shù)學(xué)保證。
3. 它不可能被惡意的對手操縱。

這種隨機(jī)性被稱為“認(rèn)證隨機(jī)性”。

驗(yàn)證數(shù)字序列是否真正來自隨機(jī)源的一種可能方法是要求提供某種簽名或證明，這些簽名或證明可能嵌入在這些數(shù)字本身中，并且不能使用可預(yù)測的來源偽造。例如，您可以要求您的隨機(jī)性提供者僅從特定概率分布中抽取數(shù)字，而使用非隨機(jī)源很難模仿這種概率分布。然后，您可以驗(yàn)證您收到的數(shù)字是否來自您選擇的分布，因此一定是真正隨機(jī)的。

事實(shí)證明，這種協(xié)議無法使用傳統(tǒng)計(jì)算機(jī)實(shí)現(xiàn)，但可以使用量子計(jì)算機(jī)實(shí)現(xiàn)。

量子計(jì)算機(jī)認(rèn)證隨機(jī)性的協(xié)議

隨機(jī)性是量子計(jì)算機(jī)的固有特性：量子比特可以處于零和一的疊加態(tài)，其測量本質(zhì)上是一個隨機(jī)過程。此外，由于量子計(jì)算機(jī)仍然受到計(jì)算復(fù)雜性和理論約束的影響，因此可以嚴(yán)格分析其輸出。這兩個特性共同提供了一種使用量子計(jì)算機(jī)生成可在數(shù)學(xué)上證明為隨機(jī)的數(shù)字的途徑。

具體而言，執(zhí)行量子程序（也稱為電路）的量子計(jì)算機(jī)產(chǎn)生的輸出本質(zhì)上是隨機(jī)的，并且對于執(zhí)行的程序來說是唯一的。雖然誠實(shí)的遠(yuǎn)程隨機(jī)性提供者可以在量子計(jì)算機(jī)上快速運(yùn)行電路以提供與量子電路相對應(yīng)的數(shù)字，但惡意服務(wù)器很難使非隨機(jī)位與提交的電路兼容。傳統(tǒng)計(jì)算機(jī)很難預(yù)測量子程序的可能輸出，因?yàn)榧词乖谧顝?qiáng)大的超級計(jì)算機(jī)上，量子程序也需要很長時間才能按經(jīng)典方式執(zhí)行。

在我們發(fā)表于《自然》雜志的最新研究中，我們在 Quantinuum、橡樹嶺國家實(shí)驗(yàn)室、阿貢國家實(shí)驗(yàn)室和德克薩斯大學(xué)奧斯汀分校的合作者的幫助下展示了這種協(xié)議的實(shí)現(xiàn)。我們將 56 量子比特 Quantinuum System Model H2 離子阱量子計(jì)算機(jī)視為不受信任的服務(wù)器，并向其逐一發(fā)送挑戰(zhàn)量子電路。

這些電路產(chǎn)生的概率分布極難用傳統(tǒng)計(jì)算機(jī)模擬：雖然我們預(yù)計(jì)量子計(jì)算機(jī)運(yùn)行每個電路大約需要兩秒鐘，但我們觀察到，世界上最大的超級計(jì)算機(jī)需要大約一百秒才能模擬同一電路的執(zhí)行。對于每個這樣的電路，我們要求 Quantinuum 在兩秒半內(nèi)向我們發(fā)送一個數(shù)字。最后，為了驗(yàn)證隨機(jī)性，我們計(jì)算收到的數(shù)字與我們開始使用的電路的相關(guān)性，并通過數(shù)學(xué)驗(yàn)證從 Quantinuum 收到的比特中至少有一部分是從最初提交的電路的基本隨機(jī)量子測量中獲得的。 

執(zhí)行此驗(yàn)證需要大量計(jì)算。在我們的演示中，為了確定電路與接收數(shù)據(jù)之間的相關(guān)性，我們使用了四臺超級計(jì)算機(jī)，其中包括 Frontier，它是實(shí)驗(yàn)時世界上最大的超級計(jì)算機(jī)，由美國能源部擁有并托管在橡樹嶺國家實(shí)驗(yàn)室。使該協(xié)議可擴(kuò)展的關(guān)鍵見解是，盡管我們只需要偶爾驗(yàn)證我們的隨機(jī)性，但惡意代理需要不斷消耗不可持續(xù)的資源來逃避檢測。

從我們的演示中，我們證實(shí)至少 71,313 位熵可以抵御比世界上最大的超級計(jì)算機(jī)強(qiáng)大至少四倍的實(shí)驗(yàn)性惡意對手。至關(guān)重要的是，即使量子計(jì)算機(jī)有惡意行為、受到第三方攻擊或被冒充，我們也能保證隨機(jī)性。因此，我們的協(xié)議產(chǎn)生的隨機(jī)性不需要信任任何外部實(shí)體。

這種可驗(yàn)證的量子隨機(jī)性是由量子計(jì)算機(jī)實(shí)現(xiàn)的，量子計(jì)算機(jī)能夠以比傳統(tǒng)計(jì)算機(jī)快得多的速度運(yùn)行程序。由于其簡單性，從量子電路中采樣的任務(wù)已成為展示量子計(jì)算機(jī)能力的基準(zhǔn)，并在實(shí)驗(yàn)室的許多實(shí)驗(yàn)中重復(fù)使用。我們的工作是第一個利用這種采樣任務(wù)來實(shí)現(xiàn)潛在有用的加密原語的工作。