正文
图丨Oded Goldreich（来源：European Committee of the Weizmann Institute of Science）
类似地，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）及其渐近界估计的依赖。
