利用量子计算实现认证随机性

随机性是现代社会的重要支柱，确保了彩票和陪审团选拔的公平性。还用于数字通信，以确保加密中使用的私钥是秘密的和不可预测的。在组织中，实施差异隐私机器学习协议也需要随机性。

作为确定性系统，传统计算机无法按需创建真正的随机性。因此，为了在传统计算中提供真正的随机性，我们经常求助于从不可预测的物理源中获取熵的专用硬件，例如，通过观察鼠标移动、观察温度波动、监测熔岩灯的运动，或者在极端情况下检测宇宙辐射。这些措施笨重、难以扩展且缺乏严格的保证，限制了我们验证其输出是否真正随机的能力。

让挑战雪上加霜的是，目前还没有办法测试一个比特序列是否真正随机。鉴于获取和验证随机性的困难，我们只能依靠信任：我们必须相信硬件能够生成新的随机性。

然而，当互不信任的各方使用随机性来做出决策时，信任要求就会成为一个问题，例如当竞争对手诉诸抛硬币来解决争端时。谁来抛硬币？如果各方远程参与，如何验证是否真的抛过硬币？

理想的解决方案是具有以下三个特征的随机性：

它来自可验证的可靠来源。
它具有严格的数学保证。
它不可能被恶意的对手操纵。

这种随机性被称为“认证随机性”。

验证数字序列是否真正来自随机源的一种可能方法是要求提供某种签名或证明，这些签名或证明可能嵌入在这些数字本身中，并且不能使用可预测的来源伪造。例如，您可以要求您的随机性提供者仅从特定概率分布中抽取数字，而使用非随机源很难模仿这种概率分布。然后，您可以验证您收到的数字是否来自您选择的分布，因此一定是真正随机的。

事实证明，这种协议无法使用传统计算机实现，但可以使用量子计算机实现。

量子计算机认证随机性的协议

随机性是量子计算机的固有特性：量子比特可以处于零和一的叠加态，其测量本质上是一个随机过程。此外，由于量子计算机仍然受到计算复杂性和理论约束的影响，因此可以严格分析其输出。这两个特性共同提供了一种使用量子计算机生成可在数学上证明为随机的数字的途径。

具体而言，执行量子程序（也称为电路）的量子计算机产生的输出本质上是随机的，并且对于执行的程序来说是唯一的。虽然诚实的远程随机性提供者可以在量子计算机上快速运行电路以提供与量子电路相对应的数字，但恶意服务器很难使非随机位与提交的电路兼容。传统计算机很难预测量子程序的可能输出，因为即使在最强大的超级计算机上，量子程序也需要很长时间才能按经典方式执行。

在我们发表于《自然》杂志的最新研究中，我们在 Quantinuum、橡树岭国家实验室、阿贡国家实验室和德克萨斯大学奥斯汀分校的合作者的帮助下展示了这种协议的实现。我们将 56 量子比特 Quantinuum System Model H2 离子阱量子计算机视为不受信任的服务器，并向其逐一发送挑战量子电路。

这些电路产生的概率分布极难用传统计算机模拟：虽然我们预计量子计算机运行每个电路大约需要两秒钟，但我们观察到，世界上最大的超级计算机需要大约一百秒才能模拟同一电路的执行。对于每个这样的电路，我们要求 Quantinuum 在两秒半内向我们发送一个数字。最后，为了验证随机性，我们计算收到的数字与我们开始使用的电路的相关性，并通过数学验证从 Quantinuum 收到的比特中至少有一部分是从最初提交的电路的基本随机量子测量中获得的。

执行此验证需要大量计算。在我们的演示中，为了确定电路与接收数据之间的相关性，我们使用了四台超级计算机，其中包括 Frontier，它是实验时世界上最大的超级计算机，由美国能源部拥有并托管在橡树岭国家实验室。使该协议可扩展的关键见解是，尽管我们只需要偶尔验证我们的随机性，但恶意代理需要不断消耗不可持续的资源来逃避检测。

从我们的演示中，我们证实至少 71,313 位熵可以抵御比世界上最大的超级计算机强大至少四倍的实验性恶意对手。至关重要的是，即使量子计算机有恶意行为、受到第三方攻击或被冒充，我们也能保证随机性。因此，我们的协议产生的随机性不需要信任任何外部实体。

这种可验证的量子随机性是由量子计算机实现的，量子计算机能够以比传统计算机快得多的速度运行程序。由于其简单性，从量子电路中采样的任务已成为展示量子计算机能力的基准，并在实验室的许多实验中重复使用。我们的工作是第一个利用这种采样任务来实现潜在有用的加密原语的工作。