基于囚禁离子量子处理器的认证随机数生成

摘要

尽管量子计算机在执行许多实际重要的任务方面，超越了经典计算机的能力1,2，但实现这一潜力仍然是一个挑战。一个例子是使用一个不受信任的远程设备生成随机比特，这些比特可以被认证为包含一定量的熵3。认证随机数生成有许多应用，但仅靠经典计算是不可能实现的。在此，我们展示了使用 56-qubit 的 Quantinuum H2-1 囚禁离子量子计算机，通过互联网访问生成可认证的随机比特。我们的协议利用了最近随机电路抽样演示的经典硬度4,5：客户端使用一个小的随机数种子生成量子“挑战”电路，将它们发送到一个不受信任的量子服务器执行，并验证服务器的结果。我们分析了我们的协议针对一类受限的、现实的近期对手的安全性。在使用经典验证方法，通过多个超级计算机测量到的持续性能为每秒 1.1 × 1018 次浮点运算，我们在这种受限的对手和附加假设下，认证了 71,313 比特的熵。我们的结果展示了朝着当今量子计算机的实际应用迈出的一步。

其他人正在浏览的相似内容

Verifiable measurement-based quantum random sampling with trapped ions 文章 开放获取 2025年1月2日

A simple low-latency real-time certifiable quantum random number generator 文章 开放获取 2021年2月24日

Interactive cryptographic proofs of quantumness using mid-circuit measurements 文章 2023年8月3日

主要内容

近年来，许多理论结果表明，量子计算机有潜力解决经典技术无法触及的各种问题。主要的例子包括分解大整数6、隐式求解指数大小的线性方程组7、优化难解问题8、学习某些函数9以及模拟大型量子多体系统10。然而，考虑到诸如量子纠错开销和门速度等因素，已知量子算法对这些问题的资源需求，远远超出了近期量子设备的范围，包括许多建议的容错架构。因此，目前还不清楚近期可用的设备是否能使实际应用受益11。

从最初的“量子霸权”演示之一开始5，一些团队已经使用随机电路抽样 (RCS) 作为一项任务的例子，这项任务可以在当今的量子计算机上更快、更低能量成本地执行，而经典方法是无法实现的4,12,13,14。然而，尽管实验进展迅速，但迄今为止，基于门控的量子计算机执行的实际有用任务的超越经典演示仍然未知。

随机数生成是一项很自然的超越经典演示的任务，因为随机性是量子力学固有的，并且在许多应用中都很重要，从信息安全到确保陪审团选择等过程的公平性15,16,17。对于从第三方提供商（如硬件安全模块）接收随机数的任何客户端来说，主要的挑战是验证接收到的比特是否是真正随机且新生成的。虽然并非随机数的每一次使用都需要认证随机数，但新鲜性要求在彩票和电子游戏等应用中尤为重要，在这些应用中，多个参与者（他们可能互相信任，也可能不互相信任）需要确保公开分发的随机数是按需生成的。此外，认证随机数可用于验证不诚实方的立场18,19,20。

存在基于违反贝尔不等式来认证随机数的协议15,21,22,23,24。然而，这些协议通常要求底层贝尔测试是无漏洞的，这对于客户端来说可能很难执行，因为量子设备由第三方提供商控制。因此，这种方法需要客户端信任第三方量子设备提供商来忠实地执行贝尔测试。

另一种方法是，参考文献 3 提出了一个认证随机数协议，该协议将 RCS 与经典超级计算机上的“验证”结合起来3,25。这种类型的协议允许经典客户端仅使用对不受信任的量子服务器的远程访问来验证随机数。经典客户端伪随机地生成 n -qubit 的挑战电路，并将它们发送到量子服务器，要求量子服务器在短时间内返回从这些电路的输出分布中抽取的长度为 n 的比特串（图 1a,c）。选择电路的方式是，没有现实的对抗服务器可以在短响应时间内以经典的方式模拟它们。然后，使用一小部分电路来计算交叉熵基准 (XEB) 分数26（图 1b），它反映了服务器返回的样本与提交电路的理想输出分布的匹配程度。广泛的复杂性理论证据表明，XEB 很难以经典的方式“欺骗”27,28。因此，高 XEB 分数，加上短响应时间，允许客户端证明服务器必须使用量子计算机来生成其响应，从而以高概率保证一定量的熵。我们的分析量化了不受信任的服务器（可能充当对手）必须提供多少熵才能在短时间内获得给定的 XEB 分数。

图 1：协议概述。

a，理想化协议。客户端将 M 个随机电路 ({{C}i}{i∈[M]}) 串行提交到随机数服务器，并期望返回比特串 ({{x}i}{i∈[M]})，每个比特串都在时间 t QC 内返回。b，电路-比特串对的一个子集用于计算 XEB 分数。XEB 分数具有分布（仅用于定性说明的底部图），对应于诚实的服务器或执行低保真经典模拟的对抗服务器。对于虚线指示的任何 XEB 目标，诚实的服务器可能无法达到高于此阈值的分数，概率为 P fail。c，挑战电路的图示，由 U ZZ 门的层夹在所有量子比特上的随机 SU(2) 门的层之间组成。双量子比特门的排列是通过随机 n 节点图上的边着色（右）获得的。d，在我们协议中实现的客户端-服务器交互。在设备就绪检查（“预检查”）之后，客户端提交一批 2 b 个电路，并期望在截止持续时间 T b,cutoff 内返回与该批次对应的所有样本。请注意，图中仅说明了一个执行时间为 T batch 的批次。客户端继续执行协议，直到成功执行总共 M 个电路。

参考文献 3 中提出的协议为服务器从同一电路返回多个样本，提供了 Ω(n) 比特熵的复杂性理论保证。此协议最适合量子计算架构，该架构的开销使得在加载一次电路后，多次采样该电路更可取。在实践中，多次采样电路的经典模拟成本与仅采样一次的成本相当29。此外，本工作使用的基于囚禁离子的量子计算机被配置为具有每个电路的最小开销，因此与多次采样一个电路相比，执行多个单次电路不会给每个电路引入实质性的时间惩罚。这两个观察结果共同促使我们通过要求服务器仅返回每个电路的一个样本来加强协议的安全性。为此，在补充信息部分 I 中，我们将复杂性理论分析扩展到每个电路一个样本的这种修改后的设置，保证了 Ω(n) 比特的熵。

在这项工作中，我们报告了基于 RCS 的认证随机数协议的实验演示。我们的主要贡献如下。首先，受参考文献 3 的启发，我们提出了一种适用于近期量子服务器的修改后的基于 RCS 的认证随机数协议。其次，我们证明了我们的实现在一类现实的有限大小的对手面前的安全性。第三，我们使用高保真量子计算机和百万兆级经典计算来实验性地实现此提议的协议，从而突破了量子和经典计算能力的界限。通过将高保真 Quantinuum H2-1 量子处理器与百万兆级验证相结合，我们展示了基于门控的数字量子计算机的有用且超越经典的应用。

在我们提出的协议中（如图 1d 所示，并在 方法 中详细描述），客户端伪随机地生成足够多的 n -qubit 量子电路，然后将它们分批发送，每批 2 b 个电路，其中 b 是一个整数。在提交一批之后，客户端等待在 T b,cutoff 秒内返回 2 b 个长度为 n 的比特串。批次截止时间可防止协议停顿，并且根据初步实验预先固定为一个值，该值旨在最大化可认证的熵量，同时确保每个电路的平均响应时间保持足够低，以排除经典模拟作为服务器生成响应的可行策略。如果某个批次超时或者报告了失败状态，则会取消该批次中的所有未完成作业，并且会丢弃从该批次接收到的所有比特串。因此，失败批次的结果不包括在计算 XEB 分数或熵提取中。不断提交批次，直到收集到 M 个有效样本。成功批次的累积响应时间给出了总时间 T tot 和每个样本的平均时间 t QC = T tot/M。随后，客户端计算从 M 个电路-样本对中随机抽取的、大小为 m 的子集上的 XEB 分数：

$${{\rm{XEB}}}{{\rm{test}}}=\frac{{2}^{n}}{m}\sum {i\in {\mathcal{V}}}{P}{{C}{i}}({x}_{i})-1,$$ (1)

其中 (\({\mathcal{V}}\) ) 是大小为 m 的随机子集的索引集，_P_C(x) = |⟨ x |_C_ |0⟩|2 是从执行电路 C 的理想量子计算机测量比特串 x 的概率。如果比特串 x i 是从足够深的随机电路 C i 的输出分布中完美抽取的，则 XEB 分数预计会集中在 1 附近。相比之下，如果 x i 是从与 C i 引起的分布不相关的分布中抽取的，则 XEB 分数预计会集中在 0 附近。客户端根据两个标准决定是否接受收到的样本作为随机比特。首先，每个样本的平均时间必须低于阈值 t threshold，该阈值选择为排除高保真经典模拟。此时间可能低于 T b,cutoff，因为从可提取熵的角度来看，只要平均响应时间保持较低，就接受一些响应时间略大于 t threshold 的样本是有利的。其次，(({\mathcal{V}}\) ) 上的 XEB 分数必须大于阈值 χ ∈ [0, 1]。所有 t threshold、χ 和 T b,cutoff 都在协议执行之前确定，例如，基于初步硬件实验，目的是在协议结束时以高概率认证一定数量的固定熵。总之，如果满足以下条件，则协议成功：

$${t}{{\rm{QC}}}={T}{{\rm{tot}}}/M\le {t}{{\rm{threshold}}}\quad ,\text{and},,,{{\rm{XEB}}}{{\rm{test}}}\ge \chi ,$$ (2)

否则中止。

我们协议的安全性依赖于一个核心假设，即对于我们考虑的伪随机电路族，不存在可以欺骗协议中使用的 XEB 测试的实用经典算法。我们通过对一个受限但现实的对抗服务器进行建模来分析协议安全性，我们认为这是最相关的：对于接收到的每个电路，对手要么从量子计算机中诚实地采样输出，要么执行经典模拟（图 2a）。由于只有前者包含熵，因此对手会尝试以最少的量子样本达到阈值 XEB 分数，以通过 XEB 测试，同时返回尽可能少的熵。对于我们的协议，我们假设对手具有完美保真度的量子计算机，这使得对手可以以经典的方式欺骗最大数量的比特串。我们进一步假设对手的经典计算能力受到每秒固定数量的浮点运算 (FLOPS) (({\mathcal{A}}\) ) 的限制，该数量可以相对于世界上最强大的超级计算机进行测量（在实验时，为 Frontier 超级计算机；参见 https://www.top500.org/lists/top500/2024/06/），并且对手拥有与客户端相同的方法来模拟电路。请注意，拥有比预期更强大的用于模拟电路的经典方法的对手可以等效地建模为具有相同经典方法和更大计算能力的对手。我们注意到，由于我们分析的对手仅允许使用一组受限的策略，因此随后的数学结果仅在此有限的设置中成立，并以补充信息部分 IIIC 中进一步详述的一些其他假设为条件。据我们所知，此处考虑的受限的经典和量子对手策略集对应于当前最先进的技术。我们将更广泛的对手类别的纳入留给未来的分析。

图 2：对手模型和协议安全性。

a，在本工作中考虑的对抗模型中，使用完美保真度的量子计算机获得 Q 个样本，并使用经典模拟获得 M − Q 个样本。b，对于重复实验，保真度为 ϕ = 0.3 的诚实服务器在针对比 Frontier 功能强大四倍的对手证明 Q min 量子样本（以及相应的阈值 χ）时，出现失败（伴随健全性 ε sou）的概率，其中协议参数设置为表 1 中的值。c，在我们的实验中，来自总共 984 个成功批次的每个成功样本的批次时间分布。垂直虚线指示每个样本的平均时间。

客户端需要确保电路难以在时间 t threshold 内模拟。否则，服务器可以使用其经典超级计算机以高保真度确定性地模拟电路，并生成容易通过方程 (2) 中的测试的样本。对于我们考虑的电路族和大小，张量网络收缩是用于有限保真度和精确模拟的最佳已知方法4，以及采样。如果一个电路的验证（精确模拟）成本为 (\({\mathcal{B}}\) ) FLOPS，则对手可以使用张量网络的部分收缩将每个电路模拟到目标保真度为 (\({\mathcal{A}}\cdot {t}_{{\rm{threshold}}}/{\mathcal{B}}\) )，模拟成本和模拟保真度线性相关30。仅当参数的选择使得诚实服务器的保真度 ϕ 满足以下条件时，协议才成功：

$$\phi \gg {\mathcal{A}}\cdot {t}_{{\rm{threshold}}}/{\mathcal{B}}.$$ (3)

此条件要求诚实服务器的保真度与主要执行经典模拟的对手可实现的保真度之间存在差距。如果满足此条件，则诚实服务器的 XEB 分数将具有概率分布，该概率分布的平均值高于对手的 XEB 的概率分布（在图 1b 中定性地显示），从而允许客户端区分两者。

认证之后（即，如果方程 (2) 中的测试通过），客户端使用随机数提取器来处理 M 个样本。一个理想的认证随机数协议要么中止，从而导致“中止状态”，要么成功，从而导致与任何边信息不相关的均匀分布的比特串。将协议视为作用于由服务器和客户端组成的某个初始状态的通道，如果对于任何初始状态，最终结果都 ε sou-接近（就迹距离而言）理想输出，则称端到端协议是 ε sou-健全的：中止状态和最大混合状态的混合（有关健全性的严格定义，请参见补充信息部分 IIIA）。

客户端从接收到的样本中成功执行协议后可以提取的熵，取决于其对响应时间（t threshold）和 XEB 分数（χ）的阈值有多严格。为了客户端的利益，应尽可能严格地设置这些阈值，以迫使假设的对手从量子计算机中抽取更多样本，同时仍然允许诚实的服务器以高概率成功。由于阈值双方都知道，因此对手的策略是尽量减少量子计算机的使用，同时确保协议不会中止。根据协议阈值，客户端可以确定量子样本的数量 Q min，这样如果对手从量子计算机返回的样本少于 Q min，则协议会以较大的概率 1 - ε accept 中止（有关详细信息，请参见补充信息部分 IVF）。这个关于 Q min 的下限可用于推导接收到的样本的最小平滑最小熵。请注意，信息源的平滑最小熵表征了可以从该源中提取的随机比特数。特别是，我们设计了一个 ε sou-健全的协议，该协议提供对平滑最小熵 (\({H}{\min }^{{\varepsilon }{{\rm{s}}}}\) ) 的下限（在补充信息部分 IIID 中定义），平滑度参数为 ε s = ε sou/4，并且 ε accept = ε sou。本文中的结果以健全性参数 ε sou 和平滑最小熵 (\({H}{\min }^{{\varepsilon }{{\rm{s}}}}\) ) 表示。

较小的 ε sou 通过使对手更难以通过具有较小 Q min 的 XEB 测试，从而提供更强的安全保证。这可以通过选择更高的阈值 χ 来实现。然而，更高的阈值也使得诚实的服务器更有可能无法通过 XEB 测试，这意味着无法证明诚实的服务器已经产生了目标的可提取熵量。请注意，这并不一定意味着诚实的服务器提供的样本不包含熵，而只是它们未能满足方程式 (2) 的标准，因此协议中止。在实践中，希望确保诚实的服务器仅以较低的失败概率 P fail 失败。为此，我们可以计算对应于任何可接受的 P fail 的阈值 χ(P fail)。然后，此阈值以及 t threshold 允许我们确定目标健全性 ε sou 的 Q min（补充信息部分 IIID）。图 2b 显示了在不同的 P fail 和 ε sou 下可实现的 Q min，显示了在固定的实验配置和对手的经典计算能力（\(\phi ,{t}_{{\rm{QC}}},M,m,{\mathcal{B}}\) 和 (\({\mathcal{A}}\) )）下，这三个量之间的权衡。

我们使用通过互联网远程访问的 Quantinuum H2-1 囚禁离子量子处理器来演示我们的协议。实验参数在表 1 中提供。挑战电路（如图 1c 所示，有关选择电路所涉及的考虑因素，请参见补充信息部分 IVC）具有 10 层纠缠 U ZZ 门的固定排列，每个门都夹在所有量子比特上伪随机生成的 S U(2) 门之间。双量子比特门的排列是通过对随机 n 节点图进行边着色获得的。初步镜像基准实验，以及基于组件操作的测量保真度的门计数参数，使我们能够估计诚实服务器的保真度4。在实验时，预计 H2-1 量子处理器在深度为 10 的电路上将达到 ϕ ≳ 0.3 或更高的保真度（在本实验的数据收集之后，对 H2-1 设备进行了多次改进，略微提高了参考文献 4 中的保真度估计）。同样，相同的初步实验也使我们能够预计每个样本的平均时间约为 2.1 秒，并且时间分布较长，一直延伸到略低于 2.5 秒，如图 2c 中完整实验中也看到的。因此，可以通过阈值 t threshold = 2.2 s 和 χ = 0.3 实现合理的 (P fail = 50%) 协议成功率。为了说明的目的，我们根据这些选择来描述实验（在实践中，人们可能希望通过将 χ 设置为略低于预期值来降低 P fail）。批次截止时间设置为 T b,cutoff = (2 b) × 2.5 s，预计平均时间在 t threshold = 2.2 s 和 2.5 s 之间的批次相对较小的预期比例将为收到的样本贡献额外的熵，同时不太可能将每个样本的平均时间从预期的 2.1 s 增加到超过 2.2 s 的阈值。

表 1 实验参数摘要

所考虑的电路族的模拟成本为 (\({\mathcal{B}}=90\times 1{0}^{18}\) ) FLOPS 在能源部的 Frontier 超级计算机上31，据我们所知，这是撰写本文时世界上最强大的超级计算机（https://www.top500.org/lists/top500/2024/06/）。在详细估计了 Frontier 上的运行时之后，我们确定在使用整个超级计算机且数值效率为 45% 时，每个电路的精确模拟时间为 100.3 秒，其中数值效率是实际算法运行时与其理论预期之间的比率（有关电路模拟成本的详细信息，请参见补充信息部分 IVA）。

在我们的实验中，我们使用两种批次大小：b = 15 和 b = 20；大多数批次的大小为 b = 15。总共，我们提交了 1,993 个批次，共计 60,952 个电路。从这些电路中，我们从 984 个成功批次中获得了总共 M = 30,010 个有效样本。成功样本的累积设备时间为 64,652 秒，得出每个样本的平均时间 t QC = 2.154 秒，包括所有开销（如通信时间）。图 2c 显示了每个成功样本的 t QC 分布。

在这项工作中，客户端的经典计算预算分布在配备图形处理单元 (GPU) 的 Frontier31、Summit32、Perlmutter33 和 Polaris34 超级计算机上，这些超级计算机特别适合量子电路模拟。在这四台超级计算机中，Frontier 和 Summit 在验证期间以全机规模使用。我们测得的持续峰值性能分别为 897 petaFLOPS 和 228 petaFLOPS（对应于 45% 和 59% 的数值效率），实现了 1.1 exaFLOPS 的组合性能（参见补充信息部分 IVE）。我们计算了 m = 1,522 个电路-样本对的 XEB 分数，获得 XEBtest = 0.32。完整的实验参数集在表 1 中列出。

测得的 XEBtest = 0.32 保真度和每个样本测得的时间 t QC = 2.154 s 通过了由 χ = 0.3 和 t threshold = 2.2 s 指定的协议。对于健全性参数 ε sou 和平滑度参数 ε s = ε sou/4 的选择，协议阈值确定了量子样本的数量 Q 和平滑最小熵 (\({H}{\min }^{{\varepsilon }{{\rm{s}}}}\) )，该最小熵通过此协议的成功，针对经典资源受 (\({\mathcal{A}}\) ) 限制的对手得到保证。在表 2 中，我们报告了在 (\({\mathcal{A}}\) ) 和 ε sou 的范围内，平滑最小熵率 (\({H}{\min }^{{\varepsilon }{{\rm{s}}}}/(56\times M)\) )（有关此计算的详细信息，请参见补充信息部分 IVF）。这是为了表明，如果我们想通过增加对手的假设经典计算能力或通过降低健全性参数来提高协议的安全性，则我们可以获得的熵量必须减少。特别是，我们强调在 ε sou = 10−6 时，我们有 Q min = 1,297，对应于 (\({H}{\min }^{{\varepsilon }{{\rm{s}}}}=\mathrm{71,313}\) )，以对抗比 Frontier 功能强大四倍的对手（在之前讨论的假设下）。

表 2 在变化的 ε sou 和 (\(\boldsymbol{\mathcal{A}}\) ) 下的平滑最小熵率

我们将 56 × 30,010 原始比特馈送到 Toeplitz 随机数提取器35，并提取 71,273 比特（有关提取和可提取熵的确定，请参见补充信息部分 IVF）。我们注意到，Toeplitz 提取器是一种“强”种子提取器，其输出独立于种子。对于随机数的私有使用，其中未显示提取的比特，可以重用提取器种子。我们将提取器中使用的种子附加到协议输出，并且不将种子计为我们协议“消耗”的随机数。因此，用于为伪随机生成器播种的总输入随机数仅为 32 比特，并且我们的协议实现了认证随机数扩展。我们进一步注意到，可以使用其他提取器，这些提取器可能消耗更少的种子，但具有不同的安全保证。

未来的实验有望提高设备保真度（更高的 ϕ）和