在量子世界中，不确定性是基本规则。一个粒子可以同时存在于多种量子状态，直到被观测的瞬间才“选择”一个确定的结果。这种内禀的随机性不仅是量子力学的基础，更是量子计算和现代密码学领域需要的资源。然而，完美地生成和操控量子随机性一直是一项成本高昂且极具挑战的任务。但现在，一项突破性研究证明了我们可以用一种更为“经济”的方式，来可靠地模拟这种强大的随机力量。
来自美国加州大学伯克利分校西蒙斯计算理论研究所的博士后研究员 Fermi Ma 和谷歌量子人工智能的高级研究科学家的黄信元（Hsin-Yuan Huang）在预印本网站arXiv上发布了题为《如何构建随机酉矩阵》（How to Construct Random Unitaries）的论文。
这项工作正面回应并解决了量子信息科学领域一个长期悬而未决的核心问题：是否存在可以被高效构建和运行的量子电路，其行为与真正完全随机的量子演化（即 Harr 随机酉变换，Haar-random unitaries）在计算上无法区分？
图丨相关论文（来源：arXiv）
他们的答案是肯定的，团队证明了这类被称为“伪随机酉算子”（PRUs，Pseudorandom Unitaries）的电路确实存在。这一结论建立在一个密码学领域广泛接受的基础假设之上——即存在能够抵抗量子计算机攻击的“量子安全单向函数”（quantum-secure one-way function）。
随机性的魅力与困境
在量子领域，理想的随机性通常通过“Harr 随机酉矩阵”来数学化描述。酉矩阵（Unitary matrix）代表了一个封闭量子系统随时间的演化过程，它保证了量子态的总概率始终为 1。而“Harr 随机”则意味着，这种演化过程是从所有可能的酉变换中完全均匀、无偏地随机抽取的，好比在一个高维球面上完全随机地选择一个点。
这种完美的 Harr 随机性是众多理论研究的基石，涵盖了量子算法设计、判定量子计算机是否超越经典计算机的“量子霸权”实验、量子机器学习、各种量子密码协议的设计，以及对极端物理现象（如黑洞内部信息处理等高度混沌系统）的建模。物理学家们常常将黑洞看作是自然界的信息“搅拌器”，其动力学行为就被认为非常接近 Harr 随机酉变换。
然而，理论上的完美往往伴随着实践中的巨大障碍。Harr 随机酉矩阵存在一个根本性的问题：它们在本质上是“非物理的”。要精确地描述一个作用于 n 个量子比特（qubit，量子信息的基本单元）系统的 Harr 随机酉矩阵，需要大约 2^n 乘以 2^n 个参数来定义。这意味着，其复杂性随着量子比特数量的增加呈指数级爆炸式增长。仅仅是“写下”这样一个矩阵的完整描述，就需要耗费远超现有及可预见未来的经典，或量子计算机能力的天文数字般的资源，更不用说在实际的量子硬件上精确地实现它了。
这种指数级的复杂性使得 Harr 随机酉矩阵在实际应用中几乎遥不可及。这自然引出了一个长期困扰研究人员的关键问题：我们能否找到一条“捷径”？是否存在某种可以被高效构建的量子电路，它本身并非真正的 Harr 随机，但其行为效果对于任何实际可行的计算探测手段（即任何在多项式时间内运行的量子算法）来说，都与真正的 Harr 随机酉矩阵无法区分？
这正是 PRU 概念试图解决的问题。PRU 的核心思想与经典计算机科学中的“伪随机函数”（PRFs，Pseudorandom Functions）一脉相承。经典 PRF 是由 Oded Goldreich 等人在 1986 年的奠基性工作中提出的。它指的是一类函数，可以由一个相对较短的密钥（或称为种子，seed）通过高效算法计算得出，但对于不知道这个密钥的观察者来说，其输出表现得就像一个完全随机选择的函数。
（来源：European Committee of the Weizmann Institu）
类似地，PRU 是一个由（相对）短的密钥参数化的、可以被高效实现的量子电路家族。其核心安全保证是：对于任何计算能力受限于多项式时间的量子算法（通常被称为“敌手”，Adversary），如果让它与一个从 PRU 家族中随机选择密钥生成的电路进行交互，或者与一个真正的 Harr 随机酉矩阵进行交互，那么这个敌手无法以不可忽略的优势（即成功概率仅略高于随机猜测）来区分这两者。简单来说，PRU 在效果上足够“随机”，同时在构造上又足够“简单”，使得它们有望在真实的量子计算机上被建造出来。
自 2017 年 PRU 概念被正式提出以来，其是否存在一直是量子信息领域的核心开放问题之一。
图丨正式提出 PRU 概念的相关论文（来源：arXiv）
在 Fermi Ma 和黄信元的工作之前，研究人员已经取得了一些重要进展，成功构建了满足较弱安全定义的伪随机结构。例如，一些工作构造出了只能抵抗“非自适应”（non-adaptive）敌手的 PRU（这类敌手必须一次性提交所有查询请求，不能根据中间结果调整后续查询）。然而，能否构建能够抵抗一般“自适应”（adaptive）敌手（可以根据之前的查询结果动态调整后续查询策略）的标准 PRU，以及能否抵抗更强大的、可以同时查询酉算子 U 及其逆算子 U† 的敌手，一直是横亘在研究人员面前的一座大山。
路径记录与量子纯化
而 Fermi Ma 和黄信元此次的研究成果一举扫清了这些障碍。他们的工作不仅证明了标准 PRU 的存在性，甚至更进一步，证明了更为强大的“强 PRU”的存在性。后者要求即使敌手拥有查询酉算子 U 及其逆算子 U† 的双重能力，也无法将 PRU 电路与真正的 Harr 随机酉矩阵区分开来。而这两种 PRU 的存在性证明都建立在同一个坚实（尽管仍是假设）的基础之上：存在量子安全的单向函数。
单向函数（One-way function）是现代密码学的基石。它指的是一类函数，其正向计算（给定输入计算输出）非常容易，但其反向计算（给定输出找到对应的输入）则极其困难，对于任何已知的算法（包括量子算法，对于量子安全单向函数而言）来说，在多项式时间内完成反向计算都是不可行的。这就像打碎一个花瓶，正向操作（打碎）很简单，但逆向操作（将碎片完美复原）几乎不可能。密码学中的许多安全构造和证明都依赖于单向函数存在性的假设。研究团队的工作揭示了，只要这个被广泛信任的密码学基石在量子计算时代依然稳固，那么高效模仿量子随机性的 PRU 就必然存在。
他们取得这一突破的核心在于一种新的模拟 Harr 随机酉矩阵的方法，他们称之为“路径记录谕示”（path-recording oracle）V。他们证明，任何与 Harr 随机酉矩阵交互的量子算法的行为，都可以被一个在量子计算机上高效运行的模拟过程所精确复制。
图丨路径记录谕示 V 的定义（来源：arXiv）
这个模拟过程的核心，是追踪并记录下算法与酉矩阵交互的“路径”或历史信息。具体而言，路径记录谕示 V 作用于算法当前的查询量子态|x⟩A 以及一个存储交互历史的辅助量子寄存器|R⟩R。R 代表一个关系的集合，例如包含了过去的输入输出对 {(x1, y1), ..., (xt, yt)}。
V 算符将输入态 |x⟩A |R⟩R 映射到一个新的量子态。在这个新态中，A 寄存器处于所有可能的输出 y 的均匀叠加态上，但这些 y 必须是“新”的，即不能等于 R 中任何已有配对的输出（y ∉ Im(R)，以保持映射的单射性）。同时，R 寄存器则更新为包含了新输入输出对 (x, y) 的状态 |R ∪ {(x, y)}⟩R。形式上可以写作：V: |x⟩A |R⟩R ↦ (1/√Zx,R) Σy∈[N], y∉Im(R) |y⟩A |R ∪ {(x, y)}⟩R，其中 Zx,R 是确保归一化的因子。
研究的关键成果在于证明了这个 V 操作不仅可以被量子计算机高效执行，而且它所模拟的 Harr 随机酉矩阵与真实的 Harr 随机酉矩阵之间，对于任何进行了 t 次查询的高效算法所产生的最终状态，其迹距离（trace distance）差异极小，仅为 O(t²/2ⁿ)（n 为量子比特数）。这意味着对于多项式次数的查询 t，这种模拟在统计意义上是极其精确的。路径记录框架因此提供了一种全新的、更为简洁的分析 Harr 随机性的有力工具，成功绕开了传统研究中对复杂的魏因加滕微积分（Weingarten calculus）及其渐近界估计的依赖。
基于这一模拟工具，研究者进一步将 PRU 的存在性与密码学的基础假设量子安全单向函数的存在性联系起来。他们采用了一种被称为 PFC 构造的方法来构建标准 PRU。最终输出的酉算子形式为 O = Pπ · Ff · C。这里的 Pπ是由均匀随机选取的置换（Permutation）π决定的置换算子；Ff 是一个对角算子，其相位由均匀随机选取的布尔函数 f 决定；而 C 则是一个从任意酉 2-设计（unitary 2-design）分布 D 中随机抽取的酉矩阵，常见的例子包括克利福德群（Clifford group）电路或 Harr 随机本身。
证明的核心逻辑结合了纯化（Purification）技巧和路径记录框架。通过引入纯化寄存器来表示随机的π和 f，对随机 PFC 算子的查询被转化为对一个固定的“纯化”谕示 pfO 的查询。然后，研究者建立了 pfO 与路径记录谕示 V 之间的紧密联系，证明了在一个部分等距同构算子 Comp 的作用下，两者在特定子空间上的行为近似等价。
最后，酉 2-设计 C 通过缠绕（twirling）效应有效地随机化输入，极大地抑制了算法查询过程中输入发生碰撞的概率。当输入无碰撞时，pfO 的行为与 V 高度一致。结合 V 与 Harr 随机的高度不可区分性，最终证明了 PFC 构造（在 OWF 假设保证了伪随机置换和函数存在的前提下）确实产生了标准 PRU。
强 PRU 的构建与模拟
研究团队还进一步探索了如何构建安全性要求更高的“强 PRU”。标准 PRU 的安全性定义是针对那些只能进行“前向”查询（即只能调用酉算子 U）的敌手。而强 PRU 则要求即使敌手被赋予了更强大的能力——可以同时进行前向查询（调用 U）和“反向”查询（调用 U 的逆算子 U†）——也无法将 PRU 电路与真正的 Harr 随机酉矩阵区分开来。
为了构建强 PRU，他们采用了一个稍微修改的构造：D · Pπ · Ff · C。这里，C 和 D 都是从 n-qubit 克利福德群（或任何 2-设计）中独立随机抽取的酉算子，Pπ 仍然是随机置换，而 Ff 这次被选为一个随机的三值相位函数（即 f(x) 可以取 0, 1, 2 中的随机值，对应于乘以相位因子 ω = exp(2πi/3) 的不同幂次）。引入两个随机酉算子 C 和 D 以及使用三值相位是为了应对反向查询带来的额外挑战。
对这个新构造的纯化版本进行分析时，他们发现情况变得更为复杂和有趣。当敌手可以进行前向和反向查询时，纯化寄存器不再是简单地记录一个包含所有 (x, y) 对的集合 S。取而代之的是，它似乎同时维护着两个独立的记录集合：一个 S^for，大致对应于前向查询所建立的路径信息；另一个 S^inv，大致对应于反向查询所建立的路径信息。更复杂的是，两者之间存在互动：一次前向查询有时会像之前一样向 S^for 中添加一个元组 (x, y)，但有时却可能需要从 S^inv 中删除一个元组。反向查询同样会对 S^inv 和 S^for 产生类似的、可能涉及增删的复杂操作。
他们通过推导证明了，这种看似混乱的复杂行为实际上精确地对应于一个更广义、更对称化的“路径记录谕示”Ṽ 的行为。同样地，他们证明了只要 C 和 D 是从 2-设计中随机抽取的，那么敌手就无法区分对构造 D · Pπ · Ff · C 的查询和对这个新的路径记录预言机 Ṽ 的查询。最后，结合 Ṽ 的行为与真正的 Harr 随机酉矩阵（即使在允许反向查询的设置下）的不可区分性，他们成功地证明了强 PRU 的存在性。这个证明过程比标准 PRU 的证明更为错综复杂，巧妙地利用了 2-设计酉算子在作用于两个量子系统（通过张量积 C ⊗ C*，其中 C* 是 C 的复共轭）时展现出的一些特殊平均性质。
这项研究对于量子信息領域而言意义重大，除了为通用 PRU 和 sPRU 的存在性提供了严格的数学证明之外，研究提出的“路径记录”框架本身也是一个强大的新理论工具，有望简化对随机酉变换性质的分析。
图丨Fermi Ma（左）和黄信元（右）（来源：资料图）
在实际应用层面，PRU 的存在意味着未来可以设计出更高效的量子算法和实验方案。例如，演示量子优势的实验可以利用 PRU 来替代难以实现的 Harr 随机电路，从而降低成本、扩大规模。黄信元指出：“这些构造对整个量子技术非常重要……我们能用更高效的资源来做这些量子优势实验。”
当然，这一切都建立在量子安全单向函数存在的假设之上。尽管这是主流假设，但其最终的可靠性仍有待数学证明。尽管如此，这项成果无疑极大地推动了我们对量子随机性的理解和操控能力。随着量子计算技术的发展，高效利用和模拟量子随机性的能力将日益重要，而这项工作恰逢其时地提供了一把关键的钥匙。获取和利用量子随机性的高昂成本，将因此而开始“下降”。
参考资料：
1.https://arxiv.org/abs/2410.10116
2.https://www.quantamagazine.org/the-high-cost-of-quantum-randomness-is-dropping-20250328/
运营/排版：何晨龙
