Learning Random Quantum Circuits and the Emergence of Pseudorandomness

技术摘要：学习随机量子电路与伪随机性的涌现

问题陈述
本文探讨了在随机量子电路背景下，可学习性（learnability）与伪随机性（pseudorandomness）之间的基本相互作用。具体而言，研究了在固定维度砖块结构（brickwork architectures）上，是否可以从其输出态的副本（状态访问模型，state access）中高效地学习局部随机量子电路，且在电路达到伪随机态（PRS）阈值之前。

研究设置涉及深度为 $d$、局部门作用于 $2\ell$ 个量子比特（局部性 $\ell$）的 $k$ 维砖块电路。核心问题在于：当深度与局部性的综合规模 $\ell d$ 满足 $\ell d = O(\log n)$ 时，是否可以在多项式时间内精确恢复此类电路。这一机制具有重要意义，因为它代表了伪随机态（PRS）预期涌现的自然边界；此前的研究表明，实现 PRS 需要 $\ell d = \omega(\log n)$。

方法论
作者提出了一种高效的学习算法，该算法在状态访问模型下运行，即学习者获得的是状态 $|\psi_0\rangle = U|0\rangle^{\otimes n}$ 的副本，但无法直接查询幺正算符 $U$ 本身。该算法采用逆向方式进行，即从最后一层 $U_d$ 开始，逐层向第一层 $U_1$ 进行电路恢复。

其核心技术创新是一个局部相关性准则（local correlation criterion），该准则避免了以往方法中依赖于重建完整后向光锥（backward lightcones）的瓶颈。关键步骤如下：

1. 光锥不相交性（Lightcone Disjointness）： 对于作用在最终层中位点 $B$ 和 $C$ 上的门 $G$，算法会识别出一个位点 $D$，使得若移除门 $G$，则 $B$ 和 $D$ 的后向光锥是不相交的。
2. 相关函数（Correlation Function）： 算法定义了一个相关函数 $\text{Corr}_{B:D}(\rho) = \|\rho_{BD} - \rho_B \otimes \rho_D\|_F^2$。如果正确的门 $G$ 被移除（或反转），生成的态在 $B$ 和 $D$ 上变为可分态，从而产生零相关性。如果选择错误的门，相关性则保持非零。
3. 门识别（Gate Identification）： 通过将候选门集中的每一个门的逆应用于 $B$ 和 $C$ 上的约化态，算法通过寻找使相关性最小化至零的门来识别正确的门。
4. 反集中性分析（Anticoncentration Analysis）： 为了保证对于错误的门，其相关性足够大（具体为 $\ge 2^{-O(\ell d)}$），作者证明了一个针对 Haar 随机幺正矩阵上的低阶多项式的、新的与维度无关的反集中性不等式。

主要贡献

1. 高效学习算法： 本文提出了一种算法，可以在 $\text{poly}(n, 2^{\ell d})$ 时间内精确恢复一个深度为 $d$、局部性为 $\ell$ 的随机 $k$ 维砖块电路。这意味着只要 $\ell d = O(\log n)$，即可实现多项式时间复杂度。
2. 维度无关的反集中性： 一个重大的技术贡献是提出了一个新的针对幺正群 $U(m)$ 上多项式的 Carbery-Wright 型不等式。不同于以往的小球指数（small-ball exponent）依赖于矩阵维度 $m$ 的多项式关系（例如 $1/m^2$），这一结果建立了一个与维度无关的指数：
   $$\Pr_{U \sim \mu_{\text{Haar}}} [|P(U)| \le \varepsilon \|P\|_\infty] \le 64m^2 \cdot \varepsilon^{\frac{1}{24\pi d}}$$
   这种与维度无关的指数对于处理局部性（$\ell$）不断增长的门至关重要，避免了复杂度随局部希尔伯特空间维度爆炸的问题。
3. 状态访问 vs. 幺正算符访问： 该工作证明了仅凭状态访问（即 $U|0\rangle$ 的副本）即可实现精确的电路恢复，这是一种比幺正算符访问（对任意输入查询 $U$）更弱的模型。这解决了先前文献中的一个空白，即在状态访问模型下，以往的方法通常需要重建巨大的光锥，从而导致超多项式复杂度。

结果

• 定理 1.1： 对于从随机门集中选择局部门的深度为 $d$、$k$ 维砖块电路，存在一种算法能以高概率在 $\text{poly}_k(n, d, \delta^{-1}) 2^{O_k(d\ell)}$ 时间内精确恢复该电路。
• 定理 1.2： 本文证明了幺正群上维度的无关 Carbery-Wright 不等式，通过 Weyl 积分公式和 Remez 型不等式将问题简化为一元极值问题。
• 相关性间隙（Correlation Gap）： 作者证明，对于任何错误的候选门，相关性 $\text{Corr}_{B:D}$ 以高概率被下界限定为 $\Gamma = 2^{-O(\ell d)} \text{poly}(\dots)$，从而确保学习算法能够将正确的门与错误的门区分开来。

意义与主张
本文声称提供了第一个同时实现以下目标的算法：

1. 对于具有增长局部性的电路，只要 $\ell d = O(\log n)$，即可实现多项式时间复杂度。
2. 精确恢复原始电路的布局与门。
3. 在状态访问模型下运行，这对于仅能获取输出态的密码学应用场景更为现实。

作者将这项工作定位为阐明伪随机性产生条件的途径。他们指出，尺度 $\ell d = O(\log n)$ 是可学习性的阈值；超过这一尺度（即 $\ell d = \omega(\log n)$）时，伪随机性的涌现使得高效学习变得不可能。这些结果支持了这样一个假设：局部 Haar 随机电路可以作为伪随机态生成器的候选，前提是其深度/局部性超过了对数阈值。

文中明确指出，虽然学习算法在指定范围内是高效的，但其目的并非声称能够破解依赖于特定结构集合或辅助工作空间的密码学构造，而是旨在澄清局部 Haar 随机电路的学习极限。此外，文中强调，关于维度无关的反集中性结果作为一个具有独立价值的工具，对量子信息理论和复杂性理论均有贡献。