查询下界的多项式方法

确定性树的叶多项式 ​

在确定性查询模型公理库确定性与随机查询复杂度Deterministic query complexity · Randomized query complexity在坐标访问模型中分别定义确定性、零误差随机和有界误差随机查询复杂度，并固定最坏与期望口径。中，设决策树至多查询 $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 :\mathrm{out}(\ell )=1}{m}_{\ell }(x),$$

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

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

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

随机算法的接受概率 ​

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

$$p(x)={\mathbb{E}}_R[p_R(x)]={\text{Pr}}_R[A(x;R)=1]$$

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

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

因此 $p$ 是一致近似公理库近似次数Approximate degree of Boolean functions · Epsilon-approximate degree在 Boolean cube 上以一致误差 ε 逼近函数所需的最低实多项式次数。多项式，得到经典随机查询下界

$$R_{\epsilon }^{\mathrm{query}}(f)\ge {\widetilde{\mathrm{deg}}}_{\epsilon }(f).$$

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

量子模型为何出现 2T ​

在标准量子 bit-query 模型中，初始振幅与输入无关。一次 oracle query 使每个基态振幅乘上某个输入 bit 或相位，因此执行 $T$ 次查询后，每个振幅是次数至多 $T$ 的 multilinear 多项式。

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

$$T\ge \frac{1}{2}{\widetilde{\mathrm{deg}}}_{\epsilon }(f).$$

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

Parity 的完整下界 ​

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

$$g(z)=\prod _{i=1}^n{z}_i.$$

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

$${\mathbb{E}}_z[g(z)q(z)]>0.$$

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

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

$${\widetilde{\mathrm{deg}}}_{\epsilon }({\mathrm{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。

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

参考资料

• 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.