随机预言机酉合成对 Haar 随机酉变换是否不可能？

问题从最坏情况转向平均情况合成

经典酉合成问题最早由 Aaronson 和 Kuperberg 提出，它问的是：对于每一个酉变换 U，是否存在一个布尔函数 f，使得在给定 f 的预言机访问下可以高效计算 U。如果成立，那么每一个难计算的酉变换背后都有一个同样难计算的函数；如果不成立，那么即使所有函数都容易计算，某些酉变换仍然难以计算。进展一直有限：反对该命题的最佳证据是一个下界，它表明一般情况下无法仅用一次对 f 的查询就高效合成 U，而这一技术后来被推广到可用两次查询合成的酉变换。

这篇论文研究的是一个不同的平均情况版本。它不问每一个酉变换，而是问：给定一个随机布尔函数的访问权限，算法能否高效实现一个 Haar 随机酉变换。作者将这样的过程称为随机预言机酉合成算法，并通过均匀随机布尔函数 f 与 Haar 随机酉变换 U 之间的耦合来定义其误差，要求由 f 计算出的信道与 U 对应的酉信道之间的期望菱形距离至多为 epsilon。

动机很具体。随机预言机模型中的伪随机酉变换，例如 PFC 系综，接收一个没有任何结构的均匀随机预言机，却仍被期望输出一个看起来随机的酉变换。Brakerski 和 Yuen 曾表明，在随机预言机模型中设计足够好的可扩展 PRU 将在正面方向上解决酉合成问题，因为一个能抵抗 O(N^2) 次查询的 PRU 必须紧密模仿 Haar 随机酉变换。平均情况问题恰好隔离了这条路线所需要的那类算法。

sqrt(N)/poly(n) 查询下界排除高效合成

论文的第一个主要结果是定理 1.2。假设 A 是一个 n 量子比特的随机预言机酉合成算法，误差为 epsilon，且 epsilon 至多为 1 减去 1/poly(n)，即误差被一个多项式因子界定在 1 之外。那么如果 k 是 A 对随机预言机进行的查询次数，则 k 必须至少为 sqrt(N)/poly(n)，其中 N = 2^n。

这里的单位是预言机查询次数，分母是 n 的多项式。该下界在 n 上是超多项式的，因此没有高效算法能满足它。适用范围很重要：该定理适用于误差即使只是稍微非平凡的情况，即被 1/poly(n) 因子界定在 1 之外。一个几乎总是错误的算法不在覆盖范围内。

作者由此得出一种解释：任何高效的酉合成算法都必须使用高度结构化的布尔函数。他们还指出，结合 Brakerski 和 Yuen 的结果，虽然在随机预言机模型中存在能抵抗 o(sqrt(N)) 次查询的 PRU，但这些 PRU 无法抵抗 O(N^2) 次查询。这是论文将其下界与先前工作结合后得出的推论，而不是一项独立实验。

随机预言机携带的比特太少，无法确定 Haar 酉变换

该下界基于一种计数式论证。一个使用 m 个总量子比特的合成算法可以写成电路 W_f = V_k O_f ... O_f V_0，其中 V_i 是 m 量子比特上的固定酉变换，O_f 是对应于随机函数 f 的对角相位酉变换。在 n 量子比特输入上，算法追加 m - n 个初始化为零的辅助量子比特，应用电路，追踪掉辅助量子比特，然后输出其余部分。

其策略是证明：即使算法从预言机中抽取大量随机比特，也只有少数比特真正影响它最终计算出的酉变换。如果算法实际依赖的随机比特数显著小于 N^2，那么它就无法模拟 Haar 随机酉变换，因为 n 量子比特上的 Haar 随机酉变换需要大约 N^2 个实参数来指定。

论文首先分析最简单的单次查询情形，其中 A_f = J^dagger V_1 O_f V_0 J，并在分析中假设算法干净地合成 U，即在辅助量子比特被追踪掉之前将其重置为零。作者指出这一假设简化了分析，并说明他们后来展示了如何去除该假设，将论证扩展到脏合成。技术工具使用表示论，包括 Schur 引理和不可约表示维数的界，来控制依赖预言机的相位能在多大程度上移动输出。

O(N) 查询安全的 PRU 突破此前的 sqrt(N) 上限

论文的第二个主要结果是定理 1.3：在随机预言机模型中存在一个 PRU，能抵抗任何进行 O(N) 次查询的对手。这是一个构造性结果，直接回应了为什么此前的 PRU 似乎卡在 o(sqrt(N)) 查询安全性上。

作者解释说，分析 PRU 的主流范式聚焦于所谓的“相异子空间”，它出现在一个 T 次查询的对手以张量积形式准备 T 个标准基向量并并行查询未知酉变换时。当 T = o(sqrt(N)) 时，有一些技巧可以假装分析生活在相异子空间中，从而简化问题。一旦 T = Omega(sqrt(N))，就不得不考虑非相异子空间。论文表明这一障碍只是技术性的，而非根本性的。

该构造很容易描述：它计算 U = F_n H_n ... F_1 H_1 F_0，其中每个 H_i 是一个固定的 n 量子比特酉变换，每个 F_i 可以看作对单独的 n 比特随机函数 f_i 的一次查询。该酉变换由 O~(N) 个随机比特生成。该 PRU 在只对随机预言机进行 poly(n) 次查询的意义上是高效的，但与 PFC 系综不同，作者不知道如何以计算高效的方式实现它。他们表示相信这只是一个技术障碍，O(N) 查询安全性应当可以由既查询高效又计算高效的 PRU 算法实现。

辅助量子比特阻止查询高效 PRU 超过 O~(N) 次查询

论文的第三个主要结果，定理 1.4，表明该构造的 O(N) 查询安全性对于随机预言机模型中的查询高效 PRU 而言本质上是优的。固定一个大于 0 的常数 gamma。假设在随机预言机模型中存在一个 n 量子比特的 PRU，能抵抗 T = Omega(N^(1+gamma)) 次查询。那么如果 k 是合成该 PRU 所需的随机预言机查询次数，则 k 必须至少为 N^(min{gamma,1}/2)/poly(n)。

这一结果在定理 1.2 和定理 1.3 之间插值。它排除了随机预言机模型中查询高效 PRU 超过 O~(N) 次查询的安全性，因此定理 1.3 构造所达到的查询安全性在 n 的多项式因子范围内是最优的。对于 T = Omega(N^2) 查询安全的 PRU，它表明合成算法必须使用大约 N^(1/2) 次查询，与定理 1.2 的界一致。

这一障碍背后的机制是辅助量子比特问题。要突破 O~(N) 查询安全性，PRU 算法需要使用超过 O~(N) 个随机比特，而在 poly(n) 次查询下做到这一点的唯一方法是在预言机的输入寄存器中加入额外的辅助量子比特。但对辅助量子比特进行查询有风险，很容易在前 n 个量子比特与辅助量子比特之间产生纠缠，这意味着算法不再像预期那样在前 n 个量子比特上计算酉变换。作者指出，辅助量子比特问题在设计一般酉合成算法时一直是一个重大障碍，而在无法控制预言机形式的随机预言机模型中，它似乎尤其具有挑战性。

三个界共同勾勒出随机预言机合成与 PRU 的失效边界

将三个定理放在一起看，它们划出了一条边界。具有非平凡误差的随机预言机酉合成至少需要 sqrt(N)/poly(n) 次查询，因此不可能高效实现。存在一个能抵抗 O(N) 次查询的 PRU，可以用 poly(n) 次预言机查询构建，但尚不知道它是否计算高效。而且，对于任何大于 0 的 gamma，随机预言机模型中没有查询高效的 PRU 能抵抗 Omega(N^(1+gamma)) 次查询。

真正重要的比较是查询安全性与查询效率之间的比较。定理 1.3 的构造以 poly(n) 次预言机查询实现了 O(N) 查询安全性，超过了此前构造 O(sqrt(N))-设计的最佳已知结果。定理 1.4 的下界表明，当目标为 Omega(N^2) 查询安全性时，将查询安全性推过 O~(N) 会迫使合成算法使用大约 N^(1/2) 次查询。因此，可构建之物与可高效构建之物之间的差距，是论文的核心张力。

论文还在否定方向上解决了 Brakerski 和 Yuen 提出的一个问题：可扩展伪随机酉变换能否在 ROM-PRU 模型中实现。特别地，在 ROM-PRU 模型中，对于任何大于 0 的 gamma，n 量子比特上的 Omega(N^(1+gamma)) 酉设计（其中 N = 2^n）都无法被高效实现。另一方面，论文在同一模型中用 poly(n) 次查询构造了一个 O(N)-设计。

不可能性特定于随机、无结构的预言机

这些下界是针对接收均匀随机布尔函数作为预言机的算法陈述的。论文明确指出这是一种限制：一般设置下的酉合成算法被给予对布尔函数 f_U 的查询访问，而该函数可能高度结构化，并可能以任意复杂的方式依赖于酉变换 U。例如，基于 Bernstein-Vazirani 的合成算法取一个 N x N 酉变换，将其表示为长度为 O~(N^2) 的比特串，取该串的 2^O~(N^2) 比特长的 Hadamard 编码，并将这个高度结构化的函数用作 f_U。

因此，这一不可能性结果并不是说无法从任何布尔函数合成任何酉变换。它说的是，当函数是随机且无结构时，合成无法成功。作者直接陈述了这一点：任何高效的酉合成算法都必须使用高度结构化的布尔函数。

第二个适用范围条件是误差阈值。定理 1.2 要求 epsilon 至多为 1 减去 1/poly(n)。该界是关于查询复杂度的，而不是关于查询次数之外的计算时间；单次查询分析中使用的干净合成假设后来通过将论证扩展到脏合成而被去除。O(N) 查询的 PRU 构造是查询高效的，但尚不知道是否计算高效，作者将这一限制放在该结果旁边，而不是把它当作最终定论。

决定性问题在于 O(N) 安全性能否变得高效

论文最具决策相关性的比较，并不只是随机预言机酉合成是否可能。它是查询安全性与查询效率之间的差距。定理 1.3 表明，O(N) 查询安全性可以用 poly(n) 次预言机查询实现，超过了此前的 O(sqrt(N))-设计。定理 1.4 表明，对于任何大于 0 的 gamma，随机预言机模型中没有查询高效的 PRU 能抵抗 Omega(N^(1+gamma)) 次查询，而达到 Omega(N^2) 查询安全性会迫使使用大约 N^(1/2) 次查询。

这把悬而未决的问题精确地定位了。定理 1.3 的构造在预言机查询上是高效的，但尚不知道是否计算高效。作者表示相信这只是一个技术障碍，O(N) 查询安全性应当可以由既查询高效又计算高效的 PRU 算法实现。如果这一信念正确，辅助量子比特障碍就是技术障碍而非根本障碍。如果不正确，那么查询高效 PRU 的 O(N) 上限就是真正的极限。

对于关注酉合成问题的读者，实际阈值是这样的：不可能性结果适用于随机、无结构的预言机，因此结构化的布尔函数仍然是通往高效合成的唯一可行路线。Brakerski 和 Yuen 指出的 PRU 路线需要抵抗 O(N^2) 次查询的安全性，而这篇论文表明没有查询高效的 ROM-PRU 能达到那里。因此，优先事项是确定 O(N) 查询安全的构造能否变得计算高效，因为这是将当前状态与随机预言机模型中可扩展 PRU 分隔开来的唯一一步。

本文引用的文献