查询下界的多项式方法

形式陈述

确定性树的叶多项式

先取整数 $n\ge1$ 与全布尔函数 $f:\{0,1\}^n\to\{0,1\}$ ；误差参数满足 $0\le\varepsilon<1/2$ 。承诺问题的补充约定见后文。

在确定性查询模型中，设决策树至多查询 $T$ 个 bit。对一条根叶路径 $\ell$ ，令 $P_\ell$ 为沿途被要求取 $1$ 的坐标， $N_\ell$ 为被要求取 $0$ 的坐标。输入到达该叶的指示函数是

m_\ell(x) =\prod_{i\in P_\ell}x_i \prod_{j\in N_\ell}(1-x_j).

若先删去重复查询，每条路径涉及至多 $T$ 个不同坐标，所以 $m_\ell$ 是次数至多 $T$ 的 multilinear 多项式。不同叶事件互斥且覆盖全部输入；把所有输出 $1$ 的叶相加，得到算法接受指示量

p_A(x)=\sum_{\ell:\operatorname{out}(\ell)=1}m_\ell(x),

次数仍至多 $T$ 。若树精确计算 $f$ ，则 $p_A=f$ 在 Boolean cube 上逐点相等，故

D^{\mathrm{query}}(f)\ge\deg(f).

证明使用叶路径的合取结构，而不是声称每次查询“把次数增加一”后不检查分支组合。

随机算法的接受概率

固定随机带 $r$ 后， $T$ -query 随机算法是一棵确定性树，接受指示多项式 $p_r(x)$ 次数至多 $T$ 。对随机币取期望

p(x)=\mathbb E_R[p_R(x)] =\Pr_R[A(x;R)=1]

只是相同次数多项式的线性组合，所以 $\deg p\le T$ 。若算法以双侧错误 $\varepsilon$ 计算 $f$ ，则

|p(x)-f(x)|\le\varepsilon \quad\text{对每个合法 }x.

因此 $p$ 是一致近似多项式，得到经典随机查询下界

R^{\mathrm{query}}_\varepsilon(f) \ge\widetilde{\deg}_\varepsilon(f).

这里采用每次运行查询数至多 $T$ 的硬上限。若算法只有期望查询界，固定随机带的树可能任意深；通常先截断并支付额外错误，再应用多项式论证。

量子模型为何出现 2T

在标准量子 bit-query 模型中，初始振幅与输入无关。记查询前基态 $|i,b,w\rangle$ 的振幅为 $\alpha_{i,b,w}(x)$ ，查询后的同一基态振幅恰为

(1-x_i)\alpha_{i,b,w}(x)+x_i\alpha_{i,b\oplus1,w}(x).

这是在“不翻转”与“翻转回答位”之间按 $x_i$ 选择，故每次查询至多增加一次次数。输入无关的 unitary 只对振幅作常系数线性组合，不增加次数。归纳得到 $T$ 次查询后振幅次数至多 $T$ ；再用 $x_i^2=x_i$ 多线性化。这一步解释了 bit oracle 的交换作用，无须把它误读成直接给每个基态乘一个 bit。

接受概率是接受基态振幅绝对值平方之和。振幅与其共轭相乘会把次数至多翻倍，所以接受概率是次数至多 $2T$ 的实多项式。于是 bounded-error 量子算法只推出

T\ge\frac12\widetilde{\deg}_\varepsilon(f).

经典随机算法直接平均 0/1 叶指示量，系数是 $1$ ；量子算法先让振幅干涉再平方，系数是 $2$ 。把两者都写成“接受概率是低次多项式”后共用同一常数，会丢掉模型的关键差别。

直觉

查询算法只能通过被读取的坐标区分输入。一条叶路径把若干回答条件相乘，得到一个只在该 transcript 上点亮的低次单项式；把接受叶相加，就把整棵决策树压成一个多项式。查询次数限制了每条路径能联合依赖多少坐标，因此也限制接受行为的代数次数。

下界证明随后把方向反转：若目标函数的高频或高阶结构无法被低次多项式捕捉，那么任何查询太少的算法都不可能产生正确接受概率。算法到多项式的转换通常统一而机械，证明无低次精确或近似表示才是针对具体函数的核心工作。

确定性、随机与量子查询算法分别转换为低次接受多项式和查询下界 — 查询算法到低次多项式的三条转换

例子与边界

Parity 的完整下界

把输入改写为 $z_i=(-1)^{x_i}\in\{-1,+1\}$ ，parity 的符号编码为

g(z)=\prod_{i=1}^n z_i.

若 $p(x)$ 以误差 $\varepsilon<1/2$ 逼近 $0/1$ parity，令 $q(z)=1-2p(x(z))$ ，则 $|q(z)-g(z)|\le2\varepsilon<1$ 。因此每个点都有 $g(z)q(z)>0$ ，特别是均匀分布下

\mathbb E_z[g(z)q(z)]>0.

按Boolean cube 的字符基展开，若 $\deg q<n$ ，它是只含 $\prod_{i\in S}z_i$ 、 $|S|<n$ 的线性组合。每个这样的单项式乘 $g$ 后至少留下一个均匀、独立、一次出现的坐标，期望为 $0$ 。于是 $\mathbb E[gq]=0$ ，矛盾。

所以对每个 $\varepsilon<1/2$ ，

\widetilde{\deg}_\varepsilon(\operatorname{PARITY}_n)=n.

多项式方法立即给经典随机查询下界 $T\ge n$ ，与读取全部 bit 的上界匹配；量子版本只给 $T\ge n/2$ ，恰反映其接受概率次数上限为 $2T$ 。

使用边界

算法诱导低次多项式只是第一步；真正的困难常在证明目标函数没有低次逼近。只写“由 polynomial method”而不给 approximate-degree 下界，证明链仍缺一半。

对非空承诺域上的偏函数，正确性只要求在 promise 域上逼近，parity 的全 cube 正交论证不能自动保留。若查询预算原本只约束合法输入，可在第 $T$ 次查询后统一截断其余执行并任意作答；这不改变合法输入上的行为，却使算法在整个 cube 上都有次数至多 $T$ （量子情形 $2T$ ）的接受多项式。但算法的接受概率在承诺外仍介于 $0$ 与 $1$ ；保留这个额外约束有时能加强下界。例如承诺重量为 $0$ 或 $1$ 时，线性式 $\sum_i x_i$ 在合法输入上精确等于 OR，却会在其他输入上超过 $1$ ，不能充当查询算法的接受概率。

单侧错误算法仍满足同样的双侧误差条件，因此普通近似次数下界依然有效；若要利用它在某一类输入上绝不出错的额外保证，才需加入相应单侧代数约束。符号表示仅约束正负，则比一致逼近弱，不能把其次数与近似次数当成同一参数。

系数可以巨大，方法仍只计算次数。低次接受概率多项式未必能反向实现为查询算法；因此近似次数主要是下界工具，不是一般的算法刻画。

推论与应用

这套方法把不同查询模型统一到“接受概率的次数上限”上，同时保留模型常数：确定性与经典随机算法给出 $T$ ，量子算法给出 $2T$ 。只要已有目标函数的 exact-degree 或 approximate-degree 下界，就能立即翻译为相应查询下界。

它也提示证明的检查顺序：先确认每次运行的查询是硬上限还是期望值，再确认逼近发生在全 cube 还是 promise 域，最后选择与双侧、单侧或符号错误匹配的代数次数。三个接口任一错位，漂亮的次数论证都可能约束了错误的算法类。

参考资料

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf, “Quantum Lower Bounds by Polynomials,” FOCS 1998 会议版；期刊版 Journal of the ACM 48(4), 2001, pp. 778–797，振幅与接受概率的次数界。
Noam Nisan and Mario Szegedy, “On the Degree of Boolean Functions as Real Polynomials,” Computational Complexity 4, 1994, pp. 301–313.
Ronald de Wolf, “A Brief Introduction to Fourier Analysis on the Boolean Cube,” Theory of Computing Graduate Surveys 1, 2008, pp. 1–20.

形式陈述 ​

确定性树的叶多项式 ​

随机算法的接受概率 ​

量子模型为何出现 2T ​

Parity 的完整下界 ​

使用边界 ​