# Boolean 公式求值：Span Program、对抗界与双反射算法

一个 **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{公式}\;\longrightarrow\;\text{span program}\;\longrightarrow\;\text{双反射量子算法}\;\longleftrightarrow\;\text{对抗界（下界）}.
$$

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

**前置知识**：本站第 3 章的 [Grover 算法](../ch03-algo-basics/grover.md) 与振幅放大、[相位估计](../ch03-algo-basics/phase-estimation.md)；第 1 章的线性代数记号（投影、谱分解）。我们会在用到的地方简要回顾，但不重新推导。

:::{admonition} 本课知识点
:class: tip

1. **[经典算法的复杂度标杆](#classical-benchmark)**——能解释确定性算法为何必须查满 $N$ 个叶子（evasive），并写出随机短路求值算法的 $N^{0.753}$ 查询复杂度，说明 $\alpha>\frac12$ 意味着经典算法达不到 $\sqrt N$。
2. **[Span program 的定义](#span-program-definition)**——能写出 span program 的组成数据与接受条件，并把 OR 这样的 Boolean 函数翻译成线性张成判定问题。
3. **[正、负 witness 与 witness size](#witness-size)**——能写出正、负 witness 的约束与成本定义，解释二者为何取几何平均，并对 OR 的 span program 完整算出 $W(P)=\sqrt n$。
4. **[双反射算法](#two-reflection-algorithm)**——能构造迭代算子 $U_x=R_\Lambda R_x$ 并区分两个反射各自的查询代价，把相位间隙 $\Omega(1/W(P))$ 换算为 $O(W(P))$ 次查询。
5. **[一般对抗界的定义](#adversary-bound-definition)**——能写出 $\operatorname{Adv}^{\pm}(f)$ 的定义并逐项解释分子与分母的含义，对 $\mathrm{OR}_n$ 手算出 $\sqrt n$ 下界。
6. **[对偶性与复杂度刻画](#adversary-duality)**——能说明 $\operatorname{Adv}^{\pm}(f)$ 的对偶 SDP 与 witness size 的对应关系，并由此推导刻画 $Q(f)=\Theta(\operatorname{Adv}^{\pm}(f))$。
7. **[复合定理与公式求值的 $\sqrt N$](#composition-theorem)**——能用复合定理推导平衡 NAND 树的 $(\sqrt 2)^d=\sqrt N$，并比较平衡树与不平衡树的 witness 权重分配策略。
8. **[Read-many 与查询/时间边界](#read-many-boundaries)**——能写出 read-many 公式的 $O(\min\{N,\sqrt S,N^{1/2}G^{1/4}\})$ 查询界并逐项解释，说明游戏树分离为何依赖 promise、查询最优为何不等于门时间最优。

:::

## 1. 从 NAND 树看问题

### 1.1 问题的精确表述

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

$$
F_v=\operatorname{NAND}(F_{v_L},F_{v_R}),\qquad \operatorname{NAND}(a,b)=\neg(a\land 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$ 阶）。

(classical-benchmark)=
### 1.2 经典算法能做到什么

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

**随机化算法**：可以做得明显更好，关键是**短路求值**。以根节点为例：先随机选择递归求值 $F_{v_L}$ 或 $F_{v_R}$。若先算出的子树值为 $0$，则 $\operatorname{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>\frac12:
$$

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

### 1.3 量子侧的历史脉络

- **Farhi–Goldstone–Gutmann**（参考文献中的 [Farhi 等](https://arxiv.org/abs/quant-ph/0702144)）首先对平衡 NAND 树给出 $O(\sqrt N)$ 查询级别的算法。他们的模型不是查询线路，而是**连续时间 Hamiltonian 演化**：构造一个由输入决定的哈密顿量 $H(x)$，让态沿一条"从叶子到根"的路径传播，通过透射/反射行为读出公式值。这个构造物理图像很美，但把连续时间演化转成离散查询模型需要额外工作（Childs 等人的后续结果完成了这一转换）。
- **Reichardt–Špalek**（[arXiv:0710.2630](https://arxiv.org/abs/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(\operatorname{Adv}^{\pm}(f))$ 查询运行的通用**双反射算法**（[arXiv:1005.1601](https://arxiv.org/abs/1005.1601)）。于是"下界方法"与"上界算法"合拢：

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

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

## 2. Span program 的线性代数定义

(span-program-definition)=
### 2.1 定义

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

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

$$
\{|v_{j,b,\ell}\rangle\}\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}\rangle$ 是**可用的 (available)**，当且仅当 $b=x_j$，即该文字被 $x$ 满足。程序**接受** $x$ 当且仅当

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

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

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

$$
|\tau\rangle\in\operatorname{range}\!\left(A\Pi(x)\right).
$$

### 2.2 手算小例子：OR 的 span program

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

$$
|v_{j,1}\rangle=1\quad(\text{当 }x_j=1\text{ 时可用}),\qquad |v_{j,0}\rangle=0\quad(\text{当 }x_j=0\text{ 时可用}).
$$

验证它确实计算 OR：

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

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

(witness-size)=
### 2.3 正、负 witness 与 witness size

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

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

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

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

$$
\operatorname{wsize}_1(P)=\max_{x:\,f(x)=1}\;\min_{|w\rangle:\,A\Pi(x)|w\rangle=|\tau\rangle}\|w\|^2,
$$

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

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

$$
\langle\omega|\tau\rangle=1,\qquad \langle\omega|A\Pi(x)=0,
$$

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

$$
\|A^\dagger|\omega\rangle\|^2=\sum_{j,b,\ell}|\langle\omega|v_{j,b,\ell}\rangle|^2,
$$

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

$$
\operatorname{wsize}_0(P)=\max_{x:\,f(x)=0}\;\min_{|\omega\rangle}\|A^\dagger|\omega\rangle\|^2.
$$

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

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

### 2.4 小例子续：OR 的 witness size

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

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

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

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

$$
\|A^\dagger|\omega\rangle\|^2=\sum_{j}|\langle\omega|v_{j,1}\rangle|^2=\sum_{j}|1|^2=n
$$

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

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

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

## 3. 两个反射怎样读取 witness

### 3.1 从 Grover 继承的骨架

回顾 [Grover 算法](../ch03-algo-basics/grover.md) 的结构：迭代算子 $G=U_S U_O$ 是**两个反射的乘积**——一个依赖输入（翻转目标相位），一个与输入无关（关于均匀叠加态的反射）。两个反射的乘积在由两条反射轴张成的平面里是旋转，旋转角由两轴夹角决定；相位估计/重复迭代把"夹角大小"转成"查询次数"。

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

(two-reflection-algorithm)=
### 3.2 两个反射的构造

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

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

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

$$
|\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$ 在起始态上是否存在近零本征相位**。这正是相位估计（见 [相位估计](../ch03-algo-basics/phase-estimation.md)）的标准任务：

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

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

$$
O\!\left(\frac{1}{\varepsilon}\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 算法](../ch03-algo-basics/grover.md) 的 Theorem 4）——拒绝输入时所有本征相位离 $0$ 至少这么远；
- **近零相位分量**：$f(x)=1$ 时存在与起始态有常数级 overlap 的近零相位本征向量，对应 Grover 中"有目标时迭代把态转到目标方向"的事实；
- **查询数**：相位估计精度 $\varepsilon=\Theta(1/\sqrt n)$ 给出 $O(\sqrt n)$ 次查询，即 Grover 的迭代次数。

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

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

(adversary-bound-definition)=
### 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\quad\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 定义为

$$
\operatorname{Adv}^{\pm}(f)=\max_{\Gamma}\;\frac{\|\Gamma\|}{\max_j\|\Gamma\circ\Delta_j\|},
$$

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

**逐项解释这个比值**：

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

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

标准的混合论证给出 $Q(f)\ge \frac{1-\text{常数误差项}}{2}\cdot\operatorname{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$ 行上），故 $\|\Gamma\|=\sqrt n$；
- **分母**：$(\Gamma\circ\Delta_j)_{e_i,0^n}=\Gamma_{e_i,0^n}\cdot 1[(e_i)_j\neq 0]$，只有 $i=j$ 时为 $1$，即每列掩膜后只剩一个非零元，$\|\Gamma\circ\Delta_j\|=1$。

代入定义：

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

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

(adversary-duality)=
### 4.3 对偶性：下界即算法

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

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

$$
\min_{P\text{ 计算 }f}W(P)=\Theta\!\left(\operatorname{Adv}^{\pm}(f)\right);
$$

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

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

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

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

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

### 5.1 单门的对抗值

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

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

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

(composition-theorem)=
### 5.2 复合定理：对抗值在函数复合下相乘

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

$$
\operatorname{Adv}^{\pm}(F)\;=\;\Theta\!\left(\operatorname{Adv}^{\pm}(f)\cdot\max_i \operatorname{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\land x_2)\lor(x_3\land x_4)$，共 $N=4$ 个叶子。用复合定理：

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

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

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

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

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

由 4.3 的对偶转换，存在 span program 使 $W(P)=\Theta(\operatorname{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}\quad\Longrightarrow\quad 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）立即给出

$$
\operatorname{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 与游戏树边界

(read-many-boundaries)=
### 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(\operatorname{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【经典算法的复杂度标杆】**（→ [1.2 节](#classical-benchmark)）

1. 基础：复述确定性决策树复杂度 $D(f)=N$ 的对手论证——对手如何安排已查叶子的回答，使"子树取值到最后一刻才被钉死"？
2. 进阶：解释随机短路求值算法为什么"先算出的子树为 $0$ 就可跳过另一棵"，并说明 $\alpha\approx 0.753>\frac12$ 意味着最好的经典随机算法也严格慢于 $\sqrt N$ 次查询。

> 提示：对"两棵子树都必须求值"的最坏输入，写出随机选择先算哪棵子树的期望查询数递归。

**练习 2【Span program 的定义】**（→ [2.1 节](#span-program-definition)）

1. 基础：列出 span program 的组成数据（空间、目标向量、输入向量族、文字与可选编号），写出接受条件，并指出向量 $|v_{j,b,\ell}\rangle$ 何时"可用"。
2. 进阶：把 2.2 节 OR 的一维构造写成矩阵语言：写出 $A$ 与 $\Pi(x)$ 的形状，分别对 $x=e_1$ 与 $x=0^n$ 验证"$|\tau\rangle\in\operatorname{range}(A\Pi(x))$ 当且仅当 $f(x)=1$"。

> 提示：一维情形 $A$ 是 $1\times 2n$ 的行向量，可用列就是取值为 $1$ 的那些位置。

**练习 3【正、负 witness 与 witness size】**（→ [2.3 节](#witness-size)）

1. 基础：写出正 witness 与负 witness 各自满足的约束及成本定义，并解释负 witness 的成本为何只由"不可用列"上的泄漏贡献。
2. 进阶：为二输入 AND 构造一个 span program，写出接受输入与拒绝输入各自的正、负 witness，并计算 $W(P)$。

> 提示：在 OR 的构造基础上调整目标与向量的维度，例如取 $\mathcal H=\mathbb C^2$、$|\tau\rangle=(1,1)^T$，接受输入只有 $(1,1)$。

**练习 4【双反射算法】**（→ [3.2 节](#two-reflection-algorithm)）

1. 基础：写出 $R_\Lambda$ 与 $R_x$ 的定义，说明实现哪个反射不需要输入查询、哪个恰好对应按位标记的相位 oracle。
2. 进阶：设 $U=R_\Lambda R_x$ 是两个反射的乘积。证明：若存在非零向量 $v\in\Lambda\cap\operatorname{range}(\Pi(x))$，则 $v$ 是 $U$ 的本征值 $+1$ 本征向量；并解释这说明"零相位本征向量"与"两子空间之交"的关系。

> 提示：两个反射分别在各自子空间上取 $+1$，而 $v$ 同时属于两个子空间。

**练习 5【一般对抗界的定义】**（→ [4.1 节](#adversary-bound-definition)）

1. 基础：写出 $\operatorname{Adv}^{\pm}(f)$ 定义中 $\Gamma$ 需满足的约束，并解释分子 $\|\Gamma\|$ 与分母 $\max_j\|\Gamma\circ\Delta_j\|$ 各自衡量什么。
2. 进阶：仿照 4.2 节，为 $\mathrm{AND}_2$ 显式写出达到 $\sqrt 2$ 的矩阵 $\Gamma$，验证 $\|\Gamma\|=\sqrt 2$ 与 $\max_j\|\Gamma\circ\Delta_j\|=1$。

> 提示：$\mathrm{AND}_2$ 的唯一拒绝输入是 $(0,0)$；只在恰含一个 $1$ 的接受输入处放非零元。

**练习 6【对偶性与复杂度刻画】**（→ [4.3 节](#adversary-duality)）

1. 基础：复述 $Q(f)=\Theta(\operatorname{Adv}^{\pm}(f))$ 的两半——上界方向与下界方向——分别由哪条论证给出。
2. 进阶：解释"下界即算法"的含义：对偶 SDP 的解如何转写成一个 span program，为什么说解一个 SDP 就同时得到最优查询复杂度与算法方案？

> 提示：对偶可行解给出的正是输入向量 $\{|v_{j,b,\ell}\rangle\}$ 与目标 $|\tau\rangle$ 的取法，其目标值对应 witness size。

**练习 7【复合定理与公式求值的 $\sqrt N$】**（→ [5.2 节](#composition-theorem)）

1. 基础：用复合定理计算 $F=\mathrm{AND}_2\circ(\mathrm{OR}_2,\mathrm{OR}_2)$（$N=4$ 叶）的对抗值，并验证结果等于 $\sqrt N$。
2. 进阶：用复合定理计算深度为 $3$ 的平衡二叉 NAND 树（$N=8$ 叶）的对抗值，并说明若改用"每层各做一次完整 Grover 搜索"的递归算法，为什么只能得到 $O(\sqrt N\,\mathrm{poly}(\log N))$ 而非 $O(\sqrt N)$（从误差预算沿层数分配的角度论证）。
3. 进阶：考虑一棵左子树有 $N/2$ 叶、右子树只有 $2$ 叶的 OR–AND 型不平衡公式。定性说明：为什么给两个子树分配相同的权重不是最优的？应按什么原则分配？

> 提示：每层树深贡献一个 $\sqrt 2$ 因子；每层固定误差会沿 $d=\log_2 N$ 层累积；不平衡树按"弱者加权、拉平各路径成本"分配权重。

**练习 8【Read-many 与查询/时间边界】**（→ [6.1 节](#read-many-boundaries)）

1. 基础：写出 read-many 公式的三因子查询界 $O(\min\{N,\sqrt S,N^{1/2}G^{1/4}\})$，并逐项说明每个因子对应哪种算法思路。
2. 基础：验证 $\sqrt S$ 与 $N^{1/2}G^{1/4}$ 恰在 $S=\Theta(N\sqrt G)$ 处交叉，并说明当 $G\approx N$、$S\gg N^{3/2}$ 时哪个因子占优。
3. 进阶：举一个具体例子，说明两个函数可以有相同的查询复杂度，但实现其 $R_\Lambda$ 反射的门复杂度截然不同。

> 提示：比较结构规则的公式（$R_\Lambda$ 可近线性实现）与一般 SDP 解出的 span program（空间维数可能巨大）。

## 参考文献与 Zoo 覆盖

- NAND/AND--OR 发展：Zoo 8、27、38、80、159，含 [Farhi 等](https://arxiv.org/abs/quant-ph/0702144)、[Reichardt--Špalek](https://arxiv.org/abs/0710.2630)。
- 对抗界与通用双反射：Zoo 149、158、165，见 [Reflections for Quantum Query Algorithms](https://arxiv.org/abs/1005.1601)。
- 非 Boolean、read-many 与游戏树：Zoo 29、101、160、164、269。