A Quantum Algorithm for Random Number Generation

本文提出了一种用于随机数生成的量子算法，该算法通过整合量子傅里叶变换、受控相位旋转和 Grover 扩散算子，实现了相对于经典马尔可夫链混合过程的可证明二次加速，并在量子比特和高维量子态（qudit）硬件上均展示了更高的效率。

要点

核心思想：更快速地洗牌宇宙

想象你有一副全新的扑克牌，从 A 到 K 整齐排列。你想通过洗牌让它们变得完全随机。在现实世界中，如果你使用标准的“顶端到随机”（将最上面的牌放到牌堆中的任意位置）洗牌法，你需要进行大约 $n \log n$ 次（其中 $n$ 是牌的数量）才能让牌堆真正混合均匀。

本文提出了一种量子算法，可以完成同样的工作，但速度要快得多。它不再是一张一张地洗牌，而是利用量子力学的奇特规则来“混合”整个牌堆。作者声称，这种量子方法可以实现与经典计算机相同的随机程度，而所需时间仅为前者的平方根左右。

三大魔法工具

研究人员利用三个特定的工具构建了一台“量子混合机”。你可以把它们想象成一个协同工作的魔术师团队：

1. 量子傅里叶变换（翻译官）：

   • 类比： 想象这副扑克牌是一首复杂的歌曲。经典方式理解这首歌的方法是逐个音符去聆听。量子傅里叶变换就像一只神奇的耳朵，能瞬间将整首歌翻译成其纯粹的音乐频率列表。
   • 作用： 它改变了量子计算机的状态，使得“混合”过程更容易计算。它将一个混乱的问题转化成了一份整洁的数字列表。

2. 受控相位旋转（调音师）：

   • 类比： 一旦歌曲被翻译成频率，这个工具就像一名音响工程师。它会根据扑克牌在洗牌过程中应该如何移动，来微调特定音符的音高（相位）。
   • 作用： 它将“顶端到随机”洗牌的规则编码进这些频率微调中。它能在所有可能性上同时模拟一次洗牌步骤。

3. Grover 扩散算子（放大器）：

   • 类比： 这是全场的明星。想象一个房间里挤满了人在低声细语。大多数人都在胡言乱语，但有几个人正在低声诉说着“完美混合”的秘密。放大器会倾听所有人的声音，找到平均音量，然后执行相反的操作：如果有人声音太小，它就让其变大；如果有人声音太大，它就让其变小。
   • 作用： 它将量子状态推向“完美随机”的平均值。通过重复这一过程，它迫使系统比自然等待发生要快得多地进入随机状态。

两个版本：量子比特（Qubits） vs 量子多位元（Qudits）

论文测试了构建这台机器的两种不同方式：

• 量子比特版本（二进制牌堆）：
  这使用的是标准的量子比特（0 和 1）。如果你有 8 张牌，你需要 3 个量子比特。论文表明，对于这个版本，混合所需的时间从漫长的等待缩短到了一个更短的时间（即“二次加速”）。
• 量子多位元版本（多面骰子）：
  这是更高级的版本。这些“多位元”（qudits）不仅仅是 0 或 1，它们可以是像 0 到 9 这样的数字（就像一个 10 面骰子）。
  • 类比： 想象尝试混合一副 100 张牌的牌堆。使用标准量子比特，你需要 7 个比特来表示 100 个状态（因为 $2^7 = 128$）。使用多位元，你可以直接使用两个“10 面骰子”（$10 \times 10 = 100$）。
  • 优势： 因为多位元能自然地契合牌堆的大小（就像用 10 面骰子对应 100 张牌的牌堆），所以这台机器更加高效，且需要更少的步骤来混合牌。

实际发现（实验）

作者不仅编写了数学公式，还在真实的量子计算机（具体为 IBM 的 ibm_marrakesh 处理器）上运行了代码。

• 经典测试： 他们在 25 张牌的牌堆上模拟了标准的洗牌过程。大约需要 7 次洗牌才能让牌堆达到“足够随机”（与完美随机的偏差小于 1%）。
• 量子比特测试： 他们在 3 个量子比特（8 张牌的牌堆）上运行了量子算法。他们观察到随机度在提升，但并不是直线下降。相反，它像波浪一样起伏（一种“Grover 振荡”）。这是量子力学的一个独特迹象：系统会超过完美的混合状态，然后自我修正。他们发现第 16 层是“甜点位”，此时随机度最高。
• 量子多位元测试： 他们在一个 100 状态的系统中运行了算法（使用两个 10 面多位元）。这是一个巨大的惊喜。仅需一个步骤，系统就从完全有序跳跃到了几乎完美的随机状态。到第 20 步时，效果甚至更好。

总结

论文声称已经证明了量子计算机可以比经典计算机更快地混合随机数。

• 经典： 需要 $n \log n$ 步。
• 量子： 大约需要 $\sqrt{n \log n}$ 步。

他们通过展示在真实硬件上，他们的量子算法比经典模拟所需的步骤更少，从而达到了高度随机的状态，验证了这一点。他们还证明了使用“多位元”（多层量子系统）处理大型牌堆比使用标准二进制量子比特更有效率。

重要提示： 本文严格侧重于洗牌的算法和数学。它并不声称这目前已准备好用于赌场、密码学或人工智能。这是一个证明，即这种加速在理论上是可能的，并且在小规模实验中得到了观察。

技术摘要

技术摘要：一种用于随机数生成的量子算法

问题陈述
本文探讨了一个算法挑战，即如何加速随机过程向均匀分布的混合（mixing），特别是在随机数生成（RNG）的背景下。虽然经典的伪随机数生成器（PRNG）已从线性同余法演进到如 PCG 和 Xoshiro 等复杂架构，但它们本质上仍是确定性的。真随机数生成器（TRNG）依赖于物理熵，但面临吞吐量受限的问题。作者关注一个特定的理论空白：量子计算是否能超越经典极限，加速马尔可夫链的“混合时间”（mixing time）——即分布变得在统计上与均匀分布不可区分所需的步数。本研究使用“顶置随机”（top-to-random）纸牌洗牌作为该混合过程的典型模型，在经典条件下，对于 $n$ 张牌的牌组，该过程需要 $O(n \log n)$ 次操作。

方法论
所提出的解决方案是一个统一的量子电路，它集成了三种不同的量子原语，用以模拟并加速顶置随机洗牌的马尔可夫转移算子：

1. 量子傅里叶变换 (QFT)： 算法初始化一个代表牌组状态的寄存器并应用 QFT。它将状态从计算基映射到傅里叶基，在此基下，马尔可夫转移算子是对角化的。这允许同时处理概率分布的所有频率分量，利用了对称群的 Diaconis–Shahshahani 傅里叶分析。
2. 受控相位旋转： 在傅里叶域中，算法应用了一层受控相位旋转。这些旋转编码了顶置随机洗牌转移矩阵的特征值谱。通过设定特定的相位角 ($\theta_{ij} = 2\pi / 2^{j-i+1}$)，该电路以酉变换的方式模拟一个马尔可夫转移步骤，近似于概率分布与洗牌算子的卷积。
3. Grover 扩散算子： 核心加速机制是应用 Grover 扩散算子 ($D = 2|s\rangle\langle s| - I$)，其中 $|s\rangle$ 是均匀叠加态。该算子围绕其均值反射概率振幅。与依赖重复随机转移的经典混合不同，扩散算子执行振幅放大，从而更迅速地驱动状态趋向于均匀分布。

作者提出了两个变体：

• 量子比特变体 (Qubit Variant)： 在 $n$ 个量子比特上运行，编码 $2^n$ 个状态。混合时间从经典的 $O(n \log n)$ 降低至 $O(\sqrt{n} \log n)$ 次迭代。
• 量子多比特变体 (Qudit Variant)： 将方法推广到 $m$ 个局部维度为 $d$ 的量子多比特（其中 $N = d^m$）。该表述将每个层级的 QFT 电路深度从 $O(\log^2 N)$ 降低到 $O(\log^2_d N)$ 个门，并实现了 $O(\sqrt{\log_d N})$ 次迭代的混合时间。

核心贡献

• 可证明的二次加速： 本文确立了在马尔可夫链混合方面相对于经典算法的理论二次加速。对于规模为 $N$ 的系统，量子算法需要 $O(\sqrt{N})$（或对于量子多比特为 $O(\sqrt{\log_d N})$）次迭代，而经典界限为 $O(N \log N)$（或对于 $n$ 张牌为 $O(n \log n)$）。
• 算法构建： 作者提供了一个详细的量子电路构建方案，通过振幅放大而非等待特定物理事件（如底部的牌升至顶部）来实现“强均匀停止时间”（strong uniform stopping time，源自 Aldous 和 Diaconis 的概念）。
• 量子多比特推广： 该工作将算法扩展到量子多比特（qudits），展示了高维局部系统如何降低电路深度并提高特定状态空间大小（例如使用基数为 10 的量子多比特处理 $N=100$）的效率。
• 输出提取： 文中详细介绍了从量子输出中提取无偏随机数的方法，利用冯·诺依曼去偏（von Neumann unbiasing）和拒绝采样来处理残余的非均匀性和范围限制。

实验结果
作者在 IBM 超导硬件（具体为 ibm_marrakesh）上验证了量子比特和量子多比特变体：

• 经典基准： 对 25 张牌牌组进行的 Gilbert–Shannon–Reeds (GSR) 乱序洗牌模拟显示，有效混合（全变差距离 TV distance $< 0.01$）需要 7 次迭代。
• 量子比特实验 ($n=3, N=8$)： 量子电路表现出非单调的“Grover 振荡”现象，这是全变差（TV）距离的变化，也是酉量子动力学的特征信号。在第 $k=16$ 次迭代时达到了最小 TV 距离 $0.0155$，这与预测的混合时间一致。
• 量子多比特实验 ($d=10, m=2, N=100$)： 量子多比特电路展示了快速转换，在仅经过一个混合层（$k=1$）后就达到了 $0.0372$ 的 TV 距离，并在 $k=20$ 时达到最小值 $0.0101$。观察到的非 2 的幂次维度的拒绝率与理论预测在 1% 以内吻合。

意义与主张
本文声称提出了第一个针对特定马尔可夫链混合问题（通过顶置随机洗牌模型）实现可证明加速的量子算法。作者强调，这并非要取代物理硬件 TRNG 或在原始吞吐量上与经典 PRNG 竞争。其意义在于算法层面的加速，即加速混合过程本身。

作者认为，Grover 扩散算子充当了 Aldous–Diaconis 强均匀停止时间的量子模拟，将经典的截断时间（cutoff）从 $n \log n$ 步压缩至约 $\pi \sqrt{n}/8$ 步。在含噪声中等规模量子（NISQ）硬件上的实验结果为这一机制提供了证据，特别是通过 TV 距离剖面中的“Grover 振荡”突出了这一特征，这种振荡是满足细致平衡（detailed balance）的经典随机过程无法复制的纯粹量子混合的独特签名。该工作表明，随着系统规模的扩大，量子在混合时间方面的优势将变得愈发显著。