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

一个 read-once Boolean 公式是一棵树：叶子是输入位，每个变量只出现一次，内部节点是常数 fan-in 的 AND、OR、NAND 等门。朴素算法可能查询所有 $N$ 个叶子；量子算法却能以 $\Theta(\sqrt N)$ 次查询求任意常数 fan-in 公式。这个结果不是每层套 Grover 的简单递归，而来自 span program 与 general adversary bound 的精确对应。

## 1. 从 NAND 树看问题

平衡二叉 NAND 树递归定义

$$
F_v=\operatorname{NAND}(F_{v_L},F_{v_R}).
$$

若树有 $N=2^d$ 个叶子，确定性最坏查询为 $N$。经典随机算法利用短路求值可少于 $N$，但仍为 $N^{\alpha}$、$\alpha>1/2$。Farhi--Goldstone--Gutmann 首先构造连续时间 Hamiltonian NAND-tree 算法达到 $O(\sqrt N)$；后续离散查询、任意不平衡 AND--OR 树与一般公式由 span program 统一。

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

Span program $P$ 包含一个内积空间、目标向量 $|\tau\rangle$，以及按输入文字 $(j,b)$ 标记的向量集合

$$
\{|v_{j,b,\ell}\rangle\}.
$$

输入 $x\in\{0,1\}^n$ 时，只允许标签满足 $b=x_j$ 的向量。程序接受当且仅当

$$
|\tau\rangle
\in\operatorname{span}
\{|v_{j,x_j,\ell}\rangle\}.
$$

写矩阵 $A$ 的列为全部输入向量，$\Pi(x)$ 投影到当前可用列。

若 $f(x)=1$，正 witness 是系数向量 $|w\rangle$：

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

其成本衡量最小 $\|w\|^2$。若 $f(x)=0$，负 witness 是 $|\omega\rangle$：

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

其成本衡量 $\|A^\dagger|\omega\rangle\|^2$。Span program witness size 是正负最坏成本的几何平均或等价归一化最优值。

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

由 $P$ 构造输入无关子空间（例如某个增广矩阵的 kernel）及其反射

$$
R_\Lambda=2\Lambda-I.
$$

输入 oracle 只需实现“哪些列可用”的反射

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

每次 $R_x$ 使用常数次输入查询。算法研究酉算子

$$
U_x=R_\Lambda R_x.
$$

两个反射乘积的本征相位由相应子空间的 principal angles 决定：

- 若 $f(x)=1$，正 witness 构造出与起始态有明显 overlap 的零相位或近零相位本征向量；
- 若 $f(x)=0$，负 witness 证明起始态在一个由 witness size 控制的相位间隙内几乎没有谱质量。

对 $U_x$ 做相位检测，判断是否存在近零本征相位。所需精度与 witness size $W(P)$ 成反比，故查询复杂度为

$$
O(W(P)).
$$

这正是 Grover 的“oracle 相位反射 × 初态反射”结构的普适推广。

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

对 Boolean 函数 $f$，选择由输入对索引的 Hermitian 矩阵 $\Gamma$，且 $\Gamma_{xy}=0$ 当 $f(x)=f(y)$。令

$$
(\Delta_j)_{xy}=1[x_j\ne y_j].
$$

general adversary bound 为

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

分子衡量算法必须区分的 yes/no 输入总体相干性；分母衡量一次查询第 $j$ 位最多破坏多少相干性，因此

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

对偶 SDP 可直接转成 span program，Reichardt 的双反射算法又以 $O(\operatorname{Adv}^{\pm}(f))$ 查询求值，最终得到

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

所以对抗界不是只会证明“不可能更快”的工具，它本身编码了最优算法。

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

AND/OR 门的对抗值与输入规模平方根同阶。General adversary 在函数复合下相乘：

$$
\operatorname{Adv}^{\pm}
(f\circ(g_1,\ldots,g_m))
$$

按各子问题成本加权组合。对 read-once 树，每个叶子的 witness 权重沿根路径相乘；经过平衡缩放，整棵大小 $N$ 的常数 fan-in 公式满足

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

下界用 OR 公式或适当 adversary 立即给出 $\Omega(\sqrt N)$，因此最优。重要的是该结论不要求树平衡；不平衡公式需为不同子树设置不同 witness 权重，机械地在每层做相同 Grover 迭代反而会损失复杂度。

## 6. Read-many 与游戏树边界

若变量可重复，记 $N$ 为不同变量数、$S$ 为叶出现总数、$G$ 为门数，已知算法给出

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

型查询界。某些 promise NAND 树中，不同输入的门数或 average choice complexity 很小，可出现更大分离；有效电阻给出 witness 的电网络解释。

查询最优也不自动意味着门时间最优。实现 $R_\Lambda$ 可能需要处理公式图的谱或稀疏线性代数；对常数 fan-in 公式可实现近线性开销，但任意 SDP 给出的 span program 可能维数巨大。

## 7. 小结与习题

- Span program 用“目标是否落在可用向量张成空间”表示 Boolean 函数。
- 正/负 witness 分别认证接受与拒绝，并控制相位检测精度。
- 双反射算法把 span program 直接变成量子查询算法。
- General adversary SDP 与量子查询复杂度等价，公式复合给出 $\Theta(\sqrt N)$。

1. 为二输入 OR 构造一个 span program 并写出正、负 witness。
2. 解释两反射乘积的零相位向量与子空间交的关系。
3. 用 adversary 复合直观推导四叶平衡 AND--OR 树的成本。
4. 举例说明查询次数相同而实现反射的门复杂度不同。

## 参考文献与 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。