量子查询的多项式方法

查询次数限制接受概率能表现的变量交互阶数；approximate degree 询问目标函数是否可被这种低阶行为逐点模拟。Dual witness 则挑出一个低阶行为全部看不见、目标函数却看得见的方向。算法、逼近和见证形成一条闭合证据链。

与量子 adversary 方法公理库量子查询的正权 Adversary 方法Positive-weight quantum adversary method · Ambainis adversary method以非负输入对权矩阵的谱范数与单坐标可区分进度之比，证明量子查询下界。不同，多项式法压缩的是输入到接受概率的代数次数，而非输入对之间状态重叠的变化。二者可在同一问题上给不同强度；不存在“量子下界”这一标签下的自动互换。

先用四点例子完整走链。对 ${\mathrm{OR}}_2$ 和误差 $1/3$，取

它与常数多项式正交、一范数为 $1$，且与 OR 的相关性为 $1/2>1/3$，所以近似次数大于 $0$。若零查询量子算法存在，其接受概率 $p$ 必为常数，便有 $⟨\psi ,p⟩=0$；误差约束却强迫相关性差至多 $1/3$，与 $1/2$ 冲突。因此 $T\ge 1$，而直接查询任一位还不够计算 total OR，但查询两位当然给上界；这个小见证只认证了它声称的一级下界。

在渐近尺度上，已知定理给出

代入即得 $Q_{1/3}({\mathrm{OR}}_n)=\mathrm{\Omega }(\sqrt{n})$，与 Grover 上界匹配。近似次数下界的实质来自对称化后的一元多项式不等式，或等价的纯高次 dual witness；仅写“接受概率次数至多 $2T$”还没有证明 OR 的次数需求。

对 promise problem，多项式只需在 $D$ 上逼近，dual witness 也只能在 $D$ 上放质量。对 expected-query 算法，某些分支可能任意长，不能直接指定统一的次数 $2T$；需先截断并把截断失败计入误差。

方法适合已有 approximate-degree 或显式 dual polynomial 的函数，并能区分 exact、two-sided、one-sided 和 sign 等代数口径。低 approximate degree 只是下界不强，不能反向推出低查询算法；接受概率多项式还受非负性、归一化与可实现性约束。

多项式法可证明 collision、element distinctness 等问题的强下界，也可经 symmetrization 把高维输入降为 Hamming 重量的一元问题。但每次降维都必须保留 promise 点和误差区间，不能在整数点有界后无条件假设整个实区间同样有界。