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

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

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

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

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

1. 它來自可驗證的可靠來源。
2. 它具有嚴格的數學保證。
3. 它不可能被惡意的對手操縱。

這種隨機性被稱為“認證隨機性”。

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

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

量子計算機認證隨機性的協(xié)議

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

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

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

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

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

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

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