技术摘要：任意群的量子随机采样与路径记录

1. 问题陈述

在量子算法分析与密码学中，一个核心挑战是推理那些对随机群元素（例如随机函数、置换或酉算子）具有算子访问权限的算法。为了分析此类算法，必须确定它们在 $t$ 次查询后获取了哪些信息，以及它们是否能将该随机对象与伪随机对象区分开来。

在经典情形下，**随机采样（random sampling）**是标准工具：模拟器不是在开始时对整个随机对象进行采样，而是在算法进行查询时，实时采样部分信息（输入-输出对）。这使得高效的模拟和对算法知识状态的清晰追踪成为可能。

在量子设定下，算法可以进行叠加态查询并遗忘信息，使得经典的随机采样不再适用。现有的解决方案是压缩算子（compressed oracles）或记录算子（recording oracles），它们维护着关于部分信息的量子数据结构。然而，先前的压缩算子存在显著局限性：

• 缺乏通用性： 大多数方案是针对特定群量身定制的（例如，Zhandry 处理布尔函数，Ma-Huang 处理 Haar 随机酉算子，Carolan 处理置换），使用了特定的论证方法。
• 缺乏可解释性： Grinko 和 Yoshida 最近提出的通用型方案（“表格记录算子”，tableau-recording oracle）在数学上是严谨的，但缺乏对所记录数据的清晰操作性解释，这阻碍了其在证明下界和安全性方面的应用。
• 近似误差： 一些通用构造（如 Ma-Huang）仅能实现带有 $O(t^2/N)$ 误差的近似模拟，而非完美模拟。

本文提出的问题是：是否存在一种通用的、具有可解释性的压缩算子，能够为每一个紧致李群（compact Lie group）提供量子随机采样？

2. 方法论

作者开发了一个从基本原理出发的框架，用于为任何通过酉表示 $\rho: G \to U(N)$ 作用于 $N$ 个量子比特的紧致李群 $G$ 构建压缩算子。该方法论分为两个阶段：

2.1 表格记录（代数基础）

作者首先重新审视并为表格记录算子（$Q^{\text{Tab}}_\rho$）提供了新的证明，该算子最初由 Grinko 和 Yoshida 研究。

• 构造： 他们将随机群元素 $g$ 纯化到希尔伯特空间 $L^2(G)$ 中，并应用傅里叶变换（广义 Peter-Weyl 定理）将其转移到由不可约表示（irreps）索引的基底中。
• 机制： 算子维护一个在傅里叶基（或“表格基”）中的“记录寄存器”。查询通过应用 Clebsch-Gordan 变换（用于分解当前不可约表示与查询表示的张量积）随后应用逆对偶 Clebsch-Gordan 变换来更新该寄存器。
• 性质： 该算子能完美模拟随机群元素，且如果 Clebsch-Gordan 变换是高效的，则该算子也是高效的。然而，记录寄存器的内容（不可约表示标签与表格态的叠加）在操作层面上难以解释。

2.2 路径记录（解释层）

为了实现可解释性，作者定义了路径记录算子（$Q^{\text{Path}}_\rho$）。

• 变换： 他们定义了一个等距映射 $\Gamma_t$，将表格基映射到路径基。路径基由有序输入-输出对 $|(x_1, y_1), \dots, (x_t, y_t)\rangle$ 的叠加组成，代表了算法探索的“费曼路径”（Feynman paths）。
• 对称化： 关键洞察在于，记录寄存器必须尊重对易代数（commutant algebra） $A_t = \text{End}_G((\mathbb{C}^N)^{\otimes t})$ 的对称性。其更新规则涉及：
  1. 重加权（Reweighting）： 根据不可约表示的维度和对易代数的维度，对 Schur 基中的子空间进行缩放。
  2. 追加（Appending）： 向数据库中添加一个新的 EPR 对（输入-输出对）。
  3. 对称化（Symmetrizing）： 将状态投影到对易 EPR 子空间（即投影算子 $\Omega_{A_t}$ 的像）上。该投影算子强制执行群作用的对称性，有效地“遗忘”了查询的顺序或其他冗余信息，类似于经典随机采样对于置换的操作会遗忘不同输入的顺序。
• 通用性： 该框架适用于任何紧致李群。对称化算子 $\Omega_{A_t}$ 的具体形式取决于对易代数（例如，$U(N)$ 对应对称群代数，$S_N$ 对应划分代数）。

3. 核心贡献

3.1 通用路径记录算子

本文定义并分析了一种路径记录算子，它具有以下特性：

• 完美模拟： 它为任何 $U(N)$ 的闭子群提供了对 Haar 随机元素的精确模拟，消除了以往通用构造中存在的 $O(t^2/N)$ 模拟误差。
• 具有可解释性： 其记录寄存器显式地存储输入-输出对的叠加，使得算法获取的信息变得透明。
• 高效性： 其更新规则通过对易代数和 Clebsch-Gordan 变换来表达，对于许多感兴趣的群（如 $U(N), S_N$）而言是可高效实现的。

3.2 统一先前工作

作者展示了其框架如何自然地恢复并统一现有的压缩算子：

• Zhandry 算子： 被恢复为群 $\mathbb{Z}_2^N$（布尔函数）的路径记录算子。
• Ma-Huang 算子： 被恢复为 $U(N)$ 的近似路径记录算子，其中子空间重加权算子被近似为标量，且差异约束被强制执行。
• 置换算子： 被恢复为对称群 $S_N$ 的算子。

3.3 新型伪随机酉算子构造

该框架的主要应用是一个简化的**伪随机酉算子（Pseudorandom Unitaries, PRUs）**构造。

• 构造方式： 乘积 $PC$，其中 $P$ 是一个随机（或伪随机）置换，$C$ 是从酉 2-设计（例如随机 Clifford 电路）中采样的电路。
• 结果： 作者证明，对于任何进行 $t$ 次查询的对手， $PC$ 与 Haar 随机酉算子的区别度为 $O(t^2/N)$。
• 改进： 这通过证明随机相位 $F$ 是不必要的，改进了之前的 “PFC” 构造（置换 + 相位 + Clifford）。它产生了迄今为止被分析过的最简单的 PRU 构造。

4. 结果

4.1 理论保证

• 定理 1.5（非正式）： 对于任何紧致李群 $G$，存在一个等距映射 $Q^{\text{Path}}_\rho$，可以完美模拟对 Haar 随机 $\rho(g)$ 的查询访问。其更新规则涉及相对于对易代数 $A_t$ 的重加权、追加和对称化。
• 定理 1.6： 对于均匀随机的原地置换 $P$ 和酉 2-设计 $C$，系综 $P \cdot C$ 与 Haar 随机酉算子的区别度为 $O(t^2/N)$。
• 定理 1.7： 如果 $P$ 是从一个 $(t, \epsilon)$-安全后量子伪随机置换族中采样的，那么 $P \cdot C$ 是一个 $\epsilon + O(t^2/N)$ 近似 $t$-设计。

4.2 用于 PRU 证明的技术机制

PRU 安全性的证明依赖于对 $S_N$（置换）和 $U(N)$（酉算子）在特定子空间上的路径记录算子的分析：

1. 不同非置换子空间（Distinct Nonplussed Subspace, $DNP$）： 这是“不同”（distinct）子空间（无重复输入）与“非置换”（nonplussed）子空间（正交于均匀叠加态 $|+\rangle$）的交集。
2. 在 $DNP$ 上的等价性： 作者证明，在 $DNP$ 子空间上，对称群的对易 EPR 投影算子（$\Omega_{S_N}$）与酉群的对易 EPR 投影算子（$\Omega_{U(N)}$）实际上是相同的。
3. 2-设计性质： 随机 2-设计 $C$ 以极高概率（$1 - O(t^2/N)$）将几乎所有状态映射到 $DNP$ 子空间中。
4. 结论： 由于在对手的状态（应用 $C$ 之后）所在的子空间内，两种算子的行为是相同的，因此对手无法区分基于置换的构造与 Haar 随机酉算子。

5. 意义与主张

本文声称，路径记录算子为量子查询复杂度与密码学提供了一个强大的通用工具。其重要性在于：

• 可解释性： 不同于以往的通用算子，它以直接对应于算法查询历史（输入-输出对）的方式记录信息，从而促进了下界证明与安全性证明。
• 统一性： 它提供了一个单一的数学框架，解释并推广了关于函数、置换和酉算子的不同研究结果。
• 密码学中的简洁性： 它实现了一个更简单的伪随机酉算子安全性证明，通过移除构造中对随机相位的需求，仅依赖于置换与 2-设计。
• 基础性洞察： 它阐明了对易代数的代数结构与量子算子操作行为之间的关系，表明在随机采样中“遗忘”信息对应于向对易 EPR 子空间进行投影。

作者强调，其工作并非提出新的实验设置，而是为分析随机预言机模型下的量子算法及密码原语提供了一套严谨的理论工具集。