量子查询复杂度的组合

形式陈述

取正整数 $m,n$ 、有限非空 $\Sigma,E$ 、非空 $S\subseteq\{0,1\}^m$ 与 $D\subseteq\Sigma^n$ 。设外层函数 $f:S\to E$ ；内层是 $g:D\to\{0,1\}$ ，并先假设 $g$ 确实取到两个输出值。查询单位是输入的完整符号坐标。对 $m$ 个独立 blocks $x^{(1)},\ldots,x^{(m)}\in D$ ，定义

F(x^{(1)},\ldots,x^{(m)}) =f(g(x^{(1)}),\ldots,g(x^{(m)})),

其自然域为 $D^m$ 中满足 $(g(x^{(1)}),\ldots,g(x^{(m)}))\in S$ 的全部输入，因此非空。这里“独立 blocks”指这一乘积与输出承诺形式，不是对输入分布作独立抽样假设。在这个标准 block composition 下，一般 adversary 界满足

\operatorname{Adv}^{\pm}(F) =\operatorname{Adv}^{\pm}(f) \operatorname{Adv}^{\pm}(g).

结合固定常数错误下 $Q(h)=\Theta(\operatorname{Adv}^{\pm}(h))$ ，得到

Q(F)=\Theta(Q(f)Q(g)).

这一等式来自两个方向。LMRSS 的 Lemma 5.1 给 $\operatorname{Adv}^{\pm}(F)\le\operatorname{Adv}^{\pm}(f)\gamma_2(J-G\mid\Delta)$ ，其中 $G_{xy}=\mathbf1[g(x)=g(y)]$ ；Boolean 输出时，该状态转换距离由同文 Theorem 3.4 等于 $\operatorname{Adv}^{\pm}(g)$ 。反向使用 Lemma 5.2 的对偶解提升：只保留外层标签落在 $S$ 的行列，半正定约束仍成立；每个合法标签的内层纤维完整保留，目标值与归一化的乘积计算不变。本文引用这两个组合引理，不从直接串接两个有误差算法来证明乘法性。[1, §5、Appendix C]

等式依赖内层输出为一个 Boolean bit，使外层的 query filters 与内层 state conversion 对齐；不同内层 $g_j$ 时应使用带 coordinate costs 的 general adversary，而不是把不等成本强行乘同一个数。

算法层也要保持 coherent oracle 接口。若 $g$ 有 clean exact unitary $B$ ，一次外层 bit query可由 $B$ 计算内层输出、控制翻转外层 answer、再以 $B^\dagger$ 清理，成本约为两次内层算法。若 $B$ 只有 bounded error，直接替换会让误差在叠加 blocks 和多轮调用中相干累积；需使用稳健组合、state-conversion 构造或额外放大，不能把一次成功概率当成完美 oracle。

直觉

外层算法每次想读取一个 summary bit $g(x^{(j)})$ ，内层算法负责从第 $j$ 块生成这个 bit。General adversary 的分子、单坐标 filters 与 costed SDP 恰好按层级张量化，所以“外层难度乘内层难度”同时给下界和存在性上界。

具体内层过程可以来自振幅放大或量子 walk，但只有整理成可逆、可清理、错误受控的 bit/phase oracle 后才能被外层相干调用。模块名字相接不等于查询接口已经组合。

例子与边界

取 total functions $f=\operatorname{OR}_m$ 、 $g=\operatorname{OR}_n$ 。每个 block 有 $n$ bits，且

\operatorname{OR}_m\circ\operatorname{OR}_n^m =\operatorname{OR}_{mn}.

General adversary 对 OR 的值为 $\Theta(\sqrt k)$ ，所以

\operatorname{Adv}^{\pm}(\operatorname{OR}_{mn}) =\Theta(\sqrt{mn}) =\Theta(\sqrt m\,\sqrt n).

算法上可把内层搜索构造成受控 phase 判断，再做外层Grover 搜索；稳健实现总查询 $O(\sqrt m\sqrt n)$ 。直接“每个 block 先测一次内层结果”会破坏外层叠加，不是这条上界的实现。

相关 promise 给出明确反例。若额外承诺所有 $m$ 个 blocks 完全相同，则 $\operatorname{OR}_m(g(x^{(1)}),\ldots,g(x^{(m)}))$ 其实只等于一次 $g(x^{(1)})$ ，复杂度为 $\Theta(Q(g))$ ，而非 $\Theta(\sqrt m\,Q(g))$ 。该联合域不是独立 block promise，故乘法定理不适用。

若 $g\equiv c$ ，只有 $c^m\in S$ 时组合域才非空，此时 $F$ 为常函数、复杂度为零；若 $c^m\notin S$ ，不存在合法组合输入，不纳入本页的非空任务约定。

Relation-valued 内层、跨 block 共享 oracle、无限输出集或输入相关查询 costs 也需重建模型。Polynomial、正权 adversary 和 approximate degree 各有自己的 composition theorem 与附加条件；general adversary 的乘法性不能替它们无条件背书。

推论与应用

组合定理允许把最优 query gadgets 层层嵌入公式、树形计算与 modular oracle algorithms，并用同一个 costed SDP 追踪非均匀 blocks。它还说明 tight lower bound 可随结构传播，而不必为每个组合函数从零构造矩阵。

应用时应依次检查：每块是否独立落在 $D$ 、内层是否 Boolean-valued、外层 promise 是否只依赖这些输出 bits、算法是否实现 clean coherent oracle、错误是否在固定常数范围。任一项失败，都只能把现成乘法式当作猜想而非证明。

参考资料

Peter Høyer, Troy Lee, and Robert Špalek, “Negative Weights Make Adversaries Stronger,” Proceedings of STOC 2007, pp. 526–535.
Ben W. Reichardt, “Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function,” Proceedings of FOCS 2009, pp. 544–551.
[1] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy, “Quantum Query Complexity of State Conversion,” Proceedings of FOCS 2011, pp. 344–353；Theorem 3.4、Lemmas 5.1–5.2 与 Appendix C 的组合证明。

形式陈述 ​

形式陈述