Boolean 公式求值

一个 read-once Boolean 公式 是一棵树：叶子是输入位 $x_1,\dots ,x_N$，每个变量只出现一次，内部节点是常数 fan-in 的门（AND、OR、NAND 等）。给定向 $x\in \{0,1{\}}^N$ 的查询 oracle，目标是用尽量少的查询算出公式值 $f(x)$。

朴素算法可能必须查询全部 $N$ 个叶子；而量子算法能以 $\Theta (\sqrt{N})$ 次查询求值任意常数 fan-in 的 read-once 公式。这是查询复杂度中最漂亮的结果之一：它不是”每层套一次 Grover”的简单递归——那种做法会丢掉对数因子，并且在不平衡树上还会更糟——而是来自 span program 与 general adversary bound 之间的精确对应。本词条的目标是把这条链完整讲一遍：

$$\text{公式}⟶\text{span program}⟶\text{双反射量子算法}⟷\text{对抗界（下界）}.$$

读完后你应当理解：为什么 $\sqrt{N}$ 是最优的、量子算法从哪里”省下”了查询、以及为什么一般性的对抗界方法本身就是一个算法设计方案。

前置知识：的 Grover 算法 与振幅放大、相位估计；的线性代数记号（投影、谱分解）。我们会在用到的地方简要回顾，但不重新推导。

1. 从 NAND 树看问题

1.1 问题的精确表述

以最基本的平衡二叉 NAND 树为例。它递归定义为

$$F_v=\mathrm{NAND}(F_{v_L},F_{v_R}),\mathrm{NAND}(a,b)=\neg (a\wedge b),$$

叶子 $F_v=x_i$。若树有 $N=2^d$ 个叶子（深度 $d$），则输出是根的 $F$ 值。注意 NAND 在经典计算意义下是通用门（任何 Boolean 线路都可以用 NAND 重写），所以 NAND 树已经捕捉到公式的本质难度；而任意 AND/OR/NOT 混合的常数 fan-in 公式最终都能归结到同一复杂度。

输入通过查询 oracle 给出：算法一次查询可以问”$x_i$ 等于多少”，代价计为一次查询。我们关心的是最坏情形查询复杂度 $Q(f)$（允许有界错误概率，比如 $1/3$；由标准重复放大，常数误差不影响 $\Theta$ 阶）。

1.2 经典算法能做到什么

确定性算法：最坏情况必须查满 $N$ 个叶子。直觉是对手论证（adversary argument）：无论算法按什么顺序查询，对手都可以把已查叶子的回答安排成”子树值到最后一刻才被钉死”。形式地说，NAND 树的输出对它的 $N$ 个叶子是完全敏感的（evasive）：确定性决策树复杂度 $D(f)=N$。这是 20 世纪 70 年代决策树理论研究 evasiveness 猜想时的经典例子。

随机化算法：可以做得明显更好，关键是短路求值。以根节点为例：先随机选择递归求值 $F_{v_L}$ 或 $F_{v_R}$。若先算出的子树值为 $0$，则 $\mathrm{NAND}(0,\cdot )=1$，另一棵子树完全不用算。只有当两棵子树都必须求值时才付出双倍代价。对”两棵子树都为 $1$“的最坏输入分析这个随机递归，可得期望查询数 $N^{\alpha }$，其中 $\alpha ={\log }_2\frac{1+\sqrt{33}}{4}\approx 0.753$（Snir 提出该随机递归方案，Saks–Wigderson 证明这是平衡 AND–OR 树的最优随机复杂度）。注意

$$\alpha \approx 0.753>\frac{1}{2}:$$

即使是最好的经典随机算法，查询数也严格大于 $\sqrt{N}$。这就是量子算法要击败的标杆。

1.3 量子侧的历史脉络

• Farhi–Goldstone–Gutmann（参考文献中的 Farhi 等）首先对平衡 NAND 树给出 $O(\sqrt{N})$ 查询级别的算法。他们的模型不是查询线路，而是连续时间 Hamiltonian 演化：构造一个由输入决定的哈密顿量 $H(x)$，让态沿一条”从叶子到根”的路径传播，通过透射/反射行为读出公式值。这个构造物理图像很美，但把连续时间演化转成离散查询模型需要额外工作（Childs 等人的后续结果完成了这一转换）。
• Reichardt–Špalek（arXiv:0710.2630）引入 span program 这一线性代数框架，把”公式求值算法”的设计变成”为公式找一个好的线性代数表示”，并把结果推广到任意（包括不平衡的）AND–OR 树，随后扩展到一般 read-once 公式。
• 与此同时，Høyer–Lee–Špalek 提出 negative-weight adversary bound（general adversary bound）作为下界工具；Reichardt 证明它的对偶半定规划恰好就是 span program 的 witness size，并给出以 $O({\mathrm{Adv}}^{\pm }(f))$ 查询运行的通用双反射算法（arXiv:1005.1601）。于是”下界方法”与”上界算法”合拢：

$$Q(f)=\Theta \left({\mathrm{Adv}}^{\pm }(f)\right)\text{对所有（部分）函数 }f.$$

下面各节按”span program 是什么 → 它怎样变成算法 → 为什么它同时也是下界 → 为什么公式给出 $\sqrt{N}$“的顺序展开。

2. Span program 的线性代数定义

2.1 定义

一个 span program $P$ 由以下数据构成：

• 一个有限维内积空间 $\mathcal{H}$（后面取为某个 ${\mathbb{C}}^m$）；
• 一个目标向量 $|\tau ⟩\in \mathcal{H}$，$|\tau ⟩\ne 0$；
• 一族输入向量

$$\{|v_{j,b,\ell }⟩\}\subseteq \mathcal{H},$$

其中 $(j,b)$ 遍历所有文字（literal，即”第 $j$ 位等于 $b$“这一断言，$j\in [n]$、$b\in \{0,1\}$），$\ell$ 是同一文字下的可选编号（一个文字可以带多个向量）。

给定输入 $x\in \{0,1{\}}^n$，称向量 $|v_{j,b,\ell }⟩$ 是可用的 (available)，当且仅当 $b=x_j$，即该文字被 $x$ 满足。程序接受 $x$ 当且仅当

$$|\tau ⟩\in \mathrm{span}\{\text{所有可用向量}\}.$$

也就是说：span program 把 Boolean 函数翻译成一个线性张成判定问题。我们称 $P$ 计算函数 $f$，如果 $f(x)=1$ 恰好对应程序接受 $x$。

记 $A$ 为以全部输入向量为列排成的矩阵，$\Pi (x)$ 为到”当前可用列”坐标子空间的投影，则 $A\Pi (x)$ 就是”只保留可用列”的矩阵，接受条件等价于

$$|\tau ⟩\in \mathrm{range}\left(A\Pi (x)\right).$$

2.2 手算小例子：OR 的 span program

取 $n$ 位 OR 函数 $f(x)=x_1\vee \cdots \vee x_n$。构造：$\mathcal{H}=\mathbb{C}$（一维），$|\tau ⟩=1$，对每个变量 $j$ 只配一个向量

$$|v_{j,1}⟩=1(\text{当 }{x}_j=1\text{ 时可用}),|v_{j,0}⟩=0(\text{当 }{x}_j=0\text{ 时可用}).$$

验证它确实计算 OR：

• 若 $f(x)=1$，存在 $j$ 使 $x_j=1$，此时 $|v_{j,1}⟩=1$ 可用，$\mathrm{span}$ 中包含 $1=|\tau ⟩$，接受。✓
• 若 $f(x)=0$，所有 $x_j=0$，可用向量全是 $|v_{j,0}⟩=0$，张成空间是 $\{0\}$，不含 $|\tau ⟩=1$，拒绝。✓

这个例子的意义在于：OR 就是 Grover 搜索判断”是否存在目标”的函数。后文会看到，它的 span program 复杂度恰好是 $\sqrt{n}$，与 Grover 的查询数一致——这不是巧合，双反射算法在这个特例上 precisely 退化为 Grover 迭代。

2.3 正、负 witness 与 witness size

仅有”接受/拒绝”还不够，算法需要定量的信息：接受时 $|\tau\rangle”容易”被张成到吗？拒绝时它”离”张成空间有多远？这两件事分别由两类 witness 度量。

正 witness（$f(x)=1$ 的情形）：是系数向量 $|w⟩$，满足

$$A\Pi (x)|w⟩=|\tau ⟩,$$

即它给出把 $|\tau ⟩$ 写成可用向量线性组合的具体系数。其成本定义为 $\Vert w{\Vert }^2$。直觉：系数越小，说明用”很小的权重”就能合成目标，这个接受实例越”容易”。定义正 witness size

$${\mathrm{wsize}}_1(P)=\underset{x:f(x)=1}{\max }\underset{|w⟩:A\Pi (x)|w⟩=|\tau ⟩}{\min }\Vert w{\Vert }^2,$$

内层取该输入下的最优（系数平方和最小）表示，外层取最难的接受输入。

负 witness（$f(x)=0$ 的情形）：是向量 $|\omega ⟩\in \mathcal{H}$，满足

$$⟨\omega |\tau ⟩=1,⟨\omega |A\Pi (x)=0,$$

第二个等式表示 $|\omega ⟩$ 与所有可用向量正交。它的存在性由线性代数保证：$|\tau ⟩\notin \mathrm{range}(A\Pi (x))$ 意味着 $|\tau ⟩$ 在其正交补上有非零投影，把该投影归一化到与 $|\tau ⟩$ 内积为 $1$ 即得 $|\omega ⟩$。换句话说，负 witness 是一个把”目标”与”可用向量的张成空间”分开的超平面的法向量。其成本定义为

$$\Vert A^{†}|\omega ⟩{\Vert }^2=\sum _{j,b,\ell }|⟨\omega |v_{j,b,\ell }⟩{|}^2,$$

注意求和跑遍全部输入向量（包括不可用的）：可用列上内积恒为 $0$，所以这个成本度量的是 $|\omega ⟩$ 在”被输入禁用的那些列”上泄漏了多少。定义负 witness size

$${\mathrm{wsize}}_0(P)=\underset{x:f(x)=0}{\max }\underset{|\omega ⟩}{\min }\Vert A^{†}|\omega ⟩{\Vert }^2.$$

Span program 的 witness size 取两者的几何平均（等价地，有归一化版本把 $⟨\omega |\tau ⟩$ 等约束吸收进去，两者给出同一 $\Theta$ 阶量）：

$$W(P)=\sqrt{{\mathrm{wsize}}_0(P)\cdot {\mathrm{wsize}}_1(P)}.$$

2.4 小例子续：OR 的 witness size

继续 2.2 的构造，把两个 witness size 实际算出来。

正 witness：设 $f(x)=1$。方程 $A\Pi (x)|w⟩=|\tau ⟩$ 在坐标上读作 ${\sum }_{j:x_j=1}{w}_j\cdot 1=1$。由 Cauchy–Schwarz，$\Vert w{\Vert }^2\ge 1/(\text{可用非零列数})$，取等当且仅当把系数均分给所有可用列。最难的输入是恰好一个 $x_j=1$：此时只能取 $w_j=1$，$\Vert w{\Vert }^2=1$。所以

$${\mathrm{wsize}}_1(P)=1.$$

负 witness：唯一的拒绝输入是 $x=0^n$。约束 $⟨\omega |\tau ⟩=1$ 即 $\omega =1$；可用列全为零向量，正交约束自动满足。成本

$$\Vert A^{†}|\omega ⟩{\Vert }^2=\sum _j|⟨\omega |v_{j,1}⟩{|}^2=\sum _j|1{|}^2=n$$

（只有不可用列 $|v_{j,1}⟩=1$ 有贡献，$|v_{j,0}⟩=0$ 不贡献）。所以 ${\mathrm{wsize}}_0(P)=n$，于是

$$W(P)=\sqrt{1\cdot n}=\sqrt{n}.$$

这与 Grover 的 $\Theta (\sqrt{n})$ 次查询遥相呼应。下一节把这个呼应变成定理。

3. 两个反射怎样读取 witness

3.1 从 Grover 继承的骨架

回顾 Grover 算法 的结构：迭代算子 $G=U_S{U}_O$ 是两个反射的乘积——一个依赖输入（翻转目标相位），一个与输入无关（关于均匀叠加态的反射）。两个反射的乘积在由两条反射轴张成的平面里是旋转，旋转角由两轴夹角决定；相位估计/重复迭代把”夹角大小”转成”查询次数”。

Span program 算法把这一骨架推广到任意 Boolean 函数。核心观察是：witness size 扮演了 Grover 中”两轴夹角”的角色——$W(P)$ 越小，两个子空间”越接近相交”（接受）或”越容易分开”（拒绝），所需的迭代/相位估计精度就越低。

3.2 两个反射的构造

由 $P$ 构造两个子空间（的具体线性代数实现见 Reichardt 与 Lee–Magniez–Reichardt 等文献；这里给出功能刻画）：

输入无关的反射。构造一个只依赖 $A$ 与 $|\tau ⟩$、不依赖 $x$ 的子空间 $\Lambda$（典型取法是某个增广矩阵 $\tilde{A}$ 的 kernel——把 $A$ 与 $|\tau ⟩$ 按”目标必须被表示”这一约束拼接起来得到的矩阵），定义反射

$$R_{\Lambda }=2\Lambda -I,$$

它在 $\Lambda$ 上为 $+1$、在 ${\Lambda }^{\perp }$ 上为 $-1$。直觉：$\Lambda$ 编码了”线性代数结构本身的约束”，与输入无关，因此实现它不花查询（但可能花门——见第 6 节）。

输入相关的反射。令 $\Pi (x)$ 为”可用列”投影，定义

$$R_x=2\Pi (x)-I,$$

它翻转”当前不可用列”方向的相位。这正是一个按位标记的相位 oracle：判断”第 $j$ 列标签 $(j,b)$ 是否满足 $b=x_j$“只需一次输入查询，所以实现 $R_x$ 花费常数次查询（具体为 $O(1)$，把标签寄存器的 $(j,b)$ 与查询结果比较即可）。

迭代算子。算法研究酉算子

$$U_x=R_{\Lambda }{R}_x,$$

并从某个固定的起始态 $|w_0⟩$（与 $|\tau ⟩$ 相关、可高效制备）出发。这就是”oracle 相位反射 × 初态反射”结构的普适推广：Grover 是它对应于 OR 的 span program 的特例。

3.3 谱结构：witness 怎样控制相位

两个反射的乘积有标准的谱理论：$U_x$ 的本征值都成对出现在单位圆上 $e^{\pm i\theta }$，其本征相位由 $\Lambda$ 与 $\Pi (x)$ 像空间之间的 principal angles（主夹角） 决定。对当前构造，起决定作用的是近零相位（对应主夹角接近 $\pi /2$），而 span program 的两类 witness 恰好从两个方向夹住这部分谱：

• 若 $f(x)=1$：正 witness $|w⟩$ 给出 $|\tau ⟩$ 的显式线性组合，由此可直接构造 $U_x$ 的一个零相位（或近零相位）本征向量，它与起始态 $|w_0⟩$ 的 overlap 下界由 ${\mathrm{wsize}}_1$ 控制（roughly：overlap² $\gtrsim 1/(1+\Vert w{\Vert }^2)$ 量级）。也就是说，接受输入会在相位 $\approx 0$ 处”放一个”起始态能看到的本征向量。
• 若 $f(x)=0$：负 witness $|\omega ⟩$ 提供一个分离超平面，用它可证起始态在一个相位间隙内几乎没有谱质量：所有相位落在 $|w_0⟩$ 上谱测度非平凡的本征值都满足

$$|\theta |\ge \Omega \left(\frac{1}{W(P)}\right),$$

间隙宽度由 witness size 控制。直观地说，拒绝输入把起始态”推离”零相位区域，推开的距离正比于 $1/W(P)$。

（这两条统称为 effective spectral gap lemma 的内容，完整证明见参考文献；这里的关键点是两个方向的常数都由同一个量 $W(P)$ 决定，这正是正、负 witness 取几何平均的原因。）

3.4 相位检测：从谱间隙到查询复杂度

于是问题归约为：判断 $U_x$ 在起始态上是否存在近零本征相位。这正是相位估计（见 相位估计）的标准任务：

1. 以精度 $\epsilon$ 对 $U_x$ 在 $|w_0⟩$ 上做相位检测（“存在零相位分量吗”），需要的受控 $U_x$ 调用次数为 $O(1/\epsilon )$——相位估计的成本与目标精度成反比；
2. 接受与拒绝两种情形的相位标度差为 $\Omega (1/W(P))$，故取 $\epsilon =\Theta (1/W(P))$ 即可区分；
3. 每次受控 $U_x$ 含常数次 $R_x$，每次 $R_x$ 花 $O(1)$ 次输入查询。

把三层的成本相乘，总查询复杂度为

$$O\left(\frac{1}{\epsilon }\right)=O\left(W(P)\right).$$

逐项解释这个复杂度表达式的来源：因子 $W(P)$ 来自相位估计精度（间隙宽度）；$R_{\Lambda }$ 与 $R_x$ 内部的常数因子被吸收进 $O(\cdot )$；成功概率为常数（必要时用标准技巧放大）。

于是整个算法设计问题被彻底线性代数化：

要为 $f$ 设计量子查询算法，只需为 $f$ 找一个 witness size 小的 span program。

剩下的唯一问题是：给定一个公式，怎样找到好的 span program？答案由对抗界给出——它告诉我们最好的 span program 有多好。

3.5 对照：OR 特例退回 Grover

把第 2 节为 ${\mathrm{OR}}_n$ 构造的 span program（$W(P)=\sqrt{n}$）代入本节框架，每一步都能与我们熟悉的 Grover 分析对上：

• 相位间隙：$f(x)=0$（即 $x=0^n$）时的间隙 $\Omega (1/W(P))=\Omega (1/\sqrt{n})$，正是 Grover 迭代转角 $2\theta \approx 2/\sqrt{n}$（见 Grover 算法 的 Theorem 4）——拒绝输入时所有本征相位离 $0$ 至少这么远；
• 近零相位分量：$f(x)=1$ 时存在与起始态有常数级 overlap 的近零相位本征向量，对应 Grover 中”有目标时迭代把态转到目标方向”的事实；
• 查询数：相位估计精度 $\epsilon =\Theta (1/\sqrt{n})$ 给出 $O(\sqrt{n})$ 次查询，即 Grover 的迭代次数。

换句话说，Grover 算法是双反射算法在”最简 span program”上的特例；span program 框架的真正威力在于：当函数不是简单的 OR、而是任意嵌套的公式时，同样的”间隙—精度—查询数”换算仍然成立，只是间隙的来源从”目标的比例 $1/N$“换成了”witness size $W(P)$“。

4. General adversary bound 为何同时是下界与算法

4.1 从”混合论证”到矩阵

下界方法的经典直觉是混合论证 (hybrid argument)：如果算法只用 $T$ 次查询就能区分 $f(x)=1$ 的 $x$ 与 $f(y)=0$ 的 $y$，那么把 $x$ 逐位”改成” $y$，每次查询最多让算法状态偏移一点点；$T$ 次查询的总偏移必须足够大才能保持区分度。General adversary bound 把这个直觉打包成一个半定规划 (SDP)。

对（部分）Boolean 函数 $f$，选取一个 Hermitian 矩阵 $\Gamma$，其行列由输入索引，约束为

$${\Gamma }_{xy}=0\text{当 }f(x)=f(y)$$

（即 $\Gamma$ 只在”yes–no 输入对”之间有非零元；可以把行排 $f=1$、列排 $f=0$ 来看，它就是一个双邻接矩阵式的对象）。再定义”第 $j$ 位差异”掩膜矩阵

$$({\Delta }_j{)}_{xy}=1[x_j\ne y_j],$$

其中 $1[\cdot ]$ 是示性函数。General adversary bound 定义为

$${\mathrm{Adv}}^{\pm }(f)=\underset{\Gamma }{\max }\frac{\Vert \Gamma \Vert }{{\max }_j\Vert \Gamma \circ {\Delta }_j\Vert },$$

其中 $\Vert \cdot \Vert$ 是谱范数（最大奇异值），$\circ$ 是逐项 (Hadamard) 乘积，最大化跑遍所有满足约束的 $\Gamma \ne 0$。允许负权重（这是 "$\pm$" 的含义）是该版本强于早期正权 adversary 方法的关键。

逐项解释这个比值：

• 分子 $\Vert \Gamma \Vert$：衡量 $\Gamma$ 选出的 yes/no 输入对之间的”总体相干性”——算法最终必须在态空间中把这些对分开，分子越大说明要分开的”重量”越大；
• 分母 ${\max }_j\Vert \Gamma \circ {\Delta }_j\Vert$：把 $\Gamma$ 限制到”仅靠第 $j$ 位区分”的那些对上后的范数，衡量一次针对第 $j$ 位的查询最多能搬运多少相干性。逐位掩膜对应混合论证中”一次查询只能暴露一位信息”的事实；
• 整个比值因而是”总工作量 / 单次查询最大进度”，即所需查询数的下界：

$$Q(f)=\Omega \left({\mathrm{Adv}}^{\pm }(f)\right).$$

标准的混合论证给出 $Q(f)\ge \frac{1-\text{常数误差项}}{2}\cdot {\mathrm{Adv}}^{\pm }(f)$ 型的定量版本；我们只需 $\Omega$ 阶。

4.2 手算小例子：OR 的对抗界

对 $f={\mathrm{OR}}_n$ 选一个具体的 $\Gamma$：行由所有 $f(x)=1$ 的 $x$ 索引、列由唯一的拒绝输入 $y=0^n$ 索引（其余行列全零），并只在重量为 $1$ 的输入 $x=e_i$（第 $i$ 位为 $1$）处放

$${\Gamma }_{e_i,0^n}=1.$$

• 分子：$\Gamma$ 只有一列非零，该列是 $n$ 维向量 $(1,1,\dots ,1{)}^T$（在 $e_i$ 行上），故 $\Vert \Gamma \Vert =\sqrt{n}$；
• 分母：$(\Gamma \circ {\Delta }_j{)}_{e_i,0^n}={\Gamma }_{e_i,0^n}\cdot 1[(e_i{)}_j\ne 0]$，只有 $i=j$ 时为 $1$，即每列掩膜后只剩一个非零元，$\Vert \Gamma \circ {\Delta }_j\Vert =1$。

代入定义：

$${\mathrm{Adv}}^{\pm }({\mathrm{OR}}_n)\ge \frac{\sqrt{n}}{1}=\sqrt{n}.$$

另一方面 Grover 算法给出 $Q({\mathrm{OR}}_n)=O(\sqrt{n})$，结合下界公式即得 ${\mathrm{Adv}}^{\pm }({\mathrm{OR}}_n)=\Theta (\sqrt{n})$。对比 2.4 节 span program 算出的 $W(P)=\sqrt{n}$——两个框架在同一个例子上吻合，这正是下面定理所保证的。

4.3 对偶性：下界即算法

General adversary bound 是一个 SDP 的最优值。SDP 的强项在于对偶理论：每个 SDP 都有一个对偶 SDP，强对偶成立时两个最优值相等。Reichardt 证明了两件事：

1. ${\mathrm{Adv}}^{\pm }(f)$ 的对偶 SDP 可以直接转写成一个 span program 的 witness size 优化问题：对偶解正好给出输入向量 $\{|v_{j,b,\ell }⟩\}$ 与目标 $|\tau ⟩$，且

$$\underset{P\text{ 计算 }f}{\min }W(P)=\Theta \left({\mathrm{Adv}}^{\pm }(f)\right);$$

2. 第 3 节的双反射算法以 $O(W(P))$ 查询运行。

合起来得到查询复杂度的精确刻画：

$$Q(f)=\Theta \left({\mathrm{Adv}}^{\pm }(f)\right).$$

所以对抗界不是只会证明”不可能更快”的工具：它本身（通过对偶）编码了最优算法。给定任意函数 $f$，原则上解一个 SDP 就同时得到最优查询算法的查询复杂度与实现方案——这是查询复杂度模型区别于时间复杂度研究的独特现象（该结论只谈查询数；把 SDP 的解编译成低门复杂度线路是另一回事，见第 6 节）。

5. 公式组合为何给出 $\sqrt{N}$

5.1 单门的对抗值

回到公式求值。二输入 AND 与二输入 OR 互为取反（对输入或输出取反不改变查询复杂度），由 4.2 的对称论证，它们的对抗值都是 $\sqrt{2}$ 阶：

$${\mathrm{Adv}}^{\pm }({\mathrm{AND}}_2)={\mathrm{Adv}}^{\pm }({\mathrm{OR}}_2)=\Theta (\sqrt{2}).$$

一般地，常数 fan-in $k$ 的门，其对抗值是只依赖 $k$ 的常数（与输入规模无关），与 $\sqrt{k}$ 同阶。

5.2 复合定理：对抗值在函数复合下相乘

设 $f$ 是 $m$ 位函数、$g_1,\dots ,g_m$ 是作用在不相交变量组上的函数，记复合函数 $F=f\circ (g_1,\dots ,g_m)$。General adversary bound 满足复合定理：

$${\mathrm{Adv}}^{\pm }(F)=\Theta \left({\mathrm{Adv}}^{\pm }(f)\cdot \underset{i}{\max }{\mathrm{Adv}}^{\pm }(g_i)\right),$$

当各 $g_i$ 相同时就是严格的乘积（更精细的版本按各子问题成本加权组合，对不同的 $g_i$ 分别计权）。这个性质正是对抗界特别适合公式求值的原因：公式树就是函数复合的树，每个内部节点把子树的函数值复合起来。复合定理告诉我们，整棵树的难度是沿途各门难度的乘积——而不需要重新分析全局结构。

5.3 手算小例子：四叶 AND–OR 树

取 $F={\mathrm{OR}}_2\circ ({\mathrm{AND}}_2,{\mathrm{AND}}_2)$，即 $F(x_1,x_2,x_3,x_4)=(x_1\wedge x_2)\vee (x_3\wedge x_4)$，共 $N=4$ 个叶子。用复合定理：

$${\mathrm{Adv}}^{\pm }(F)={\mathrm{Adv}}^{\pm }({\mathrm{OR}}_2)\cdot {\mathrm{Adv}}^{\pm }({\mathrm{AND}}_2)=\sqrt{2}\cdot \sqrt{2}=2=\sqrt{N}.$$

换成深度为 $d$ 的平衡二叉树（$N=2^d$ 叶）：沿根到叶的每条路径有 $d$ 个门，每个门贡献一个 $\sqrt{2}$ 因子，故

$${\mathrm{Adv}}^{\pm }(F)=(\sqrt{2}{)}^d=2^{d/2}=\sqrt{N}.$$

这就是 $\sqrt{N}$ 的来源：每一层树深贡献一个平方根因子，而不是什么更微妙的机制。

5.4 从对抗值到 span program：权重沿路径相乘

由 4.3 的对偶转换，存在 span program 使 $W(P)=\Theta ({\mathrm{Adv}}^{\pm }(f))$；对 read-once 公式还可以直接递归构造 span program：每个门配一个小 span program，复合时把子程序的向量嵌入更大的空间。这时每个叶子的 witness 权重沿它到根的路径相乘——路径上有 $d_v$ 个门，叶子 $v$ 对总成本的贡献就带因子 $\prod (\text{沿途各门的权重})$。

• 平衡树：所有叶子深度相同，均匀取权重即得 $W(P)=O(\sqrt{N})$。
• 不平衡树：必须按子树大小设置不同权重（小的子树给较大的权重，因为它的对抗值较小、可以”花”更多），再做一次平衡缩放，使得各路径的权重乘积均匀。经过这样的缩放，任意大小为 $N$ 的常数 fan-in read-once 公式都满足

$$W(P)=O(\sqrt{N}).$$

这一”按子树规模加权”正是本词条开头所说”机械地在每层做相同 Grover 迭代反而会损失复杂度”的原因：递归 Grover 给每层分配同样的迭代次数与误差预算，等价于假设树平衡；而 span program/对抗界框架自动给出了正确的权重分配。

一个小型不平衡例子。设根为 ${\mathrm{OR}}_2$，左子树是 $4$ 叶的平衡 AND–OR 子公式（$N_L=4$），右子树是单叶（$N_R=1$），总叶子数 $N=5$。各部分的对抗值：左子树 $\sqrt{N_L}=2$，右子树 $\sqrt{N_R}=1$，根门 $\sqrt{2}$。若直接套用复合定理的”粗粒度”版本，以各子问题的对抗值加权，总对抗值为

$$\sqrt{2}\cdot \max \{2,1\}=2\sqrt{2}=\sqrt{8}>\sqrt{5},$$

这比 $\sqrt{N}$ 大——因为粗粒度复合按最难的那个子问题计费，浪费了右子树”很便宜”这一事实。正确的做法是给右子树（对抗值小）分配更大的权重系数 $c_R$，给左子树分配较小的 $c_L$，使两路加权后的成本拉平：

$$c_L\cdot \sqrt{N_L}=c_R\cdot \sqrt{N_R}⟹2c_L=c_R,$$

即右路的权重是左路的两倍；再做一次整体归一化（把所有权重同乘一个常数不改变接受/拒绝，只改变 witness size 的标度），使总成本最小。拉平后两路贡献相等，总规模 $N=N_L+N_R=5$ 代入即恢复 $W(P)=O(\sqrt{5})$。这个”弱者加权、强者减重、拉平路径”的原则，就是平衡缩放的一般机制；把它沿整棵树递归执行，即得不依赖平衡性的 $O(\sqrt{N})$。

5.5 下界与最优性

上界 $Q(f)\le O(W(P))=O(\sqrt{N})$ 已成立。下界同样由对抗界给出：公式包含 $N$ 个叶子，取 $\Gamma$ 为 OR 型（或沿一条根–叶路径构造适当 adversary）立即给出

$${\mathrm{Adv}}^{\pm }(f)=\Omega (\sqrt{N}),$$

从而 $Q(f)=\Omega (\sqrt{N})$。合上上界，任意常数 fan-in read-once 公式的量子查询复杂度恰为 $\Theta (\sqrt{N})$——与 $N$ 个叶子的 OR（Grover 搜索）同阶。换句话说：树结构带来的”短路”可能性，量子算法通过 witness 权重充分利用之后，并不会比裸的搜索更难，也不会更容易。

6. Read-many 与游戏树边界

6.1 变量重复出现的情形

以上假设 read-once（每个变量恰出现一次）。若变量可在公式中重复出现（read-many），记

• $N$：不同变量的个数；
• $S$：叶子出现总次数（即公式大小，$S\ge N$）；
• $G$：门的总数，

已知算法给出形如

$$O\left(\min \{N,\sqrt{S},N^{1/2}{G}^{1/4}\}\right)$$

的查询界。逐项解释三个候选因子：

• $N$：最坏情况把所有变量查一遍的朴素上界；
• $\sqrt{S}$：把公式当成”有 $S$ 个叶子但叶子有重复”来处理，span program 方法对叶子出现计权，给出与 $\sqrt{\text{大小}}$ 同阶的界；
• $N^{1/2}{G}^{1/4}$：把”不同变量数”与”门数”分开利用的混合界——在 $G\ll S$（许多叶子共享同一批门输出、公式有大量重复结构）时它优于 $\sqrt{S}$。取三者最小表示按实例形状选择最有利的一项。

求解参数平衡的示范：比较后两项，$\sqrt{S}=N^{1/2}{G}^{1/4}$ 两边平方得 $S=N{G}^{1/2}$，即 $S$ 与 $N\sqrt{G}$ 同阶时两项交叉；$S$ 小于此阈值时 $\sqrt{S}$ 占优，大于则 $N^{1/2}{G}^{1/4}$ 占优。当 $G\approx N$（每个变量”平均只喂给一个门”的稀疏情形），第三项为 $N^{3/4}$，优于 $\sqrt{S}$（若 $S\gg N^{3/2}$）也优于 $N$。

6.2 游戏树、有效电阻与保留条款

游戏树：带 promise 的 NAND 树（例如限制每个内部节点的两棵子树取值模式）中，不同输入下的有效门数或 average choice complexity 可以很小，此时可出现比 $\sqrt{N}$ 更大的量子–经典分离。这类结果强依赖 promise 结构，不能外推到无 promise 的公式——这是本节最重要的保留条款。

有效电阻：span program 的 witness size 有一个优美的电网络解释——把公式树看成一个电阻网络，正 witness 对应从根注入单位电流时各支路的电流分配，负 witness 对应电压分布，witness size 就是根到叶的有效电阻。这个对应既给出直观的计算工具（串并联公式、Y–Δ 变换都可用），也解释了”按子树大小加权”其实就是电路里的阻抗匹配。

查询 ≠ 时间：查询最优不自动意味着门时间最优。双反射算法每次迭代除了 $R_x$（便宜，$O(1)$ 查询）还要实现 $R_{\Lambda }$，后者可能涉及公式图的谱计算或稀疏线性代数：

• 对常数 fan-in 的 read-once 公式，$R_{\Lambda }$ 可以高效实现，总时间开销近线性（polylog 因子内），查询优势基本转化为时间优势；
• 但对任意 SDP 解出的 span program，其空间维数可能巨大，实现 $R_{\Lambda }$ 的门复杂度可能远超查询数。

因此引用本节任何复杂度时都应分清”查询复杂度”与”时间复杂度”两本账——本词条 index 中反复强调的 setup/update/check 成本区分，根源就在这里。

7. 小结与习题

小结：

• Span program 用”目标向量是否落在可用输入向量的张成空间”表示 Boolean 函数；正/负 witness 分别认证接受与拒绝，其成本（witness size）控制双反射算法所需的相位检测精度。
• 双反射算法 $U_x=R_{\Lambda }{R}_x$ 是 Grover 结构的普适推广：任何 span program 直接变成 $O(W(P))$ 查询的量子算法。
• General adversary SDP 与量子查询复杂度等价：$Q(f)=\Theta ({\mathrm{Adv}}^{\pm }(f))$；它的对偶解就是最优 span program，下界工具本身编码了最优算法。
• 对抗值在函数复合下相乘，每层树深贡献一个 $\sqrt{\cdot }$ 因子，故任意常数 fan-in read-once 公式（包括不平衡的）满足 $Q(f)=\Theta (\sqrt{N})$；正确处理不平衡树的关键是按子树规模分配 witness 权重。
• Read-many 公式有 $O(\min \{N,\sqrt{S},N^{1/2}{G}^{1/4}\})$ 型界；游戏树中的大分离依赖 promise；查询最优不等于门时间最优。

习题：

1. （定义）为二输入 AND 构造一个 span program（提示：在 OR 的构造基础上调整目标与向量的维度），写出接受输入与拒绝输入各自的正、负 witness，并计算 $W(P)$。
2. （谱结构）设 $U=R_{\Lambda }{R}_x$ 是两个反射的乘积。证明：若存在非零向量 $v\in \Lambda \cap \mathrm{range}(\Pi (x))$，则 $v$ 是 $U$ 的本征值 $+1$ 本征向量；并解释这说明”零相位本征向量”与”两子空间之交”的关系。
3. （对抗界计算）仿照 4.2 节，为 ${\mathrm{AND}}_2$ 显式写出达到 $\sqrt{2}$ 的矩阵 $\Gamma$，验证 $\Vert \Gamma \Vert =\sqrt{2}$ 与 ${\max }_j\Vert \Gamma \circ {\Delta }_j\Vert =1$。
4. （复合）用复合定理计算深度为 $3$ 的平衡二叉 NAND 树（$N=8$ 叶）的对抗值，并说明若改用”每层各做一次完整 Grover 搜索”的递归算法，为什么只能得到 $O(\sqrt{N}\mathrm{poly}(\log N))$ 而非 $O(\sqrt{N})$（从误差预算沿层数分配的角度论证）。
5. （不平衡树）考虑一棵左子树有 $N/2$ 叶、右子树只有 $2$ 叶的 OR–AND 型不平衡公式。定性说明：为什么给两个子树分配相同的权重不是最优的？应按什么原则分配？
6. （查询 vs 时间）举一个具体例子，说明两个函数可以有相同的查询复杂度，但实现其 $R_{\Lambda }$ 反射的门复杂度截然不同（提示：比较结构规则的公式与一般 SDP 解出的 span program）。

参考文献与 Zoo 覆盖

• NAND/AND—OR 发展：Zoo 8、27、38、80、159，含 Farhi 等、Reichardt—Špalek。
• 对抗界与通用双反射：Zoo 149、158、165，见 Reflections for Quantum Query Algorithms。
• 非 Boolean、read-many 与游戏树：Zoo 29、101、160、164、269。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch11-query-complexity/formula-evaluation-span-programs
• 内容遵循 CC BY-NC-SA 4.0 许可协议