Promises should be taken seriously: On relativization with promise problems

技术摘要：必须认真对待承诺问题：论带有承诺问题的相对化

问题陈述
本文研究了当计算复杂度类在访问“承诺问题”（promise problems）而非标准语言时，其相对化行为的变化。在标准的相对化中，预言机（oracle）为每个查询提供确定的答案（0 或 1）。相比之下，一个承诺问题 $\Pi = (\Pi_{yes}, \Pi_{no})$ 仅对属于承诺集 $\Pi_{yes} \cup \Pi_{no}$ 内的输入进行约束；对于承诺之外（off-promise）的输入，则不作约束。

核心难点在于，标准的预言机访问定义假设了一个全函数。对于承诺问题，必须定义机器在查询承诺之外的输入时如何表现。作者分析了两种不同的访问语义：

1. 鲁棒查询（Robust Queries）： 机器必须无论如何完成（completion）承诺中的离承诺输入都能正确解决问题（即对于承诺的所有完成方式 $A$，机器都成功）。
2. 松散查询（Loose Queries）： 机器的内部选择（例如随机字符串或见证/witnesses）在选择完成方式之前即已固定。机器必须使用相同的内部选择对所有完成方式都成功。

本文探讨了已知于语言的相对化结果（例如 $BPP \subseteq P/poly$，$Toda$ 定理）在这些语义下是否能转移到承诺问题。

方法论
作者结合使用了相对化技术、预言机构造和算术化方法：

• 预言机构造： 为了分离基于语言的结果与基于承诺的结果，作者通过结合一个 PSPACE 完全语言与一个相对于 PSPACE 的 Cohen-generic 集来构造特定的预言机 $O$。他们在该 generic 集中编码了 Simon 问题的独立实例。
• 直接积界限（Direct-Product Bounds）： 他们利用直接积界限 (Dru12) 来论证带有建议（advice）的机器无法同时解决编码在预言机中的所有 Simon 问题的独立实例，从而在这一相对化世界中分离了 $PromiseBQP$与$PromiseP/poly$。
• 松散访问与算术化： 为了改进量子-经典多项式层级（$QCPH$）的上界，作者改编了 $Toda$ 定理。他们引入了一个“松散访问无歧义层级”（loose-access unambiguous hierarchy），并使用精确算术化（通过 GapP 函数表示接受概率）将随机种子压缩为单个查询。这使得他们能够绕过 $PromiseBQP$不能简单地被替换为$BQP$ 中任意完成方式的问题。
• 通过随机阈值实现自低性（Self-Lowness）： 为了证明 $PromiseBQP$的自低性结果，作者解决了离承诺查询的接受概率可能任意接近$1/2$ 的问题。他们将离承诺区间划分为子区间，并为每个查询分配一个随机阈值，从而确保模拟误差保持在多项式级微小。
• 后选择变体： 为了处理计数结果，他们引入了 $PromisePostBQP^*$，这是 $PostBQP$的一个变体，其中后选择电路仅取决于输入长度，而非输入本身。这使他们能够弥合$PromiseYQP^*$与$PP$ 之间的差距。

主要贡献与结果

1. 语言与承诺设置的分离：
   作者构造了一个预言机 $O$，使得：
   $$P^O = BPP^O = BQP^O = AWPP^O$$
   然而，
   $$PromiseBQP^O \not\subseteq PromiseP^O/poly$$
   这证明了对于语言成立的结果（如 $BPP \subseteq P/poly$）并不一定能转移到承诺问题。具体而言，它回答了 Nisan 关于是否存在一个预言机使得 $BPP = BQP$ 但 $PromiseBQP \neq PromiseBPP$ 的问题。这强调了承诺问题的“完成方式”不能被假定属于对应的语言类。

2. 改进 $QCPH$ 的上界：
   通过使用松散预言机访问，作者改进了量子-经典多项式层级（$QCPH$）的上界。他们证明了：
   $$QCPH \subseteq BP \cdot PP \subseteq PromiseBPP^{PP}$$
   这改进了此前自该类引入以来一直未曾改变的最佳上界 $PP^{PP}$。该证明通过适配 $Toda$ 定理来直接处理承诺问题，利用了松散访问无歧义层级和 GapP 算术化。作为推论，他们表明 $PP^{PromiseBQP} = PP$。

3. $PromiseBQP$ 的自低性：
   作者确立了 $PromiseBQP$ 在鲁棒查询下是自低的，即使带有量子建议：
   $$PromiseBQP^{PromiseBQP} = PromiseBQP$$
   $$PromiseBQP^{PromiseBQP/qpoly} = PromiseBQP/qpoly$$
   这是通过随机化用于模拟查询的阈值来实现的，确保即使在离承诺概率接近 $1/2$ 时，模拟误差也是可以忽略不计的。

4. 对计数层级坍缩的阻碍：
   论文表明 $GapP \subseteq FP^{PromiseAWPP}$。因此，如果 $PromiseAWPP \subseteq PromiseBQP/qpoly$，则计数层级（$CH$）将坍缩至 $YQP^*$。这表明 $PromiseAWPP$和$PromiseBQP$ 很可能是不同的。
   此外，虽然 $AWPP$ 在语言设置下对于 $PP$ 是低的（$PP^{AWPP} = PP$），但作者展示了对于承诺类的直接类比会导致计数层级坍缩。为了解决这个问题，他们引入了 $PromisePostBQP^*$ 并证明：
   $$PP^{PromisePostBQP^*} = PP \implies PP^{PromiseYQP^*} = PP$$

意义
本文认为，对于语义复杂度类（由接受概率而非句法约束定义的类），处理离承诺查询是至关重要的，且不能被忽视。研究结果表明：

• 语言的相对化结果并不会自动转移到承诺问题。
• “鲁棒”与“松散”查询语义的选择会显著改变所得复杂度类的能力。
• 标准技术（如算术化和自低性证明）在应用于承诺问题时需要仔细适配（例如通过随机化阈值或限制后选择），以避免错误的结论或计数层级的坍缩。

这项工作为在相对化世界中分析承诺问题提供了一个严谨的框架，阐明了将基于语言的复杂度结果扩展到承诺设置时的局限性。