技术摘要：浅层电路采样中的无条件量子优势

问题陈述

本文探讨了常数深度量子电路（$QNC_0$）是否能够执行常数深度具有有界扇入（fan-in）的经典电路（$NC_0$）无法完成的采样任务，特别是在**输入无关（input-independent）**的设定下。

虽然 Bravyi、Gosset 和 Koenig 此前的研究已经确立了 $QNC_0$ 与 $NC_0$ 在搜索问题（将输入映射到有效输出）上的无条件分离，但对于采样问题（目标是生成来自固定分布 $D_n$ 的样本，而不依赖于特定的计算输入）的问题仍然悬而未决。在输入相关（input-dependent）的设定中，经典的困难性通常依赖于复杂度理论的猜想（例如 $P \neq NP$）。而在输入无关的设定中，挑战在于证明一个仅能获得固定数量随机位的经典电路，即使在允许加性误差（全变分距离）的情况下，也无法重现浅层量子电路的输出分布。

方法论

作者构建了一个特定的分布族 $\{D_n\}$，并通过以下三部分方法论展示了这种分离：

1. 带有 GHZ 建议（Advice）的量子构建

作者首先设计了一个常数深度量子电路，用于从接近于 $(X, \text{majmod}_p(X) \oplus \text{parity}(X))$ 的分布中进行采样，其中 $X$ 是均匀随机比特串，$\text{majmod}_p$ 是“模 $p$ 多数值（Majority mod $p$）”函数。

• 初始方法： 他们利用作用于 GHZ 态（$|GHZ_n\rangle = \frac{1}{\sqrt{2}}(|0^n\rangle + |1^n\rangle)$）的一个“自控型（self-controlled）”非幺正旋转门 $A_\theta$。这使得电路能够将最终输出位与输入位的汉明重量（Hamming weight）模 $p$ 的结果相关联。
• 幺正编译： 为了使电路符合物理实现，他们使用多比特幺正门 $U_{m,\theta}$ 替换了非幺正门。他们证明了这些幺正门可以在保持常数深度的同时，以高保真度逼近非幺正操作。
• 结果： 一个拥有 GHZ 态（被视为“建议”）的常数深度量子电路可以以低全变分距离对目标分布进行采样。

2. 去除 GHZ 建议（“穷人的 GHZ”）

为了在没有外部建议的情况下实现分离，作者使用“穷人的 GHZ（Poor Man's GHZ）”态替换了输入的 GHZ 态。

• 构建： 该状态由一个作用于 $2n-1$ 个量子比特（基于二叉树结构）的常数深度电路生成，随后对 $n-1$ 个辅助量子比特进行测量。
• 适配： 辅助量子比特的测量结果会在剩余状态上引入 Pauli 误差（符号翻转）。作者并没有纠正这些误差（因为纠正需要对数深度），而是将这些误差吸收进目标分布的定义中。
• 新分布： 生成的电路从修改后的分布 $(Z, \text{pmmajmod}_p(Z))$ 中采样。函数 $\text{pmmajmod}_p$ 是一个加权比特之和，其权重取决于用于生成状态的二叉树结构。

3. 经典下界

作者证明，任何具有有界扇入的常数深度经典电路，如果随机输入位的数量受限，则无法对这些分布进行采样。

• 技术： 他们借鉴了 Viola 关于采样困难性的研究技术。该证明依赖于**局部性（locality）**的概念。具有有界扇入的常数深度电路具有有限的局部性；其输出位仅依赖于输入比特的一个小子集。
• 统计检验： 他们构建了一个统计检验（一组“坏”字符串），目标分布通过该检验的概率极低，而任何局部函数（经典电路）通过该检验的概率都很高。
• 核心洞察： 对于分布 $(X, \text{majmod}_p(X) \oplus \text{parity}(X))$，固定大部分输入位会使剩余比特的汉明重量成为独立随机变量之和。作者表明，局部函数无法同时满足这些和的奇偶校验（parity）和模 $p$ 多数值约束。
• 推广至 $\text{pmmajmod}_p$： 在没有 GHZ 建议的情况下，由于存在树状结构的权重，依赖结构变得更加复杂。作者根据二叉树结构将输出变量划分为“森林（forest）”块。他们表明，即使存在这种复杂的依赖关系，通过固定足够的输入位也可以隔离出独立的块，从而允许应用相同的下界逻辑。

关键贡献与结果

1. 采样任务的无条件分离： 本文提供了第一个无条件证明，即常数深度量子电路可以从常数深度具有有界扇入的经典电路无法实现的分布中进行采样，即使是在允许加性误差的情况下。

   • 定理 3： 对于任何 $\delta < 1$，存在一个分布 $D_n$，使得常数深度量子电路以距离 $\le 1/6 + O(n^{-c})$ 进行采样，而任何拥有 $n + n^\delta$ 个随机输入位且具有有界扇入的经典电路，若要达到距离 $\le 1/2 - \omega(1/\log n)$，则需要 $\Omega(\log \log n)$ 的深度。

2. 处理随机性约束： 这种分离特指当经典电路获取的随机性受到限制时（具体为 $n + n^\delta$ 位）。作者指出，如果经典电路可以获取不受限数量的随机位，它可以平凡地模拟该分布。然而，他们也展示了对于拥有**有界扇出（fan-out）**但可获取量子建议的经典电路，同样存在分离。

3. 对偏置输入的鲁棒性： 作者将下界扩展到了接收偏置随机输入（熵为 $1/k$ 的伯努利变量）的经典电路，只要总熵受限即可。这解决了关于分离是否依赖于经典电路获取完美均匀随机性的潜在疑虑。

4. 显式电路构建： 文中详细说明了使用标准门集（单比特门和 CNOT）构建量子电路的过程，并证明它们是一个一致的族（uniform family）。此外，还给出了“穷人的 GHZ”态以及由此产生的采样分布的具体数学定义。

意义

本文声称其意义体现在以下领域：

• 输入无关的量子优势： 它回答了 Bravyi、Gosset 和 Koenig 提出的关于输入无关采样的问题，证明了量子优势并不局限于搜索问题或输入相关的任务。
• 无条件困难性： 不同于许多采样困难性结果（如随机电路采样）依赖于未经验证的复杂度猜想（如多项式层级不塌缩），这一结果是无条件的。它仅依赖于常数深度经典电路的结构性限制。
• 态制备复杂度： 研究结果对态制备的复杂度具有影响。由于从分布 $(X, f(X))$ 采样在经典上类似于制备特定的量子态，这种分离表明，某些量子态（及其关联的分布）对于浅层经典电路来说，即使拥有随机性，也是本质上难以制备或模拟的。
• 细化边界： 这项工作通过展示浅层量子电路可以产生浅层经典电路无法复制的关联（特别是涉及奇偶校验和模 $p$ 多数值的关联），从而细化了对浅层量子电路能力的理解，即便经典电路被允许拥有额外的随机性。

作者保持了谦逊的态度，指出其经典下界仅适用于随机比特数量受限（具体为 $n + n^\delta$）的情况。他们承认，将这些界限扩展到具有不受限随机性的经典电路仍是一个开放性问题，尽管他们在有界扇出的设定下取得了进展。