查询下界的多项式方法

形式陈述

确定性树的叶多项式

在确定性查询模型中，设决策树至多查询 $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 模型中，初始振幅与输入无关。一次 oracle query 使每个基态振幅乘上某个输入 bit 或相位，因此执行 $T$ 次查询后，每个振幅是次数至多 $T$ 的 multilinear 多项式。

接受概率是接受基态振幅绝对值平方之和。振幅与其共轭相乘会把次数至多翻倍，所以接受概率是次数至多 $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.

若 $\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 正交论证不能自动保留。对 one-sided error 或 sign 表示，也要换成相应的 one-sided degree 或 threshold degree，不能继续套 uniform approximation。

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

推论与应用

这套方法把不同查询模型统一到“接受概率的次数上限”上，同时保留模型常数：确定性与经典随机算法给出 $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,” 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 的完整下界 ​