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 覆盖