为什么更强的量子态制备下界如此难以证明？

壁垒限制的是证明技术而非电路

这篇论文针对的不是某个特定的量子电路类，而是一类论证方式。态制备下界的一种常见策略是：先指出目标态具有的某个性质，然后证明允许的电路所能制备的任何态都不具有该性质。作者把这样的性质称为自然的，当它满足两个条件：可构造性，即一个经典算法在给定该态全部振幅（达到足够精度）的列表时能高效判定该性质；以及普遍性，即该性质对足够大比例的 Haar 随机态成立。若某个电路模型近似可制备的任何态都不具有该性质，则称该性质对该模型是有用的；若一个下界证明可以被重新表述为识别这样一个自然且有用的性质，则称该证明是自然的。

这里的可构造性是刻意宽松的。算法可以检查全部 2^n 个振幅，运行时间是振幅列表长度的多项式，因此可以随量子比特数呈指数增长。振幅列表所扮演的角色，相当于经典自然证明框架中布尔函数的真值表。这是对态性质的一种经典数学检验，而不是验证该性质的高效物理过程。

主要结果是条件性的。假设经典亚指数安全的伪随机函数可以由多项式规模、深度为 d 的阈值电路实现，那么没有任何自然性质能够证明：某个态不能被 Magic Hierarchy 第 (8d+20) 层中的多项式规模电路以 e^{-n} 的误差近似制备。该密码学假设完全是经典的，与用于得到针对 TC^0 电路的经典自然证明壁垒的假设相同。因此，该壁垒约束的是哪些证明方法可行，而不是哪些电路存在。

Magic Hierarchy 固定了电路模型

Magic Hierarchy 是一个受限的电路模型，其电路在任意 Clifford 电路与单、双量子比特门的常数深度电路之间交替。它的层级限定了交替的次数。作者在这一层级体系内工作，是为了方便，并直接与先前把该层级固定层级与经典下界联系起来的结果进行比较。

这一比较之所以重要，是因为 Magic Hierarchy 固定层级上的态制备下界此前已知可推出固定深度经典阈值电路的下界。当时缺少的是量子态的自然性质概念与布尔函数的自然性质概念之间的联系。这篇论文通过把障碍直接放在量子态的性质上，避免了需要这样的对应关系。

该壁垒并不专属于 Magic Hierarchy。任何能够模拟制备论文中伪随机振幅列表族各态的电路的制备模型，都会继承相应的壁垒。作者使用该层级体系来追踪所需的电路资源并给出定量界，并指出同样的障碍也适用于固定深度的其他常数深度模型。

伪随机振幅列表把有用性变成矛盾

核心的技术对象是伪随机振幅列表族：一个纯态集合，即使一个经典算法拿到完整的有限精度振幅列表、并拥有该列表长度的多项式时间，它看起来仍像 Haar 随机。该族支持任意多项式有界的振幅精度。若族中的某个态可以由模型 C 中多项式规模的电路以误差 e 制备，则称它是 e-近似 C-可制备的；这要求每个态都有一个小型制备电路，而不是要求存在高效采样该集合的过程。

壁垒的逻辑因此很短。如果这样一个族可以由 C 中多项式规模的电路以 e 的误差近似制备，那么没有任何自然性质对 C 的态制备是 e-有用的。一个有用的自然性质会拒绝这些伪随机态，而普遍性又会使它接受足够大比例的 Haar 随机态。由可构造性保证的识别算法因此会区分这两个集合，从而与伪随机性矛盾。

标准的伪随机态构造并不能直接满足需要。由伪随机函数构造的二元相位态，在给定多项式多个副本时，对多项式时间量子对手而言与 Haar 随机不可区分；但一个能看到完整振幅列表的对手可以轻易区分它，因为它的所有振幅大小都相同，为 2^{-n/2}，而 Haar 随机态的振幅大小是变化的。因此，论文采用基于高斯的框架，生成近似的复高斯分量并对所得向量归一化。

高斯采样加振幅加载隐藏了这些态

该构造包含三个概念步骤。第一，一个从 n 位串到 R 位串的随机函数 H 提供决定每个振幅的随机比特，一个采样器把这些比特转换为近似高斯样本。当 H 是随机的时候，它的取值相互独立，因此各振幅表现得像独立高斯样本；归一化之后，截断的振幅列表在统计上接近 Haar 随机态的振幅列表。

第二，目标态必须确实可制备。一个相干采样器计算与输入索引相关联的振幅的数值描述，一个振幅加载器把这些描述转换为归一化态的实际振幅。两个组件都在 Magic Hierarchy 的固定层级内实现，因此当 H 可以在固定层级内求值时，整个制备过程也保持在固定层级内。

第三，随机函数被替换为一个足够安全的伪随机函数。一个能区分所得振幅列表的测试可以被转化为伪随机函数的区分器：从函数计算振幅列表，然后运行该测试。构造整个振幅列表需要 2^{O(n)} 时间，因此普通的伪随机函数多项式时间安全性不够。作者把安全参数取为态参数和精度参数的足够大的多项式，使亚指数安全性同时覆盖这一运行时间和所需的区分优势。由于区分器接收的是经典振幅列表，该归约只需要经典亚指数安全的伪随机函数，而不需要更强的量子假设。

近似次数、基态与互信息都是自然的

论文表明，若干现有的态制备下界技术在其意义下是自然的。这些包括基于近似次数的论证、基于态不是局部哈密顿量唯一基态的论证，以及基于互信息的论证。每一种都可以被重新表述为识别一个可从振幅列表高效检验、且对很大比例 Haar 随机态成立的性质。

互信息的例子是在干净输出制备模型中展开的，该模型是有用性论证所必需的。互信息承诺性质被证明对干净输出 A1CQ 态制备是 e_MI-有用的，其中 e_MI(n) := 2^{-4n-10}。证明应用了一个已有的下界，并表明对于足够大的 n，一个近似可干净制备的态必须落入 NO 集合。因此，相应的自然证明壁垒使用一个同样可在干净输出模型中制备的伪随机振幅列表族。

论文还给出了一个对受限模型确实有效的自然证明的简单例子。考虑所有非单位 Pauli 期望的绝对值都远离 1 的态，即 max_{P != I} |<psi|P|psi>| < 0.9。这一条件可以在多项式时间内从振幅列表检验，并以高概率对 Haar 随机态成立；而 Clifford 电路制备的每个态都有许多绝对值等于 1 的非单位 Pauli 期望。这为 Clifford 电路这一受限态制备模型证明了困难性。

QAC^0 与酉实现仍待解决

只要伪随机振幅列表族中的态可以在所关注的电路模型内制备，该壁垒就适用。因此，把它扩展到更弱的模型，等价于问：能否用更少的计算资源制备可比的族。一个特别值得关注的目标是 QAC^0，它包含在 Magic Hierarchy 所涵盖的更强的常数深度模型中，但被猜想为严格更弱。

近期工作表明，现有技术正接近一个阈值。在多项式多个不受限辅助比特下，已知最强的下界只能达到非常小的常数深度；对于任意常数深度，已知结果需要对辅助比特数量或电路规模施加额外限制。一项结果表明，计算 PARITY 的深度为 d 的 QAC^0 电路至少需要 n^{1+3^{-d}} 个辅助比特，而该工作的作者指出，若能把这一结果强化到 n^{1+exp(-o(d))}，就已经能推出 PARITY 不属于 QAC^0。

伪随机酉，以及通常副本访问意义下的伪随机态，可以由多项式规模的 QAC^0 电路以高精度实现。对该壁垒而言不足的是安全性保证：现有构造只对拟多项式时间对手安全，而拿到完整振幅列表的区分器可能运行 2^{O(n)} 时间。强化这一安全性将为 QAC^0 的自然证明壁垒提供一条有前景的路径。

对于酉实现，论文提出了自然酉性质的相应概念，并指出了能推出壁垒的伪随机矩阵对象，但没有从密码学假设构造出该对象。酉情形看起来在定性上更难：对完整酉矩阵用高效布尔预言机实现复现统计随机函数阶段，就已经能解决 Aaronson-Kuperberg 酉合成问题。作者表明，有限精度矩阵描述在精度 T = n+10 下的统计接近性，将给出具有多项式查询复杂度、多项式布尔预言机输入长度、且菱形范数误差至多 1/10 的酉合成。

决定性问题在于技术是否自然

对于评估某个态制备下界提议的读者来说，论文最有用的区分不是该下界针对哪个电路类，而是该证明是否自然。如果一种技术可以被重新表述为一个可从完整振幅列表高效检验、且对很大比例 Haar 随机态成立的性质，那么在所述经典密码学假设下，它无法建立超多项式下界，即使针对 Magic Hierarchy 的固定层级也不行。具体的推论把层级明确化：如果 Naor-Reingold 伪随机函数构造是经典亚指数安全的，那么没有任何自然性质对 Magic Hierarchy 第 52 层中用于态制备的多项式规模电路是有用的。

这重新界定了实际的优先事项。值得关注的前沿并不是简单地把某个已知的自然技术推向更强的电路模型，因为壁垒会随该技术一起移动。进展需要一种在这一意义下不自然的证明方法，或者一个无法在所研究模型内制备的伪随机振幅列表族。QAC^0 的情形说明了第二条路径：缺失的要素是一个安全性能够对抗运行 2^{O(n)} 时间的区分器的构造，而不仅仅是对抗拟多项式时间的区分器。

论文自身的边界同样具体。该壁垒以经典亚指数安全、可由多项式规模、深度为 d 的阈值电路实现的伪随机函数为条件，并且是针对 e^{-n} 近似制备陈述的。它并未表明强的态制备下界不可能，也没有构造酉对应版本所需的伪随机矩阵对象。它表明的是，包括近似次数、唯一基态障碍和互信息在内的一大类现有论证，无法单凭自身给出更强的下界，因此下一步必须来自这一类之外。

本文引用的文献