技术摘要：对数深度费米子采样

问题陈述

量子与经典计算之间的可证明分离是非常罕见的，而采样问题为这种条件性证据提供了最清晰的途径。**费米子采样（Fermion Sampling）**涉及通过被动线性光学系统移动非相互作用的费米子，并测量其占据数。虽然在占据基底输入下的动力学过程是经典可模拟的，但当输入为非高斯“魔术态（magic state）”时，该问题会变得在计算上极其困难。

先前的研究表明，当变换取自全局 Haar 随机被动系综时，费米子采样表现出反集中性（anticoncentration）（输出概率分布在指数级数量的结果中）和平均情况下的硬度（average-case hardness）（估计概率在典型实例上是困难的）。然而，这种全局随机性需要 $O(n)$ 的电路深度和 $O(n^2)$ 个两模门。一个核心开放问题是：这种线性深度是否是必要的，或者是否可以通过更浅的对数深度电路来实现相同的保证。

研究方法

作者分析了一个作用于 $n$ 个模式（其中 $n$ 可被 4 整除）的特定电路系综，这些模式由四个模式配对的魔术态乘积制备而成。该电路包含 $t$ 层，其中每一层独立地选择模式的一个均匀完美匹配，并在匹配的对之间应用独立的 Haar 随机两模被动门。

分析依赖于两个不同的技术框架：

1. 碰撞动力学的谱分析：

   • 作者追踪了碰撞比（collision ratio）（$R_{n,t}$），定义为两次独立运行同一电路得到相同结果的概率，并针对均匀分布进行归一化。
   • 利用 Howe 对偶性和置换对称性，碰撞的动力学从指数级的多粒子空间简化为一个具有 $O(n)$ 个状态的可逆马尔可夫链（具体而言，是基于两个副本中双占据模式数量的 $n/2 + 1$ 个扇区）。
   • 碰撞的衰减受该链特征值的控制。至关重要的是，作者展示了输入态如何决定谱权重。对于魔术输入，最慢弛豫模式的权重被限制为一个常数，而第二种模式的权重随 $n$ 线性增长。这改变了主导的弛豫尺度。

2. 通过嵌入与插值进行的硬度归约：

   • 为了证明平均情况下的硬度，作者在浅深度内构造了一个“困难”实例（后选择的通用计算）。
   • 他们证明了这些困难实例可以通过“开关（switch）”门（恒等门或费米子交换门）路由相互作用的模式，从而被嵌入到该系综的典型随机匹配方案中。
   • 一条 Cayley 路径插值将 Haar 随机门连接到嵌入的困难电路。通过在靠近 Haar 端点处查询预言机，并使用有理线性规划解码器（一种鲁棒的 Berlekamp-Welch 插值变体），他们可以恢复困难端点的概率。该解码器可以在不需要额外 NP 预言机的情况下容忍一定比例的错误答案。

核心贡献与结果

1. 反集中性的锐利对数阈值

本文确立了对数深度足以实现反集中性。

• 阈值深度： 碰撞比达到被动-Haar 基准的任何固定倍数 $q > 1$ 的深度为：
  $$t^*(q) \approx \frac{\log n}{\log(9/4)} \approx 0.855 \log_2 n$$
• 过渡剖面： 过渡是锐利的，具有显式的极限剖面 $R_{n,t}/R_{Haar}(n) \to e^{3z/2}$，其中 $z = n(4/9)^t$。
• 最优性： 通过两粒子相关性导出的下界证明，在这一系综内，没有任何显著更早的深度可以实现有界的碰撞比，从而证实了对数标度的最优性。
• 有限门集： 作者确定了一个由 192 个两模门（$U(2)$ 的一个子群）组成的有限字母表，它能精确重现 Haar 测度的两副本通道。因此，所有碰撞和反集中结果都完全适用于这个离散门集。

2. 概率估计的平均情况硬度

本文证明了在此浅深度系综下，估计输出概率在平均情况下是困难的。

• 硬度结果： 在 Real-RAM 模型中，在至少 $3/4 + \gamma$ 的实例上，将固定半填充输出的概率估计到加性误差 $2^{-O(n \log_2 n)}$ 是 #P-困难的。
• 机制： 证明过程通过图态测量模式和费米子 I 型融合，将一个最坏情况下的 #P-困难计算嵌入到随机方案中。由于随机匹配的混合特性，这种嵌入以高概率成功。
• 鲁棒性： 该归约使用了一个能够处理噪声或错误预言机回复的有理线性程序解码器，避免了类似于其他归约中通常需要的 NP 预言机。

3. 确定性路由变体

作者提出了一种混合系综，其包含一个固定的 Beneš 路由前缀，随后是随机匹配层。该变体保证了每一个困难实例和输出都可以被嵌入（失败概率 $\eta = 0$），消除了纯随机匹配情况下所需的填充和渐近失败界限。

意义与主张

本文声称解决了关于费米子采样硬度是否需要线性深度的开放问题。通过证明对数深度（$O(\log n)$）和 $O(n \log n)$ 个门足以实现反集中性和平均情况下的硬度，这项工作显著降低了实现潜在量子优势所需的资源要求。

与之前工作的关键区别在于：

• 输入依赖机制： 分析明确追踪了魔术输入如何抑制最慢的弛后模式，这是通用的电路随机性界限所忽略的机制。
• 精确有限字母表： 192 门字母表对碰撞律的保持，提供了一个具体的、离散的门集，这不同于以往依赖连续 Haar 随机性的结果。
• 精细化硬度： 所证明的加性误差精度比标准采样到计数归约所需的 $1/N$ 量级更精细。作者明确指出，采样到常数全变差距离的硬度仍然是一个开放问题，因为他们的归约针对的是高精度概率估计而非常数距离采样。

这项工作为浅深度费米子量子优势提供了严谨的理论基础，将输入制备（魔术态）与电路深度在产生计算硬度方面的作用进行了分离。