量子查询复杂度的组合

形式陈述

设外层函数 $f:S\to E$ ， $S\subseteq\{0,1\}^m$ ；内层是 Boolean-valued partial function $g:D\to\{0,1\}$ ， $D\subseteq\Sigma^n$ 。对 $m$ 个独立 blocks $x^{(1)},\ldots,x^{(m)}\in D$ ，定义

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

其自然域还要求输出向量 $(g(x^{(1)}),\ldots,g(x^{(m)}))\in S$ 。在这个标准 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)).

等式依赖内层输出为一个 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，故乘法定理不适用。

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.
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.

形式陈述 ​

形式陈述